[Routing] generalized routing format

[Marcus Wolschon]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

David Lynch schrieb:
> On Fri, Oct 10, 2008 at 12:32, flo Detig <florian_detig at yahoo.de>
> 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

I thought about such a thing but found that to only work
out if you are loading complete layers into memory.
If you load single ways with their nodes and attriutes
from your data-store you can stick to Dijkstra/A* and
know to get an optimal result even in cases where there
is a higher-order-road near to start- and one near to end-
node but both are in the opposide direction of the short
direct connection from start to end.
Checking out the ways with the lower cost, e.g. length*(1-order)
will take care of all the layering you need.

Here it makes sense to use the order of the road
(motorway,motorway-link,trunk,trunk-link,...,track)
to order the ways in your storage, so that higher order
roads are feched faster and cached longer then lower order
ones.

>
> I'm working on testing an idea that works backwards from the
> destination and forwards from the origin at the same time and stops
>  when they intersect each other. That sounds like it would be a
> solution to your problem.
I think this will be slower then to go from target to start
because it cripples your caching. In your case you have
half your memory filled with cached roads from the target
and half from the start, both with reduced hit-rates compared
to a single cache storing local roads around the one area
you are currently examining.

Marcus



-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFI8Ml+f1hPnk3Z0cQRAofbAJ46V8C5KWjk2rNToGy4nIcAgsyFXwCeI3A5
8pdrOQAN7RtaAcuCXhnGbuE=
=H1Vi
-----END PGP SIGNATURE-----