We need a whole lot of point-to-point routes for our multi-stop routing system. As we use Openstreetmap as a source for this, we’ve set up a comparison between two well-known OSM routing systems: Gosmore and OSRM.
First of all, we have set up this test for our own needs. It’s not meant to be representative for all routing needs in all situations. The results and conclusions do not need to be valid for you. If you understand this and agree, continue reading.
Why: distance matrix
To find the fastest route with multiple stops, we need to know A-to-B travel durations between all points. To visit 4 destinations from one origin location, we need to route 5 x 4 = 20 legs. This travel distance matrix grows exponentially. With 40 destinations, it’s 41 x 40 = 1.640 legs, with 80 destinations 6.480 legs, and so on.
So, how long does your in-car navigation take to find the route to one destination? If it’s fast, it will do so within one second. That seems fast, but with 1.000 legs that’s more than 16 minutes. We don’t want our users to wait that long. We need to be ready and done in less than that, which includes the optimization itself.
Therefore, we minimize the number of legs that we actually need for our optimization, we want the fastest routing system available and run it on multiple dedicated servers.
What: OSM routers
Openstreetmap, the free map of the world, is the base that we use for our multi-stop routing optimization models. It’s free to use and the whole planet is only some tens of gigabytes to download. And there is a bunch of free software that use OSM for route calculation.
Earlier, we selected the renowned Gosmore as the router for its good performance, stability and generous license. It’s programmed in C++ and works great on our setup with dedicated Linux servers. But its development is not too active and seems more aimed towards stand-alone navigation for Android devices.
Recently, another well-known routing machine OSRM changed its rather restrictive license. Previously it was licensed under the AGPL. Since October 2013 it’s made available under the very permissive (simplified) 2-clause BSD license. It’s meant to run as a service, which seems more geared to our need. It’s also C++ and its development seems more active.
Note: there are many more routers for Openstreetmap.How: setup for multiple routes
We used the latest Gosmore and OSRM, build from source on the same Intel i7 2.6 GHz machine with 8 GB RAM, running Ubuntu Linux Desktop 13.10. Gosmore was build headless (no GUI). For both routers we prepared maps of the Netherlands, as described in their documentation.
A php script was used as a wrapper to call both routers. That is: OSRM is used as a rest service and Gosmore as a plain system command (exec with a CPU limit of 1 second). The script generates random legs, which are made up by two random locations (lat, lng) in an fixed area in The Netherlands. These locations may not be real addresses, they can also be in the midst of a forest or a lake. Our users do enter all kinds of locations they need to visit for work or pleasure, not necessarily homes or businesses only.
We had both Gosmore and OSRM find the route for each leg. We checked wether a route was found, wether the travel duration was valid and measured the time spent for the calculation. We validated by comparing each duration with an estimated minimum and maximum value. Those were calculated from the leg distance as the crow flies, the maximum speed limit 130 km/h (minimum duration) and a walking speed of 5 km/h (maximum duration).
Test results
While one run of the script should be enough, we ran it three times. The output:
Run #1
Total legs: 1000
Total time OSRM: 7.851sec, Gosmore: 170.296 sec
Success OSRM: 96.5%, Gosmore: 94.6%
Too slow OSRM: 0%, Gosmore: 0%
Too fast OSRM: 0%, Gosmore: 0%
Run #2
Total legs: 1000
Total time OSRM: 7.941sec, Gosmore: 174.774 sec
Success OSRM: 96.8%, Gosmore: 94.7%
Too slow OSRM: 0%, Gosmore: 0%
Too fast OSRM: 0%, Gosmore: 0%
Run #3
Total legs: 1000
Total time OSRM: 7.785sec, Gosmore: 168.599 sec
Success OSRM: 95.5%, Gosmore: 94.9%
Too slow OSRM: 0%, Gosmore: 0%
Too fast OSRM: 0%, Gosmore: 0%
The winner: OSRM (faster, but fat)
Both routers have a high success rate. Close to 100% of all legs are successfully routed. Those legs that were routed, meet all the validity checks. But OSRM is faster, a lot faster. It calculates routes for 1000 legs in less than 8 seconds, where Gosmore takes roughly 2 minutes and 50 seconds.
Based on this test results, we have a clear winner and OSRM seems to be more fit for our job. It has the same quality as Gosmore, but is much faster.
There is one remark to be made. We ran this test on a rather small map of The Netherlands. So far, we did not succeed in getting OSRM to run for the whole planet, which we need for our public routing service. Gosmore does serve routes all over the planet on rather small, and cheap, but dedicated servers (currently: Amazon EC2 c3.large). So, while OSRM is very promising, we need another effort to get it to work for us.