[pgrouting-users] pgr_tsp performance

[Diogo Silva]

Hello everyone,

I need to determine a good route for an asymmetric travelling salesman type problem that can have up to hundreds of nodes.
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.
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.

What I want to know is:

                1 - Does this function usually gives good results for instances with 30+ 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.
                3 - Are there any good free libraries that you can suggest for this purpose apart from pgrouting?


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.


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/pgrouting-users/attachments/20141001/2ee75c6e/attachment.html>