pgr_trsp - Turn Restriction Shortest Path (TRSP)

pgr_trsp — Returns the shortest path with support for turn restrictions.

Availability

  • Version 2.1.0

    • New Via prototypes

      • pgr_trspViaVertices

      • pgr_trspViaEdges

  • Version 2.0.0

    • Official function

Description

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 (seq, id1, id2, cost) or (seq, id1, id2, id3, cost) rows, that make up a path.

pgr_trsp(sql text, source integer, target integer,
                  directed boolean, has_rcost boolean [,restrict_sql text]);
RETURNS SETOF (seq, id1, id2, cost)
pgr_trsp(sql text, source_edge integer, source_pos float8,
                      target_edge integer, target_pos float8,
                  directed boolean, has_rcost boolean [,restrict_sql text]);
RETURNS SETOF (seq, id1, id2, cost)
pgr_trspViaVertices(sql text, vids integer[],
                  directed boolean, has_rcost boolean
                  [, turn_restrict_sql text]);
RETURNS SETOF (seq, id1, id2, id3, cost)
pgr_trspViaEdges(sql text, eids integer[], pcts float8[],
                  directed boolean, has_rcost boolean
                  [, turn_restrict_sql text]);
RETURNS SETOF (seq, id1, id2, id3, cost)

The main characteristics are:

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
id:

int4 identifier of the edge

source:

int4 identifier of the source vertex

target:

int4 identifier of the target vertex

cost:

float8 value, of the edge traversal cost. A negative cost will prevent the edge from being inserted in the graph.

reverse_cost:

(optional) the cost for the reverse traversal of the edge. This is only used when the directed and has_rcost parameters are true (see the above remark about negative costs).

source:

int4 NODE id of the start point

target:

int4 NODE id of the end point

directed:

true if the graph is directed

has_rcost:

if true, the reverse_cost column of the SQL generated set of rows will be used for the cost of the traversal of the edge in the opposite direction.

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
to_cost:

float8 turn restriction cost

target_id:

int4 target id

via_path:

text comma separated list of edges in the reverse order of rule

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:

seq:

row sequence

id1:

node ID

id2:

edge ID (-1 for the last row)

cost:

cost to traverse from id1 using id2

Support for Vias

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
id:

int4 identifier of the edge

source:

int4 identifier of the source vertex

target:

int4 identifier of the target vertex

cost:

float8 value, of the edge traversal cost. A negative cost will prevent the edge from being inserted in the graph.

reverse_cost:

(optional) the cost for the reverse traversal of the edge. This is only used when the directed and has_rcost parameters are true (see the above remark about negative costs).

vids:

int4[] An ordered array of NODE id the path will go through from start to end.

directed:

true if the graph is directed

has_rcost:

if true, the reverse_cost column of the SQL generated set of rows will be used for the cost of the traversal of the edge in the opposite direction.

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
to_cost:

float8 turn restriction cost

target_id:

int4 target id

via_path:

text commar separated list of edges in the reverse order of rule

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:

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

Additional Examples

Example:

Without turn restrictions

    SELECT * FROM pgr_trsp(
        'SELECT id::INTEGER, source::INTEGER, target::INTEGER, cost FROM edges',
        1, 17, false, false
    );
 seq | id1 | id2 | cost
-----+-----+-----+------
   0 |   1 |   6 |    1
   1 |   3 |   7 |    1
   2 |   7 |   8 |    1
   3 |  11 |   9 |    1
   4 |  16 |  15 |    1
   5 |  17 |  -1 |    0
(6 rows)

Example:

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 edges',
        6, 1, false, false,
        'SELECT to_cost, target_id::int4,
        from_edge || coalesce('','' || via_path, '''') AS via_path
        FROM restrictions'
    );
 seq | id1 | id2 | cost
-----+-----+-----+------
   0 |   6 |   4 |    1
   1 |   7 |  10 |    1
   2 |   8 |  12 |    1
   3 |  12 |  11 |    1
   4 |  11 |   8 |    1
   5 |   7 |   7 |    1
   6 |   3 |   6 |    1
   7 |   1 |  -1 |    0
(8 rows)

SELECT * FROM pgr_trsp(
        'SELECT id::INTEGER, source::INTEGER, target::INTEGER, cost FROM edges',
        1, 12, false, false,
        'SELECT to_cost, target_id::int4,
        from_edge || coalesce('','' || via_path, '''') AS via_path
        FROM restrictions'
    );
 seq | id1 | id2 | cost
