pgr_TSP

• pgr_TSP - Aproximation using metric algorithm.

Boost Graph Inside

Availability:

• Version 3.2.1

  • Metric Algorithm from Boost library

  • Simulated Annealing Algorithm no longer supported

    • The Simulated Annealing Algorithm related parameters are ignored: max_processing_time, tries_per_temperature, max_changes_per_temperature, max_consecutive_non_changes, initial_temperature, final_temperature, cooling_factor, randomize

• Version 2.3.0

  • Signature change

    • Old signature no longer supported

• Version 2.0.0

  • Official function

Description

Problem Definition

The travelling salesperson problem (TSP) 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?

Characteristics

• This problem is an NP-hard optimization problem.

• Metric Algorithm is used

• Implementation generates solutions that are twice as long as the optimal tour in the worst case when:

  • Graph is undirected

  • Graph is fully connected

  • Graph where traveling costs on edges obey the triangle inequality.

• On an undirected graph:

  • The traveling costs are symmetric:

  • Traveling costs from u to v are just as much as traveling from v to u

• Can be Used with Cost Matrix - Category functions preferably with directed => false.

  • With directed => false

    • Will generate a graph that:

      • is undirected

      • is fully connected (As long as the graph has one component)

      • all traveling costs on edges obey the triangle inequality.

    • When start_vid = 0 OR end_vid = 0

      • The solutions generated is garanteed to be twice as long as the optimal tour in the worst case

    • When start_vid != 0 AND end_vid != 0 AND start_vid != end_vid

      • It is not garanteed that the solution will be, in the worse case, twice as long as the optimal tour, due to the fact that end_vid is forced to be in a fixed position.

  • With directed => true

    • It is not garanteed that the solution will be, in the worse case, twice as long as the optimal tour

    • Will generate a graph that:

      • is directed

      • is fully connected (As long as the graph has one component)

      • some (or all) traveling costs on edges might not obey the triangle inequality.

    • As an undirected graph is required, the directed graph is transformed as follows:

      • edges (u, v) and (v, u) is considered to be the same edge (denoted (u, v)

      • if agg_cost differs between one or more instances of edge (u, v)

      • The minimum value of the agg_cost all instances of edge (u, v) is going to be considered as the agg_cost of edge (u, v)

      • Some (or all) traveling costs on edges will still might not obey the triangle inequality.

• When the data is incomplete, but it is a connected graph:

  • the missing values will be calculated with dijkstra algorithm.

Signatures

Summary

pgr_TSP(Matrix SQL, [start_id, end_id])

Returns set of (seq, node, cost, agg_cost)

OR EMTPY SET

Example:

Using pgr_dijkstraCostMatrix to generate the matrix information

• Line 4 Vertices \(\{2, 4, 13, 14\}\) are not included because they are not connected.

SELECT * FROM pgr_TSP(
  $$SELECT * FROM pgr_dijkstraCostMatrix(
    'SELECT id, source, target, cost, reverse_cost FROM edges',
    (SELECT array_agg(id) FROM vertices WHERE id NOT IN (2, 4, 13, 14)),
    directed => false) $$);
 seq | node | cost | agg_cost
-----+------+------+----------
   1 |    1 |    0 |        0
   2 |    3 |    1 |        1
   3 |    7 |    1 |        2
   4 |    6 |    1 |        3
   5 |    5 |    1 |        4
   6 |   10 |    2 |        6
   7 |   11 |    1 |        7
   8 |   12 |    1 |        8
   9 |   16 |    2 |       10
  10 |   15 |    1 |       11
  11 |   17 |    2 |       13
  12 |    9 |    3 |       16
  13 |    8 |    1 |       17
  14 |    1 |    3 |       20
(14 rows)

Parameters

Parameter	Type	Description
Matrix SQL	TEXT	Matrix SQL as described below

TSP optional parameters

Column	Type	Default	Description
start_id	ANY-INTEGER	0	The first visiting vertex When 0 any vertex can become the first visiting vertex.
end_id	ANY-INTEGER	0	Last visiting vertex before returning to start_vid. When 0 any vertex can become the last visiting vertex before returning to start_id. When NOT 0 and start_id = 0 then it is the first and last vertex

Inner Queries

Matrix SQL

Column	Type	Description
start_vid	ANY-INTEGER	Identifier of the starting vertex.
end_vid	ANY-INTEGER	Identifier of the ending vertex.
agg_cost	ANY-NUMERICAL	Cost for going from start_vid to end_vid

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

Additional Examples

Start from vertex \(1\)

• Line 6 start_vid => 1

SELECT * FROM pgr_TSP(
  $$SELECT * FROM pgr_dijkstraCostMatrix(
    'SELECT id, source, target, cost, reverse_cost FROM edges',
    (SELECT array_agg(id) FROM vertices WHERE id NOT IN (2, 4, 13, 14)),
    directed => false) $$,
  start_id => 1);
 seq | node | cost | agg_cost
-----+------+------+----------
   1 |    1 |    0 |        0
   2 |    3 |    1 |        1
   3 |    7 |    1 |        2
   4 |    6 |    1 |        3
   5 |    5 |    1 |        4
   6 |   10 |    2 |        6
   7 |   11 |    1 |        7
   8 |   12 |    1 |        8
   9 |   16 |    2 |       10
  10 |   15 |    1 |       11
  11 |   17 |    2 |       13
  12 |    9 |    3 |       16
  13 |    8 |    1 |       17
  14 |    1 |    3 |       20
(14 rows)

Using points of interest to generate an asymetric matrix.

To generate an asymmetric matrix:

• Line 4 The side information of pointsOfInterset is ignored by not including it in the query

• Line 6 Generating an asymetric matrix with directed => true

  • \(min(agg\_cost(u, v), agg\_cost(v, u))\) is going to be considered as the agg_cost

  • The solution that can be larger than twice as long as the optimal tour because:

    • Triangle inequality might not be satisfied.

    • start_id != 0 AND end_id != 0

SELECT * FROM pgr_TSP(
  $$SELECT * FROM pgr_withPointsCostMatrix(
    'SELECT id, source, target, cost, reverse_cost FROM edges ORDER BY id',
    'SELECT pid, edge_id, fraction from pointsOfInterest',
    array[-1, 10, 7, 11, -6],
    directed => true) $$,
  start_id => 7,
  end_id => 11);
 seq | node | cost | agg_cost
-----+------+------+----------
   1 |    7 |    0 |        0
   2 |   -6 |  0.3 |      0.3
   3 |   -1 |  1.3 |      1.6
   4 |   10 |  1.6 |      3.2
   5 |   11 |    1 |      4.2
   6 |    7 |    1 |      5.2
(6 rows)

Connected incomplete data

Using selected edges \(\{2, 4, 5, 8, 9, 15\}\) the matrix is not complete.

SELECT * FROM pgr_dijkstraCostMatrix(
  $q1$SELECT id, source, target, cost, reverse_cost FROM edges WHERE id IN (2, 4, 5, 8, 9, 15)$q1$,
  (SELECT ARRAY[6, 7, 10, 11, 16, 17]),
  directed => true);
 start_vid | end_vid | agg_cost
-----------+---------+----------
         6 |       7 |        1
         6 |      11 |        2
         6 |      16 |        3
         6 |      17 |        4
         7 |       6 |        1
         7 |      11 |        1
         7 |      16 |        2
         7 |      17 |        3
        10 |       6 |        1
        10 |       7 |        2
        10 |      11 |        1
        10 |      16 |        2
        10 |      17 |        3
        11 |       6 |        2
        11 |       7 |        1
        11 |      16 |        1
        11 |      17 |        2
        16 |       6 |        3
        16 |       7 |        2
        16 |      11 |        1
        16 |      17 |        1
        17 |       6 |        4
        17 |       7 |        3
        17 |      11 |        2
        17 |      16 |        1
(25 rows)

Cost value for \(17 \rightarrow 10\) do not exist on the matrix, but the value used is taken from \(10 \rightarrow 17\).

SELECT * FROM pgr_TSP(
  $$SELECT * FROM pgr_dijkstraCostMatrix(
  $q1$SELECT id, source, target, cost, reverse_cost FROM edges WHERE id IN (2, 4, 5, 8, 9, 15)$q1$,
  (SELECT ARRAY[6, 7, 10, 11, 16, 17]),
  directed => true)$$);
 seq | node | cost | agg_cost
-----+------+------+----------
   1 |    6 |    0 |        0
   2 |    7 |    1 |        1
   3 |   11 |    1 |        2
   4 |   16 |    1 |        3
   5 |   17 |    1 |        4
   6 |   10 |    3 |        7
   7 |    6 |    1 |        8
(7 rows)

See Also

• Traveling Sales Person - Family of functions

• Sample Data

• Boost’s metric appro’s metric approximation

• Wikipedia: Traveling Salesman Problem

Indices and tables

• Index

• Search Page