pgr_TSP

  • pgr_TSP - Aproximation using metric algorithm.

_images/boost-inside.jpeg

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 SETOF (seq, node, cost, agg_cost)
Example

Using pgr_dijkstraCostMatrix to generate the matrix information

  • Line 5 Vertices 15 to 18 are not included because they are not connected.

 1SELECT * FROM pgr_TSP(
 2  $$
 3  SELECT * FROM pgr_dijkstraCostMatrix(
 4    'SELECT id, source, target, cost, reverse_cost FROM edge_table',
 5    (SELECT array_agg(id) FROM edge_table_vertices_pgr WHERE id < 14),
 6    directed => false)
 7  $$);
 8 seq | node | cost | agg_cost
 9-----+------+------+----------
10   1 |    1 |    0 |        0
11   2 |    2 |    1 |        1
12   3 |    3 |    1 |        2
13   4 |    4 |    1 |        3
14   5 |    9 |    1 |        4
15   6 |   12 |    1 |        5
16   7 |    6 |    2 |        7
17   8 |    5 |    1 |        8
18   9 |    8 |    1 |        9
19  10 |    7 |    1 |       10
20  11 |   10 |    3 |       13
21  12 |   11 |    1 |       14
22  13 |   13 |    2 |       16
23  14 |    1 |    4 |       20
24(14 rows)
25

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

Example

Start from vertex \(7\)

  • Line 9 start_vid => 7

 1SELECT * FROM pgr_TSP(
 2  $$
 3  SELECT * FROM pgr_dijkstraCostMatrix(
 4    'SELECT id, source, target, cost, reverse_cost FROM edge_table',
 5    (SELECT array_agg(id) FROM edge_table_vertices_pgr WHERE id < 14),
 6    directed => false
 7  )
 8  $$,
 9  start_id => 7
10);
11 seq | node | cost | agg_cost
12-----+------+------+----------
13   1 |    7 |    0 |        0
14   2 |    8 |    1 |        1
15   3 |    5 |    1 |        2
16   4 |    2 |    1 |        3
17   5 |    1 |    1 |        4
18   6 |    3 |    2 |        6
19   7 |    4 |    1 |        7
20   8 |    9 |    1 |        8
21   9 |   12 |    1 |        9
22  10 |   11 |    1 |       10
23  11 |    6 |    1 |       11
24  12 |   10 |    2 |       13
25  13 |   13 |    1 |       14
26  14 |    7 |    4 |       18
27(14 rows)
28
Example

Using points of interest to generate an asymetric matrix.

To generate an asymmetric matrix:

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

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

 1SELECT * FROM pgr_TSP(
 2  $$
 3  SELECT * FROM pgr_withPointsCostMatrix(
 4    'SELECT id, source, target, cost, reverse_cost FROM edge_table ORDER BY id',
 5    'SELECT pid, edge_id, fraction from pointsOfInterest',
 6    array[-1, 3, 5, 6, -6],
 7    directed => true)
 8  $$,
 9  start_id => 5,
10  end_id => 6
11);
12 seq | node | cost | agg_cost
13-----+------+------+----------
14   1 |    5 |    0 |        0
15   2 |   -6 |  0.3 |      0.3
16   3 |   -1 |  1.3 |      1.6
17   4 |    3 |  1.6 |      3.2
18   5 |    6 |    1 |      4.2
19   6 |    5 |    1 |      5.2
20(6 rows)
21
Example

Connected incomplete data

Using selected edges (2, 4, 5, 8, 9, 15) the matrix is not complete but it is connected

 1SELECT source AS start_vid, target AS end_vid, 1 AS agg_cost
 2FROM edge_table WHERE id IN (2, 4, 5, 8, 9, 15);
 3 start_vid | end_vid | agg_cost
 4-----------+---------+----------
 5         2 |       3 |        1
 6         2 |       5 |        1
 7         3 |       6 |        1
 8         5 |       6 |        1
 9         6 |       9 |        1
10         9 |      12 |        1
11(6 rows)
12

Edge (5,12) does not exist on the initial data, but it is calculated internally.

 1SELECT * FROM pgr_TSP(
 2  $$
 3  SELECT source AS start_vid, target AS end_vid, 1 AS agg_cost
 4  FROM edge_table WHERE id IN (2, 4, 5, 8, 9, 15)
 5  $$);
 6 seq | node | cost | agg_cost
 7-----+------+------+----------
 8   1 |    2 |    0 |        0
 9   2 |    3 |    1 |        1
10   3 |    6 |    1 |        2
11   4 |   12 |    1 |        3
12   5 |    9 |    1 |        4
13   6 |    5 |    1 |        5
14   7 |    2 |    1 |        6
15(7 rows)
16

The queries use the Sample Data network.

See Also

Indices and tables