-----+-----+-----+------
   0 |   1 |   6 |    1
   1 |   3 |   7 |    1
   2 |   7 |   8 |    1
   3 |  11 |   9 |    1
   4 |  16 |  15 |    1
   5 |  17 |  13 |    1
   6 |  12 |  -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 edges',
        ARRAY[6,1,12]::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 |   6 |   4 |    1
   2 |   1 |   7 |  10 |    1
   3 |   1 |   8 |  12 |    1
   4 |   1 |  12 |  11 |    1
   5 |   1 |  11 |   8 |    1
   6 |   1 |   7 |   7 |    1
   7 |   1 |   3 |   6 |    1
   8 |   2 |   1 |   6 |    1
   9 |   2 |   3 |   7 |    1
  10 |   2 |   7 |   8 |    1
  11 |   2 |  11 |   9 |    1
  12 |   2 |  16 |  15 |    1
  13 |   2 |  17 |  13 |    1
  14 |   2 |  12 |  -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 edges',
        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 |   6 |   4 |    1
   3 |   1 |   7 |   8 |    1
   4 |   1 |  11 |   9 |    1
   5 |   1 |  16 |  16 |    1
   6 |   1 |  15 |   3 |    1
   7 |   1 |  10 |   5 |    1
   8 |   1 |  11 |   8 |    1
   9 |   1 |   7 |   7 |    1
  10 |   2 |   7 |   8 |    1
  11 |   2 |  11 |   9 |    1
  12 |   2 |  16 |  16 |    1
  13 |   2 |  15 |   3 |    1
  14 |   2 |  10 |   5 |    1
  15 |   2 |  11 |  11 |  0.5
(15 rows)

The queries use the Sample Data network.

Known Issues

Introduction

pgr_trsp code has issues that are not being fixed yet, but as time passes and new functionality is added to pgRouting with wrappers to hide the issues, not to fix them.

For clarity on the queries:

  • _pgr_trsp (internal_function) is the original code

  • pgr_trsp (lower case) represents the wrapper calling the original code

  • pgr_TRSP (upper case) represents the wrapper calling the replacement function, depending on the function, it can be:

    • pgr_dijkstra

    • pgr_dijkstraVia

    • pgr_withPoints

    • _pgr_withPointsVia (internal function)

The restrictions

The restriction used in the examples does not have to do anything with the graph:

  • No vertex has id: 25, 32 or 33

  • No edge has id: 25, 32 or 33

A restriction is assigned as:

SELECT 100::float AS to_cost, 25::INTEGER AS target_id, '32, 33'::TEXT AS via_path;
 to_cost | target_id | via_path
---------+-----------+----------
     100 |        25 | 32, 33
(1 row)

The back end code has that same restriction as follows

SELECT 1 AS id, 100::float AS cost, 25::INTEGER AS target_id, ARRAY[33, 32, 25] AS path;
 id | cost | target_id |    path
----+------+-----------+------------
  1 |  100 |        25 | {33,32,25}
(1 row)

therefore the shortest path expected are as if there was no restriction involved

The “Vertices” signature version

pgr_trsp(sql text, source integer, target integer,
         directed boolean, has_rcost boolean [,restrict_sql text]);

