[Routing] generalized routing format

[Philip Homburg]

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.