[pgrouting-dev] TSP Question

[Daniel Kastl]

On Fri, Apr 5, 2013 at 5:33 AM, Stephen Woodbridge
<woodbri at swoodbridge.com>wrote:

> Hi All,
>
> I'm working on porting a new TSP algorithm into pgRouting. With the follow
> example query:
>
> 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,**13,14,15,16,17,18,19,20,21,22'**, 1);
>
> Is the expected result a loop starting at node 1 and ending back there?
>


Hi Steve,

I remember these two cases for TSP:

   1. Start point is defined
   2. Start point is defined + return to start point in the end

(1) is how it currently works
(2) has been requested several times:

https://github.com/pgRouting/pgrouting/issues/56
https://github.com/pgRouting/pgrouting/issues/2

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:
https://github.com/pgRouting/pgrouting/pull/49 (includes a pull request)

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:
https://developers.google.com/maps/documentation/javascript/3.exp/reference#DirectionsRoute
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).

Daniel













>
> -Steve
> ______________________________**_________________
> pgrouting-dev mailing list
> pgrouting-dev at lists.osgeo.org
> http://lists.osgeo.org/**mailman/listinfo/pgrouting-dev<http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>
>



-- 
Georepublic UG & Georepublic Japan
eMail: daniel.kastl at georepublic.de
Web: http://georepublic.de
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20130405/b45e3552/attachment.html>