1 Different ways to represent ‘no path found`

  • Sometimes represents with EMPTY SET a no path found

  • Sometimes represents with Error a no path found

Returning EMPTY SET to represent no path found

SELECT * FROM pgr_trsp(
    $$SELECT id::INTEGER, source::INTEGER, target::INTEGER, cost, reverse_cost  FROM edges$$,
    7, 4, true, true
);
 seq | id1 | id2 | cost
-----+-----+-----+------
(0 rows)

pgr_trsp calls pgr_dijkstra when there are no restrictions which returns EMPTY SET when a path is not found

SELECT * FROM pgr_dijkstra(
    $$SELECT id::INTEGER, source::INTEGER, target::INTEGER, cost, reverse_cost  FROM edges$$,
    7, 4
);
 seq | path_seq | node | edge | cost | agg_cost
-----+----------+------+------+------+----------
(0 rows)

Throwing EXCEPTION to represent no path found

SELECT * FROM pgr_trsp(
     $$SELECT id::INTEGER, source::INTEGER, target::INTEGER, cost, reverse_cost  FROM edges$$,
     7, 4, true, true,
     $$SELECT 100::float AS to_cost, 25::INTEGER AS target_id, '32, 33'::TEXT AS via_path$$
);
ERROR:  Error computing path: Path Not Found
CONTEXT:  PL/pgSQL function pgr_trsp(text,integer,integer,boolean,boolean,text) line 53 at RAISE

pgr_trsp use the original code when there are restrictions, even if they have nothing to do with the graph, which will throw an EXCEPTION to represent no path found.

1 Routing from/to same location

When routing from location \(1\) to the same location \(1\), no path is needed to reach the destination, its already there. Therefore is expected to return an EMPTY SET or an EXCEPTION depending on the parameters

  • Sometimes represents with EMPTY SET no path found (expected)

  • Sometimes represents with EXCEPTION no path found (expected)

  • Sometimes finds a path (not expected)

Returning expected EMPTY SET to represent no path found

SELECT * FROM pgr_trsp(
    $$SELECT id::INTEGER, source::INTEGER, target::INTEGER, cost, reverse_cost FROM edges$$,
    7, 7,  true, true
);
 seq | id1 | id2 | cost
-----+-----+-----+------
(0 rows)

pgr_trsp calls pgr_dijkstra when there are no restrictions which returns the expected to return EMPTY SET to represent no path found.

Returning expected EXCEPTION to represent no path found

SELECT * FROM pgr_trsp(
    $$SELECT id::INTEGER, source::INTEGER, target::INTEGER, cost, reverse_cost FROM edges$$,
    2, 2, true, true,
    $$SELECT 100::float AS to_cost, 25::INTEGER AS target_id, '32, 33'::TEXT AS via_path$$
);
ERROR:  Error computing path: Path Not Found
CONTEXT:  PL/pgSQL function pgr_trsp(text,integer,integer,boolean,boolean,text) line 53 at RAISE

In this case pgr_trsp calls the original code when there are restrictions, even if they have nothing to do with the graph, in this case that code throws the expected EXCEPTION

Returning unexpected path

SELECT * FROM pgr_trsp(
    $$SELECT id::INTEGER, source::INTEGER, target::INTEGER, cost, reverse_cost FROM edges$$,
    5, 5, true, true,
    $$SELECT 100::float AS to_cost, 25::INTEGER AS target_id, '32, 33'::TEXT AS via_path$$
);
 seq | id1 | id2 | cost
-----+-----+-----+------
   0 |   5 |   1 |    1
   1 |   6 |   4 |    1
   2 |   7 |   8 |    1
   3 |  11 |   9 |    1
   4 |  16 |  16 |    1
   5 |  15 |   3 |    1
   6 |  10 |   2 |    1
   7 |   6 |   1 |    1
   8 |   5 |  -1 |    0
(9 rows)

In this case pgr_trsp calls the original code when there are restrictions, even if they have nothing to do with the graph, in this case that code finds an unexpected path.

1 User contradictions

pgr_trsp unlike other pgRouting functions does not autodectect the existence of reverse_cost column. Therefor it has has_rcost parameter to check the existence of reverse_cost column. Contradictions happen:

  • When the reverse_cost is missing, and the flag has_rcost is set to true

  • When the reverse_cost exists, and the flag has_rcost is set to false

When the reverse_cost is missing, and the flag has_rcost is set to true.

SELECT * FROM pgr_trsp(
    $$SELECT id::INTEGER, source::INTEGER, target::INTEGER, cost FROM edges$$,
    6, 10, false, true,
    $$SELECT 100::float AS to_cost, 25::INTEGER AS target_id, '32, 33'::TEXT AS via_path$$
);
ERROR:  Error, reverse_cost is used, but query did't return 'reverse_cost' column
CONTEXT:  PL/pgSQL function pgr_trsp(text,integer,integer,boolean,boolean,text) line 24 at RAISE

An EXCEPTION is thrown.

When the reverse_cost exists, and the flag has_rcost is set to false

SELECT * FROM pgr_trsp(
    $$SELECT id::INTEGER, source::INTEGER, target::INTEGER, cost, reverse_cost FROM edges$$,
    6, 10, false, false,
    $$SELECT 100::float AS to_cost, 25::INTEGER AS target_id, '32, 33'::TEXT AS via_path$$
);
 seq | id1 | id2 | cost
-----+-----+-----+------
   0 |   6 |   4 |    1
   1 |   7 |   8 |    1
   2 |  11 |   5 |    1
   3 |  10 |  -1 |    0
(4 rows)

The reverse_cost column will be effectively removed and will cost execution time

The “Edges” signature version

pgr_trsp(sql text, source_edge integer, source_pos float8,
         target_edge integer, target_pos float8,
         directed boolean, has_rcost boolean [,restrict_sql text]);

2 Different ways to represent ‘no path found`

  • Sometimes represents with EMPTY SET a no path found

  • Sometimes represents with EXCEPTION a no path found

