<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40"><head><META HTTP-EQUIV="Content-Type" content="text/html; charset=ISO-8859-1"><meta name=Generator content="Microsoft Word 15 (filtered medium)"><style><!--
/* Font Definitions */
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0cm;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri","sans-serif";
mso-fareast-language:EN-US;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:#0563C1;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:#954F72;
text-decoration:underline;}
span.EmailStyle17
{mso-style-type:personal-compose;
font-family:"Calibri","sans-serif";
color:windowtext;}
.MsoChpDefault
{mso-style-type:export-only;
font-family:"Calibri","sans-serif";
mso-fareast-language:EN-US;}
@page WordSection1
{size:612.0pt 792.0pt;
margin:70.85pt 3.0cm 70.85pt 3.0cm;}
div.WordSection1
{page:WordSection1;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]--></head><body lang=PT link="#0563C1" vlink="#954F72"><div class=WordSection1><p class=MsoNormal><span lang=EN-US>Hello everyone,<o:p></o:p></span></p><p class=MsoNormal><span lang=EN-US><o:p> </o:p></span></p><p class=MsoNormal><span lang=EN-US>I need to determine a good route for an asymmetric travelling salesman type problem that can have up to hundreds of nodes.<o:p></o:p></span></p><p class=MsoNormal><span lang=EN-US>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.<o:p></o:p></span></p><p class=MsoNormal><span lang=EN-US>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.<o:p></o:p></span></p><p class=MsoNormal><span lang=EN-US><o:p> </o:p></span></p><p class=MsoNormal><span lang=EN-US>What I want to know is:<o:p></o:p></span></p><p class=MsoNormal><span lang=EN-US><o:p> </o:p></span></p><p class=MsoNormal><span lang=EN-US> 1 - Does this function usually gives good results for instances with 30+ nodes?<o:p></o:p></span></p><p class=MsoNormal><span lang=EN-US> 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.<o:p></o:p></span></p><p class=MsoNormal><span lang=EN-US> 3 - Are there any good free libraries that you can suggest for this purpose apart from pgrouting?<o:p></o:p></span></p><p class=MsoNormal><span lang=EN-US><o:p> </o:p></span></p><p class=MsoNormal><span lang=EN-US><o:p> </o:p></span></p><p class=MsoNormal>Thank you,<o:p></o:p></p><p class=MsoNormal>Diogo Silva<span style='mso-fareast-language:PT'><o:p></o:p></span></p></div><p><font size="1"></font></p><font size="1"><span lang="EN-GB" style="FONT-SIZE: 8pt; COLOR: #333333; FONT-FAMILY: "><p style="MARGIN: 0cm 0cm 0pt; TEXT-ALIGN: justify"><font color="#000000"><strong><span lang="PT" style="FONT-SIZE: 8pt; mso-ansi-language: PT">AVISO DE CONFIDENCIALIDADE</span></strong><span lang="PT" style="FONT-SIZE: 8pt; mso-ansi-language: PT">: 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. <p /></span></font></p><p style="MARGIN: 6pt 0cm 0pt; TEXT-ALIGN: justify"><font color="#000000"><strong><span lang="EN-GB" style="FONT-SIZE: 8pt; LINE-HEIGHT: 115%; mso-ansi-language: EN-GB; mso-fareast-font-family: Calibri; mso-fareast-theme-font: minor-latin; mso-fareast-language: EN-US; mso-bidi-language: AR-SA">CONFIDENTIALITY WARNING</span></strong><span lang="EN-GB" style="FONT-SIZE: 8pt; LINE-HEIGHT: 115%; FONT-FAMILY: "Times New Roman","serif"; mso-ansi-language: EN-GB; mso-fareast-font-family: Calibri; mso-fareast-theme-font: minor-latin; mso-fareast-language: EN-US; mso-bidi-language: AR-SA">: 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.</span></font></p><p style="MARGIN: 6pt 0cm 0pt; TEXT-ALIGN: justify"><font size="1"><span lang="EN-GB" style="FONT-SIZE: 8pt; COLOR: #333333; FONT-FAMILY: "> </span><b><span lang="EN-GB" style="FONT-SIZE: 24pt; COLOR: green; FONT-FAMILY: Webdings; mso-ansi-language: EN-GB">P</span></b><strong><span lang="EN-GB" style="FONT-SIZE: 24pt; COLOR: green; FONT-FAMILY: "> </span></strong><strong><span lang="PT" style="FONT-SIZE: 8pt; COLOR: #006600; FONT-FAMILY: ">Antes de imprimir este mail, pense bem se tem mesmo que o fazer. Proteja o meio ambiente.</span></strong><b><span lang="PT" style="FONT-SIZE: 8pt; COLOR: navy; FONT-FAMILY: "></span></b></font></p><p><font size="1"></font></p></span></font>
</body></html>