pgr_TSP
¶
pgr_TSP
- Aproximation using metric algorithm.
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
- Signature change
- 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
tov
are just as much as traveling fromv
tou
- 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.
- Will generate a graph that:
- 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 theagg_cost
of edge (u, v) - Some (or all) traveling costs on edges will still might not obey the triangle inequality.
- With
- 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 4 Vertices \(\{2, 4, 13, 14\}\) are not included because they are not connected.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | 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
|
end_id |
ANY-INTEGER | 0 |
Last visiting vertex before returning to
|
Inner Queries¶
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
|
agg_cost | FLOAT |
Aggregate cost from the
|
Additional Examples¶
Start from vertex \(1\)¶
- Line 6
start_vid => 1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | 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 ofpointsOfInterset
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
- \(min(agg\_cost(u, v), agg\_cost(v, u))\) is going to be considered as
the
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | 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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 | 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\).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | 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)
|