Routing in R Using the Open Source Routing Machine (OSRM)

I often find myself needing to establish the travel time or distance between arrays of addresses from R. Here we describe how we can use a local install of Open Source Routing Machine as a solution which is highly performant, and relatively easy to implement.
R
geospatial
OSRM
Author

Chris Hansen

Published

November 27, 2016

Overview

Edit 2020-07-16: The original version of this post included a bespoke decoder for geometries encoded as Google polylines. The post has been updated to use the googlePolylines package instead.

I often find myself needing to establish the travel time or distance between arrays of addresses. In the past I have used ArcMap’s Network Analyst tool, but have found the syntax to be clunky at best, and the performance to be very mediocre. And, besides, I am often working in R and sometimes it’s nice to be able to do everything in the one environment, rather than doing the routing in Python, say, and then using the results in R.

The open source routing machine is a very fast routing engine which can be accessed via an HTTP API, which means it can be queried relatively easy from most languages, including R. And while public servers are available for use, it is also relatively easy to set up locally resulting in excellent throughput due to the lack of latency.

Prerequisites

The following R packages are required:

  • rjson for reading web service results in JSON format
  • bitops used to decode polylines (has convenient bitshift operators, etc.)
  • sp for spatial projections, etc.
  • leaflet for rendering leaflet maps in a browser
  • googlePolylines for converting routes returned from OSRM to sp-compatible paths

Geocoding addresses

The HERE Geocoding & Search API is used to geocode addresses. Usage is free, but the free license is limited to 1000 requests per day, at a rate no faster than 5 per second. There are free alternatives, but I’ve not found any that are satisfactorally accurate for New Zealand addresses. That said, interesting alternatives worth keeping an eye on are:

  • data science toolkit - doesn’t work at all for New Zealand
  • Nominatim - finds addresses but probably only okay if approximate locations are acceptable.

The following code results in two addresses being geocoded which we will use as an origin and a destination later when using a routing service.

library(rjson)

# use HERE API to geocode a start point...
get_location <- function(
  search_text,
  app_id = params$app_id, 
  app_code = params$app_code
) {
  service <- "https://geocoder.api.here.com/6.2/geocode.json"
  
  query <- sprintf(
    "%s?app_id=%s&app_code=%s&searchtext=%s",
    service, app_id, app_code,
    gsub(" ", "%20", search_text, fixed = TRUE)
  )

  res1 <- jsonlite::fromJSON(query, simplifyVector = FALSE)
  res2 <- res1$Response$View[[1]]$Result[[1]]$Location

  list(
    lng = res2$DisplayPosition$Longitude, 
    lat = res2$DisplayPosition$Latitude, 
    address = res2$Address$Label
  )
}

# start point...
(o <- get_location("25 Edelweiss Grove, Timberlea, Upper Hutt"))
$lng
[1] 175.1085

$lat
[1] -41.10678

$address
[1] "25 Edelweiss Grv, Timberlea, Upper Hutt 5018, New Zealand"
# ...and destination
(d <- get_location("1 Pipitea Street, Wellington"))
$lng
[1] 174.7811

$lat
[1] -41.27568

$address
[1] "1 Pipitea St, Thorndon, Wellington 6011, New Zealand"

Open Source Routing Machine (OSRM)

Open Source Routing Machine is an open source route solver. It is written in C++ and runs on Linux (maybe other platforms, but stick with Linux), and is very fast. There is a nice web demo which uses the service as a back-end here. The back-end service is available to the public at https://router.project-osrm.org. Details, including usage policy, is available here.

The code below shows how to find a route between the origin and destination locations found above:

url <- paste0(
  "https://router.project-osrm.org/route/v1/driving/",
  o$lng,",",o$lat,";",d$lng,",",d$lat,"?overview=full"
)

route <- jsonlite::fromJSON(url, simplifyVector = FALSE)

Again, assuming a route was successfully found, route will now contain a list including, among other things, time in seconds to traverse the route, distance in metres, and the route geometry stored in encoded polyline algorithm format.

