pgr_TSP

Name

  • pgr_TSP - Returns a route that visits all the nodes exactly once.

Availability: 2.0.0

  • Signature changed 2.3.0

Synopsis

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, what is the shortest possible route that visits each city exactly once and returns to the origin city?

This implementation uses simulated annealing to return the approximate solution when the input is given in the form of matrix cell contents. The matrix information must be symmetrical.

Signature Summary

pgr_TSP(matrix_cell_sql)
pgr_TSP(matrix_cell_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)

Signatures

Basic Use

pgr_TSP(matrix_cell_sql)
RETURNS SETOF (seq, node, cost, agg_cost)
Example:

Because the documentation examples are auto generated and tested for non changing results, and the default is to have random execution, the example is wrapping the actual call.

WITH
query AS (
    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
        )
        $$
    )
)
SELECT agg_cost < 20 AS under_20 FROM query WHERE seq = 14;
 under_20 
----------
 t
(1 row)

Complete Signature

pgr_TSP(matrix_cell_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:

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)

Description of the Signatures

Description of the Matrix Cell SQL query

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:

To generate a symmetric matrix

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


Description Of the Control parameters
.....................................................................

The control parameters are optional, and have a default value.

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

=============================== ===========  ============  =================================================



Description of the return 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`` ito 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.

============= =========== =================================================

Examples

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 |    1 |        0
   2 |    6 |    1 |        1
   3 |    3 |  1.6 |        2
   4 |   -1 |  1.3 |      3.6
   5 |   -6 |  0.3 |      4.9
   6 |    5 |    0 |      5.2
(6 rows)

The queries use the Sample Data network.