<div dir="ltr"><br><div class="gmail_extra"><br><br><div class="gmail_quote">On Fri, Apr 5, 2013 at 5:33 AM, Stephen Woodbridge <span dir="ltr"><<a href="mailto:woodbri@swoodbridge.com" target="_blank">woodbri@swoodbridge.com</a>></span> wrote:<br>

<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">Hi All,<br>
<br>
I'm working on porting a new TSP algorithm into pgRouting. With the follow example query:<br>
<br>
select * from tsp('select id as source_id,x,y from tsp_00', '1,2,3,4,5,6,7,8,9,10,11,12,<u></u>13,14,15,16,17,18,19,20,21,22'<u></u>, 1);<br>
<br>
Is the expected result a loop starting at node 1 and ending back there?<br></blockquote><div><br></div><div><br></div><div style>Hi Steve,</div><div style><br></div><div style>I remember these two cases for TSP:</div><div style>

<ol style><li style>Start point is defined</li><li style>Start point is defined + return to start point in the end</li></ol><div style>(1) is how it currently works</div><div style>(2) has been requested several times:</div>

<div style><br></div><div style><a href="https://github.com/pgRouting/pgrouting/issues/56">https://github.com/pgRouting/pgrouting/issues/56</a><br></div><div style><a href="https://github.com/pgRouting/pgrouting/issues/2">https://github.com/pgRouting/pgrouting/issues/2</a><br>

</div><div style><br></div><div style>Convenient would be to be able to define start as well as end point. Then returning to the start point would be just a special case where start and end point are the same:</div><div style>

<a href="https://github.com/pgRouting/pgrouting/pull/49">https://github.com/pgRouting/pgrouting/pull/49</a> (includes a pull request)<br></div><div style><br></div><div style>Google Maps API offers some optional setting for its "Directions Service", where you can indicate if the waypoints should be returned in an optimized order or in the listed order:</div>

<div style><a href="https://developers.google.com/maps/documentation/javascript/3.exp/reference#DirectionsRoute">https://developers.google.com/maps/documentation/javascript/3.exp/reference#DirectionsRoute</a><br></div><div style>

So "optimized" is lyouike TSP and otherwise it's just concatenated shortest path requests. There it's possible to specify origin and destination, which would be case (2).<br></div><div style><br></div><div style>

Daniel<br><br></div><div style><br></div><div style><br></div><div style><br></div><div style><br></div><div><br></div><div><br></div><div><br></div></div><div><br></div><div><br></div><div><br></div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">


<br>
-Steve<br>
______________________________<u></u>_________________<br>
pgrouting-dev mailing list<br>
<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.osgeo.org</a><br>
<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/<u></u>mailman/listinfo/pgrouting-dev</a><br>
</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>
</div></div>