# pgRouting Manual (3.0-rc1)

## pgr_TSPeuclidean

`pgr_TSPeuclidean` - Using Simulated Annealing approximation algorithm

Availability

- Version 3.0.0
  - Name change from pgr_eucledianTSP
- Version 2.3.0
  - New Official function

Support

- Supported versions: current(3.0) 2.6
- Unsupported versions: 2.5 2.4 2.3

## Description

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, which is the shortest possible route that visits each city exactly once and returns to the origin city?

See Simulated Annealing Algorithm for a complete description of this implementation

## Signatures

Summary

    pgr_TSPeuclidean(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: | Not having a random execution

    SELECT * FROM pgr_TSPeuclidean(
        $$
        SELECT id, st_X(the_geom) AS x, st_Y(the_geom)AS y  FROM edge_table_vertices_pgr
        $$,
        randomize := false);
     seq | node |       cost        |     agg_cost
    -----+------+-------------------+------------------
       1 |    1 |   1.4142135623731 |                0
       2 |    3 |                 1 |  1.4142135623731
       3 |    4 |                 1 | 2.41421356237309
       4 |    9 |                 1 | 3.41421356237309
       5 |    6 |  0.58309518948453 | 4.41421356237309
       6 |   16 | 0.860232526704263 | 4.99730875185763
       7 |   12 |  1.11803398874989 | 5.85754127856189
       8 |   17 |  1.11803398874989 | 6.97557526731178
       9 |   11 |                 1 | 8.09360925606168
      10 |   10 |               0.5 | 9.09360925606168
      11 |   15 |               0.5 | 9.59360925606168
      12 |   13 |  1.58113883008419 | 10.0936092560617
      13 |   14 |  1.58113883008419 | 11.6747480861459
      14 |    7 |                 1 | 13.2558869162301
      15 |    8 |                 1 | 14.2558869162301
      16 |    5 |                 1 | 15.2558869162301
      17 |    2 |                 1 | 16.2558869162301
      18 |    1 |                 0 | 17.2558869162301
    (18 rows)

## Parameters

Parameter | Description
--- | ---
Coordinates SQL | an SQL query, described in the Inner query

### Optional Parameters

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.

## Inner query

Coordinates SQL: an SQL query, which should return a set of rows with the following columns:

Column | Type | Description
--- | --- | ---

id

`BIGINT`

(optional) Identifier of the coordinate.

- When missing the coordinates will receive an id starting from 1, in the order given.

x | `FLOAT` | X value of the coordinate.
y | `FLOAT` | Y value of the coordinate.

## Result 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` to 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.

## Additional Examples

Example: | Try \(3\) times per temperature with cooling factor of \(0.5\), not having a random execution

    SELECT* from pgr_TSPeuclidean(
        $$
        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)

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

    SET client_min_messages TO DEBUG1;
    SET
    SELECT* from pgr_TSPeuclidean(
        $$
        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:  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.

## See Also

- Traveling Sales Person - Family of functions
- Simulated annaeling algorithm for beginners
- Wikipedia: Traveling Salesman Problem
- Wikipedia: Simulated annealing

Indices and tables

- Index
- Search Page