pgr_trspVia_withPoints
¶
pgr_trspVia_withPoints
- Route that goes through a list of vertices and/or
points with restrictions.
Availability
Version 4.0.0
Function promoted to official.
Version 3.4.0
New proposed function.
Description¶
Given a graph, a set of restriction on the graph edges, a set of points on the graphs edges and a list of vertices, this function is equivalent to finding the shortest path between \(vertex_i\) and \(vertex_{i+1}\) (where \(vertex\) can be a vertex or a point on the graph) for all \(i < size\_of(via\;vertices)\) trying not to use restricted paths.
- Route:
is a sequence of paths
- Path:
is a section of the route.
The general algorithm is as follows:
Build the Graph with the new points.
The points identifiers will be converted to negative values.
The vertices identifiers will remain positive.
Execute a pgr_withPointsVia.
For the set of paths of the solution that pass through a restriction then
Execute the TRSP algorithm with restrictions for the path.
NOTE when this is done,
U_turn_on_edge
flag is ignored.
Note
Do not use negative values on identifiers of the inner queries.
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 \(\{-6, 15, -5\}\) in that order on an directed graph.
SELECT * FROM pgr_trspVia_withPoints(
$$SELECT id, source, target, cost, reverse_cost FROM edges ORDER BY id$$,
$$SELECT path, cost FROM restrictions$$,
$$SELECT pid, edge_id, side, fraction FROM pointsOfInterest$$,
ARRAY[-6, 15, -5]);
seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost | route_agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------+----------------
1 | 1 | 1 | -6 | 15 | -6 | 4 | 0.3 | 0 | 0
2 | 1 | 2 | -6 | 15 | 7 | 10 | 1 | 0.3 | 0.3
3 | 1 | 3 | -6 | 15 | 8 | 12 | 1 | 1.3 | 1.3
4 | 1 | 4 | -6 | 15 | 12 | 13 | 1 | 2.3 | 2.3
5 | 1 | 5 | -6 | 15 | 17 | 15 | 1 | 3.3 | 3.3
6 | 1 | 6 | -6 | 15 | 16 | 16 | 1 | 4.3 | 4.3
7 | 1 | 7 | -6 | 15 | 15 | -1 | 0 | 5.3 | 5.3
8 | 2 | 1 | 15 | -5 | 15 | 3 | 1 | 0 | 5.3
9 | 2 | 2 | 15 | -5 | 10 | 5 | 0.8 | 1 | 6.3
10 | 2 | 3 | 15 | -5 | -5 | -2 | 0 | 1.8 | 7.1
(10 rows)
Parameters¶
Parameter |
Type |
Default |
Description |
---|---|---|---|
|
SQL query as described. |
||
|
SQL query as described. |
||
via vertices |
|
Array of ordered vertices identifiers that are going to be visited.
|
Where:
- ANY-INTEGER:
SMALLINT, INTEGER, BIGINT
- ANY-NUMERICAL:
SMALLINT, INTEGER, BIGINT, REAL, FLOAT
Optional parameters¶
Column |
Type |
Default |
Description |
---|---|---|---|
|
|
|
|
Via optional parameters¶
Parameter |
Type |
Default |
Description |
---|---|---|---|
|
|
|
|
|
|
|
|
With points optional parameters¶
Parameter |
Type |
Default |
Description |
---|---|---|---|
|
|
|
Value in [
|
|
|
|
|
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
Points SQL¶
Parameter |
Type |
Default |
Description |
---|---|---|---|
|
ANY-INTEGER |
value |
Identifier of the point.
|
|
ANY-INTEGER |
Identifier of the “closest” edge to the point. |
|
|
ANY-NUMERICAL |
Value in <0,1> that indicates the relative postition from the first end point of the edge. |
|
|
|
|
Value in [
|
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 |
Note
When start_vid
, end_vid
and node
columns have negative values,
the identifier is for a Point.
Additional Examples¶
Use pgr_findCloseEdges
for points on the fly¶
Using pgr_findCloseEdges - Proposed:
Visit from vertex \(1\) to the two locations on the graph of point (2.9, 1.8) in order of closeness to the graph.
SELECT * FROM pgr_trspVia_withPoints(
$e$ SELECT * FROM edges $e$,
$r$ SELECT path, cost FROM restrictions $r$,
$p$ SELECT edge_id, round(fraction::numeric, 2) AS fraction, side
FROM pgr_findCloseEdges(
$$SELECT id, geom FROM edges$$,
(SELECT ST_POINT(2.9, 1.8)),
0.5, cap => 2)
$p$,
ARRAY[1, -1, -2], details => true);
seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost | route_agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------+----------------
1 | 1 | 1 | 1 | -1 | 1 | 6 | 1 | 0 | 0
2 | 1 | 2 | 1 | -1 | 3 | 7 | 1 | 1 | 1
3 | 1 | 3 | 1 | -1 | 7 | 8 | 0.9 | 2 | 2
4 | 1 | 4 | 1 | -1 | -2 | 8 | 0.1 | 2.9 | 2.9
5 | 1 | 5 | 1 | -1 | 11 | 8 | 1 | 3 | 3
6 | 1 | 6 | 1 | -1 | 7 | 10 | 1 | 4 | 4
7 | 1 | 7 | 1 | -1 | 8 | 12 | 1 | 5 | 5
8 | 1 | 8 | 1 | -1 | 12 | 13 | 1 | 6 | 6
9 | 1 | 9 | 1 | -1 | 17 | 15 | 1 | 7 | 7
10 | 1 | 10 | 1 | -1 | 16 | 16 | 1 | 8 | 8
11 | 1 | 11 | 1 | -1 | 15 | 3 | 1 | 9 | 9
12 | 1 | 12 | 1 | -1 | 10 | 5 | 0.8 | 10 | 10
13 | 1 | 13 | 1 | -1 | -1 | -1 | 0 | 10.8 | 10.8
14 | 2 | 1 | -1 | -2 | -1 | 5 | 0.2 | 0 | 10.8
15 | 2 | 2 | -1 | -2 | 11 | 8 | 1 | 0.2 | 11
16 | 2 | 3 | -1 | -2 | 7 | 8 | 0.9 | 1.2 | 12
17 | 2 | 4 | -1 | -2 | -2 | -2 | 0 | 2.1 | 12.9
(17 rows)
Point \(-1\) corresponds to the closest edge from point (2.9, 1.8).
Point \(-2\) corresponds to the next close edge from point (2.9, 1.8).
Point \(-2\) is visited on the route to from vertex \(1\) to Point \(-1\) (See row where \(seq = 4\)).
Usage variations¶
All this examples are about the route that visits the vertices \(\{-6, 7, -4, 8, -2\}\) in that order on a directed graph.
SELECT * FROM pgr_trspVia_withPoints(
$$SELECT id, source, target, cost, reverse_cost FROM edges ORDER BY id$$,
$$SELECT path, cost FROM restrictions$$,
$$SELECT pid, edge_id, side, fraction FROM pointsOfInterest$$,
ARRAY[-6, 7, -4, 8, -2]
);
seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost | route_agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------+----------------
1 | 1 | 1 | -6 | 7 | -6 | 4 | 0.3 | 0 | 0
2 | 1 | 2 | -6 | 7 | 7 | -1 | 0 | 0.3 | 0.3
3 | 2 | 1 | 7 | -4 | 7 | 7 | 1 | 0 | 0.3
4 | 2 | 2 | 7 | -4 | 3 | 6 | 1.3 | 1 | 1.3
5 | 2 | 3 | 7 | -4 | -4 | -1 | 0 | 2.3 | 2.6
6 | 3 | 1 | -4 | 8 | -4 | 6 | 0.7 | 0 | 2.6
7 | 3 | 2 | -4 | 8 | 3 | 7 | 1 | 0.7 | 3.3
8 | 3 | 3 | -4 | 8 | 7 | 4 | 0.6 | 1.7 | 4.3
9 | 3 | 4 | -4 | 8 | 7 | 10 | 1 | 2.3 | 4.9
10 | 3 | 5 | -4 | 8 | 8 | -1 | 0 | 3.3 | 5.9
11 | 4 | 1 | 8 | -2 | 8 | 10 | 1 | 0 | 5.9
12 | 4 | 2 | 8 | -2 | 7 | 8 | 1 | 1 | 6.9
13 | 4 | 3 | 8 | -2 | 11 | 9 | 1 | 2 | 7.9
14 | 4 | 4 | 8 | -2 | 16 | 15 | 0.4 | 3 | 8.9
15 | 4 | 5 | 8 | -2 | -2 | -2 | 0 | 3.4 | 9.3
(15 rows)
Aggregate cost of the third path.¶
SELECT agg_cost FROM pgr_trspVia_withPoints(
$$SELECT id, source, target, cost, reverse_cost FROM edges ORDER BY id$$,
$$SELECT path, cost FROM restrictions$$,
$$SELECT pid, edge_id, side, fraction FROM pointsOfInterest$$,
ARRAY[-6, 7, -4, 8, -2]
)
WHERE path_id = 3 AND edge <0;
agg_cost
----------
3.3
(1 row)
Route’s aggregate cost of the route at the end of the third path.¶
SELECT route_agg_cost FROM pgr_trspVia_withPoints(
$$SELECT id, source, target, cost, reverse_cost FROM edges ORDER BY id$$,
$$SELECT path, cost FROM restrictions$$,
$$SELECT pid, edge_id, side, fraction FROM pointsOfInterest$$,
ARRAY[-6, 7, -4, 8, -2]
)
WHERE path_id = 3 AND edge < 0;
route_agg_cost
----------------
5.9
(1 row)
Nodes visited in the route.¶
SELECT row_number() over () as node_seq, node
FROM pgr_trspVia_withPoints(
$$SELECT id, source, target, cost, reverse_cost FROM edges ORDER BY id$$,
$$SELECT path, cost FROM restrictions$$,
$$SELECT pid, edge_id, side, fraction FROM pointsOfInterest$$,
ARRAY[-6, 7, -4, 8, -2]
)
WHERE edge <> -1 ORDER BY seq;
node_seq | node
----------+------
1 | -6
2 | 7
3 | 3
4 | -4
5 | 3
6 | 7
7 | 7
8 | 8
9 | 7
10 | 11
11 | 16
12 | -2
(12 rows)
The aggregate costs of the route when the visited vertices are reached.¶
SELECT path_id, route_agg_cost FROM pgr_trspVia_withPoints(
$$SELECT id, source, target, cost, reverse_cost FROM edges ORDER BY id$$,
$$SELECT path, cost FROM restrictions$$,
$$SELECT pid, edge_id, side, fraction FROM pointsOfInterest$$,
ARRAY[-6, 7, -4, 8, -2]
)
WHERE edge < 0;
path_id | route_agg_cost
---------+----------------
1 | 0.3
2 | 2.6
3 | 5.9
4 | 9.3
(4 rows)
Status of “passes in front” or “visits” of the nodes and points.¶
SELECT seq, route_agg_cost, node, agg_cost ,
CASE WHEN edge = -1 THEN $$visits$$
ELSE $$passes in front$$
END as status
FROM pgr_trspVia_withPoints(
$$SELECT id, source, target, cost, reverse_cost FROM edges ORDER BY id$$,
$$SELECT path, cost FROM restrictions$$,
$$SELECT pid, edge_id, side, fraction FROM pointsOfInterest$$,
ARRAY[-6, 7, -4, 8, -2])
WHERE agg_cost <> 0 or seq = 1;
seq | route_agg_cost | node | agg_cost | status
-----+----------------+------+----------+-----------------
1 | 0 | -6 | 0 | passes in front
2 | 0.3 | 7 | 0.3 | visits
4 | 1.3 | 3 | 1 | passes in front
5 | 2.6 | -4 | 2.3 | visits
7 | 3.3 | 3 | 0.7 | passes in front
8 | 4.3 | 7 | 1.7 | passes in front
9 | 4.9 | 7 | 2.3 | passes in front
10 | 5.9 | 8 | 3.3 | visits
12 | 6.9 | 7 | 1 | passes in front
13 | 7.9 | 11 | 2 | passes in front
14 | 8.9 | 16 | 3 | passes in front
15 | 9.3 | -2 | 3.4 | passes in front
(12 rows)
Simulation of how algorithm works.¶
The algorithm performs a pgr_withPointsVia
SELECT * FROM pgr_withPointsVia(
$$SELECT id, source, target, cost, reverse_cost FROM edges ORDER BY id$$,
$$SELECT pid, edge_id, side, fraction FROM pointsOfInterest$$,
ARRAY[-6, 15, -5]);
seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost | route_agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------+----------------
1 | 1 | 1 | -6 | 15 | -6 | 4 | 0.3 | 0 | 0
2 | 1 | 2 | -6 | 15 | 7 | 8 | 1 | 0.3 | 0.3
3 | 1 | 3 | -6 | 15 | 11 | 9 | 1 | 1.3 | 1.3
4 | 1 | 4 | -6 | 15 | 16 | 16 | 1 | 2.3 | 2.3
5 | 1 | 5 | -6 | 15 | 15 | -1 | 0 | 3.3 | 3.3
6 | 2 | 1 | 15 | -5 | 15 | 3 | 1 | 0 | 3.3
7 | 2 | 2 | 15 | -5 | 10 | 5 | 0.8 | 1 | 4.3
8 | 2 | 3 | 15 | -5 | -5 | -2 | 0 | 1.8 | 5.1
(8 rows)
Detects which of the paths pass through a restriction in this case is for the
path_id = 1
from -6
to 15
because the path \(9 \rightarrow 16\)
is restricted.
Executes the TRSP algorithm for the conflicting paths.
SELECT 1 AS path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost
FROM pgr_trsp_withPoints(
$$SELECT id, source, target, cost, reverse_cost FROM edges$$,
$$SELECT path, cost FROM restrictions$$,
$$SELECT pid, edge_id, side, fraction FROM pointsOfInterest$$,
-6, 15);
path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
---------+----------+-----------+---------+------+------+------+----------
1 | 1 | -6 | 15 | -6 | 4 | 0.3 | 0
1 | 2 | -6 | 15 | 7 | 10 | 1 | 0.3
1 | 3 | -6 | 15 | 8 | 12 | 1 | 1.3
1 | 4 | -6 | 15 | 12 | 13 | 1 | 2.3
1 | 5 | -6 | 15 | 17 | 15 | 1 | 3.3
1 | 6 | -6 | 15 | 16 | 16 | 1 | 4.3
1 | 7 | -6 | 15 | 15 | -1 | 0 | 5.3
(7 rows)
From the pgr_withPointsVia result it removes the conflicting paths and builds the solution with the results of the pgr_trsp algorithm:
WITH
solutions AS (
SELECT path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost
FROM pgr_withPointsVia(
$$SELECT id, source, target, cost, reverse_cost FROM edges$$,
$$SELECT pid, edge_id, side, fraction FROM pointsOfInterest$$,
ARRAY[-6, 15, -5]) WHERE path_id != 1
UNION
SELECT 1 AS path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost
FROM pgr_trsp_withPoints(
$$SELECT id, source, target, cost, reverse_cost FROM edges$$,
$$SELECT path, cost FROM restrictions$$,
$$SELECT pid, edge_id, side, fraction FROM pointsOfInterest$$,
-6, 15)),
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 | 15 | -6 | 4 | 0.3 | 0 | 0
2 | 1 | 2 | -6 | 15 | 7 | 10 | 1 | 0.3 | 0.3
3 | 1 | 3 | -6 | 15 | 8 | 12 | 1 | 1.3 | 1.3
4 | 1 | 4 | -6 | 15 | 12 | 13 | 1 | 2.3 | 2.3
5 | 1 | 5 | -6 | 15 | 17 | 15 | 1 | 3.3 | 3.3
6 | 1 | 6 | -6 | 15 | 16 | 16 | 1 | 4.3 | 4.3
7 | 1 | 7 | -6 | 15 | 15 | -1 | 0 | 5.3 | 5.3
8 | 2 | 1 | 15 | -5 | 15 | 3 | 1 | 0 | 5.3
9 | 2 | 2 | 15 | -5 | 10 | 5 | 0.8 | 1 | 6.3
10 | 2 | 3 | 15 | -5 | -5 | -2 | 0 | 1.8 | 7.1
(10 rows)
Getting the same result as pgr_trspVia_withPoints
:
SELECT * FROM pgr_trspVia_withPoints(
$$SELECT id, source, target, cost, reverse_cost FROM edges ORDER BY id$$,
$$SELECT path, cost FROM restrictions$$,
$$SELECT pid, edge_id, side, fraction FROM pointsOfInterest$$,
ARRAY[-6, 15, -5]);
seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost | route_agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------+----------------
1 | 1 | 1 | -6 | 15 | -6 | 4 | 0.3 | 0 | 0
2 | 1 | 2 | -6 | 15 | 7 | 10 | 1 | 0.3 | 0.3
3 | 1 | 3 | -6 | 15 | 8 | 12 | 1 | 1.3 | 1.3
4 | 1 | 4 | -6 | 15 | 12 | 13 | 1 | 2.3 | 2.3
5 | 1 | 5 | -6 | 15 | 17 | 15 | 1 | 3.3 | 3.3
6 | 1 | 6 | -6 | 15 | 16 | 16 | 1 | 4.3 | 4.3
7 | 1 | 7 | -6 | 15 | 15 | -1 | 0 | 5.3 | 5.3
8 | 2 | 1 | 15 | -5 | 15 | 3 | 1 | 0 | 5.3
9 | 2 | 2 | 15 | -5 | 10 | 5 | 0.8 | 1 | 6.3
10 | 2 | 3 | 15 | -5 | -5 | -2 | 0 | 1.8 | 7.1
(10 rows)
- Example 8:
Sometimes
U_turn_on_edge
flag is ignored when is set tofalse
.
The first step, doing a pgr_withPointsVia does consider not making a U turn on the same edge. But the path \(9 \rightarrow 16\) (Rows 4 and 5) is restricted and the result is using it.
SELECT * FROM pgr_withPointsVia(
$$SELECT id, source, target, cost, reverse_cost FROM edges ORDER BY id$$,
$$SELECT pid, edge_id, side, fraction FROM pointsOfInterest$$,
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_withPoints algorithm for the conflicting
path, there is no U_turn_on_edge
flag.
SELECT 5 AS path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost
FROM pgr_trsp_withPoints(
$$SELECT id, source, target, cost, reverse_cost FROM edges$$,
$$SELECT path, cost FROM restrictions$$,
$$SELECT pid, edge_id, side, fraction FROM pointsOfInterest$$,
7, 6);
path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
---------+----------+-----------+---------+------+------+------+----------
5 | 1 | 7 | 6 | 7 | 4 | 1 | 0
5 | 2 | 7 | 6 | 6 | -1 | 0 | 1
(2 rows)
Therefore the result ignores the U_turn_on_edge
flag when set to false
.
From the pgr_withPointsVia result it removes the conflicting paths and
builds the solution with the results of the pgr_trsp algorithm.
In this case a U turn is been done using the same edge.
SELECT * FROM pgr_trspVia_withPoints(
$$SELECT id, source, target, cost, reverse_cost FROM edges ORDER BY id$$,
$$SELECT path, cost FROM restrictions$$,
$$SELECT pid, edge_id, side, fraction FROM pointsOfInterest$$,
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¶
Indices and tables