> 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 _______________________________________________ Routing mailing list [email protected] http://lists.openstreetmap.org/listinfo/routing
