bks_engineering: From Paper Maps to Digital Routing Engine
Turn by turn directions are at the heart of Bike Streets.
Generating these directions is a complicated problem that luckily has many open source projects aiming to make it easy, generally, using OpenStreetMap (OSM) data.
OSM is an incredibly powerful digital public good that provides map data for the entire world. If you’re unfamiliar, OSM has been around for 20 years and is like Wikipedia, but for maps. It’s constantly being edited by hand and in an automated fashion (by companies like Lyft and others), which is especially important for us since we rely on the data being an accurate representation of what exists in the real world.
For a variety of reasons, Bike Streets chose the Open Source Routing Machine (OSRM) as the solution for delivering turn-by-turn directions. OSRM takes an export of OSM data and then processes it to provide routes within continental sized networks within milliseconds.
OpenStreetMap Data
The main problem (outside of the normal OSRM functionality) was that Bike Streets directions need to follow the predefined Low-Stress bike map. The Low-Stress network is a subset of OSM ways containing cycleways, protected bike lanes, quiet residential streets, and similar facilities. This required a mechanism to store whether a given way is or is not part of the Low-Stress network. Storing this in the public OSM data wasn’t an option because it would violate the agreed upon conventions that keep OSM from becoming the Wild West. Therefore we decided it would be best to have a periodic copy of OSM (we call it private OSM) in an internal Postgres database with a specific tag (bikestreets=1) on the way to indicate when a way should be considered on the network. This allowed the use of the openstreetmap-website Rails application, hosted internally, pointed at the private OSM database to add the internal tags. The OSM export needed for OSRM could then be extracted from the private OSM database with all public and our (small amount of) internal data.
Bike Streets tag in OSM data
The complexity with this approach was mostly in importing new OSM data. That process went as follows:
Download a new export of public OSM data.
Run a diff process to gather all the Low-Stress network ways that had either the start or end node edited in public OSM when compared to the private OSM representation.
Update the private OSM database with the new data while carrying forward all the internal tags.
A human, who goes by the name of Avi, would go through the diff from (2) to ensure all issues identified were resolved in private OSM using the private OSM Rails application.
The issues identified in step 2 typically involved someone splitting a way (turning one way into two or more ways) or adjustments to the underlying data to make it more correct. We built internal tools to identify “network disconnections”, which are the leaf nodes in the Low-Stress network, since this essentially encapsulated all the problems from step 2 but could be represented visually to make fixing the issues easier. Most of the time these leaf nodes were just the boundary of the Low-Stress network but they could also be places where data changes or data input errors caused the network to not be continuous.
Snapshot of network leaf nodes
Initially notating the entire Low-Stress network (over 500 miles) in private OSM took some time but was easier to maintain (over 10,000 ways in Denver!) with this toolset because it helped provide assurance of network continuity while allowing data correctness updates from OSM.
Some ways in OSM are only a few feet long
Routing Engine
Now that we had a representation of which ways were on the Low-Stress network using the private OSM approach above, the next challenge was communicating this non-standard network to OSRM for routing’s sake. As mentioned before, OSRM takes OSM data and processes it to enable turn-by-turn routing. OSRM uses a Lua “profile” (example bicycle profile) to produce a score for each way, node, and turn in the OSM data.
Example Bike Streets route
Routes can generally be split up into three different components:
Safely getting from the origin to the Low-Stress network (AKA “first mile”).
Using the network to get as close to the destination (AKA “on network”).
Safely getting from the Low-Stress network to the destination (AKA “last mile”).
The “first mile” and “last mile” components are similar because these are parts of the world where the route is following infrastructure that isn’t on the Low-Stress network. The profile was updated to do many things to keep these segments of the route as safe as possible. For example, the Bike Streets routes avoid crossing large roads (think Colfax in Denver) unless a signal is present.
“First mile” and “last mile” of a Bike Streets route
The “on network” component’s main technical problem was convincing the OSRM routing algorithm to avoid leaving the network since all the Low-Stress ways had already been deemed safe by humans. “Network departures” (what we call it when the network is left mid-route) result in a poor user experience and have all the same complexities as the first and last mile segments. The routing profile had many changes to ensure the stickiness of the network is as high as possible once following it. For example, the turn penalties are increased when the turn is one that leaves the network and riding speed is considered higher when on the network.
OSRM debug output showing score of ways and turns
Wrapping Up
Hopefully this sheds some light on the way Bike Streets initially transitioned from a paper map to a digital routing algorithm powered by OSM and OSRM. First, we want to thank the developers and maintainers of all the open source programs that are used within our systems, we are truly standing on the shoulders of giants. Second, we want to thank the hundreds of thousands of OSM contributors that work tirelessly to keep OSM data accurate.
Download the Bike Streets app today to discover Low-Stress routes to any destination in your city.