# pgRouting Manual (2.5)

## pgr_eucledianTSP

## Name

`pgr_eucledianTSP` - Returns a route that visits all the coordinates pairs exactly once.

Availability: 2.3.0

## Synopsis

The travelling salesman problem (TSP) or travelling salesperson problem asks the following question:

> - Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?

This implementation uses simulated annealing to return the approximate solution when the input is given in the form of coordinates.

## Signature Summary

    pgr_eucledianTSP(coordinates_sql)
    pgr_eucledianTSP(coordinates_sql,
        start_id, end_id,
        max_processing_time,
        tries_per_temperature, max_changes_per_temperature, max_consecutive_non_changes,
        initial_temperature, final_temperature, cooling_factor,
        randomize,
    RETURNS SETOF (seq, node, cost, agg_cost)

## Signatures

### Minimal Signature

    pgr_eucledianTSP(coordinates_sql)
    RETURNS SETOF (seq, node, cost, agg_cost)

Example: |

Because the documentation examples are auto generated and tested for non changing results, and the default is to have random execution, the example is wrapping the actual call.

    WITH
    query AS (
        SELECT * FROM pgr_eucledianTSP(
            $$
            SELECT id, st_X(the_geom) AS x, st_Y(the_geom)AS y  FROM edge_table_vertices_pgr
            $$
        )
    )
    SELECT agg_cost < 20 AS under_20 FROM query WHERE seq = 18;
     under_20
    ----------
     t
    (1 row)

### Complete Signature

    pgr_eucledianTSP(coordinates_sql,
        start_id, end_id,
        max_processing_time,
        tries_per_temperature, max_changes_per_temperature, max_consecutive_non_changes,
        initial_temperature, final_temperature, cooling_factor,
        randomize,
    RETURNS SETOF (seq, node, cost, agg_cost)

Example:

    SELECT* from pgr_eucledianTSP(
        $$
        SELECT id, st_X(the_geom) AS x, st_Y(the_geom) AS y FROM edge_table_vertices_pgr
        $$,
        tries_per_temperature := 3,
        cooling_factor := 0.5,
        randomize := false
    );
     seq | node |       cost       |     agg_cost
    -----+------+------------------+------------------
       1 |    1 |  1.4142135623731 |                0
       2 |    3 |                1 |  1.4142135623731
       3 |    4 |                1 | 2.41421356237309
       4 |    9 | 0.58309518948453 | 3.41421356237309
       5 |   16 | 0.58309518948453 | 3.99730875185762
       6 |    6 |                1 | 4.58040394134215
       7 |    5 |                1 | 5.58040394134215
       8 |    8 |                1 | 6.58040394134215
       9 |    7 | 1.58113883008419 | 7.58040394134215
      10 |   14 |   1.499999999999 | 9.16154277142634
      11 |   15 |              0.5 | 10.6615427714253
      12 |   13 |              1.5 | 11.1615427714253
      13 |   17 | 1.11803398874989 | 12.6615427714253
      14 |   12 |                1 | 13.7795767601752
      15 |   11 |                1 | 14.7795767601752
      16 |   10 |                2 | 15.7795767601752
      17 |    2 |                1 | 17.7795767601752
      18 |    1 |                0 | 18.7795767601752
    (18 rows)

## Description of the Signatures

### Description of the coordinates SQL query

Column | Type | Description
--- | --- | ---
id | `BIGINT` | Identifier of the coordinate. (optional)
x | `FLOAT` | X value of the coordinate.
y | `FLOAT` | Y value of the coordinate.

When the value of id is not given then the coordinates will receive an id starting from 1, in the order given.

    Description Of the Control parameters
    .....................................................................

    The control parameters are optional, and have a default value.

    =============================== ===========  ============  =================================================
    Parameter                       Type         Default       Description
    =============================== ===========  ============  =================================================
    **start_vid**                   ``BIGINT``    `0`          The greedy part of the implementation will use this identifier.
    **end_vid**                     ``BIGINT``    `0`          Last visiting vertex before returning to start_vid.
    **max_processing_time**         ``FLOAT``    `+infinity`   Stop the annealing processing when the value is reached.
    **tries_per_temperature**       ``INTEGER``  `500`         Maximum number of times a neighbor(s) is searched in each temperature.
    **max_changes_per_temperature** ``INTEGER``  `60`          Maximum number of times the solution is changed in each temperature.
    **max_consecutive_non_changes** ``INTEGER``  `100`         Maximum number of consecutive times the solution is not changed in each temperature.
    **initial_temperature**         ``FLOAT``    `100`         Starting temperature.
    **final_temperature**           ``FLOAT``    `0.1`         Ending temperature.
    **cooling_factor**              ``FLOAT``    `0.9`         Value between between 0 and 1 (not including) used to calculate the next temperature.
    **randomize**                   ``BOOLEAN``  `true`        Choose the random seed

                                                               - true: Use current time as seed
                                                               - false: Use `1` as seed. Using this value will get the same results with the same data in each execution.

    =============================== ===========  ============  =================================================

    Description of the return columns
    ...............................................................................

    Returns set of ``(seq, node, cost, agg_cost)``

    ============= =========== =================================================
    Column           Type              Description
    ============= =========== =================================================
    **seq**       ``INTEGER`` Row sequence.
    **node**      ``BIGINT``  Identifier of the node/coordinate/point.
    **cost**      ``FLOAT``   Cost to traverse from the current ``node`` ito the next ``node`` in the path sequence.
                                - ``0`` for the last row in the path sequence.

    **agg_cost**  ``FLOAT``   Aggregate cost from the ``node`` at ``seq = 1`` to the current node.
                                - ``0`` for the first row in the path sequence.

    ============= =========== =================================================

## Examples

Example: | Skipping the Simulated Annealing & showing some process information

    SET client_min_messages TO DEBUG1;
    SET
    SELECT* from pgr_eucledianTSP(
        $$
        SELECT id, st_X(the_geom) AS x, st_Y(the_geom) AS y FROM edge_table_vertices_pgr
        $$,
        tries_per_temperature := 0,
        randomize := false
    );
    DEBUG:  pgr_eucledianTSP Processing Information
    Initializing tsp class ---> tsp.greedyInitial ---> tsp.annealing ---> OK

    Cycle(100) 	total changes =0	0 were because  delta energy < 0
    Total swaps: 3
    Total slides: 0
    Total reverses: 0
    Times best tour changed: 4
    Best cost reached = 18.7796
     seq | node |       cost       |     agg_cost
    -----+------+------------------+------------------
       1 |    1 |  1.4142135623731 |                0
       2 |    3 |                1 |  1.4142135623731
       3 |    4 |                1 | 2.41421356237309
       4 |    9 | 0.58309518948453 | 3.41421356237309
       5 |   16 | 0.58309518948453 | 3.99730875185762
       6 |    6 |                1 | 4.58040394134215
       7 |    5 |                1 | 5.58040394134215
       8 |    8 |                1 | 6.58040394134215
       9 |    7 | 1.58113883008419 | 7.58040394134215
      10 |   14 |   1.499999999999 | 9.16154277142634
      11 |   15 |              0.5 | 10.6615427714253
      12 |   13 |              1.5 | 11.1615427714253
      13 |   17 | 1.11803398874989 | 12.6615427714253
      14 |   12 |                1 | 13.7795767601752
      15 |   11 |                1 | 14.7795767601752
      16 |   10 |                2 | 15.7795767601752
      17 |    2 |                1 | 17.7795767601752
      18 |    1 |                0 | 18.7795767601752
    (18 rows)

The queries use the Sample Data network.

History

- New in version 2.3.0

## See Also

- Traveling Sales Person - Family of functions
- http://en.wikipedia.org/wiki/Traveling_salesman_problem
- http://en.wikipedia.org/wiki/Simulated_annealing

Indices and tables

- Index
- Search Page