# pgRouting Manual (3.6)

## pgr_TSP

# `pgr_TSP`

- `pgr_TSP` - Aproximation using metric algorithm.

Boost Graph Inside

Availability:

- Version 3.2.1

  - Metric Algorithm from Boost library

  - Simulated Annealing Algorithm no longer supported

    - The Simulated Annealing Algorithm related parameters are ignored: max_processing_time, tries_per_temperature, max_changes_per_temperature, max_consecutive_non_changes, initial_temperature, final_temperature, cooling_factor, randomize

- Version 2.3.0

  - Signature change

    - Old signature no longer supported

- Version 2.0.0

  - Official function

## Description

### Problem Definition

The travelling salesperson problem (TSP) 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?

### Characteristics

- This problem is an NP-hard optimization problem.

- Metric Algorithm is used

- Implementation generates solutions that are twice as long as the optimal tour in the worst case when:

  - Graph is undirected

  - Graph is fully connected

  - Graph where traveling costs on edges obey the triangle inequality.

- On an undirected graph:

  - The traveling costs are symmetric:

  - Traveling costs from `u` to `v` are just as much as traveling from `v` to `u`

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

  - With `directed => false`

    - Will generate a graph that:

      - is undirected

      - is fully connected (As long as the graph has one component)

      - all traveling costs on edges obey the triangle inequality.

    - When `start_vid = 0 OR end_vid = 0`

      - The solutions generated is garanteed to be twice as long as the optimal tour in the worst case

    - When `start_vid != 0 AND end_vid != 0 AND start_vid != end_vid`

      - It is not garanteed that the solution will be, in the worse case, twice as long as the optimal tour, due to the fact that end_vid is forced to be in a fixed position.

  - With `directed => true`

    - It is not garanteed that the solution will be, in the worse case, twice as long as the optimal tour

    - Will generate a graph that:

      - is directed

      - is fully connected (As long as the graph has one component)

      - some (or all) traveling costs on edges might not obey the triangle inequality.

    - As an undirected graph is required, the directed graph is transformed as follows:

      - edges (u, v) and (v, u) is considered to be the same edge (denoted (u, v)

      - if `agg_cost` differs between one or more instances of edge (u, v)

      - The minimum value of the `agg_cost` all instances of edge (u, v) is going to be considered as the `agg_cost` of edge (u, v)

      - Some (or all) traveling costs on edges will still might not obey the triangle inequality.

- When the data is incomplete, but it is a connected graph:

  - the missing values will be calculated with dijkstra algorithm.

## Signatures

Summary

pgr_TSP(Matrix SQL, `[start_id, end_id]`)
Returns set of `(seq, node, cost, agg_cost)`
OR EMTPY SET

Example:

  Using pgr_dijkstraCostMatrix to generate the matrix information

- Line 4 Vertices \(\{2, 4, 13, 14\}\) are not included because they are not connected.

     1SELECT * FROM pgr_TSP(
     2  $$SELECT * FROM pgr_dijkstraCostMatrix(
     3    'SELECT id, source, target, cost, reverse_cost FROM edges',
     4    (SELECT array_agg(id) FROM vertices WHERE id NOT IN (2, 4, 13, 14)),
     5    directed => false) $$);
     6 seq | node | cost | agg_cost
     7-----+------+------+----------
     8   1 |    1 |    0 |        0
     9   2 |    3 |    1 |        1
    10   3 |    7 |    1 |        2
    11   4 |    6 |    1 |        3
    12   5 |    5 |    1 |        4
    13   6 |   10 |    2 |        6
    14   7 |   11 |    1 |        7
    15   8 |   12 |    1 |        8
    16   9 |   16 |    2 |       10
    17  10 |   15 |    1 |       11
    18  11 |   17 |    2 |       13
    19  12 |    9 |    3 |       16
    20  13 |    8 |    1 |       17
    21  14 |    1 |    3 |       20
    22(14 rows)
    23

## Parameters

Parameter | Type | Description
--- | --- | ---
Matrix SQL | `TEXT` | Matrix SQL as described below

### TSP optional parameters

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

`start_id`

ANY-INTEGER

`0`

The first visiting vertex

- When 0 any vertex can become the first visiting vertex.

`end_id`

ANY-INTEGER

`0`

Last visiting vertex before returning to `start_vid`.

- When `0` any vertex can become the last visiting vertex before returning to `start_id`.

- When `NOT 0` and `start_id = 0` then it is the first and last vertex

## Inner Queries

### Matrix SQL

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

## 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 tour sequence.

agg_cost

`FLOAT`

Aggregate cost from the `node` at `seq = 1` to the current node.

- `0` for the first row in the tour sequence.

## Additional Examples

### Start from vertex \(1\)

- Line 6 `start_vid => 1`

     1SELECT * FROM pgr_TSP(
     2  $$SELECT * FROM pgr_dijkstraCostMatrix(
     3    'SELECT id, source, target, cost, reverse_cost FROM edges',
     4    (SELECT array_agg(id) FROM vertices WHERE id NOT IN (2, 4, 13, 14)),
     5    directed => false) $$,
     6  start_id => 1);
     7 seq | node | cost | agg_cost
     8-----+------+------+----------
     9   1 |    1 |    0 |        0
    10   2 |    3 |    1 |        1
    11   3 |    7 |    1 |        2
    12   4 |    6 |    1 |        3
    13   5 |    5 |    1 |        4
    14   6 |   10 |    2 |        6
    15   7 |   11 |    1 |        7
    16   8 |   12 |    1 |        8
    17   9 |   16 |    2 |       10
    18  10 |   15 |    1 |       11
    19  11 |   17 |    2 |       13
    20  12 |    9 |    3 |       16
    21  13 |    8 |    1 |       17
    22  14 |    1 |    3 |       20
    23(14 rows)
    24

### Using points of interest to generate an asymetric matrix.

To generate an asymmetric matrix:

- Line 4 The `side` information of `pointsOfInterset` is ignored by not including it in the query

- Line 6 Generating an asymetric matrix with `directed => true`

  - \(min(agg\_cost(u, v), agg\_cost(v, u))\) is going to be considered as the `agg_cost`

  - The solution that can be larger than twice as long as the optimal tour because:

    - Triangle inequality might not be satisfied.

    - `start_id != 0 AND end_id != 0`

     1SELECT * FROM pgr_TSP(
     2  $$SELECT * FROM pgr_withPointsCostMatrix(
     3    'SELECT id, source, target, cost, reverse_cost FROM edges ORDER BY id',
     4    'SELECT pid, edge_id, fraction from pointsOfInterest',
     5    array[-1, 10, 7, 11, -6],
     6    directed => true) $$,
     7  start_id => 7,
     8  end_id => 11);
     9 seq | node | cost | agg_cost
    10-----+------+------+----------
    11   1 |    7 |    0 |        0
    12   2 |   -6 |  0.3 |      0.3
    13   3 |   -1 |  1.3 |      1.6
    14   4 |   10 |  1.6 |      3.2
    15   5 |   11 |    1 |      4.2
    16   6 |    7 |    1 |      5.2
    17(6 rows)
    18

### Connected incomplete data

Using selected edges \(\{2, 4, 5, 8, 9, 15\}\) the matrix is not complete.

     1SELECT * FROM pgr_dijkstraCostMatrix(
     2  $q1$SELECT id, source, target, cost, reverse_cost FROM edges WHERE id IN (2, 4, 5, 8, 9, 15)$q1$,
     3  (SELECT ARRAY[6, 7, 10, 11, 16, 17]),
     4  directed => true);
     5 start_vid | end_vid | agg_cost
     6-----------+---------+----------
     7         6 |       7 |        1
     8         6 |      11 |        2
     9         6 |      16 |        3
    10         6 |      17 |        4
    11         7 |       6 |        1
    12         7 |      11 |        1
    13         7 |      16 |        2
    14         7 |      17 |        3
    15        10 |       6 |        1
    16        10 |       7 |        2
    17        10 |      11 |        1
    18        10 |      16 |        2
    19        10 |      17 |        3
    20        11 |       6 |        2
    21        11 |       7 |        1
    22        11 |      16 |        1
    23        11 |      17 |        2
    24        16 |       6 |        3
    25        16 |       7 |        2
    26        16 |      11 |        1
    27        16 |      17 |        1
    28        17 |       6 |        4
    29        17 |       7 |        3
    30        17 |      11 |        2
    31        17 |      16 |        1
    32(25 rows)
    33

Cost value for \(17 \rightarrow 10\) do not exist on the matrix, but the value used is taken from \(10 \rightarrow 17\).

     1SELECT * FROM pgr_TSP(
     2  $$SELECT * FROM pgr_dijkstraCostMatrix(
     3  $q1$SELECT id, source, target, cost, reverse_cost FROM edges WHERE id IN (2, 4, 5, 8, 9, 15)$q1$,
     4  (SELECT ARRAY[6, 7, 10, 11, 16, 17]),
     5  directed => true)$$);
     6 seq | node | cost | agg_cost
     7-----+------+------+----------
     8   1 |    6 |    0 |        0
     9   2 |    7 |    1 |        1
    10   3 |   11 |    1 |        2
    11   4 |   16 |    1 |        3
    12   5 |   17 |    1 |        4
    13   6 |   10 |    3 |        7
    14   7 |    6 |    1 |        8
    15(7 rows)
    16

## See Also

- Traveling Sales Person - Family of functions

- Sample Data

- Boost’s metric appro’s metric approximation

- Wikipedia: Traveling Salesman Problem

Indices and tables

- Index

- Search Page