pgr_trspVia - Proposed - pgRouting Manual (3.4)
pgr_trspVia
- Proposed
pgr_trspVia
Route that goes through a list of vertices with restrictions.
Warning
Proposed functions for next mayor release.
-
They are not officially in the current release.
-
They will likely officially be part of the next mayor release:
-
The functions make use of ANY-INTEGER and ANY-NUMERICAL
-
Name might not change. (But still can)
-
Signature might not change. (But still can)
-
Functionality might not change. (But still can)
-
pgTap tests have being done. But might need more.
-
Documentation might need refinement.
-
Availability
-
Version 3.4.0
-
New proposed function:
-
pgr_trspVia( One Via )
-
-
Description
Given a list of vertices and a graph, this function is equivalent to finding the shortest path between \(vertex_i\) and \(vertex_{i+1}\) for all \(i < size\_of(via\;vertices)\) trying not to use restricted paths.
The paths represents the sections of the route.
The general algorithm is as follows:
-
Execute a pgr_dijkstraVia - Proposed .
-
For the set of sub paths of the solution that pass through a restriction then
-
Execute the TRSP algorithm with restrictions for the paths.
-
NOTE when this is done,
U_turn_on_edgeflag is ignored.
-
Signatures
One Via
[directed,
strict,
U_turn_on_edge]
(seq,
path_id,
path_seq,
start_vid,
end_vid,
node,
edge,
cost,
agg_cost,
route_agg_cost)
- Example :
-
Find the route that visits the vertices \(\{ 5, 1, 8\}\) in that order on an directed graph.
SELECT * FROM pgr_trspVia(
$$SELECT id, source, target, cost, reverse_cost FROM edges$$,
$$SELECT path, cost FROM restrictions$$,
ARRAY[5, 1, 8]);
seq path_id path_seq start_vid end_vid node edge cost agg_cost route_agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------+----------------
1 1 1 5 1 5 1 1 0 0
2 1 2 5 1 6 4 1 1 1
3 1 3 5 1 7 10 1 2 2
4 1 4 5 1 8 12 1 3 3
5 1 5 5 1 12 13 1 4 4
6 1 6 5 1 17 15 1 5 5
7 1 7 5 1 16 9 1 6 6
8 1 8 5 1 11 8 1 7 7
9 1 9 5 1 7 7 1 8 8
10 1 10 5 1 3 6 1 9 9
11 1 11 5 1 1 -1 0 10 10
12 2 1 1 8 1 6 1 0 10
13 2 2 1 8 3 7 1 1 11
14 2 3 1 8 7 10 101 2 12
15 2 4 1 8 8 -2 0 103 113
(15 rows)
Parameters
|
Parameter |
Type |
Description |
|---|---|---|
|
|
Edges SQL query as described. |
|
|
|
Restrictions SQL query as described. |
|
|
via vertices |
|
Array of ordered vertices identifiers that are going to be visited. |
Where:
- ANY-INTEGER :
-
SMALLINT, INTEGER, BIGINT
Optional parameters
|
Column |
Type |
Default |
Description |
|---|---|---|---|
|
|
|
|
|
Via optional parameters
|
Parameter |
Type |
Default |
Description |
|---|---|---|---|
|
|
|
|
|
|
|
|
|
|
Inner Queries
Edges SQL
|
Column |
Type |
Default |
Description |
|---|---|---|---|
|
|
ANY-INTEGER |
Identifier of the edge. |
|
|
|
ANY-INTEGER |
Identifier of the first end point vertex of the edge. |
|
|
|
ANY-INTEGER |
Identifier of the second end point vertex of the edge. |
|
|
|
ANY-NUMERICAL |
Weight of the edge (
|
|
|
|
ANY-NUMERICAL |
-1 |
Weight of the edge (
|
Where:
- ANY-INTEGER :
-
SMALLINT,INTEGER,BIGINT - ANY-NUMERICAL :
-
SMALLINT,INTEGER,BIGINT,REAL,FLOAT
Restrictions SQL
|
Column |
Type |
Description |
|---|---|---|
|
|
|
Sequence of edge identifiers that form a path that is not allowed to be
taken.
- Empty arrays or
|
|
|
ANY-NUMERICAL |
Cost of taking the forbidden path. |
Where:
- ANY-INTEGER :
-
SMALLINT,INTEGER,BIGINT - ANY-NUMERICAL :
-
SMALLINT,INTEGER,BIGINT,REAL,FLOAT
Result Columns
|
Column |
Type |
Description |
|---|---|---|
|
|
|
Sequential value starting from 1 . |
|
|
|
Identifier of a path. Has value 1 for the first path. |
|
|
|
Relative position in the path. Has value 1 for the beginning of a path. |
|
|
|
Identifier of the starting vertex of the path. |
|
|
|
Identifier of the ending vertex of the path. |
|
|
|
Identifier of the node in the path from
|
|
|
|
Identifier of the edge used to go from
|
|
|
|
Cost to traverse from
|
|
|
|
Aggregate cost from
|
|
|
|
Total cost from
|
Additional Examples
All this examples are about the route that visits the vertices \(\{5, 7, 1, 8, 15\}\) in that order on a directed graph.
The main query
SELECT * FROM pgr_trspVia(
$$SELECT id, source, target, cost, reverse_cost FROM edges$$,
$$SELECT path, cost FROM restrictions$$,
ARRAY[5, 7, 1, 8, 15]);
seq path_id path_seq start_vid end_vid node edge cost agg_cost route_agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------+----------------
1 1 1 5 7 5 1 1 0 0
2 1 2 5 7 6 4 1 1 1
3 1 3 5 7 7 -1 0 2 2
4 2 1 7 1 7 7 1 0 2
5 2 2 7 1 3 6 1 1 3
6 2 3 7 1 1 -1 0 2 4
7 3 1 1 8 1 6 1 0 4
8 3 2 1 8 3 7 1 1 5
9 3 3 1 8 7 10 101 2 6
10 3 4 1 8 8 -1 0 103 107
11 4 1 8 15 8 12 1 0 107
12 4 2 8 15 12 13 1 1 108
13 4 3 8 15 17 15 1 2 109
14 4 4 8 15 16 16 1 3 110
15 4 5 8 15 15 -2 0 4 111
(15 rows)
Aggregate cost of the third path.
SELECT agg_cost FROM pgr_trspVia(
$$SELECT id, source, target, cost, reverse_cost FROM edges$$,
$$SELECT path, cost FROM restrictions$$,
ARRAY[5, 7, 1, 8, 15])
WHERE path_id = 3 AND edge < 0;
agg_cost
----------
103
(1 row)
Route’s aggregate cost of the route at the end of the third path.
SELECT route_agg_cost FROM pgr_trspVia(
$$SELECT id, source, target, cost, reverse_cost FROM edges$$,
$$SELECT path, cost FROM restrictions$$,
ARRAY[5, 7, 1, 8, 15])
WHERE path_id = 3 AND edge < 0;
route_agg_cost
----------------
107
(1 row)
Nodes visited in the route.
SELECT row_number() over () as node_seq, node
FROM pgr_trspVia(
$$SELECT id, source, target, cost, reverse_cost FROM edges$$,
$$SELECT path, cost FROM restrictions$$,
ARRAY[5, 7, 1, 8, 15])
WHERE edge <> -1 ORDER BY seq;
node_seq node
----------+------
1 5
2 6
3 7
4 3
5 1
6 3
7 7
8 8
9 12
10 17
11 16
12 15
(12 rows)
The aggregate costs of the route when the visited vertices are reached.
SELECT path_id, route_agg_cost FROM pgr_trspVia(
$$SELECT id, source, target, cost, reverse_cost FROM edges$$,
$$SELECT path, cost FROM restrictions$$,
ARRAY[5, 7, 1, 8, 15])
WHERE edge < 0;
path_id route_agg_cost
---------+----------------
1 2
2 4
3 107
4 111
(4 rows)
Status of "passes in front" or "visits" of the nodes.
SELECT seq, route_agg_cost, node, agg_cost ,
CASE WHEN edge = -1 THEN $$visits$$
ELSE $$passes in front$$
END as status
FROM pgr_trspVia(
$$SELECT id, source, target, cost, reverse_cost FROM edges$$,
$$SELECT path, cost FROM restrictions$$,
ARRAY[5, 7, 1, 8, 15])
WHERE agg_cost <> 0 or seq = 1;
seq route_agg_cost node agg_cost status
-----+----------------+------+----------+-----------------
1 0 5 0 passes in front
2 1 6 1 passes in front
3 2 7 2 visits
5 3 3 1 passes in front
6 4 1 2 visits
8 5 3 1 passes in front
9 6 7 2 passes in front
10 107 8 103 visits
12 108 12 1 passes in front
13 109 17 2 passes in front
14 110 16 3 passes in front
15 111 15 4 passes in front
(12 rows)
Simulation of how algorithm works.
The algorithm performs a pgr_dijkstraVia - Proposed
SELECT * FROM pgr_dijkstraVia(
$$SELECT id, source, target, cost, reverse_cost FROM edges$$,
ARRAY[6, 3, 6]);
seq path_id path_seq start_vid end_vid node edge cost agg_cost route_agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------+----------------
1 1 1 6 3 6 4 1 0 0
2 1 2 6 3 7 7 1 1 1
3 1 3 6 3 3 -1 0 2 2
4 2 1 3 6 3 7 1 0 2
5 2 2 3 6 7 4 1 1 3
6 2 3 3 6 6 -2 0 2 4
(6 rows)
Detects which of the sub paths pass through a restriction in this case is for
the
path_id
=
5
from
6
to
3
because the path
\(15 \rightarrow 1\)
is restricted.
Executes the pgr_trsp - Proposed algorithm for the conflicting paths.
SELECT 1 AS path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost FROM pgr_trsp(
$$SELECT id, source, target, cost, reverse_cost FROM edges$$,
$$SELECT path, cost FROM restrictions$$,
6, 3);
path_id path_seq start_vid end_vid node edge cost agg_cost
---------+----------+-----------+---------+------+------+------+----------
1 1 6 3 6 4 1 0
1 2 6 3 7 10 1 1
1 3 6 3 8 12 1 2
1 4 6 3 12 13 1 3
1 5 6 3 17 15 1 4
1 6 6 3 16 9 1 5
1 7 6 3 11 8 1 6
1 8 6 3 7 7 1 7
1 9 6 3 3 -1 0 8
(9 rows)
From the pgr_dijkstraVia - Proposed result it removes the conflicting paths and builds the solution with the results of the pgr_trsp - Proposed algorithm:
WITH
solutions AS (
SELECT path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost FROM pgr_dijkstraVia(
$$SELECT id, source, target, cost, reverse_cost FROM edges$$,
ARRAY[6, 3, 6]) WHERE path_id != 1
UNION
SELECT 1 AS path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost FROM pgr_trsp(
$$SELECT id, source, target, cost, reverse_cost FROM edges$$,
$$SELECT path, cost FROM restrictions$$,
6, 3)),
with_seq AS (
SELECT row_number() over(ORDER BY path_id, path_seq) AS seq, *
FROM solutions),
aggregation AS (SELECT seq, SUM(cost) OVER(ORDER BY seq) AS route_agg_cost FROM with_seq)
SELECT with_seq.*, COALESCE(route_agg_cost, 0) AS route_agg_cost
FROM with_seq LEFT JOIN aggregation ON (with_seq.seq = aggregation.seq + 1);
seq path_id path_seq start_vid end_vid node edge cost agg_cost route_agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------+----------------
1 1 1 6 3 6 4 1 0 0
2 1 2 6 3 7 10 1 1 1
3 1 3 6 3 8 12 1 2 2
4 1 4 6 3 12 13 1 3 3
5 1 5 6 3 17 15 1 4 4
6 1 6 6 3 16 9 1 5 5
7 1 7 6 3 11 8 1 6 6
8 1 8 6 3 7 7 1 7 7
9 1 9 6 3 3 -1 0 8 8
10 2 1 3 6 3 7 1 0 8
11 2 2 3 6 7 4 1 1 9
12 2 3 3 6 6 -2 0 2 10
(12 rows)
Getting the same result as
pgr_trspVia
:
SELECT * FROM pgr_trspVia(
$$SELECT id, source, target, cost, reverse_cost FROM edges$$,
$$SELECT path, cost FROM restrictions$$,
ARRAY[6, 3, 6]);
seq path_id path_seq start_vid end_vid node edge cost agg_cost route_agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------+----------------
1 1 1 6 3 6 4 1 0 0
2 1 2 6 3 7 10 1 1 1
3 1 3 6 3 8 12 1 2 2
4 1 4 6 3 12 13 1 3 3
5 1 5 6 3 17 15 1 4 4
6 1 6 6 3 16 9 1 5 5
7 1 7 6 3 11 8 1 6 6
8 1 8 6 3 7 7 1 7 7
9 1 9 6 3 3 -1 0 8 8
10 2 1 3 6 3 7 1 0 8
11 2 2 3 6 7 4 1 1 9
12 2 3 3 6 6 -2 0 2 10
(12 rows)
- Example 8 :
-
Sometimes
U_turn_on_edgeflag is ignored when is set tofalse.
The first step, doing a pgr_dijkstraVia - Proposed does consider not making a U turn on the same edge. But the path \(16 \rightarrow 13\) (Rows 4 and 5) is restricted and the result is using it.
SELECT * FROM pgr_dijkstraVia(
$$SELECT id, source, target, cost, reverse_cost FROM edges$$,
ARRAY[6, 7, 6], U_turn_on_edge => false);
seq path_id path_seq start_vid end_vid node edge cost agg_cost route_agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------+----------------
1 1 1 6 7 6 4 1 0 0
2 1 2 6 7 7 -1 0 1 1
3 2 1 7 6 7 8 1 0 1
4 2 2 7 6 11 9 1 1 2
5 2 3 7 6 16 16 1 2 3
6 2 4 7 6 15 3 1 3 4
7 2 5 7 6 10 2 1 4 5
8 2 6 7 6 6 -2 0 5 6
(8 rows)
When executing the
pgr_trsp - Proposed
algorithm for the conflicting path, there is
no
U_turn_on_edge
flag.
SELECT 1 AS path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost FROM pgr_trsp(
$$SELECT id, source, target, cost, reverse_cost FROM edges$$,
$$SELECT path, cost FROM restrictions$$,
7, 6);
path_id path_seq start_vid end_vid node edge cost agg_cost
---------+----------+-----------+---------+------+------+------+----------
1 1 7 6 7 4 1 0
1 2 7 6 6 -1 0 1
(2 rows)
Therefore the result ignores the
U_turn_on_edge
flag when set to
false
.
SELECT * FROM pgr_trspVia(
$$SELECT id, source, target, cost, reverse_cost FROM edges$$,
$$SELECT path, cost FROM restrictions$$,
ARRAY[6, 7, 6], U_turn_on_edge => false);
seq path_id path_seq start_vid end_vid node edge cost agg_cost route_agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------+----------------
1 1 1 6 7 6 4 1 0 0
2 1 2 6 7 7 -1 0 1 1
3 2 1 7 6 7 4 1 0 1
4 2 2 7 6 6 -2 0 1 2
(4 rows)
See Also
-
Sample Data network.
Indices and tables