Returning EMPTY SET to represent no path found

SELECT * FROM pgr_trsp(
    $$SELECT id::INTEGER, source::INTEGER, target::INTEGER, cost, reverse_cost  FROM edges$$,
    1, 0.5, 17, 0.5, true, true
);
 seq | id1 | id2 | cost
-----+-----+-----+------
(0 rows)

pgr_trsp calls pgr_withPoints - Proposed when there are no restrictions which returns EMPTY SET when a path is not found

Throwing EXCEPTION to represent no path found

SELECT * FROM _pgr_trsp(
    $$SELECT id::INTEGER, source::INTEGER, target::INTEGER, cost, reverse_cost  FROM edges$$,
    1, 0.5, 17, 0.5, true, true,
    $$SELECT 100::float AS to_cost, 25::INTEGER AS target_id, '32, 33'::TEXT AS via_path$$
);
ERROR:  Error computing path: Path Not Found

pgr_trsp use the original code when there are restrictions, even if they have nothing to do with the graph, which will throw an EXCEPTION to represent no path found.

Paths with equal number of vertices and edges

A path is made of N vertices and N - 1 edges.

  • Sometimes returns N vertices and N - 1 edges.

  • Sometimes returns N - 1 vertices and N - 1 edges.

Returning N vertices and N - 1 edges.

SELECT * FROM pgr_TRSP(
    $$SELECT id::INTEGER, source::INTEGER, target::INTEGER, cost, reverse_cost  FROM edges$$,
    1, 0.5, 1, 0.8, true, true
);
 seq | id1 | id2 | cost
-----+-----+-----+------
   0 |  -1 |   1 |  0.3
   1 |  -2 |  -1 |    0
(2 rows)

pgr_trsp calls pgr_withPoints - Proposed when there are no restrictions which returns the correct number of rows that will include all the vertices. The last row will have a -1 on the edge column to indicate the edge number is invalidu for that row.

Returning N - 1 vertices and N - 1 edges.

SELECT * FROM pgr_TRSP(
    $$SELECT id::INTEGER, source::INTEGER, target::INTEGER, cost, reverse_cost  FROM edges$$,
    1, 0.5, 1, 0.8, true, true,
    $$SELECT 100::float AS to_cost, 25::INTEGER AS target_id, '32, 33'::TEXT AS via_path$$
);
 seq | id1 | id2 | cost
-----+-----+-----+------
   0 |  -1 |   1 |  0.3
(1 row)

pgr_trsp use the original code when there are restrictions, even if they have nothing to do with the graph, and will not return the last vertex of the path.

2 Routing from/to same location

When routing from the same edge and position to the same edge and position, no path is needed to reach the destination, its already there. Therefore is expected to return an EMPTY SET or an EXCEPTION depending on the parameters, non of which is happening.

A path with 2 vertices and edge cost 0

SELECT * FROM pgr_TRSP(
    $$SELECT id::INTEGER, source::INTEGER, target::INTEGER, cost, reverse_cost  FROM edges$$,
    1, 0.5, 1, 0.5, true, true
);
 seq | id1 | id2 | cost
-----+-----+-----+------
   0 |  -1 |   1 |    0
   1 |  -2 |  -1 |    0
(2 rows)

