[Routing] How to Establish Road Hierarchy

[David Piepgrass]

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

Oh? So where in the paper does it mention the number or ratio of shortcuts to direct edges?

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

That's neat... what is the "edge-expanded" representation?

I whipped up a demo to show what I'm talking about... I lost track of the original graphs that were giving me 10x ratios, but this one I just made has a 7x ratio.
http://qscribble.blogspot.ca/2012/12/contraction-hierarchies.html 

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

Possibly, but other than slow flash memory and a less efficient on-disk layout, I couldn't find the problem. The tricky thing about CHs is that they can work perfectly in terms of routing, but still have some hidden flaw that makes them run more slowly, with no obvious way to track it down.

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

10x faster compared to my own CH implementation (which in turn was over 100x slower than the implementation made by the team that invented them.) I had trouble understanding how the dynamic version of CHs worked, but it appeared to me that there would be a substantial performance impact that I obviously couldn't afford, given that my implementation was already too slow (no performance figures had been published at the time though.)