# pgr_TSP¶

• pgr_TSP - Aproximation using metric algorithm.

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.

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