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

pgRouting pgrouting-users
1

Hello, I'm testing the TSP feature using this example from the documentation:

SELECT * FROM pgr_TSP(
     $$
     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

2

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/

Regards

Vicky

···

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

Hello, I’m testing the TSP feature using this example from the documentation:

SELECT * FROM pgr_TSP(
$$
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@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@[georepublic.de](http://georepublic.de)
Web: [https://georepublic.info](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