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 |              1 | 3.41421356237
   5 |    6 | 0.583095189485 | 4.41421356237
   6 |   16 | 0.860232526704 | 4.99730875186
   7 |   12 |  1.11803398875 | 5.85754127856
   8 |   17 |  1.11803398875 | 6.97557526731
   9 |   11 |              1 | 8.09360925606
  10 |   10 |            0.5 | 9.09360925606
  11 |   15 |            0.5 | 9.59360925606
  12 |   13 |  1.58113883008 | 10.0936092561
  13 |   14 |  1.58113883008 | 11.6747480861
  14 |    7 |              1 | 13.2558869162
  15 |    8 |              1 | 14.2558869162
  16 |    5 |              1 | 15.2558869162
  17 |    2 |              1 | 16.2558869162
  18 |    1 |              0 | 17.2558869162
(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.

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.