[Routing] Routing algorithms

Nic Roets nroets at gmail.com
Sun Sep 21 21:33:16 BST 2008


Well take any traveling salesman problem : You are given a graph and
required to find the shortest path from A to B that visits at all the nodes
in the 'cities' subset at least once. Now  create a new graph by adding node
C and an edge BC. Now you choose your metric to be the length of each edge,
except for BC. The metric for BC is 0 if the route travel included visits to
all the cities, and very large (sum of all edges / infinite) otherwise. Now
you have Stefan's problem. So finding an efficient solution for the general
case looks very unlikely.

On Sun, Sep 21, 2008 at 9:18 PM, Marcus Wolschon <Marcus at wolschon.biz>wrote:

> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> Nic Roets schrieb:
> > (So why didn't Stefan say that in the first place ...)
> >
> > The turn restriction problem is easy to solve once you realize that
> >  OSM nodes need not correspond to graph vertexes. The graph
> > vertexes are states (search google for state machine).
> >
> > Let's say node N1 is part of  one simple turn restriction relation
> > W1,N1,W2 and one complicated turn restriction relation
> > W3,N2,W4,N1,W5. Then we would associate 3 states with N1 : N1a : N1
> > was reached after traveling along W1. N1b : N1 was reached after
> > traveling along W3, then N2, then W4. N1c : N1 was reached in some
> > other way.
> >
> > And N2 will have at least 2 states associated with it.
>
>
> Yes, that will work for me. Thanks for the idea!
> Expand a node into a small graph with one-way
> - -edges that represents the same rule.
>
> This however is my problem. Stefan has a different
> issue. His metric depends on the metric of the path
> used to reach the currently evaluated node.
>
> Marcus
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.4.6 (GNU/Linux)
> Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org
>
> iD8DBQFI1p33f1hPnk3Z0cQRAtfTAJ4p73mDHfTnrfWkwI5cPskf78FVnwCeMYzd
> WLWLzSTZAZ15NfBwfvg7qHI=
> =B560
> -----END PGP SIGNATURE-----
>
>
> _______________________________________________
> Routing mailing list
> Routing at openstreetmap.org
> http://lists.openstreetmap.org/listinfo/routing
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstreetmap.org/pipermail/routing/attachments/20080921/e2998b9d/attachment.html>


More information about the Routing mailing list