Doing some highway/routing QA with Mapbox's Distance API

Posted by naoliv on 2 October 2015 in English (English)

After reading about Mapbox’s Distance API I thought “Hmmm… this could be used to QA highways…”.

Nothing suspicious was found after taking a (really) quick glance at the distance matrix from the 100 most populous cities in São Paulo state.

But when using the 3 most populous cities from each state in Brazil we saw that Parintins was isolated from the world (and it seems that it was isolated since always).
boneco forcibly^W kindly fixed it in #34348258.

We still need to test some ideas (and milky needs to code them), but we think that they should bring improvements in detecting broken routes (as we could see with Parintins) and misclassified highways.

Comment from flohoff on 2 October 2015 at 17:50

I had a QA prototype running for years since OSRM was released. The problem i have and had is that OSRM does not in all cases produce reproducible results. In case there are multiple routes you’ll one of them or all - you cant reliably tell which. The cause here is that OSRM does some rounding on the travel time and thus it is easy to have exact same distances e.g. travel times. Now the sort order of the osrm indexes will decide which route you’ll get returned. As the sorting of the index is multithreaded on preparation of the index the order changes and voila - you get random results.

My QA system recreated the OSRM index every 4 hours and then calculated ~100-150K routes between selected nodes. I then compared the lengths of the routes and when the length changed by more than 300m or 10% i got an email with a link of the 2 route geometries. This caused a wide network of important roads to be checked. Also motorway exits were checked if you would be allowed to leave or enter a motorway.

The problem with the non reproducible routes is that suddenly certain routes started to flap between alternates and there is no way to stop this with OSRM.

See this thread:

In the end i ended the RouteQA with OSRM. I need to have a look at graphhopper or the valhalla stuff. OSRM is unsuitable for this.


Comment from SomeoneElse on 9 October 2015 at 10:53

@flohoff - would a changing travel time still help to indicate that there’s a problem? As I read it from it sounds like the alternative routes all have the same length.

Comment from karussell on 9 October 2015 at 15:57

Interesting! So you check only the connectivity or also the distance changes over time like @flohoff is doing? If the first, then you should be able to easily do this with (a local) GraphHopper, it is called subnetwork calculation and will be much faster and precise with regards to the precise node set. Or just use normal route calculation.

@flohoff let me know if you need support when testing this with graphhopper :)

BTW: GraphHopper is deterministic, even if it does stuff in parallel while import.

Comment from sabas88 on 9 October 2015 at 19:26

I wrote a tool to bruteforce routes with OSRM (before distance matrix was implemented), but I didn’t succeed in using it as a QA tool because of the amount of data required - for a country. Instead I did use it at regional scale to compute matrices between points.

Valhalla could be cool to try for this kind of tests

Login to leave a comment