[Routing] How to Establish Road Hierarchy

[Dennis Luxen]

Am 11.12.2012 um 19:45 schrieb David Piepgrass <dpiepgrass at mentoreng.com>:

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

+1

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

The categorization is quite alright, but mileage may vary depending on your categorization heuristic.

> 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 

It is _A_GPL. A much simpler, but improved implementation is the basis of OSRM [1]. Note that neither implementation is suitable for handheld/mobile devices.

--Dennis

[1] http://project-osrm.org