Discussion on coding turn restrictions using Boost

[woodbri]

The current pgr_trsp function does not use Boost in its underlying implementation, in part because Boost Graph does not support it natively. There has been some discussion about re-implementing the pgr_trsp like functionality using Boost Graph. I'm opening this issue to collect ideas and references regarding this.

• http://lists.boost.org/boost-users/2011/11/71549.php
• https://lists.osgeo.org/pipermail/pgrouting-dev/2011-May/000208.html
• https://github.com/mixedbredie/itn-for-pgrouting (extracting turn-restrictions for OS data)
• https://github.com/Ifsttar/Tempus/blob/master/src/core/road_graph.hh (routing supporting turn restrictions)
• https://groups.google.com/forum/#!topic/opentripplanner-dev/hrsa7V0OSKY (interesting discussion)

There are also two terms that I have come across in this research "turn-penalties" and "turn-restrictions". An infinite penalty can be considered a restriction. From an implementation point of view having penalties is probably preferable because applying a penalty allows you more flexibility like applying a cost to making a turn or applying a greater cost to make a turn across traffic, or at traffic lights ot stop signs, etc.

In my mind "turn-restrictions" could be viewed as dynamic modification to the graph, based on the first link above this might be problematic, while changing the costs to a particular node based on the path to get there might be less problematic.

Please add additional useful comments and research.

[dkastl]

I like the term "turn-penalties".
Describing "restrictions" as a special case for "penalties" reminds me a bit how one-way restrictions are handled. While in the beginning we said, that you just need to make the cost "very high" to apply one-way restrictions, it still means, that the route might violate the rule, if there is no other way.

I prefer to use -1 however rather than using high costs, so I would also like to handle turn-restrictions/penalties in a similar way.

[cvvergara]

Family of functions:

using acronyms

TRSP

pgr_TRSP(one to one, one to many, many to one, many to many)
pgr_TRSPCost(one to one, one to many, many to one, many to many)
pgr_TRSPCostMatrix
pgr_TRSPDD(single start point, multiple start point)
pgr_TRSPKSP()
pgr_TRSPVIA()

TRSPWithPoints

pgr_TRSPWithPoints(one to one, one to many, many to one, many to many)
pgr_TRSPWithPointsCost(one to one, one to many, many to one, many to many)
pgr_TRSPWithPointsCostMatrix()
pgr_TRSPWithPointsDD(single start point, multiple start point)
pgr_TRSPWithPointsKSP()
pgr_TRSPWithPointsVIA()

Not using acronyms (this is my preference)

turnRestricted

pgr_turnRestricted(one to one, one to many, many to one, many to many)
pgr_turnRestrictedCost(one to one, one to many, many to one, many to many)
pgr_turnRestrictedCostMatrix
pgr_turnRestrictedDD(single start point, multiple start point)
pgr_turnRestrictedKSP()
pgr_turnRestrictedVIA()

turnRestrictedWithPoints

pgr_turnRestrictedWithPoints(one to one, one to many, many to one, many to many)
pgr_turnRestrictedWithPointsCost(one to one, one to many, many to one, many to many)
pgr_turnRestrictedWithPointsCostMatrix()
pgr_turnRestrictedWithPointsDD(single start point, multiple start point)
pgr_turnRestrictedWithPointsKSP()
pgr_turnRestrictedWithPointsVIA()

[woodbri]

On 7/8/2016 9:38 PM, Daniel Kastl wrote:

I like the term "turn-penalties".
Describing "restrictions" as a special case for "penalties" reminds me a
bit how one-way restrictions are handled. While in the beginning we
said, that you just need to make the cost "very high" to apply one-way
restrictions, it still means, that the route might violate the rule, if
there is no other way.

I prefer to use |-1| however rather than using high costs, so I would
also like to handle turn-restrictions/penalties in a similar way.

The issue here has more to do with how the code is implemented. We use
-1 to remove the edge but with turn restrictions it is potentially much
more complicated because the same edges need to be there for some paths
through the intersection and not for restricted paths.

So until we understand how we want to build the graph and process it and
what constraints that puts on the code it is hard to determine what is
possible. Anyway, I hear what you are asking for and tend to agree that
that should be the plan if we can make it work that way.

---

This email has been checked for viruses by Avast antivirus software.
https://www.avast.com/antivirus

[cvvergara]

-1 on the internal sql query cost & reverse_cost the corresponding (source, target), (target, source) edge is not inserted. (for one way)
Internally:
if the algorithm needs to remove it, it can be done.
if the algorithm needs to recover it, it can be done.
if the algorithm needs to change the value, it can be done.

[dkastl]

Don't take my comment as how you should implement it ;-)
I'm speaking from the user perspective and I find it better to assign -1 to apply a restriction than a very high cost. That's all. How this is applied internally is a different problem.

[cvvergara]

"no u-turn"
"no right turn"
"no left turn"

[cvvergara]

currently there is this way of representing "saving restrictions" in sample data

CREATE TABLE restrictions (
    rid BIGINT NOT NULL,
    to_cost FLOAT,
    target_id BIGINT,
    from_edge BIGINT,
    via_path TEXT
);

COPY restrictions (rid, to_cost, target_id, from_edge, via_path) FROM stdin WITH NULL '__NULL__' DELIMITER ',';
1,100,7,4,__NULL__
1,100,11,8,__NULL__
1,100,10,7,__NULL__
2,4,8,3,5
3,100,9,16,__NULL__
\.

