Hi Mario,<div><br></div><div>I think Anton knows how it is done at the moment and Steve seems to know how to do it better ;-)</div><div><br></div><div>I guess that there are many TSP solvers available or recipes how to implement your own. It's kind of popular topic, I think.</div>
<div><br></div><div>One important point for me is, that a new TSP function should allow to pass a distance matrix, because the current one takes the linear distance. IMO the user should be able to decide how to calculate distances, and with Jay's APSP (all-pair-shortest-path) there is now a way to compute a "real distance" matrix much more efficient than before.</div>
<div><br></div><div>Daniel</div><div><br><br><div class="gmail_quote">On Mon, Sep 19, 2011 at 11:30 PM, Mario Basa <span dir="ltr"><<a href="mailto:mario.basa@gmail.com">mario.basa@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
Daniel,<br>
<br>
I am trying to understand this: the mutation computation will be done<br>
in SQL? Wouldn't that be expensive?<br>
<br>
For me, implementing the GA specifically for pgRouting will be the<br>
best way to remove GAUL dependency. No idea how complex that will be<br>
though.<br>
<font color="#888888"><br>
Mario.<br>
</font><div><div></div><div class="h5"><br>
On Sun, Sep 18, 2011 at 2:50 AM, Daniel Kastl <<a href="mailto:daniel@georepublic.de">daniel@georepublic.de</a>> wrote:<br>
> Hi list,<br>
> On Friday at FOSS4G in Denver I discussed with Steve about TSP, and I want<br>
> to share a bit of what we came up with:<br>
><br>
> According to Steve there is a way to solve TSP without GA (Genetic<br>
> Algorithm), and that way we could get rid off GAUL dependency and make it a<br>
> "core" function.<br>
> Instead of calculation of a distance matrix within the TSP function, the<br>
> distance matrix could be passed as a "SELECT". Then the user could decide<br>
> the way distances should be calculated. And APSP would be a nice way to<br>
> calculate a distance matrix for example.<br>
><br>
> Any other ideas how to improve the current implementation of TSP?<br>
> Do you have some other use cases with specific requirements?<br>
> Daniel<br>
><br>
><br>
> --<br>
> Georepublic UG & Georepublic Japan<br>
> eMail: <a href="mailto:daniel.kastl@georepublic.de">daniel.kastl@georepublic.de</a><br>
> Web: <a href="http://georepublic.de" target="_blank">http://georepublic.de</a><br>
><br>
</div></div><div><div></div><div class="h5">> _______________________________________________<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>
><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>
</div></div></blockquote></div><br><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>