[Routing] generalized routing format

[Philip Homburg]

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.