Grade separation routing using pgRouting

Question

I am using pgRouting version 2.6.

I am creating a routing topology from a subset of lion data https://www1.nyc.gov/site/planning/data-maps/open-data/dwn-lion.page

I have gone through the process of setting up the network and I am able to do some basic shortest path routing using the pgr_dijkstra function.

However I am running into the routing issue of overpasses/bridges/tunnels where the network is not aware of the grade separations or heights of the roads that are intersecting. As a few resources on the web have mentioned this issue

• How to create a routable road network from Ordnance Survey data?
• Create a network topology for pgrouting with grade separation
• https://github.com/mixedbredie/highways-for-pgrouting

These questions and answers have helped me contextualize my problem but the solutions they came up with do no really apply to the dataset I am using.

I have already figured out the logic on what I need to do but I do not know how to implement it into either the network topology creation or the routing functions

Example

WITH
dijkstra AS (
    SELECT  *
      FROM pgr_dijkstra('SELECT id, source, target, cost_drive AS cost, rcost_drive as reverse_cost 
                         FROM edges where driveable = true',
           getnearestnode(40.5993439,-74.0642904),
           getnearestnode(40.71204,-73.9616284),
           --getnearestnode(40.7059044,-74.0078728),
           directed := TRUE)
           )
    SELECT *
    FROM dijkstra left JOIN edges ON (edge = id)
    ORDER BY seq

The query above routes from Staten Island to Williamsburg BK and for the most part it does a good job accurately finding the route however in the picture below the route is on the BQE and then makes an impossible left turn onto Borinquen Place.

I have been able to identify when a turn or route should not be allowed.

In the data there are two columns that deal with gradient. nodelevelf (Level code indicator vertical topology at the start of the street segment. goes from A-Z where z is the highest level) and nodelevelt (Level code indicator vertical topology at the end of the street segment. goes from A-Z where z is the highest level)

Two segments should ONLY be routed together if the nodelevelt of the 1st segment equals the nodelevelf of the 2nd segment.

In the above example the BQE segment (highlighted in red) has a gradient of I for both its nodelevelf and nodelevelt and the next segment which is a left turn onto Borinquen Place has a nodelevelf and nodelevelt of M which is a level higher than the previous BQE segment. This should not happen.

How do I implement such a rule in the routing?

Things I have tried:

1. pre-processing the data to merge streets with similar attributes but this creates multilinestrings which does not work in the pgrouting functions
2. run the above SQL query to generate the route then identify the wrong turn link and delete that node from the vertices table (abandoned that idea once other routes were not working because of it)

Answer 1

I think this is a super fun problem you are working on and I did have an idea although it may not be what you are looking for.

Essentially, I think you need to pre-process the data for speed (so the route can create relatively quickly). Now, you tried to combine like-data but I think you're right that that is the wrong route (haha). If I had this dataset, I would append a column to it which holds a list of possibilities. Essentially, each segment checks every segment it intersects and only adds an intersected segment if it has the same nodelevelf value as the master segment (that which is being compared). This logic gate should allow each segment to hold a small dictionary of segments it can turn onto if the routing suggests. You could also speed this pre-processing up by creating some sort of r-tree or association to see if two segments are already related, they do not need to be compared again (although, in real life, it is possible to make a turn from A --> B and not B--> A) but the nodelevelf variable does not account for that.

A problem you may need to think about is directionality and side but these could be thought about after you test and see if this works. The side issue will come up first. Each segment has two nodes on either side of it and this dictionary will have to have a list in each. So side 0 can turn onto segments (a,b,c) but side 1 can only turn onto segments (a,c).

Once the data is pre-processed, you will just need to add logic to the routing which does the following:

1. Route starts to create
2. When a turn is indicated as needed, the corresponding segments need to be related to each other (a turn from A to B means B needs to be in A's dictionary)
3. If related, continue with route. If not-related, find alternate route from this segment towards end-goal (i.e. take the shortest path if segment B did not exist)
4. Continue with route until next route and repeat