[Routing] How to Establish Road Hierarchy

[David Piepgrass]

> There is no need for an explicit hierarchy. Routing is best done by applying
> weightings to each route segment, which is an arc in the directed graph, so as
> to create an overall arc cost that, broadly speaking, is the estimated time
> taken to traverse that arc.
> 
> You can use the OSM information in the 'highway' tag as input data to your
> weighting system. For example, I use an estimated speed of 120kph for a
> motorway, 80kph for a motorway link, 110kph for a trunk road, etc.
> 
> Then you should use the A* routing algorithm, and the best route according
> to those weightings will be found.
> 
> I have developed a routing system (part of CartoType, which is free for non-
> commercial use). My experience has been that A* is all you need - as long as
> you code it up carefully, with due regard for speed optimisation, it works fast
> enough even on mobile devices.

In my experience as the author of routing software for 400MHz ARM devices, you're wrong. Hierarchical routing is necessary for long-distance routing. You can get away with bidirectional A* and no hierarchy for up to medium distances, but for long distances or in megacities (Los Angeles) I would strongly recommend some kind of hierarchical approach that entirely excludes minor roads from the search.

I haven't used OpenStreetMap data myself but I expect it might have problems with quality control on the road categories. If even a single tiny road segment on a major highway is marked as a minor road, long-distance hierarchical routing that excludes that road from the search "because it's minor" will fail or will find a poor route. To avoid such problems, the contraction hierarchy or highway hierarchy techniques (derived from Dijkstra rather than A*) can be used. These are challenging to implement correctly and efficiently, but do not depend on road attributes that are consistently accurate, and a GPL implementation of the contraction algorithm is available.

http://algo2.iti.kit.edu/documents/routeplanning/geisberger_dipl.pdf