pgr_trsp calls pgr_withPoints - Proposed setting the first \((edge, position)\) with a differenct point id from the second \((edge, position)\) making them different points. But the cost using the edge, is \(0\).

A path with 1 vertices and edge cost 0

SELECT * FROM pgr_TRSP(
    $$SELECT id::INTEGER, source::INTEGER, target::INTEGER, cost, reverse_cost  FROM edges$$,
    1, 0.5, 1, 0.5, true, true,
    $$SELECT 100::float AS to_cost, 25::INTEGER AS target_id, '32, 33'::TEXT AS via_path$$
);
 seq | id1 | id2 | cost
-----+-----+-----+------
   0 |  -1 |   1 |    0
(1 row)

pgr_trsp use the original code when there are restrictions, even if they have nothing to do with the graph, and will not have the row for the vertex \(-2\).

2 User contradictions

pgr_trsp unlike other pgRouting functions does not autodectect the existence of reverse_cost column. Therefor it has has_rcost parameter to check the existence of reverse_cost column. Contradictions happen:

  • When the reverse_cost is missing, and the flag has_rcost is set to true

  • When the reverse_cost exists, and the flag has_rcost is set to false

When the reverse_cost is missing, and the flag has_rcost is set to true.

SELECT * FROM pgr_trsp(
    $$SELECT id::INTEGER, source::INTEGER, target::INTEGER, cost FROM edges$$,
    1, 0.5, 1, 0.8, false, true,
    $$SELECT 100::float AS to_cost, 25::INTEGER AS target_id, '32, 33'::TEXT AS via_path$$
);
ERROR:  Error, reverse_cost is used, but query did't return 'reverse_cost' column
CONTEXT:  PL/pgSQL function pgr_trsp(text,integer,double precision,integer,double precision,boolean,boolean,text) line 36 at RAISE

An EXCEPTION is thrown.

When the reverse_cost exists, and the flag has_rcost is set to false

SELECT * FROM pgr_trsp(
    $$SELECT id::INTEGER, source::INTEGER, target::INTEGER, cost, reverse_cost FROM edges$$,
    1, 0.5, 1, 0.8, false, false,
    $$SELECT 100::float AS to_cost, 25::INTEGER AS target_id, '32, 33'::TEXT AS via_path$$
);
 seq | id1 | id2 | cost
-----+-----+-----+------
   0 |  -1 |   1 |  0.3
(1 row)

The reverse_cost column will be effectively removed and will cost execution time

Using a points of interest table

Given a set of points of interest:


SELECT * FROM pointsOfInterest;
 pid |  x  |  y  | edge_id | side | fraction |                    geom                    |                  newpoint
-----+-----+-----+---------+------+----------+--------------------------------------------+--------------------------------------------
   1 | 1.8 | 0.4 |       1 | l    |      0.4 | 0101000000CDCCCCCCCCCCFC3F9A9999999999D93F | 010100000000000000000000409A9999999999D93F
   2 | 4.2 | 2.4 |      15 | r    |      0.4 | 0101000000CDCCCCCCCCCC10403333333333330340 | 010100000000000000000010403333333333330340
   3 | 2.6 | 3.2 |      12 | l    |      0.6 | 0101000000CDCCCCCCCCCC04409A99999999990940 | 0101000000CDCCCCCCCCCC04400000000000000840
   4 | 0.3 | 1.8 |       6 | r    |      0.3 | 0101000000333333333333D33FCDCCCCCCCCCCFC3F | 0101000000333333333333D33F0000000000000040
   5 | 2.9 | 1.8 |       5 | l    |      0.8 | 01010000003333333333330740CDCCCCCCCCCCFC3F | 01010000000000000000000840CDCCCCCCCCCCFC3F
   6 | 2.2 | 1.7 |       4 | b    |      0.7 | 01010000009A99999999990140333333333333FB3F | 01010000000000000000000040333333333333FB3F
(6 rows)

Using pgr_trsp

SELECT * FROM pgr_TRSP(
    $$SELECT id::INTEGER, source::INTEGER, target::INTEGER, cost, reverse_cost  FROM edges$$,
    (SELECT edge_id::INTEGER  FROM pointsOfInterest WHERE pid = 1),
    (SELECT fraction  FROM pointsOfInterest WHERE pid = 1),
    (SELECT edge_id::INTEGER  FROM pointsOfInterest WHERE pid = 6),
    (SELECT fraction  FROM pointsOfInterest WHERE pid = 6),
    true, true,
    $$SELECT 100::float AS to_cost, 25::INTEGER AS target_id, '32, 33'::TEXT AS via_path$$
);
 seq | id1 | id2 | cost
