[Routing] How to Establish Road Hierarchy

[David Piepgrass]

>A* is just so much more flexible. For example, you can add a new vehicle type without 
>any significant penalty in terms of preprocessing. Or avoid traffic jams that 
>change frequently. And the flexibility can result in significant savings on fuel and time.

Yes, but it's not the only way to gain flexibility. My own hierarchical bidirectional Dijkstra algorithm can do that too (the basic idea of it is creating successive simplified versions of the road network based on manually-determined road attributes--without the rigid need for the search to always go up to higher levels, as in CHs). There is also an approach that allows CHs to be dynamic, although AFAIK it is underdocumented (I saw one paper that mentioned the idea, but it's very hard to follow ... and I can't find seem to find it); oh and in a similar vein, one might want to look at the paper "Route Planning with Flexible Objective Functions" (Robert Geisberger, Moritz Kobitzsch and Peter Sanders).

>Furthermore, as computers get cheaper and devices get faster, the difference in 
>speed between A* and CH is becoming insignificant.

The ratio between A* and CH is independent of processor speed. A* speed is O(N) amortized over many random routes in a road network of size N, while CH is closer to O(log N) under the right conditions. In large road networks, there is no comparison. A* is not even faster than Dijkstra necessarily, and when it is faster, it is only faster by a constant factor (same big-O).

I have found it is better to do bidirectional Dijkstra rather than unidirectional A*, as the speed increase versus normal Dijkstra is reliably 2x and once you have a bidirectional algorithm, it is more straightforward to optimize it compared to a unidirectional algorithm (you can do bidirectional A* too, it's just easier to start with Dijkstra.)