Building cycle.travel’s bike directions with OSRM.
Last month, I took the wraps off cycle.travel, the everyday cycling website I’ve been working on since leaving Waterways World.
One of the major features is a bike-friendly journey planner. That’s not a new thing, of course: CycleStreets has blazed a trail for many years and does a superb job of finding good, reliable routes from OpenStreetMap data.
cycle.travel takes a different approach. Rather than CycleStreets’ three journey options, it provides only one, but allows you to drag the route (Google-style) until it meets your needs. In that way, it offers a mix between a detailed bike-friendly journey planner and a route drawing tool like MapMyRide. And this is all good: just as there are many different types of cyclist, so should there be many journey planners.
The alchemy behind this is OSRM – the Open Source Routing Machine. Largely written by Dennis Luxen, it’s been proven for heavy-duty bike use by IBikeCPH. But finding bike directions in Copenhagen, with its abundance of high-quality infrastructure, is a very different challenge to finding directions in Britain, with its abundance of cycle-wats.
Cycle-wat, noun: a cycleway that merits only one response, ‘WAT’. Like ‘farcility’ but without the sneery taint of vehicular cycling. (Picture by Rachel Coleman-Finch, CC-BY-SA.)
Parsing OSM data
The first challenge is to make sense of OSM cycle data, which is an unholy mess.
Shortcomings in OSM coverage, by region (e.g. rural North America) or topic (e.g. addresses), are well known. Shortcomings in data standards, less so. Broadly, OSM only has sensible, commonly agreed tagging for a few base concepts, principally roads and addresses. Anything else? It’s like the Wild West, but with more bureaucracy.
This makes extracting meaningful information about cycle routes much harder than it need be. There are two competing standards for mapping paths, one with a forest of trivial differences (bicycle=yes vs bicycle=designated – no, me neither). There are three competing standards for mapping surface quality, one descriptive, one generalised, one... wat. And so on.
OSRM’s stroke of genius is to embed the Lua scripting engine. Rather than a simple lookup table (“give highway=cycleway a score of 10, highway=tertiary a score of 5, etc.”), you can write code in Lua to parse tags programmatically, unifying all these different standards. In cycle.travel’s case, the logic for scoring way types is over 300 lines of code, backed with five separate lookup tables. It’s not pretty, but it’s very effective.
As yet, OSRM doesn’t support route relations off the shelf. Cycle route relations are important, not just for instructions (“follow cycle route 5 for two miles”), but also as an indicator of quality. No, not all cycle routes are good, but on average, inclusion in the National Cycle Network demonstrates (for example) that traffic levels are more likely to be low. Fortunately, Emil Tin from IBikeCPH has patched route relation support into OSRM, and I’m using his fork as the basis for cycle.travel’s instance.
Turn-by-turn directions
OSRM provides a simple API: send start/end points (and any via points along the way), get route back as JSON. As standard, the turn-by-turn directions simply list the names or road numbers – ‘Market Street’ or ‘A44’ – of the route chosen.
But we can do much more than that. Is the road part of a numbered cycle route? What’s the surface? Is it a road, a cycleway, a footpath or a ferry?
Once again, the name of each ‘segment’ is chosen by the Lua profile, based on the tags of the underlying OSM way. We can use this to pack more information into the name field. For example, Park Street in Charlbury is stored as “ncn 442|||u|Park Street||CHARLBURY”: not just the name, but also the cycle route (NCN 442), the type of road (u=unclassified), and the village it’s in.
cycle.travel’s clientside JavaScript takes this and presents clear turn-by-turn directions from it. The village name is particularly useful for rural cycle route planning. For a countryside ride, you’d rarely say “turn left onto Forest Road, then right onto Catsham Lane, continue on Horseshoe Lane, then left onto Chapel Road”. Instead, you’d name the villages you cycle through.
Elevation and external data
Elevation is crucial to cycle route-planning. A quiet ten-mile country lane is no fun at all if those ten miles finish at the summit of Mont Ventoux. OSRM doesn’t have explicit elevation support built in, but there are ways to add it.
There are long discussions on the OSRM Github issue tracker about the best approach. I chose to load compressed tiles of SRTM data (Shuttle Radar Topography Mission, the most frequently used elevation source) into a Redis data store, which gives an elevation grid for the whole of Britain. Then, when OSRM calculates the weighting for each segment, it looks up the start and end elevation, and computes a penalty.
This isn’t the fastest approach. The overhead of communicating with Redis, and the SRTM lookup code (which is, once again, in Lua), make it slower than a pure C++ mmaped solution.
On the other hand, it’s achievable within my limited C++ skills, and can be applied to other external data sources loaded into Redis. So as well as getting elevation data this way, I use this in the Lua profile’s way_function (which scores and names each way) to find what village each road is in.
Dennis Luxen explained a similar way of accessing external data in a Mapbox blog post, and the feature powers Mapbox’s new Smart Directions product. PostGIS queries have an even greater overhead than Redis commands, so should be used sparingly. Nonetheless, if you’re working at city scale (as IBikeCPH does), it’s a very practical solution.
Circular routes
cycle.travel has a fun circular route function: ask it for a route from Charlbury to Oxford and click ‘Circular route’, and you’ll get a route that’s different on the outbound and return journeys.
This is very simple, a hack in true Systeme D fashion. It just asks OSRM for an alternative route, and uses this as the return journey. There are two disadvantages: the route is no longer draggable (because any via point would be applied to both legs), and one-way directions will be wrong. Both of these are surmountable at some future point, but for now it’s a fun feature.
Why routing?
For OpenStreetMap, there’s a pressing reason to popularise high-quality routing software such as OSRM, CycleStreets and GraphHopper. It’s only by using these route planners that mappers discover ‘routing bugs’: broken connections, missing surface or speed limit information, and so on. And conversely, end-users who find routing bugs are more likely to sign up as mappers to fix them.
As a mapper, I’ve been driven to fix dozens of routing bugs by encountering them while testing cycle.travel. That’s why I’ve coded up a routing interface for openstreetmap.org which will hopefully go live shortly.
An OSRM wishlist
OSRM is a superb piece of software, and one which I greatly enjoy working with. There’s so much it does right, but the Lua profiles are the clincher. Mapbox have done a lot of smart things: hiring Dennis Luxen and adding OSRM to their product offering is one of the smartest yet.
Its development is going in the right direction, too: for example, although it’s undeniable that OSRM has heavy memory requirements, recent work should see that reduced by ~30%.
So what else would I like to see it do? In approximate order:
- Route relation support in trunk. As yet I’ve not been able to take advantage of the latest and greatest OSRM improvements because I’m using Emil’s (fairly old) route relations fork, and route relation support is essential for cycle.travel.
- Multiple datasets, one host. There are many reasons that you might want to generate more than one OSRM routing graph. You could have different styles, for example, like CycleStreets (fastest/quietest/balanced). Or you could provide directions for several unconnected cities or countries: after all, you can’t actually cycle from England to France. At present, you need to run several instances of osrm-routed and set up an arcane Apache config. It would be much better if osrm-routed could handle several datasets/profiles.
- Circular routes by length, not destination. This paper considers how to calculate circular routes from a given start point, with length specified but not destination: for example, “give me a 10-mile circuit from home”. Similar features are offered by walks.io and plotaroute.com. OSRM already has most of the logic to do this: it would make a natural addition.
- Node tags in turn-by-turn directions. The use case described in this OSRM issue is motorway junctions: “turn off at junction 8”. For cyclists, this is, of course, “turn left at the Rose & Crown”. (After a judiciously chosen break.)
- Improve processing times for external data. It takes three hours for my well-specced Hetzner box to generate cycle.travel’s routing graph, largely due to the elevation overhead. Native (C++) mmapped elevation support would be wonderful, but addresses one use case only. Providing Redis support via a Unix socket may be more generally useful.
There’s lots more I’m planning to add to the cycle.travel route planner, with two big new features set to land in the next few months. I’ve been delighted with the feedback received so far – comments such as “best routing I've seen so far”, “what a great route planner”, and “I put in a circular route for an area I know well and it came up with a lovely route, part of which would never have occurred to me”. All this, of course, is thanks to OpenStreetMap’s armies of mappers and to OSRM. Cycling on the shoulders of giants, perhaps?
If you’d like to talk cycle routing, or you’re interested in working with cycle.travel’s technology, I’m both available for freelance work and am interested in expanding cycle.travel’s scope: drop me a line.
Posted on Tuesday 22 April 2014. Link.