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?

General 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

Characteristics

  • 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

Default

Description

Matrix SQL

TEXT

An SQL query, described in the Matrix SQL section.

start_vid

BIGINT

0

The first visiting vertex

  • When 0 any vertex can become the first visiting vertex.

end_vid

BIGINT

0

Last visiting vertex before returning to start_vid .

  • When 0 any vertex can become the last visiting vertex before returning to start_vid .

  • When NOT 0 and start_vid = 0 then it is the first and last vertex

Inner query

Matrix SQL

Matrix SQL : an SQL query, which should return a set of rows with the following columns:

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
 5  WHERE id IN (2,4,5,8,9,15)
 6  $$);
 7 seq  node  cost  agg_cost
 8-----+------+------+----------
 9   1     2     0         0
10   2     3     1         1
11   3     6     1         2
12   4    12     1         3
13   5     9     1         4
14   6     5     1         5
15   7     2     1         6
16(7 rows)
17

The queries use the Sample Data network.

See Also

Indices and tables