[pgrouting-users] pgr_TSP(): how to avoid the route returning to the start point

Vicky Vergara vicky at georepublic.de
Wed Apr 18 05:43:32 PDT 2018

Hello Tom.

The traveling salesman problem (TSP) is defined as follows:
 "Given a list of cities and the distances between each pair of cities,
find is the shortest possible route that visits each city and returns to
the origin city?"

So, because of the "and returns to the original city" you wont be able to
find any option allowing not to go back to the point of origin.
On [1] you can find a nice site about TSP:

[1] http://www.math.uwaterloo.ca/tsp/


On Wed, Apr 11, 2018 at 7:35 AM, tommaso <tommasodb at googlemail.com> wrote:

> Hello, I'm testing the TSP feature using this example from the
> documentation:
>     $$
>     SELECT * FROM pgr_dijkstraCostMatrix(
>         'SELECT id, source, target, cost, reverse_cost FROM edge_table',
>         (SELECT array_agg(id) FROM edge_table_vertices_pgr WHERE id < 14),
>         directed := false
>     )
>     $$,
>     start_id := 7,
>     randomize := false
> );
> My problem is that the algorithm returns to the start point after visiting
> the last one, while in my use case this is not requested.
> There is a option to avoid this? Until now I could not find such a option
> in the documentation.
> Simply ignoring the last segment is not a solution, because in certain
> cases the order of the last and second the last points changes if the route
> goes back to the first point. So, I cannot predict which one is the desired
> last point.
> Regards, Tom
> _______________________________________________
> Pgrouting-users mailing list
> Pgrouting-users at lists.osgeo.org
> https://lists.osgeo.org/mailman/listinfo/pgrouting-users


Georepublic UG (haftungsbeschränkt)
Salzmannstraße 44,
81739 München, Germany

Vicky Vergara
Operations Research

eMail: vicky at georepublic.de
Web: https://georepublic.info

Tel: +49 (089) 4161 7698-1
Fax: +49 (089) 4161 7698-9

Commercial register: Amtsgericht München, HRB 181428
CEO: Daniel Kastl
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/pgrouting-users/attachments/20180418/062304e7/attachment.html>

More information about the Pgrouting-users mailing list