[pgrouting-users] pgr_tsp performance

[Stephen Woodbridge]

Hello Diogo,

On 10/1/2014 5:27 AM, Diogo Silva wrote:
> Hello everyone,
>
> I need to determine a good route for an asymmetric travelling salesman
> type problem that can have up to hundreds of nodes.

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

> For now I was able to use the pgr_tsp function (with driving distance
> matrix input) from pgrouting to determine a route for an instance with
> 100 nodes in less than 10 seconds.

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.

> I know that this function uses a simulated annealing heuristic so I
> can't expect the optimal route, but the problem is that the output route
> is not very good, having several points where it backtracks.

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.


> What I want to know is:
>
>                  1 - Does this function usually gives good results for
> instances with 30+ nodes?

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

>                  2 - I would not have a problem with waiting up to an
> hour for the results if it meant a better route... is there a way to
> change any of the simulated annealing parameters? The algorithm seems to
> be converging prematurely.

Some pictures and an explaination 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.

>                  3 - Are there any good free libraries that you can
> suggest for this purpose apart from pgrouting?

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

Hope this helps,
   -Steve

> Thank you,
>
> Diogo Silva
>
> *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.
>
> *P****Antes de imprimir este mail, pense bem se tem mesmo que o fazer.
> Proteja o meio ambiente.***
>
>
>
> _______________________________________________
> Pgrouting-users mailing list
> Pgrouting-users at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-users
>