[Routing] How to Establish Road Hierarchy

[Dennis Luxen]

Am 11.12.2012 um 20:50 schrieb David Piepgrass <dpiepgrass at mentoreng.com>:

>> See here for results on a mobile implementation.
>> 
>> http://algo2.iti.kit.edu/1264.php
>> 
>>> I would be interested to hear how OSRM can be both simpler and
>> improved at the same time.
> 
> Yeah, I've seen that. This reminds me: one should not expect anywhere near 100ms from one's own implementation, it's not realistic for a commercial-grade product. Their optimizations were very good, plus they used a "simple" contraction hierarchy in which nodes in the graph represent intersections and edges in the graph represent roads. So their code was very fast but it has a key problem: it cannot represent turn restrictions.

Right, the test set that was used for the experiments did not have any turn restrictions.

> The inventors of the CH wrote another brief paper ("Route Planning in Road Networks with Turn Costs") that solved the problem (in the same way I had earlier), by representing roads as pairs of nodes (one for each direction of travel) and intersections as clusters of edges (one edge per transition between roads.) Their paper on the subject leaves out the fact that the contraction hierarchy expands wildly in size when you use this representation, especially if you also model turn costs (as I did, with different costs for left and right turns).

I do not think this is left out.

>  found out (too late to change my implementation) that the CH becomes about 10x as large and contracts far, far more slowly (it's 3x bigger due to the change in representation and >3x again due to the additional shortcuts).

It is less than your estimated factor of 10. OSRM uses a so-called edge-expanded representation that handles turn restrictions. It is more like a factor of 2-3.

> So ultimately, my home-grown implementation, with its vastly larger hierarchy, was more than 100x slower than theirs. Not only was the hierarchy as a whole 10x bigger, I suspect the size increases were disproportionately in the higher levels of the hierarchy, where the routing algorithm spends most of its time.

If there is more than two orders of difference in the running time then I suspect something is wrong with the implementation.

> Plus my data structures re-used my existing serialization code so they weren't well optimized for CHs specifically.

Oh well.

> Plus my flash memory was really slow. Bottom line, if you're gonna use CHs, either settle for the simple kind (which will not enforce turn restrictions or represent turn costs) or figure out some hybrid approach.

Not necessarily true.

> I would be curious to hear if someone knows how to represent turn restrictions without greatly bloating up the CH.

As I wrote above. Factor of 2-3 with edge-expansion.

> As for me, I couldn't think of a way to support the turn restrictions, and ended up rewriting all the routing code to use a relatively simple "heuristic" hierarchical algorithm that was about 10x faster and required far less space, but still modeled turn restrictions and turn costs and cheaply allowed dynamic cost increases (e.g. temporarily prohibiting routing on ferries or gravel roads or roads with less than 9 feet of clearance, which CHs don't normally handle dynamically.)

10x faster compared to what algorithm? There is also a dynamic CH query that handles a number of blocked/clogged roads easily.