TRSP for railroads
The following example assumes a railroad network with switches, which don't allow turns for the pointed angle. To take this into account turn restrictions are needed, which are supported by TRSP algorithm.
- Sample Network
- Example with version 3.4 Verbatim of original example but with pgRouting v3.4
- Example with versions < 3.4 Original example
-- Create network table
CREATE TABLE network (
id serial,
source integer,
target integer,
cost double precision,
reverse_cost double precision,
x1 double precision,
y1 double precision,
x2 double precision,
y2 double precision,
the_geom geometry
);
-- Create restrictions table
CREATE TABLE restrictions (
id serial,
cost FLOAT,
path BIGINT[]
);
-- Populate network table
INSERT INTO network (x1,y1,x2,y2) VALUES
(0,0,1,0),(1,0,4,0),(4,0,5,0),(5,0,5,5),(5,5,0,5),(0,5,0,0),
(1,0,2,1),(2,1,3,1),(3,1,4,0)
;
UPDATE network SET the_geom = ST_makeline(ST_point(x1,y1),ST_point(x2,y2));
UPDATE network SET cost = ST_length(the_geom), reverse_cost = ST_length(the_geom);
SELECT pgr_createTopology('network',0.001)
- Trains can move in both directions, so
costis the same asreverse_cost. - The
costof the links is their length.
INSERT INTO restrictions (cost, path)
VALUES (100,ARRAY[9,2]),(100,ARRAY[2,9]),(100,ARRAY[7,2]),(100, ARRAY[2,7]);
- Restrictions apply for the pointed angles at
Node 2andNode 3. - Turn restrictions apply in both directions:
Edge 2 <-> Edge 7Edge 2 <-> Edge 7
- The cost for restrictions is set to
100, so the algorithm will avoid these turns if there is any other route possible.
The following queries always use the directed network flag set to true and use the reverse_cost column for the cost in the opposite direction. In our sample data cost == reverse_cost.
SELECT *
FROM pgr_dijkstra(
'SELECT * FROM network',
4, 1
);
First we route from Node 4 to Node 1 without restrictions, which returns the shortest path 4 -> 3 -> 2 -> 1.
seq | path_seq | node | edge | cost | agg_cost
-----+----------+------+------+------+----------
1 | 1 | 4 | 3 | 1 | 0
2 | 2 | 3 | 2 | 3 | 1
3 | 3 | 2 | 1 | 1 | 4
4 | 4 | 1 | -1 | 0 | 5
(4 rows)
If we want to start/end between two nodes, we can use the TRSP like this:
SELECT *
FROM pgr_withPoints(
$$SELECT id, source, target, cost, reverse_cost FROM network$$,
$$SELECT * FROM (VALUES (1, 2, 0.75),(2, 8, 0.5)) AS t(pid, edge_id, fraction)$$,
-1, -2,
details => false);
Now we start at 75% of Edge 2 and in the middle of Edge 8:
seq | path_seq | node | edge | cost | agg_cost
-----+----------+------+------+--------------------+-------------------
1 | 1 | -1 | 2 | 0.75 | 0
2 | 2 | 3 | 9 | 1.4142135623730951 | 0.75
3 | 3 | 8 | 8 | 0.5 | 2.164213562373095
4 | 4 | -2 | -1 | 0 | 2.664213562373095
(4 rows)
No restrictions are applied in this query, so the route makes a sharp turn at Node 3
To prevent sharp turns at switches we need to make use of the restrictions from the restrictions table:
id | cost | path
----+------+-------
1 | 100 | {9,2}
2 | 100 | {2,9}
3 | 100 | {7,2}
4 | 100 | {2,7}
(4 rows)
The restrictions are loaded as the second function argument providing an SQL SELECT statement:
SELECT *
FROM pgr_trsp_withPoints(
$$SELECT id, source, target, cost, reverse_cost FROM network$$,
$$SELECT * FROM restrictions$$,
$$SELECT * FROM (VALUES (1, 2, 0.75),(2, 8, 0.5)) AS t(pid, edge_id, fraction)$$,
-1, -2
);
The resulting path now does not turn sharply, but instead takes the long way through Nodes 3 -> 4 -> 5 -> 6 -> 1 -> 2 -> 7.
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+--------------------+--------------------
1 | 1 | -1 | -2 | -1 | 2 | 0.75 | 0
2 | 2 | -1 | -2 | 3 | 3 | 1 | 0.75
3 | 3 | -1 | -2 | 4 | 4 | 5 | 1.75
4 | 4 | -1 | -2 | 5 | 5 | 5 | 6.75
5 | 5 | -1 | -2 | 6 | 6 | 5 | 11.75
6 | 6 | -1 | -2 | 1 | 1 | 1 | 16.75
7 | 7 | -1 | -2 | 2 | 7 | 1.4142135623730958 | 17.75
8 | 8 | -1 | -2 | 7 | 8 | 0.5 | 19.164213562373096
9 | 9 | -1 | -2 | -2 | -1 | 0 | 19.664213562373096
(9 rows)
Note: No need of coalesce
-- Add postgis and pgrouting
CREATE EXTENSION postgis;
CREATE EXTENSION pgrouting;
-- Create network table
CREATE TABLE network (
id serial,
source integer,
target integer,
cost double precision,
reverse_cost double precision,
x1 double precision,
y1 double precision,
x2 double precision,
y2 double precision,
the_geom geometry
);
-- Create restrictions table
CREATE TABLE restrictions (
rid serial,
to_cost double precision,
to_edge integer,
from_edge integer,
via text
);
-- Populate network table
INSERT INTO network (x1,y1,x2,y2) VALUES
(0,0,1,0),(1,0,4,0),(4,0,5,0),(5,0,5,5),(5,5,0,5),(0,5,0,0),
(1,0,2,1),(2,1,3,1),(3,1,4,0)
;
UPDATE network SET the_geom = ST_makeline(ST_point(x1,y1),ST_point(x2,y2));
UPDATE network SET cost = ST_length(the_geom), reverse_cost = ST_length(the_geom);
SELECT pgr_createTopology('network',0.001);
- Trains can move in both directions, so
costis the same asreverse_cost. - The
costof the links is their length.
INSERT INTO restrictions (to_cost,to_edge,from_edge) VALUES
(100,9,2),(100,2,9),(100,7,2),(100,2,7);
- Restrictions apply for the pointed angles at
Node 2andNode 3. - Turn restrictions apply in both directions:
Edge 2 <-> Edge 7Edge 2 <-> Edge 7
- The cost for restrictions is set to
100, so the algorithm will avoid these turns if there is any other route possible.
The following queries always use the directed network flag set to true and use the reverse_cost column for the cost in the opposite direction. In our sample data cost == reverse_cost.
SELECT seq, id1 AS node, id2 AS edge, cost
FROM pgr_trsp(
'SELECT id, source, target, cost::float, reverse_cost::float FROM network',
4, 1, true, true
);
First we route from Node 4 to Node 1 without restrictions, which returns the shortest path 4 -> 3 -> 2 -> 1.
seq | node | edge | cost
-----+------+------+------
0 | 4 | 3 | 1
1 | 3 | 2 | 3
2 | 2 | 1 | 1
3 | 1 | -1 | 0
(4 rows)
If we want to start/end between two nodes, we can use the TRSP like this:
SELECT seq, id1 AS node, id2 AS edge, cost
FROM pgr_trsp(
'SELECT id, source, target, cost::float, reverse_cost::float FROM network',
2, 0.75, 8, 0.5, true, true
);
Now we start at 75% of Edge 2 and in the middle of Edge 8:
SELECT seq, id1 AS node, id2 AS edge, cost
FROM pgr_trsp(
'SELECT id, source, target, cost::float, reverse_cost::float FROM network',
2, 0.75, 8, 0.5, true, true
);
No restrictions are applied in this query, so the route makes a sharp turn at Node 3
seq | node | edge | cost
-----+------+------+------------------
0 | -1 | 2 | 0.75
1 | 3 | 9 | 1.41421356237309
2 | 8 | 8 | 0.5
(3 rows)
To prevent sharp turns at switches we need to make use of the restrictions from the restrictions table:
rid | to_cost | to_edge | from_edge | via
-----+---------+---------+-----------+-----
1 | 100 | 9 | 2 |
2 | 100 | 2 | 9 |
3 | 100 | 7 | 2 |
4 | 100 | 2 | 7 |
(4 rows)
The restrictions are loaded as the last function argument providing an SQL SELECT statement:
SELECT seq, id1 AS node, id2 AS edge, cost
FROM pgr_trsp(
'SELECT id, source, target, cost::float, reverse_cost::float FROM network',
2, 0.75, 8, 0.5, true, true,
'SELECT to_cost, to_edge AS target_id, from_edge || coalesce('','' || via, '''') AS via_path FROM restrictions'
);
The resulting path now does not turn sharply, but instead takes the long way through Nodes 3 -> 4 -> 5 -> 6 -> 1 -> 2 -> 7.
seq | node | edge | cost
-----+------+------+-----------------
0 | -1 | 2 | 0.75
1 | 3 | 3 | 1
2 | 4 | 4 | 5
3 | 5 | 5 | 5
4 | 6 | 6 | 5
5 | 1 | 1 | 1
6 | 2 | 7 | 1.4142135623731
7 | 7 | 8 | 0.5
(8 rows)
Note: from_edge || coalesce('','' || via, '''') AS via_path takes into account complex turn restrictions. If restrictions only contain "sharp turns at switches", then the query can be shortened to:
SELECT seq, id1 AS node, id2 AS edge, cost
FROM pgr_trsp(
'SELECT id, source, target, cost::float, reverse_cost::float FROM network',
2, 0.75, 8, 0.5, true, true,
'SELECT to_cost, to_edge AS target_id, from_edge::text AS via_path FROM restrictions'
);
