pgr_TSP - pgRouting Manual (3.4)

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.

TSP optional parameters

Matrix SQL

Start from vertex \(1\)

• Line 6 start_vid => 1

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

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

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

Connected incomplete data

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

 1SELECT * FROM pgr_dijkstraCostMatrix(
 2  $q1$SELECT id, source, target, cost, reverse_cost FROM edges WHERE id IN (2, 4, 5, 8, 9, 15)$q1$,
 3  (SELECT ARRAY[6, 7, 10, 11, 16, 17]),
 4  directed => true);
 5 start_vid  end_vid  agg_cost
 6-----------+---------+----------
 7         6        7         1
 8         6       11         2
 9         6       16         3
10         6       17         4
11         7        6         1
12         7       11         1
13         7       16         2
14         7       17         3
15        10        6         1
16        10        7         2
17        10       11         1
18        10       16         2
19        10       17         3
20        11        6         2
21        11        7         1
22        11       16         1
23        11       17         2
24        16        6         3
25        16        7         2
26        16       11         1
27        16       17         1
28        17        6         4
29        17        7         3
30        17       11         2
31        17       16         1
32(25 rows)
33

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

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