Hi,<br><br><div class="gmail_quote">On Sat, Sep 17, 2011 at 11:20 PM, Daniel Kastl <span dir="ltr"><<a href="mailto:daniel@georepublic.de">daniel@georepublic.de</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
Hi list,<div><br></div><div>On Friday at FOSS4G in Denver I discussed with Steve about TSP, and I want to share a bit of what we came up with:</div><div><ul><li>According to Steve there is a way to solve TSP without GA (Genetic Algorithm), and that way we could get rid off GAUL dependency and make it a "core" function.</li>
</ul></div></blockquote><div>I believe TSP is a NP Complete problem. So a polynomial time solution does not exist. Steve, can you elaborate what heuristic might be used besides GA?<br> </div><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
<div><ul>
<li>Instead of calculation of a distance matrix within the TSP function, the distance matrix could be passed as a "SELECT". Then the user could decide the way distances should be calculated. And APSP would be a nice way to calculate a distance matrix for example.</li>
</ul></div></blockquote><div>+1 for use of APSP!<br></div><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"><div><ul>
</ul><div>Any other ideas how to improve the current implementation of TSP?</div></div><div>Do you have some other use cases with specific requirements?</div><div><br></div><div>Daniel</div><div><br></div><font color="#888888"><div>
<br clear="all">
<div><br></div>-- <br><span style="font-family: arial,sans-serif; font-size: 13px; border-collapse: collapse;">Georepublic UG & Georepublic Japan<br>eMail: <a href="mailto:daniel.kastl@georepublic.de" style="color: rgb(66, 99, 171);" target="_blank">daniel.kastl@georepublic.de</a><br>
Web: <a href="http://georepublic.de/" style="color: rgb(66, 99, 171);" target="_blank">http://georepublic.de</a></span><br>
</div>
</font><br>_______________________________________________<br>
pgrouting-dev mailing list<br>
<a href="mailto:pgrouting-dev@lists.osgeo.org">pgrouting-dev@lists.osgeo.org</a><br>
<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/mailman/listinfo/pgrouting-dev</a><br>
<br></blockquote></div><br><br clear="all"><br>-- <br>Regards,<br>-Jay Mahadeokar<br><br>