# pgRouting Manual (3.1)

## pgr_TSP

- `pgr_TSP` - Using Simulated Annealing approximation algorithm

Availability: 2.0.0

- Version 2.3.0

  - Signature change

    - Old signature no longer supported

- Version 2.0.0

  - Official function

Support

- Supported versions: current(3.1) 3.0 2.6

- Unsupported versions: 2.5 2.4 2.3 2.2 2.1 2.0

## 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_TSP(Matrix 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_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)
        $$,
        randomize := false);
     seq | node | cost | agg_cost
    -----+------+------+----------
       1 |    1 |    1 |        0
       2 |    2 |    1 |        1
       3 |    3 |    1 |        2
       4 |    4 |    1 |        3
       5 |    9 |    1 |        4
       6 |    6 |    1 |        5
       7 |   11 |    1 |        6
       8 |   12 |    2 |        7
       9 |   10 |    1 |        9
      10 |   13 |    4 |       10
      11 |    7 |    1 |       14
      12 |    8 |    1 |       15
      13 |    5 |    2 |       16
      14 |    1 |    0 |       18
    (14 rows)

## Parameters

Parameter | Description
--- | ---
Matrix 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

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

Column | Type | Description
--- | --- | ---
start_vid | `BIGINT` | Identifier of the starting vertex.
end_vid | `BIGINT` | Identifier of the ending vertex.
agg_cost | `FLOAT` | Cost for going from start_vid to end_vid

Can be Used with Cost Matrix - Category functions with directed := false.

If using directed := true, the resulting non symmetric matrix must be converted to symmetric by fixing the non symmetric values according to your application needs.

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

  Start from vertex \(7\)

    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
    );
     seq | node | cost | agg_cost
    -----+------+------+----------
       1 |    7 |    1 |        0
       2 |    8 |    1 |        1
       3 |    5 |    1 |        2
       4 |    2 |    1 |        3
       5 |    1 |    2 |        4
       6 |    3 |    1 |        6
       7 |    4 |    1 |        7
       8 |    9 |    1 |        8
       9 |   12 |    1 |        9
      10 |   11 |    1 |       10
      11 |   10 |    1 |       11
      12 |   13 |    3 |       12
      13 |    6 |    3 |       15
      14 |    7 |    0 |       18
    (14 rows)

Example

  Using with points of interest.

To generate a symmetric matrix:

- the side information of pointsOfInterset is ignored by not including it in the query

- and directed := false

    SELECT * FROM pgr_TSP(
        $$
        SELECT * FROM pgr_withPointsCostMatrix(
            'SELECT id, source, target, cost, reverse_cost FROM edge_table ORDER BY id',
            'SELECT pid, edge_id, fraction from pointsOfInterest',
            array[-1, 3, 5, 6, -6], directed := false)
        $$,
        start_id := 5,
        randomize := false
    );
     seq | node | cost | agg_cost
    -----+------+------+----------
       1 |    5 |  0.3 |        0
       2 |   -6 |  1.3 |      0.3
       3 |   -1 |  1.6 |      1.6
       4 |    3 |    1 |      3.2
       5 |    6 |    1 |      4.2
       6 |    5 |    0 |      5.2
    (6 rows)

The queries use the Sample Data network.

## See Also

- Traveling Sales Person - Family of functions

- Wikipedia: Traveling Salesman Problem

- Wikipedia: Simulated annealing

Indices and tables

- Index

- Search Page