Systeme D

8.

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:

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.

Previous post: Why you should credit OpenStreetMap.