[pgrouting-users] pgr_tsp performance

[Diogo Silva]

Thanks you for the quick reply. :-)


-----Original Message-----
From: pgrouting-users-bounces at lists.osgeo.org [mailto:pgrouting-users-bounces at lists.osgeo.org] On Behalf Of Stephen Woodbridge
Sent: 1 de outubro de 2014 15:21
To: pgrouting-users at lists.osgeo.org
Subject: Re: [pgrouting-users] pgr_tsp performance

Hello Diogo,

---

First off as of pgRouting 2.0 we only solve the symmetric TSP. Although some is working on an asymmetric solver.

Yes, I have been looking over the pgr_tsp source code and saw some comments on it about what changes need to be done for it to work on an asymmetric TSP. But I did not wanted to change the code unless I was sure it was the cause of the problem.
Do you think using a non-symmetrical distance matrix as input for  pgr_tsp can be the cause of problem? In my case, the distance from A to B can be very different than that from B to A because of one-way streets. (see attachment).

---

You probably need to break down what costs what here. I believe the time here is being spent on computing the distance matrix and NOT on solving the TSP which is very fast and has no problem handling 100 nodes.

Sorry I did not go into more detail on this part. I pre-calculated the distance matrix (driving distances by road) on another one of my functions using the pgr_kdijkstraCost function. You are right, the pgr_tsp function is more than fast enough for what I need. The 10 seconds I mentioned include the execution of other parts of code. Time is not the problem for me.

---

TSP is ONLY solving the order of the nodes based on the distance matrix. 
When you map the order of the nodes to a road network is will backtrack.

       o       o       o
       |       |       |
       A       B       C
       |       |       |
------+-------+-------+------

Say you have a TSP solution that has a sequence of ....,A,B,C,.... but the road network above where A, B, C are on dead-end streets you can only sevice them by back track on the route.

Yes, of course, I agree. But the cases I am referring to are like this:

	--A-----B-----C-----D-----E--

Say you have a normal two-way street with five service points. The type of backtracking solution I am talking about contain segments like: ...,A,D,B,C,E,...

The attachment has some pictures of two parts of the same route (step 1 to 14 and step 29 to 38) and a picture showing one-way streets. Black lines are the roads, green lines are roads used in the route, yellow node and line represent the current step start node and path.

I have tested this visualization method with a route that I manually created as if it were the output of the pgr_tsp funtion and it worked fine, so doubt the problem is in converting the output of the pgr_tsp funtion to QuantumGIS.

---

The function give good results regardless of the number of nodes.

Good to know.

---

Some pictures and an explanation of what you think is wrong would help a lot here. You can also play with the source code and change the parameters if you want. I think it is working fine for the problems it was intended to solve and that the problem is that it might not be the correct tool for your problem (based on symmetric vs asymmetric), but I happy to be convinced otherwise.

(See attachment)

---

Yes, lots are available on the net google is your friend.
https://www.google.com/?gws_rd=ssl#q=asymmetric+tsp+source+code

Thanks, yes he is. :-)



AVISO DE CONFIDENCIALIDADE: Este e-mail e quaisquer ficheiros informáticos com ele transmitidos são confidenciais e destinados ao conhecimento e uso exclusivo do respectivo destinatário, não podendo o conteúdo dos mesmos ser alterado. Caso tenha recebido este e-mail indevidamente, queira informar de imediato o remetente e proceder à destruição da mensagem. 

CONFIDENTIALITY WARNING: This e-mail and any files transmitted with it are confidential and intended solely for the use of the individual or entity to whom they are addressed. Their contents may not be altered. If you have received this e-mail in error please notify the sender and destroy it immediately.


-------------- next part --------------
A non-text attachment was scrubbed...
Name: Route.zip
Type: application/x-zip-compressed
Size: 1499303 bytes
Desc: Route.zip
URL: <http://lists.osgeo.org/pipermail/pgrouting-users/attachments/20141002/9fb8f72f/attachment-0001.bin>