OSRM and Valhalla are two popular open source routing engines. Both of them have worldwide contributors, majority developer for OSRM is MapBox and Lyft, for Valhalla is MapZen and Tesla.
MapBox, Pinterest and Foursquare chosed OSRM for cloud routing. Tesla selects Valhalla as its navigation engine.
This page tracks highlights from both engines, we also try to list design tradeoffs so it would be easier to find best practise.
One Line Summary
- OSRM: accurate route with live traffic, monolithic data, high memory needs, very high performance
- Valhalla: flexible tiled data, customizable routing, low memory requirements, reasonably fast point-to-point routing
Direction as service
Hide all logic such as algorithm/version control/traffic in the service itself. Both of them use node.js to provide restful request and response.
Release Docker
Docker image hides the complexity of dependency management and deployment complexity
Separate algorithm with dynamic configuration
For data import and cost model, both of the engine use Lua to manage frequently change items
Algorithm
OSRM provides an example of modern cloud solution.
Its routing solution is based on CRP, which has been widely used by cloud based navigation products. CRP considers all elements during real time route calculation which provides a firm foundation for cloud routing application, while all previous Telenav cloud routing solution need to have trade-off between quality and performance during handling real time information.
OSRM's MapMatching solution is based on Hidden Markov Model and Viterbi, which also proven to be standard and best practice. The same strategy also be used in Valhalla Map Matching.
Data structure
To hide complexity of geographic road graph information, OSRM defines graph representation which decouples graph algorithm with cost model
Data Schema
Valhalla gave us an example of how to design data schema for Streaming
Fixed tile's boundary in Valhalla makes its easy to enable streaming feature, like caching home area data, onboard routing and guidance.
Valhalla could calculate route for multiple mode, such as pedestrian, bike, public transportation.
Parallel processing
Both of them use OSMIUM and Intel-ThreadBuildingBlocks to speed up processing. OSMIUM helps to divide and conquer large input files, ThreadBuildingBlocks act as MapReduce in single process.
| OSRM | Valhalla | |
|---|---|---|
| Summary by Kevin Kreiser | 1. It precomputes routes so requests are super fast (faster than valhalla) 2. The precomputed stuff is stored in memory so depending on your dataset you might need a lot of ram 3. Precomputing them means you can't get different routes at runtime (ie. avoid tolls, favor hills, penalize ferries, etc) because its precomputed it will only support one mode of travel 4. Localization support is better although comes via a javascript add-on |
1. It only stores the graph so routes are computed on the fly (slower than OSRM) 2. It doesn't store the entire graph in memory so you can run it on memory constrained devices 3. You can get different routes at run time by varying some parameters in the request 4. Since it stores the graph you can change mode of travel on the fly (bike/ped/car/motorcycle/truck/etc) 5. Localization is built into the engine but not as extensive as OSRMTI 6. The data is tiled so you can make the planet and then distribute smaller extracts 7. Supports time based routing 8. Supports transit routing 9. Supports isochrones |
| Pros (Feature could learn) |
Support display-tile service Support multi-mode travel |
Support streaming feature is its original target Fixed tile boundary Road data is not duplicated between levels(shortcuts are built on lower levels with high function class edges) |
| Cons (Need improve) |
Additional effort for HERE/TomTom support Complex restriction and condition oneway is not supported TomTom Traffic source support Large memory usage |
Not much of data compression strategy(profile) Only one thread for initilization Lack of code orgnization for forward/backward compatibility |
Use business-readable specifications to test product features
Both of engines provide sufficient unit test to guarantee code quality, and also implement javascript framework to visualize routing test result, but most impressive part is the use of Cucumber testing framework in OSRM. It enables product owner or QA to use stories to write testing cases, which guides final result is really the expected one. You could find samples here.