In your letter dated Mon, 13 Oct 2008 16:06:31 +0200 you wrote: >Philip Homburg wrote: >> 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 >Would it help if a certain level of 'sparseness' could be guaranteed for >every layer (i.e. a minimum distance between nodes) to guarantee an >optimal solution after examining some n closest nodes of the next higher >level?
One thing that would be nice, but I'm not sure if it would fly, is to take a number of nodes n for which you can easily store all pairs shortest path results. Now, compute those results at various 'zoom levels'. At each zoom level you have virtual tiles with n nodes for which you store the APSP results. To compute a route between two nodes, a and b, you find the smallest virtual tile that contains both a and b. Then for every node in that tile, you compute the distance to a and b. The smallest sum wins. Most of this can be pre-computed because for every node in the smallest tiles you can store the distances to all nodes in encompassing tiles. >It would certainly speed up to pre-compute all (necessary) >'connection-nodes' to the next higher layer. In case of a city every >major junction would have pointers (with associated cost) to every >motorway-link that is reached at fastest solely via the secondary layer >network. Do you think like that? Would it be storage space overkill to >do that? The big question is whether at the more global level there are essentially the right number of nodes that you always want to route through (i.e. is the highway system hierarchical enough). For systems with harddisks (online route planners, etc) storage is essentially unlimited. The main bottleneck on those systems is the number of disk accesses. For portable systems, you may have to do with less storage, at the expense of more searching or less optimal routes. _______________________________________________ Routing mailing list [email protected] http://lists.openstreetmap.org/listinfo/routing
