[Routing] Find shortest path using OSM format file for a country.
Marcus at Wolschon.biz
Tue Jun 29 21:19:26 BST 2010
-----BEGIN PGP SIGNED MESSAGE-----
Am 29.06.2010 21:24, schrieb Oleg Demchenko:
> I have more specific question about
> TurnRestrictedMultiTargetDijkstraRouter class. My understating it
> is more advanced router from
> org.openstreetmap.travelingsalesman.routing.routers Problem is for
> some Target/Single nodes selected with .GetNearestNode method
> distanced each other 15-20 Kms route method get a "dead" loop. Even
> after 20 minutes it continue calculates something ( I see it from
> console). From other side if I change Start or Target coordinates a
> little bit, route method could be completed successfully after
> 10-15 secs.
If you find a test-case that can be reproduced with a map of managable
Please open a ticket in the bug-reporting.
Finding the cause of such issues is important.
(Even though I cannot promise to have a look myself as I
an moving to a new job at the moment.)
> Taking into account find ANY car route between to points is on top
> priority for my application comparing with other options (find a
> best way using one turn-restrictions (etc) I have the following
> 1) Does TurnRestrictedMultiTargetDijkstraRouter is suitable for my
> case ( I believe Yes:-))
Yes, it is.
You may be faster and more reliable with one of the simpler algorithms
but the resulting routes may be illegal due to turn-restrictions.
> 2) Shall I pass to route method collection of Target nodes instead
> of single node? How to find this collection?
> getNearestNode()returns a single node.
You could pass it e.g. all nodes in a given radius but it is okay to
route to any random node in this set.
> 3) It is possible to ask route method after N seconds of
> processing: well, give me actual best path you've found for this
> moment. I see addProgressListener for this class.
Not with the ProgressListener (that is only for progress-bars) and not
with this routing-algorithm.
This algorithm aborts as soon as it reaches the start-node from the
set of target-nodes. So if you abort,
you will only get a minimum-cost path that comes near the start-node
but you will not have a route from
the start-node to any of the target-nodes.
> 4) Any links on source examples to find how last
> TurnRestrictedMultiTargetDijkstraRouter is working? Link
> http://travelingales.sourceforge.net/ts.jnlp from
> page is broken.
> From my side I'm ready to prepare a document like "How to find
> optimal car/vehicle/pedestrian path with
> TurnRestrictedMultiTargetDijkstraRouter?" with a concept and
> source code example when explore it with myself.
If you want to understand how it is working, you may read the
DijkstraRouter, then MultiTargetDijkstraRouter and then
The idea behind the MultiTargetDijkstraRouter is to route from target
to start and to let the target be a set of nodes connecting to a
virtual target-nodes with links of metric 0.
The turn-restricted variation improves on that by routing not on edges
of the graph but on pairs of edges. This we we can disallow to make
certain turns on intersections.
It´s not very complicated, quite managable in code-size and the
comments try to explain what is done pretty well.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/
-----END PGP SIGNATURE-----
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Routing