Dennis Luxen wrote: >> if you organise a hierarchy of roads, say highways, then "route >> nationale", then "departementale", you can always prefer to take >> highways instead of nationales, etc, for a LONG journey. And I guess >> there is a relation between "hierarchy" and "dichotomy" somewhere. >> Where do they meet ?? > > This idea is actually a very common heuristic to find paths. There are > several commercial vendors that do their route planning that way. First, > find a nearby highway from the origin, then get as close as possible to > the destination and from there find your way "somehow" to the > destination. For those of you who have experienced bad routes with a > commercial navigation device, this is most probably the reason for it. > Exact routing in the sense of shortest = best routes is not easy to > computed on an onboard unit because of speed and memory limitations. > > In some cases, the above routing scheme might work reasonable, but this > not exact at all. When looking at shortest paths, routes can be > arbitrarily wrong with this routing scheme. Although, there is also an > exact routing algorithm called "Highway Hierarchies", which is exact and > computes a hierarchy of streets on its own. > > You can find many scientific publications on the subject at the > following website: > https://algo2.iti.uni-karlsruhe.de/english/publications.php > > I'd suggest to look at "Contraction Hierarchies". > > -Dennis > I've done a few tests with the online demo of their contraction hierarchies routing engine and the results are astonishing: South- to North- Germany in 65 milliseconds. Very impressive. But I don't know how many parameters are considered on each edge (turn restrictions, traffic lights, sharp corners etc).
It would be awesome if this routing engine could be tested with OSM data. I.e. how much disk space, preprocessing time and memory needed for generating a routing database containing the whole OSM database, and also how these parameters look like when doing routing calculations on that database. _______________________________________________ Routing mailing list [email protected] http://lists.openstreetmap.org/listinfo/routing