and when passed as a parameter to pgr_TRSP

'SELECT to_cost, target_id,
        from_edge || coalesce('','' || via_path, '''') AS via_path
        FROM restrictions'

What would be the wish list for storing the restrictions so its easy to understand/use?
(I am asking for a wish list, so we can have options for analysis of pro & con)

[dkastl]

I would say:

• "no value" or 0 means no restriction and no penalty
• a value >0 would be a turn penalty
• -1 would be a turn restriction (prohibited)

Thoughts?

[cvvergara]

(rid, to_cost, target_id, from_edge, via_path)
(1, 0,7,4,NULL)
(1,100,7,4,NULL)
(1,-1,7,4,NULL)

(1, 0,7,4, {1,2,3}) <---
(1,100,7,4, {1,2,3})
(1,-1,7,4, {1,2,3})

this 7,4, {1,2,3} without looking at the documentation can you explain what it means?

[woodbri]

The definition of a restriction is:

• rid - unique id for restriction in table of restrictions
• to_cost - cost to be applied when the restriction is applied
• target_id - the id that we going to
• from_edge - the edge we are on when evaluating the target_id
• via_path - a comma separated list of ancestor edges to from_edge that the path came through

For simple restrictions, via_path is NULL as the whole restriction can be defined using target_id and from_edge. For more complex restrictions, you need to define a path of multiple edges that represent the restriction.

[woodbri]

We have the following pages in the wiki related to turn restrictions:

• https://github.com/pgRouting/pgrouting/wiki/Turn-Restricted-Shortest-Path-(TRSP)
• https://github.com/pgRouting/pgrouting/wiki/TRSP-Enhancements-Planning
• https://github.com/pgRouting/pgrouting/wiki/TRSP-for-railroads

Also the sample data was originally designed for test various simple and complex restrictions.

[woodbri]

Basically, our restriction model is identical to the OSM model:
http://wiki.openstreetmap.org/wiki/Relation:restriction

[woodbri]

Here are some references to various papers discussing turn restriction implementation:

• https://algo2.iti.kit.edu/download/turn_ch.pdf
• http://www.isprs.org/proceedings/XXXIV/part4/pdfpapers/410.pdf
• http://geo.fsv.cvut.cz/gdata/2013/pin2/d/dokumentace/line_graph_teorie.pdf

[cvvergara]

Here is the link of the current user's documentation:
http://docs.pgrouting.org/2.2/en/src/trsp/doc/pgr_trsp.html

[cvvergara]

@sankepallyrohithreddy
(rid, to_cost, target_id, from_edge, via_path)
(1, 0,7,4, {1,2,3}) <---
This:
7,4, {1,2,3}
With the detailed information given above, what do you think it means?

[woodbri]

I will leave the explaination to @sankepallyrohithreddy but will note that for this restriction:

(1, 0,7,4, {1,2,3}) <---

that regardless of the meaning, that the "effect" will be nothing because even if the restriction is triggered, the 0 cost would be the same as if it were not triggered.

[rohithsankepally]

Upon reading through, what I understand is

• from_edge -> the id of the edge we are on
• target_id -> the id of the edge which we want to go
• via_path -> sequence of edge ids
• the_cost -> the cost applied we want to reach the target_id from the from_edge given that we have reached the from_edge along via_path

please correct me if I am wrong.

[woodbri]

@sankepallyrohithreddy so what is the path that is being restricted? ie: what is the sequence of edge ids in the path that is the restriction?

[cvvergara]

I'll rephrase the question. for the current implementation what is the meaning of all of this:
(rid, to_cost, target_id, from_edge, via_path)
(1, 100,7,4, {1,2,3})

[cvvergara]

@sankepallyrohithreddy
can you draw, how the restricted path looks?

[rohithsankepally]

I think I misunderstood the definiton of via_edges. I think it is a sequence of edges which connects the from_edge and the target_edge. I would like to explain the following restriction
(rid, to_cost, target_id, from_edge, via_path)
(2, 4, 8, 3, {5} )
which is one of the restrictions mentioned in the documentation.

from_edge: v4-----e3------>v3
target_id: v6------e8------>v5, v5------e8------>v6
via_path: v3------e5----->v6

So now when we want to reach from v4 to v5 through the via_path the to_cost applied would be 4.

please correct me if I am wrong.

[cvvergara]

(rid, to_cost, target_id, from_edge, via_path)
(2, 4, 8, 3, {5} )
id of the restriction is: 2
cost is: 4
target_id is: 8 <<-- documentation is not clear if its a node or an edge
This table has to be used with:
'SELECT to_cost, target_id, from_edge ||
coalesce('',''||via_path,'''') AS via_path FROM restrictions');
so
3, 5 and 5 are edges ids

so the restriction is you want to go to 8 via 3 and 5.
I would understand that
e3->e5->8 where 8 is not clear if its a vertex or and edge

[cvvergara]

(rid, to_cost, target_id, from_edge, via_path)
(1, 100,7,4, {1,2,3})
I understand that
e4->e1->e2->e3->7

[woodbri]

Here is an interesting ticket from OSRM regarding restrictions and CH.
Project-OSRM/osrm-backend#2681