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

classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

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

tommaso
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
[hidden email]
https://lists.osgeo.org/mailman/listinfo/pgrouting-users
Reply | Threaded
Open this post in threaded view
|

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

Vicky Vergara-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 <[hidden email]> 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
[hidden email]
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
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


_______________________________________________
Pgrouting-users mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/pgrouting-users