route$routes[[1]]$duration
[1] 1734.7
route$routes[[1]]$distance
[1] 35333.2
route$routes[[1]]$geometry
[1] "~t{yFozwk`@[hAo@rAOKMEOAO?MBqBfBIHBH@H@HTj@BFBJ?JBFBFDDDBDFn@|AJVHXF\\b@pCJf@BP?F@DDDDDNRRXJJLLzB~APJLDFBF@H@J@LANATCt@MPAP@NBJDLDFFJHNRPXHJHFJDLBJ?J?XAH?HBHDFDHJlCrE`A~AHNBF@F?H?HAF?DCDIJeBdCyAlBcCjDMRIPEHELGXQz@@X@H@DBFHNH@JDf@BXBTF^BhBJt@Fb@H`@JVH^PXPZRLJTVVZJJNVHPLTTb@P`@PDL^N`@HPHVFNFLf@vAPj@Pl@Db@`@jBXbATlANjAHd@FbAHrA@P@HJbBHzAL|AJxAHjAJjA@PTfC\\bDXhC\\dDZlC\\`DRjBP`ARhBNpALtAHzA@FBRDTVtELzB?zAN`EL`DNpDH~AFpBHtBBhABjA@hA?tA?|@Cz@IhEA`A?l@?j@@~@B`ABt@Hr@^~ON~G?V@n@Bn@@xA?jAAxAC|BGzFGV?`BEpY?bE?dB@fBBxAD~ADpAFjAFlAJpAPnBNtANvAR|ATzAn@hD^hAf@pBPr@Pr@Z`A\\`APf@z@xB^|@lAfCJNj@dAd@x@`@r@l@bAtBdD|BnD~BjDlAjBp@~@d@r@T^P^L^L`@Fb@Hf@Fl@@b@@V?XA`@C^EPCTKrBA^Ab@A^?\\@Z@ZBXD`@DXFZH^J\\N^P`@Vf@p@pARVp@rAZr@N^x@dCvBxGvAjFfAnEb@zA^jAh@~AjArCVl@d@fAdAlB~@`B|A~BzD`G|CtEfC|DzBjDfBlCh@x@~@zA`@p@d@z@h@bAh@dAt@|A|@xB\\~@h@`Bh@|A\\fA|@|Cz@jCp@nBj@|Az@zBr@jBfAdCf@dAh@jAdArBz@`Bp@lA~A`Dr@xAp@|Af@fAhAvCv@xBfA~Cj@zAb@fAr@dB|@lBt@zAbAjB~@~AfBlC`ClDhB~Bt@fAl@|@f@`Ad@x@\\v@Tl@d@pAf@bBH\\j@pBb@~Al@xBXpAR~@XzAVpATz@V~@Tv@~AzEfBhF`@hA`@hAj@nAn@pAt@rA^l@bApAtBlCJNLNLNJLLNLLLNLLLLNLLLLLLJNLLJNJNLLJNHxCtBNJLJNJNJLLNJLLLJNLLLLLLLLLLNLLLNLLLNJNLNLNJNJNLPJNJNLPJPJNJPHPJPlNhWnCbFJRJRHPJRJRJRHRJRHRHRHRJTHRHTHRHTFRHTHTFRHTnBzGHTFTHTFTHTHRFTHTHRHTHRHTHRJRHTHRJRHRJRHRJRJRJPHRJRJPJRJPJRLPJPJRJPLPJPLPJPLNLPJPLNLPLNLPLNLNLNLNLNLNLNNNLLNNLNLLNLNNzDpDLLNLLLLLLNLLLNJLLNLLLNJNLNLNJNLNJPJNLNJPJNJPJN~DxGLNJPJPJNJPJNLPJNJPJNLNJPJNLNJNxHdKhBdCpBnCxB`DzAjClAfClB|Dv@vA`A|AjA|AvAbBtCnDpCbDfAzAbA`BnA`CvA~Ch@hAl@hA`@r@b@r@b@p@Z`@r@|@t@x@pBrB|BbCxE~E~BbCvAxAfAlApA`BbBhCnCtEtC|EpAxB`@v@`@v@^v@rAzC~AtDlDdIvDxIpAxC`AnBjBlDjBfDz@zAjArBr@hAFJHNb@z@|@pBHNj@rAx@dBZl@Zl@rAfCx@|ApB~DvBpExBzE~AjD`@`A|AjD@BPZjAnCtC|GxBdFj@nAd@hAl@nApAlCbArBp@tAb@`Ar@fBn@xAVp@d@bA`AzBxA~CvChGhDdHTb@N`@Vh@nAxCFFFLDJXt@\\bAPl@Nb@FNFNJPPj@|@`CnAfDnDjJpAjD`@bA^t@vBnDn@rAt@xA|AfDbA~Bz@xBt@dBdAbCf@pAjCjHxBzFv@~Bh@pAt@nAdAlBt@fA|@rAnAlB~BlDx@tAbCrDvA~Bn@dAbAzBr@rARf@^|@j@~Ah@vAh@zAXfAVv@ZdAZ~@h@xA\\z@\\`A`A`Cp@fBLd@j@|AZfAx@xCjApEhB|Gv@pCv@jCfCjHt@pBb@hAh@vAhAdDj@hBf@`B`@zAz@bDv@dDvAdG~AlHf@xBRbALx@Jz@Hx@Fv@Bp@BdA@`AAp@?VAX?HA^C\\C\\CXI|@Eb@CVA\\?T@XBVF^Lh@R|@^~ApCrL|AxG~AhH^`Bb@|AtAhD^dAZhATnATlAj@~CxBvMrAnIZdBXbA^bAl@tAp@dAv@~@|@x@nCbCh@l@^l@p@lAb@bAd@~A~@lE\\|A\\fAd@jAj@`A^h@`@f@`GvGlCrDlCtExG~M~IfR~ExH`ElIfFxKrBjElBjE`AnBpArCx@bBjAtBjAnBlBhCfBdC~@rAr@bAp@fAj@~@x@zAn@hAx@vAx@~A`AfBfBrDnArCdFbL~@pBj@lAn@dAj@|@b@n@j@n@v@|@`AbAt@~@h@r@dA|Av@xA`@|@`@bAlAvCj@`Bj@tB`@jBd@pCd@xCf@dCr@fCbAbDfBrFb@nAl@`Br@`BjAbCrBfDrAhBz@bA|@~@fAdAz@t@vApAv@t@h@h@f@n@^n@h@bA`@bAt@tBn@`B^`Ad@~@NXVZf@n@j@l@pCfCpDdDv@t@hIpJz@`AzAtA~AxAtIvHl@p@p@~@Zh@xFnIh@p@TRZLVFV?ZAp@Ox@ULGhAm@l@YtAs@ZQr@]BCj@YXOVMPInAo@BaDBqA?GAGAIFCDAB???"

