-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 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 size. 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 > questions > > 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 > http://sourceforge.net/apps/phpbb/travelingsales/viewtopic.php?f=3&t=46&p=138 > 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 TurnRestrictedMultiTargetDijkstraRouter. 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. Marcus -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAkwqVU0ACgkQf1hPnk3Z0cRCjwCfeuZQ+rEzw161LdR0DfUIEdM2 Ix4AnRM9zIoSC+K+Xuqawhwk7/nIPltK =VoTy -----END PGP SIGNATURE-----
_______________________________________________ Routing mailing list [email protected] http://lists.openstreetmap.org/listinfo/routing
