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

0 
The greedy part of the implementation will use this identifier. 
end_vid 

0 
Last visiting vertex before returning to start_vid. 
max_processing_time 

+infinity 
Stop the annealing processing when the value is reached. 
tries_per_temperature 

500 
Maximum number of times a neighbor(s) is searched in each temperature. 
max_changes_per_temperature 

60 
Maximum number of times the solution is changed in each temperature. 
max_consecutive_non_changes 

100 
Maximum number of consecutive times the solution is not changed in each temperature. 
initial_temperature 

100 
Starting temperature. 
final_temperature 

0.1 
Ending temperature. 
cooling_factor 

0.9 
Value between between 0 and 1 (not including) used to calculate the next temperature. 
randomize 

true 
Choose the random seed

Inner query¶
Matrix SQL: an SQL query, which should return a set of rows with the following columns:
Column 
Type 
Description 

start_vid 

Identifier of the starting vertex. 
end_vid 

Identifier of the ending vertex. 
agg_cost 

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 

Row sequence. 
node 

Identifier of the node/coordinate/point. 
cost 


agg_cost 


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¶
Indices and tables