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.41421356237 |             0
   2 |    3 |              1 | 1.41421356237
   3 |    4 |              1 | 2.41421356237
   4 |    9 | 0.583095189485 | 3.41421356237
   5 |   16 | 0.583095189485 | 3.99730875186
   6 |    6 |              1 | 4.58040394134
   7 |   11 |              1 | 5.58040394134
   8 |   12 |  1.11803398875 | 6.58040394134
   9 |   17 |            1.5 | 7.69843793009
  10 |   13 |            0.5 | 9.19843793009
  11 |   15 |            0.5 | 9.69843793009
  12 |   10 |  1.58113883008 | 10.1984379301
  13 |   14 |  1.58113883008 | 11.7795767602
  14 |    7 |              1 | 13.3607155903
  15 |    8 |              1 | 14.3607155903
  16 |    5 |              1 | 15.3607155903
  17 |    2 |              1 | 16.3607155903
  18 |    1 |              0 | 17.3607155903
(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

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.

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.

Additional Examples¶

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.41421356237 |             0
   2 |    3 |              1 | 1.41421356237
   3 |    4 |              1 | 2.41421356237
   4 |    9 | 0.583095189485 | 3.41421356237
   5 |   16 | 0.583095189485 | 3.99730875186
   6 |    6 |              1 | 4.58040394134
   7 |    5 |              1 | 5.58040394134
   8 |    8 |              1 | 6.58040394134
   9 |    7 |  1.58113883008 | 7.58040394134
  10 |   14 |            1.5 | 9.16154277143
  11 |   15 |            0.5 | 10.6615427714
  12 |   13 |            1.5 | 11.1615427714
  13 |   17 |  1.11803398875 | 12.6615427714
  14 |   12 |              1 | 13.7795767602
  15 |   11 |              1 | 14.7795767602
  16 |   10 |              2 | 15.7795767602
  17 |    2 |              1 | 17.7795767602
  18 |    1 |              0 | 18.7795767602
(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.41421356237 |             0
   2 |    3 |              1 | 1.41421356237
   3 |    4 |              1 | 2.41421356237
   4 |    9 | 0.583095189485 | 3.41421356237
   5 |   16 | 0.583095189485 | 3.99730875186
   6 |    6 |              1 | 4.58040394134
   7 |    5 |              1 | 5.58040394134
   8 |    8 |              1 | 6.58040394134
   9 |    7 |  1.58113883008 | 7.58040394134
  10 |   14 |            1.5 | 9.16154277143
  11 |   15 |            0.5 | 10.6615427714
  12 |   13 |            1.5 | 11.1615427714
  13 |   17 |  1.11803398875 | 12.6615427714
  14 |   12 |              1 | 13.7795767602
  15 |   11 |              1 | 14.7795767602
  16 |   10 |              2 | 15.7795767602
  17 |    2 |              1 | 17.7795767602
  18 |    1 |              0 | 18.7795767602
(18 rows)

The queries use the Sample Data network.