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
- 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
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
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
corresponds to the closest edge from point (2.9, 1.8).Point
corresponds to the next close edge from point (2.9, 1.8).Point
is visited on the route to from vertex to Point (See row where ).
Usage variations¶
All this examples are about the route that visits the vertices
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
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
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