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

[Vicky Vergara]

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 at 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 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>