-----+-----+-----+------
   0 |  -1 |   1 |  0.6
   1 |   6 |   4 |  0.7
(2 rows)

On pgr_trsp, to be able to use the table information:

  • Each parameter has to be extracted explicitly from the table

  • Regardles of the point pid original value

    • will always be -1 for the first point

    • will always be -2 for the second point

      • the row reaching point -2 will not be shown

Using pgr_withPoints - Proposed

SELECT * FROM pgr_withPoints(
    $$SELECT id::INTEGER, source::INTEGER, target::INTEGER, cost, reverse_cost  FROM edges$$,
    $$SELECT pid, edge_id, fraction FROM pointsOfInterest$$,
    -1, -6
);
 seq | path_seq | node | edge | cost | agg_cost
-----+----------+------+------+------+----------
   1 |        1 |   -1 |    1 |  0.6 |        0
   2 |        2 |    6 |    4 |  0.7 |      0.6
   3 |        3 |   -6 |   -1 |    0 |      1.3
(3 rows)

Suggestion: use pgr_withPoints - Proposed when there are no turn restrictions:

  • Results are more complete

  • Column names are meaningful

Routing from a vertex to a point

Solving a shortest path from vertex \(6\) to pid 1 using a points of interest table

Using pgr_trsp

SELECT * FROM pgr_trsp(
    $$SELECT id::INTEGER, source::INTEGER, target::INTEGER, cost, reverse_cost FROM edges$$,
    8, 1,
    (SELECT edge_id::INTEGER  FROM pointsOfInterest WHERE pid = 1),
    (SELECT fraction  FROM pointsOfInterest WHERE pid = 1),
    true, true,
    $$SELECT 100::float AS to_cost, 25::INTEGER AS target_id, '32, 33'::TEXT AS via_path$$
);
 seq | id1 | id2 | cost
-----+-----+-----+------
   0 |  11 |   8 |    1
   1 |   7 |   4 |    1
   2 |   6 |   1 |  0.6
(3 rows)

  • Vertex 6 is on edge 8 at 1 fraction

SELECT * FROM pgr_trsp(
    $$SELECT id::INTEGER, source::INTEGER, target::INTEGER, cost, reverse_cost FROM edges$$,
    11, 0,
    (SELECT edge_id::INTEGER  FROM pointsOfInterest WHERE pid = 1),
    (SELECT fraction  FROM pointsOfInterest WHERE pid = 1),
    true, true,
    $$SELECT 100::float AS to_cost, 25::INTEGER AS target_id, '32, 33'::TEXT AS via_path$$
);
 seq | id1 | id2 | cost
-----+-----+-----+------
   0 |  11 |   8 |    1
   1 |   7 |   4 |    1
   2 |   6 |   1 |  0.6
(3 rows)

  • Vertex 6 is also edge 11 at 0 fraction

Using pgr_withPoints - Proposed

SELECT * FROM pgr_withPoints(
    $$SELECT id::INTEGER, source::INTEGER, target::INTEGER, cost, reverse_cost  FROM edges$$,
    $$SELECT pid, edge_id, fraction FROM pointsOfInterest$$,
    11, -1
);
 seq | path_seq | node | edge | cost | agg_cost
-----+----------+------+------+------+----------
   1 |        1 |   11 |    8 |    1 |        0
   2 |        2 |    7 |    4 |    1 |        1
   3 |        3 |    6 |    1 |  0.6 |        2
   4 |        4 |   -1 |   -1 |    0 |      2.6
(4 rows)

Suggestion: use pgr_withPoints - Proposed when there are no turn restrictions:

  • No need to choose where the vertex is located.

  • Results are more complete

  • Column names are meaningful

prototypes

pgr_trspViaVertices and pgr_trspViaEdges were added to pgRouting as prototypes

These functions use the pgr_trsp functions inheriting all the problems mentioned above. When there are no restrictions and have a routing “via” problem with vertices:

See Also

Indices and tables