TRSP Enhancements Planning - pgRouting/pgrouting GitHub Wiki

This document is to capture plans and ideas and document changes to the TRSP code. Currently we have some changes from Roni that provide code to build the graph once and then solve multiple routes within that graph. The code currently only supports this for node input and not edge input. Using this code we can build interfaces to more efficiently solve routes with via points, IE: A-B-C-D-..., and routes based on one-to-many, IE: A-B, A-C, A-D, ..., and many-to-many solutions like filling out a distance matrix.

One of the biggest concerns here is how to define and structure the API and the resulting SQL functions so that we have something that is consistent and easy to use.

There has also been a request from the list to consolidate the various Dijkstra shortest path functions to use one code base. While I think this has merit, I should be potentially trivial to do after these proposed changes get put in place. These could be mapped like this:

  • pgr_dijkstra() -> pgr_trsp() based one nodes
  • pgr_kdijkstra() -> pgr_trsp() based on one-to-many
  • pgr_makeDistanceMatric() -> pgr_trsp() based on many-to-many

So my thoughts on the new trsp api would look something like:

pgr_trsp(edgesForGraph text, nodes int[], restrictions text, has_rcost boolean, directed boolean, mode int)
pgr_trsp(edgesForGraph text, edges int[], epos float[], restrictions text, has_rcost boolean, directed boolean, mode int)

where:

  • edgesForGraph is the SQL to select the edges needed to build the graph

  • nodes is an array of node ids

  • edges is an array of edge ids

  • epos is an array of positions (0.0 .. 1.0) corresponding to the edges

  • restrictions is the SQL to select the turn restrictions or NULL

  • has_rcost indicates if edgesForGraph has reverse_cost column

  • directed indicates if the graph is directed or undirected

  • mode is a flag to indicate how to use the input data

    mode description
    1 point to point, A-B-C-D-...
    2 one to many, A-B, A-C, A-D, ...
    3 many to many, a distance matrix

Existing Functions

pgr_trsp(text, integer, integer, boolean, boolean)
-- node to node

pgr_trsp(text, integer, integer, boolean, boolean, text)
-- node to node with restrictions

pgr_trsp(text, integer, double precision, integer, double precision, boolean, boolean)
-- edge to edge

pgr_trsp(text, integer, double precision, integer, double precision, boolean, boolean, text)
-- edge to edge with restrictions

pgr_trsp(text, integer[], boolean, boolean, text)
-- array of nodes **this gets changed to use new code (1)**

pgr_trsp(text, integer[], float8[], boolean, boolean, text)
-- array of edges **this gets changed to use new code (2)**

  1. should plug directly into your code. I currently do this in C by calling your old code multiple times, but it will be more efficient to change this to call multi_dijkstra because we only build the graph once.

  2. currently this is done in C by making multiple calls to the old code. The multi_dijkstra only accepts nodes, not edges, so we'll need to look at making a version that can be called by edges.

I think I would like to add a new argument to (1) and (2) above "boolean onetomany" and if it is true then we compute A-B, A-C, A-D, ... and if it is false it will compute A-B-C-...

Roni says: "You must be careful when implementing multi_dijkstra with edges. Because the algorithm creates pseudo-nodes at the starting and ending point, We must track the pseudo-nodes carefully. Also there may be critical cases like all the points lie on a single feature/ link. This get complicated when the link is directed. So I think, first complete the node based multi_dijkstra and onetomany_dijkstra and after completing that start to look at the one with edges. I mean do them in separate milestone."