We then call a function to convert the encoded route to a SpatialLines object:

path <- googlePolylines::decode(route$routes[[1]]$geometry)[[1]]

Using leaflet to make a nicer map

It is relatively easy to make a nice interactive map. Here we draw a simple leaflet map, and overlay the origin and destination points, as well as the route between.

library(leaflet)

#make a string to nicely label the route
s <- route$routes[[1]]$duration
kms <- round(route$routes[[1]]$distance/1000, 1)
routelabel <- paste0(s%/%60, "m ", s%%60, "s , ", kms, "kms")

#create a basic map
m <- leaflet(width="100%") %>% 
  addTiles()  %>% 
  addPolylines(
    lng = path$lon,
    lat = path$lat,
    popup = routelabel, 
    color = "#000000", 
    opacity = 1, 
    weight = 3
  ) %>%
  addMarkers(lng=o$lng, lat=o$lat, popup=o$address) %>%
  addMarkers(lng=d$lng, lat=d$lat, popup=d$address)

It’s also relatively straight forward to use different base maps, and a nice demo of some other providers can be found here. For example:

require(leaflet)

leaflet(width="100%") %>% 
  addTiles(
    urlTemplate='https://stamen-tiles-{s}.a.ssl.fastly.net/watercolor/{z}/{x}/{y}.png',
    attribution = sprintf(
      "Map tiles by %s", 
      '<a href="http://stamen.com">Stamen Design</a>'
    )
  ) %>%
  addTiles(
    urlTemplate = 'https://stamen-tiles-{s}.a.ssl.fastly.net/toner-hybrid/{z}/{x}/{y}{r}.png'
  ) %>%
  addPolylines(
    lng = path$lon,
    lat = path$lat,
    popup=routelabel, 
    color = "#000000", 
    opacity = 1, 
    weight = 3
  ) %>%
  addMarkers(lng = o$lng, lat = o$lat, popup = o$address) %>%
  addMarkers(lng = d$lng, lat = d$lat, popup = d$address)