TRSP for railroads - pgRouting/pgrouting GitHub Wiki

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

trsp_network

Example with version 3.4

Create database with tables network and restrictions

-- 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)                                                                                         
;

Insert sample network

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 cost is the same as reverse_cost.
  • The cost of the links is their length.

Insert network restrictions

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 2 and Node 3.
  • Turn restrictions apply in both directions:
    • Edge 2 <-> Edge 7
    • Edge 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.

Sample Queries

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.

WITHOUT restrictions

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

WITH restrictions

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

Example with versions < 3.4

Create database with tables network and restrictions

-- 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
);

Insert sample network

-- 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 cost is the same as reverse_cost.
  • The cost of the links is their length.

Insert network restrictions

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 2 and Node 3.
  • Turn restrictions apply in both directions:
    • Edge 2 <-> Edge 7
    • Edge 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.

Sample Queries

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.

WITHOUT restrictions

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)

WITH restrictions

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'
        );