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 NPhard 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
tov
are just as much as traveling fromv
tou
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 theagg_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
[start_id, end_id]
)(seq, node, cost, agg_cost)
 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 as described below 
TSP optional parameters¶
Column 
Type 
Default 
Description 


ANYINTEGER 

The first visiting vertex


ANYINTEGER 

Last visiting vertex before returning to

Inner Queries¶
Matrix SQL¶
Column 
Type 
Description 



Identifier of the starting vertex. 


Identifier of the ending vertex. 


Cost for going from start_vid to end_vid 
Result columns¶
Returns SET OF (seq, node, cost, agg_cost)
Column 
Type 
Description 

seq 

Row sequence. 
node 

Identifier of the node/coordinate/point. 
cost 

Cost to traverse from the current

agg_cost 

Aggregate cost from the

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 ofpointsOfInterset
is ignored by not including it in the queryLine 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¶
Indices and tables