In your letter dated Fri, 10 Oct 2008 19:32:33 +0200 you wrote: >ps: some random thoughts: >What about even more layers? >In case of greedy (dijkstra-/a*-style) BFS you could start 'searching' >until the first higher-layer-node appears, for instance a > >residential-junction. >After that stay on that layer and only examine 'arcs' to other junctions >until you reach the first 'secondary-layer-junction', after which you > >can ignore >junctions to residential (lower-level) streets and move on in bigger steps. >Once you arrive at the motorway-level you search on that layer / graph >that solely consists of arcs between 'motorway-junctions'
I'm not a routing expert, but I would search the other way around: first find the closest nodes (based on geographical distance) in the highest level (most sparse) graph, and route between those nodes. By construction, that route should be optimal. Now, compute both a route from your actual starting point to the first node in the higher level graph and to the second node. If going directly to the second node is (much) faster, then drop the first node and repeat the process. You may try a third or fourth node as well, depending on a cut off distance (how sparse is the higher level graph) or on how optimal the result has to be (it usually beter to get a good route in one second than a slightly beter 'optimal' route after one minute) For intermediate levels, you can pre-compute routes from nodes in the intermediate level to a number of nodes the next higher level. _______________________________________________ Routing mailing list [email protected] http://lists.openstreetmap.org/listinfo/routing
