pgr_TSP
 Using Simulated Annealing approximation algorithmAvailability: 2.0.0
Support
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
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)
Parameter  Description 

Matrix SQL  an SQL query, described in the Inner query 
Parameter  Type  Default  Description 

start_vid  BIGINT 
0  The greedy part of the implementation will use this identifier. 
end_vid  BIGINT 
0  Last visiting vertex before returning to start_vid. 
max_processing_time  FLOAT 
+infinity  Stop the annealing processing when the value is reached. 
tries_per_temperature  INTEGER 
500  Maximum number of times a neighbor(s) is searched in each temperature. 
max_changes_per_temperature  INTEGER 
60  Maximum number of times the solution is changed in each temperature. 
max_consecutive_non_changes  INTEGER 
100  Maximum number of consecutive times the solution is not changed in each temperature. 
initial_temperature  FLOAT 
100  Starting temperature. 
final_temperature  FLOAT 
0.1  Ending temperature. 
cooling_factor  FLOAT 
0.9  Value between between 0 and 1 (not including) used to calculate the next temperature. 
randomize  BOOLEAN 
true  Choose the random seed

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

start_vid  BIGINT 
Identifier of the starting vertex. 
end_vid  BIGINT 
Identifier of the ending vertex. 
agg_cost  FLOAT 
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.
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 

agg_cost  FLOAT 

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:
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.
Indices and tables