pgr_trspVia_withPoints
 Proposed¶
pgr_trspVia_withPoints
 Route that goes through a list of vertices and/or
points 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 ANYINTEGER and ANYNUMERICAL
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_withPoints
(One Via)
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  Proposed.
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:
 ANYINTEGER:
SMALLINT, INTEGER, BIGINT
 ANYNUMERICAL:
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 


ANYINTEGER 
Identifier of the edge. 


ANYINTEGER 
Identifier of the first end point vertex of the edge. 


ANYINTEGER 
Identifier of the second end point vertex of the edge. 


ANYNUMERICAL 
Weight of the edge ( 


ANYNUMERICAL 
1 
Weight of the edge (

Where:
 ANYINTEGER:
SMALLINT
,INTEGER
,BIGINT
 ANYNUMERICAL:
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 

ANYNUMERICAL 
Cost of taking the forbidden path. 
Where:
 ANYINTEGER:
SMALLINT
,INTEGER
,BIGINT
 ANYNUMERICAL:
SMALLINT
,INTEGER
,BIGINT
,REAL
,FLOAT
Points SQL¶
Parameter 
Type 
Default 
Description 


ANYINTEGER 
value 
Identifier of the point.


ANYINTEGER 
Identifier of the “closest” edge to the point. 


ANYNUMERICAL 
Value in <0,1> that indicates the relative postition from the first end point of the edge. 




Value in [

Where:
 ANYINTEGER:
SMALLINT
,INTEGER
,BIGINT
 ANYNUMERICAL:
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:
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  Proposed
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  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_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  Proposed 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  Proposed 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  Proposed result it removes the conflicting paths and
builds the solution with the results of the pgr_trsp  Proposed 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