# pgRouting Manual (3.3)

## pgr_TSP

- Supported versions: Latest (3.3) 3.2 3.1 3.0

- Unsupported versions: 2.6 2.5 2.4 2.3 2.2 2.1 2.0

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

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

### Characteristics

- 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 SETOF (seq, node, cost, agg_cost)

Example: Using pgr_dijkstraCostMatrix to generate the matrix information

- Line 5 Vertices 15 to 18 are not included because they are not connected.

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

## Parameters

Parameter | Type | Default | Description
--- | --- | --- | ---
Matrix SQL | `TEXT` |  | An SQL query, described in the Matrix SQL section.

start_vid

`BIGINT`

`0`

The first visiting vertex

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

end_vid

`BIGINT`

`0`

Last visiting vertex before returning to `start_vid`.

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

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

## Inner query

### Matrix SQL

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

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

Example

  Start from vertex \(7\)

- Line 9 `start_vid => 7`

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

Example

  Using points of interest to generate an asymetric matrix.

To generate an asymmetric matrix:

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

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

Example

  Connected incomplete data

Using selected edges (2, 4, 5, 8, 9, 15) the matrix is not complete but it is connected

     1SELECT source AS start_vid, target AS end_vid, 1 AS agg_cost
     2FROM edge_table WHERE id IN (2,4,5,8, 9, 15);
     3 start_vid | end_vid | agg_cost
     4-----------+---------+----------
     5         2 |       3 |        1
     6         2 |       5 |        1
     7         3 |       6 |        1
     8         5 |       6 |        1
     9         6 |       9 |        1
    10         9 |      12 |        1
    11(6 rows)
    12

Edge (5,12) does not exist on the initial data, but it is calculated internally.

     1SELECT * FROM pgr_TSP(
     2  $$
     3  SELECT source AS start_vid, target AS end_vid, 1 AS agg_cost
     4  FROM edge_table
     5  WHERE id IN (2,4,5,8,9,15)
     6  $$);
     7 seq | node | cost | agg_cost
     8-----+------+------+----------
     9   1 |    2 |    0 |        0
    10   2 |    3 |    1 |        1
    11   3 |    6 |    1 |        2
    12   4 |   12 |    1 |        3
    13   5 |    9 |    1 |        4
    14   6 |    5 |    1 |        5
    15   7 |    2 |    1 |        6
    16(7 rows)
    17

The queries use the Sample Data network.

## See Also

- Traveling Sales Person - Family of functions

- Metric Algorithm from Boost library

- Boost library

- Wikipedia: Traveling Salesman Problem

Indices and tables

- Index

- Search Page