# pgr_TSPeuclidean¶

pgr_TSPeuclidean - Using Simulated Annealing approximation algorithm

Availability

• Version 3.0.0
• Name change from pgr_eucledianTSP
• Version 2.3.0
• New Official function

Support

## 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_TSPeuclidean(Coordinates 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_TSPeuclidean(
$$SELECT id, st_X(the_geom) AS x, st_Y(the_geom)AS y FROM edge_table_vertices_pgr$$,
randomize := false);
seq | node |       cost        |     agg_cost
-----+------+-------------------+------------------
1 |    1 |   1.4142135623731 |                0
2 |    3 |                 1 |  1.4142135623731
3 |    4 |                 1 | 2.41421356237309
4 |    9 |                 1 | 3.41421356237309
5 |    6 |  0.58309518948453 | 4.41421356237309
6 |   16 | 0.860232526704263 | 4.99730875185763
7 |   12 |  1.11803398874989 | 5.85754127856189
8 |   17 |  1.11803398874989 | 6.97557526731178
9 |   11 |                 1 | 8.09360925606168
10 |   10 |               0.5 | 9.09360925606168
11 |   15 |               0.5 | 9.59360925606168
12 |   13 |  1.58113883008419 | 10.0936092560617
13 |   14 |  1.58113883008419 | 11.6747480861459
14 |    7 |                 1 | 13.2558869162301
15 |    8 |                 1 | 14.2558869162301
16 |    5 |                 1 | 15.2558869162301
17 |    2 |                 1 | 16.2558869162301
18 |    1 |                 0 | 17.2558869162301
(18 rows)



## Parameters¶

Parameter Description
Coordinates SQL an SQL query, described in the Inner query

### Optional Parameters¶

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

• true: Use current time as seed
• false: Use 1 as seed. Using this value will get the same results with the same data in each execution.

## Inner query¶

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

Column Type Description
id BIGINT

(optional) Identifier of the coordinate.

• When missing the coordinates will receive an id starting from 1, in the order given.
x FLOAT X value of the coordinate.
y FLOAT Y value of the coordinate.

## 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 path sequence.
agg_cost FLOAT
Aggregate cost from the node at seq = 1 to the current node.
• 0 for the first row in the path sequence.

Example: Try $$3$$ times per temperature with cooling factor of $$0.5$$, not having a random execution
SELECT* from pgr_TSPeuclidean(
$$SELECT id, st_X(the_geom) AS x, st_Y(the_geom) AS y FROM edge_table_vertices_pgr$$,
tries_per_temperature := 3,
cooling_factor := 0.5,
randomize := false);
seq | node |       cost       |     agg_cost
-----+------+------------------+------------------
1 |    1 |  1.4142135623731 |                0
2 |    3 |                1 |  1.4142135623731
3 |    4 |                1 | 2.41421356237309
4 |    9 | 0.58309518948453 | 3.41421356237309
5 |   16 | 0.58309518948453 | 3.99730875185762
6 |    6 |                1 | 4.58040394134215
7 |    5 |                1 | 5.58040394134215
8 |    8 |                1 | 6.58040394134215
9 |    7 | 1.58113883008419 | 7.58040394134215
10 |   14 |   1.499999999999 | 9.16154277142634
11 |   15 |              0.5 | 10.6615427714253
12 |   13 |              1.5 | 11.1615427714253
13 |   17 | 1.11803398874989 | 12.6615427714253
14 |   12 |                1 | 13.7795767601752
15 |   11 |                1 | 14.7795767601752
16 |   10 |                2 | 15.7795767601752
17 |    2 |                1 | 17.7795767601752
18 |    1 |                0 | 18.7795767601752
(18 rows)


Example: Skipping the Simulated Annealing & showing some process information
SET client_min_messages TO DEBUG1;
SET
SELECT* from pgr_TSPeuclidean(
$$SELECT id, st_X(the_geom) AS x, st_Y(the_geom) AS y FROM edge_table_vertices_pgr$$,
tries_per_temperature := 0,
randomize := false);
DEBUG:  Processing Information
Initializing tsp class ---> tsp.greedyInitial ---> tsp.annealing ---> OK

Cycle(100) 	total changes =0	0 were because  delta energy < 0
Total swaps: 3
Total slides: 0
Total reverses: 0
Times best tour changed: 4
Best cost reached = 18.7796
seq | node |       cost       |     agg_cost
-----+------+------------------+------------------
1 |    1 |  1.4142135623731 |                0
2 |    3 |                1 |  1.4142135623731
3 |    4 |                1 | 2.41421356237309
4 |    9 | 0.58309518948453 | 3.41421356237309
5 |   16 | 0.58309518948453 | 3.99730875185762
6 |    6 |                1 | 4.58040394134215
7 |    5 |                1 | 5.58040394134215
8 |    8 |                1 | 6.58040394134215
9 |    7 | 1.58113883008419 | 7.58040394134215
10 |   14 |   1.499999999999 | 9.16154277142634
11 |   15 |              0.5 | 10.6615427714253
12 |   13 |              1.5 | 11.1615427714253
13 |   17 | 1.11803398874989 | 12.6615427714253
14 |   12 |                1 | 13.7795767601752
15 |   11 |                1 | 14.7795767601752
16 |   10 |                2 | 15.7795767601752
17 |    2 |                1 | 17.7795767601752
18 |    1 |                0 | 18.7795767601752
(18 rows)



The queries use the Sample Data network.