pgr_trsp — Returns the shortest path with support for turn restrictions.
The turn restricted shorthest path (TRSP) is a shortest path algorithm that can optionally take into account complicated turn restrictions like those found in real world navigable road networks. Performamnce wise it is nearly as fast as the A* search but has many additional features like it works with edges rather than the nodes of the network. Returns a set of pgr_costResult (seq, id1, id2, cost) rows, that make up a path.
pgr_costResult[] pgr_trsp(sql text, source integer, target integer,
directed boolean, has_rcost boolean [,restrict_sql text]);
pgr_costResult[] pgr_trsp(sql text, source_edge integer, source_pos float8,
target_edge integer, target_pos float8,
directed boolean, has_rcost boolean [,restrict_sql text]);
pgr_costResult3[] pgr_trspViaVertices(sql text, vids integer[],
directed boolean, has_rcost boolean
[, turn_restrict_sql text]);
pgr_costResult3[] pgr_trspViaEdges(sql text, eids integer[], pcts float8[],
directed boolean, has_rcost boolean
[, turn_restrict_sql text]);
The Turn Restricted Shortest Path algorithm (TRSP) is similar to the shooting star in that you can specify turn restrictions.
The TRSP setup is mostly the same as Dijkstra shortest path with the addition of an optional turn restriction table. This provides an easy way of adding turn restrictions to a road network by placing them in a separate table.
| sql: | a SQL query, which should return a set of rows with the following columns: SELECT id, source, target, cost, [,reverse_cost] FROM edge_table
|
||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| source: |
|
||||||||||
| target: |
|
||||||||||
| directed: |
|
||||||||||
| has_rcost: | if |
||||||||||
| restrict_sql: | (optional) a SQL query, which should return a set of rows with the following columns: SELECT to_cost, target_id, via_path FROM restrictions
|
Another variant of TRSP allows to specify EDGE id of source and target together with a fraction to interpolate the position:
| source_edge: | int4 EDGE id of the start edge |
|---|---|
| source_pos: | float8 fraction of 1 defines the position on the start edge |
| target_edge: | int4 EDGE id of the end edge |
| target_pos: | float8 fraction of 1 defines the position on the end edge |
Returns set of pgr_costResult[]:
| seq: | row sequence |
|---|---|
| id1: | node ID |
| id2: | edge ID (-1 for the last row) |
| cost: | cost to traverse from id1 using id2 |
History
Warning
The Support for Vias functions are prototypes. Not all corner cases are being considered.
We also have support for vias where you can say generate a from A to B to C, etc. We support both methods above only you pass an array of vertices or and array of edges and percentage position along the edge in two arrays.
| sql: | a SQL query, which should return a set of rows with the following columns: SELECT id, source, target, cost, [,reverse_cost] FROM edge_table
|
||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| vids: |
|
||||||||||
| directed: |
|
||||||||||
| has_rcost: | if |
||||||||||
| restrict_sql: | (optional) a SQL query, which should return a set of rows with the following columns: SELECT to_cost, target_id, via_path FROM restrictions
|
Another variant of TRSP allows to specify EDGE id together with a fraction to interpolate the position:
| eids: | int4 An ordered array of EDGE id that the path has to traverse |
|---|---|
| pcts: | float8 An array of fractional positions along the respective edges in eids, where 0.0 is the start of the edge and 1.0 is the end of the eadge. |
Returns set of pgr_costResult[]:
| seq: | row sequence |
|---|---|
| id1: | route ID |
| id2: | node ID |
| id3: | edge ID (-1 for the last row) |
| cost: | cost to traverse from id2 using id3 |
History
Without turn restrictions
SELECT * FROM pgr_trsp(
'SELECT id::INTEGER, source::INTEGER, target::INTEGER, cost FROM edge_table',
7, 12, false, false
);
seq | id1 | id2 | cost
-----+-----+-----+------
0 | 7 | 6 | 1
1 | 8 | 7 | 1
2 | 5 | 8 | 1
3 | 6 | 9 | 1
4 | 9 | 15 | 1
5 | 12 | -1 | 0
(6 rows)
With turn restrictions
Then a query with turn restrictions is created as:
SELECT * FROM pgr_trsp(
'SELECT id::INTEGER, source::INTEGER, target::INTEGER, cost FROM edge_table',
2, 7, false, false,
'SELECT to_cost, target_id::int4,
from_edge || coalesce('','' || via_path, '''') AS via_path
FROM restrictions'
);
seq | id1 | id2 | cost
-----+-----+-----+------
0 | 2 | 4 | 1
1 | 5 | 10 | 1
2 | 10 | 12 | 1
3 | 11 | 11 | 1
4 | 6 | 8 | 1
5 | 5 | 7 | 1
6 | 8 | 6 | 1
7 | 7 | -1 | 0
(8 rows)
SELECT * FROM pgr_trsp(
'SELECT id::INTEGER, source::INTEGER, target::INTEGER, cost FROM edge_table',
7, 11, false, false,
'SELECT to_cost, target_id::int4,
from_edge || coalesce('','' || via_path, '''') AS via_path
FROM restrictions'
);
seq | id1 | id2 | cost
-----+-----+-----+------
0 | 7 | 6 | 1
1 | 8 | 7 | 1
2 | 5 | 8 | 1
3 | 6 | 9 | 1
4 | 9 | 15 | 1
5 | 12 | 13 | 1
6 | 11 | -1 | 0
(7 rows)
An example query using vertex ids and via points:
SELECT * FROM pgr_trspViaVertices(
'SELECT id::INTEGER, source::INTEGER, target::INTEGER, cost FROM edge_table',
ARRAY[2,7,11]::INTEGER[],
false, false,
'SELECT to_cost, target_id::int4, from_edge ||
coalesce('',''||via_path,'''') AS via_path FROM restrictions');
seq | id1 | id2 | id3 | cost
-----+-----+-----+-----+------
1 | 1 | 2 | 4 | 1
2 | 1 | 5 | 10 | 1
3 | 1 | 10 | 12 | 1
4 | 1 | 11 | 11 | 1
5 | 1 | 6 | 8 | 1
6 | 1 | 5 | 7 | 1
7 | 1 | 8 | 6 | 1
8 | 2 | 7 | 6 | 1
9 | 2 | 8 | 7 | 1
10 | 2 | 5 | 8 | 1
11 | 2 | 6 | 9 | 1
12 | 2 | 9 | 15 | 1
13 | 2 | 12 | 13 | 1
14 | 2 | 11 | -1 | 0
(14 rows)
An example query using edge ids and vias:
SELECT * FROM pgr_trspViaEdges(
'SELECT id::INTEGER, source::INTEGER, target::INTEGER, cost,
reverse_cost FROM edge_table',
ARRAY[2,7,11]::INTEGER[],
ARRAY[0.5, 0.5, 0.5]::FLOAT[],
true,
true,
'SELECT to_cost, target_id::int4, FROM_edge ||
coalesce('',''||via_path,'''') AS via_path FROM restrictions');
seq | id1 | id2 | id3 | cost
-----+-----+-----+-----+------
1 | 1 | -1 | 2 | 0.5
2 | 1 | 2 | 4 | 1
3 | 1 | 5 | 8 | 1
4 | 1 | 6 | 9 | 1
5 | 1 | 9 | 16 | 1
6 | 1 | 4 | 3 | 1
7 | 1 | 3 | 5 | 1
8 | 1 | 6 | 8 | 1
9 | 1 | 5 | 7 | 1
10 | 2 | 5 | 8 | 1
11 | 2 | 6 | 9 | 1
12 | 2 | 9 | 16 | 1
13 | 2 | 4 | 3 | 1
14 | 2 | 3 | 5 | 1
15 | 2 | 6 | 11 | 0.5
(15 rows)
The queries use the Sample Data network.