[Routing] How to Establish Road Hierarchy

[David Piepgrass]

> 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.

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 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).

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. Plus my data structures re-used my existing serialization code so they weren't well optimized for CHs specifically. 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.

I would be curious to hear if someone knows how to represent turn restrictions without greatly bloating up the CH. 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.)