Default value of strict in pgr_dijkstraTRSP

[vidhan13j07]

I am adding a strict parameter to pgr_dijkstraTRSP.

Suppose that all possible routes from the given source and destination passes through a restriction.
false: when all paths found use a restriction, put the shortest one
true: EMPTY SET when all paths found use a restriction
What is better as default value true or false for strict?

[woodbri]

I think strict should default to true. The reason being is that if I provide a restriction table, then I expect it to be honored and I don't want the code to silently ignore the the restrictions in some cases. It is one thing if I'm interactively running a query and a notice is presented to me that I can read, but more users will integrate pgRouting into things like web services where there is only code and no human eyes other than the web user seeing results. If the route fails in that case then the web user needs to complain to the developer that there is a problem so the developer can then look into whether it is a data problem or an algorithm problem.

I'm not sure I would include the strict option at all as I think it should always be strict, but it might be a useful debugging tool. If I don't care about restrictions, then it is easy enough to not pass in the restriction table.

In the big picture, I believe the value of TRSP is to provide real world routes that people can drive. Think Google or OSRM driving directions. We need good routes that can turned into driving directions in the future.

[dkastl]

I agree with Steve. If there is no valid route, then there is no route ;-)
I don't see right now, how "not strict" would help users, because if you run TRSP with restrictions configured, then you want them applied.

However, there should be a way to run TRSP with no restrictions, but then a user knows this.

What would be use cases for a strict parameter? Maybe I just didn't see them.

[cvvergara]

Case Here:
https://github.com/pgRouting/pgrouting/wiki/TRSP-for-railroads

I quote

The cost for restrictions is set to 100, so the algorithm will avoid these turns if there is any other route possible.

I understand that: if there is no other route possible, the algorithm will use the restriction

[cvvergara]

Other case:

#491

@woodbri expects results with a cost because the returned route uses a restriction.
In other words, the algorithm did not find a route that does not use restrictions, but its returning a route.

[cvvergara]

About:

However, there should be a way to run TRSP with no restrictions, but then a user knows this.

Then the user might want to use pgr_dijkstra or pgr_withPoints or pgr_aStar or pgr_bdAstar or pgr_bdDijkstra they don't have turn restrictions.

I must say that @vidhan13j07 is considering the case when the restrictions query returns an empty set.
I quote him (have to use my memory, too much conversation on gitter to find the exact words):

Maybe the restrictions selection is based on a bounding box and so happens that the selected bounding box returns no restriction.

[cvvergara]

btw, the name he is using is pgr_dijkstraTRSP maybe to open doors in the future: where maybe there can be a pgr_astarTRSP

[dkastl]

Can we first define, what we understand, when we say restriction?

It seems you thought of restrictions with some sort of "cost penalty", so the algorithm would only consider such a turn, when there is no other "cheaper" way. This is how we would apply costs to edges, that we try to avoid.

Or, we see restrictions as "not possible", such as no bicycles on highways (at least where I live) or one-way streets. In pgRouting we can just exclude them, when we select the network data (works for highways for example) or we can set costs very high (which is probably similar to the strict = false issue), or in case of one-way restrictions pgRouting handles that correctly.

I think it would be good to support both:

• turn maneuvers with "restrictions" (like the railways example)
• turn maneuvers with "cost penalties" (like avoiding u-turns)

Maybe we the word "restrictions" was confusing, because you think of "strictly forbidden".
Eventually the word "(turn) maneuvers" is better.

[vidhan13j07]

If we want to include turn costs along with the turn restrictions, another alternative approach could be to include cost column in the restriction table for each turn. In case of restriction, this value can be -1 or infinity.

[woodbri]

I agree with @dkastl the there needs to be come clarification about restrictions vs turn costs. I view restrictions as absolute, but costs as being allowed. If the cost is say -1, then this should be considered an absolute restriction, but a cost of 100 would just add 100 to the cost of the the route taking that turn path. I still do not see a valid need for a strict option.

[dkastl]

@vidhan13j07 this sounds like a good approach, if we follow the way one-way restrictions are handled. So -1 would be a restriction and any other value would be a cost (=penalty).

[dkastl]

Re-STRICT-ions ... as the word says ;-)

[woodbri]

@vidhan13j07 +1 I agree with the -1 as restriction or cost (=penalty)

[dkastl]

Shall we somewhere (also in the documentation) define the terminology?
I would like to go with this:

• maneuver (what we called so far "turn restriction")
• restriction (maneuver is not possible, so -1)
• penalty (maneuver requires additional cost)

[rohithsankepally]

Re-STRICT-ions ... as the word says

There is no need for a penalty, the algorithm he intends to implement does not use any kind of cost, its simply forbidden.

He is clear mentioning what may be called a corner case:

all possible routes from the given source and destination passes through a restriction

I took the liberty of putting the word all in bold.

which means that he intends to find a path that does not use a (manouver) restriction, and preferable to be the shortest.

In the case that there is no such path he is suggesting the strict parameter to give the user the option to tell the algorithm, to return a path or not to return a path on that corner case.

In case of being "strict", no path is returned in the corner case.
In case of being "not strict" and all paths pass thru a restriction, to return the one that has less number of restrictions used (and maybe an extra column to indicate where are the restriction(s) being used

[rohithsankepally]

I give a +1 to make strict to be true.

[dkastl]

@sankepallyrohithreddy, if it's like you explain and penalty costs care not used but only restrictions, then my (and probably Steve's) position is, that the result should be empty.

It makes no sense to me to apply restrictions and then return a result, that actually violates a restriction.

Second argument:
You say "all possible routes from the given source and destination passes through a restriction".
Are you going to test then for this case in the algorithm? What if all possible routes can passe more than one restriction?

I think it is going to become hard to define, possible to become a source for bugs.
Why not just leave it out for now, create an issue, that describes a possible improvement, and see, if anyone needs this feature.

[cvvergara]

It makes no sense to me to apply restrictions and then return a result, that actually violates a restriction.

To me it makes sense:

I am an ambulance I need to reach my destination or my patient dies.

1. Suppose that there exists a path: (not the corner case)
   Time to load a graph + time to calculate the shortest path that does not use the "subpaths" considered restrictions
   get result, OK, path I get to my destination without causing much distress to the traffic.

2. Suppose that there does not exists a path: (the corner case)
   Time to load a graph + time to calculate the shortest path that does not use the "subpaths" considered restrictions
   get result, its EMPTY SET
   Use pgr_dijkstra to get a path:
   time to load graph again + time to calculate the path
   get a route, maybe its the shortest one but it will pass at least through one restriction and maybe more.

3. Suppose that there does not exists a path (the corner case) but there is this strict flag: strict = false
   Time to load a graph + time to calculate the shortest path that does not use the "subpaths" considered restrictions
   get result a result, its a path, with restrictions, but minimal amount of "subpaths" that are considered restrictions.

Third case: no need to load twice the graph, gets a route that has the minimal amount of restrictions.

[cvvergara]

Answering to this:

I agree with @dkastl the there needs to be come clarification about restrictions vs turn costs. I view restrictions as absolute, but costs as being allowed.

You can review all of our gitter conversation, there is no mention about "turn cost" so I think you are the ones to explain to him, and to me, what you mean with "turn cost".
From the sample data

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

INSERT INTO restrictions (rid, to_cost, target_id, from_edge, via_path) VALUES
(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 its used like this:

SELECT * FROM pgr_trsp(
        'SELECT id::INTEGER, source::INTEGER, target::INTEGER, cost FROM edge_table',
        2, 7, false, false,
        'SELECT to_cost, target_id::int4,
        from_edge || coalesce('','' || via_path, '''') AS via_path
        FROM restrictions'
    );
 seq | id1 | id2 | cost 
-----+-----+-----+------
   0 |   2 |   4 |    1
   1 |   5 |  10 |    1
   2 |  10 |  12 |    1
   3 |  11 |  11 |    1
   4 |   6 |   8 |    1
   5 |   5 |   7 |    1
   6 |   8 |   6 |    1
   7 |   7 |  -1 |    0
(8 rows)

[cvvergara]

Please tell me more about the "turn cost" there is no such thing in osm restrictions
http://wiki.openstreetmap.org/wiki/Relation:restriction

[cvvergara]

About:

turn maneuvers with "cost penalties" (like avoiding u-turns)

he is not doing a "Via" version, he is doing a one to one version. And using dijkstra underneath, which by does not do a U turn (go and comeback using the same edge)

[vidhan13j07]

I really appreciate all of your comments.
After reading and reviewing the links that you kindly gave for me to take a decision, I am going to base my decision in the following:
from @woodbri comment:

I think strict should default to true. The reason being is that if I provide a restriction table, then I expect it to be honored and I don't want the code to silently ignore the the restrictions in some cases.

from @dkastl comment

Re-STRICT-ions ... as the word says ;-)

From @sankepallyrohithreddy comment

I give a +1 to make strict to be true.

without forgetting @sankepallyrohithreddy suggestion

and maybe an extra column to indicate where are the restriction(s) being used

I am making strict parameter to be true.

Current pgtap unit tests:

• using the default (strict := true)
  https://github.com/vidhan13j07/pgrouting/blob/gsoc/rewritetrsp/src/dijkstraTRSP/test/pgtap/empty_set_default_strict.sql
• using the explicit value (strict := false)
  https://github.com/vidhan13j07/pgrouting/blob/gsoc/rewritetrsp/src/dijkstraTRSP/test/pgtap/empty_set_NO_default_strict.sql

The both files tests pass on travis

[dkastl]

@cvvergara I will try to concentrate on the case "restricted", so no cost penalty just the case maneuver is allowed or not allowed, "yes" or "no".

For the strict=false mode, tell me, if the following is correct:

1. It's a "corner case". So in reality it will probably not happen (often).
2. The convenience is, that you don't need to make another query without restrictions, if the first query returned no result.
   (So in your case with the ambulance the "die or not die" example, we help to save the time of 1 extra query ;-) )

That said, what does it mean to us in terms of "work":

• Additional tests
• Additional documentation
• More source code to maintain

And all we gain is saving an additional query for a corner case, that in normal scenarios will not happen.

You see, I'm not convinced ;-)

Furthermore, with the introduction of a strict mode for convenience, the question is, why we don't implement this also for pgr_dijkstra and others in case of one-way streets?
What if the algorithm doesn't find a route, because the only possible path is one-way in the opposite direction?

In my opinion the advantage of saving a query in a very rare case isn't really worth it.
If I had to write an application for an ambulance service, I would fully ignore restrictions, if ambulances don't need to follow those rules.

[woodbri]

The case of an ambulance or other special vehicle is a vehicle class problem and should be handled by the user's input. This problem refers to the fact that different classes of vehicles have different restrictions that apply. The user needs to supply the appropriate set of restrictions for that vehicle class that it is routing. Lets say you have a no right turn restriction and you allow the ambulance to violate it, but the reason for the restriction is that there are concrete barriers preventing the turn. There are restrictions for logical reasons, legal reasons, physical reasons and restrictions by vehicle class like emergency, regular, over-sized, delivery, etc. Some data sets differentiate these and some do not. We should not make assumptions about them in the code. It is the users responsibility to select which apply for any given query.

While OSM may not include "turn costs", it is convenient to build this into the code so that you can say there is additional cost for following a path thru a restriction. This can be used to penalize access to toll roads, to adding costs for making left hand turns in a right side drive county, or penalizing sharp turns for tractor tailor rigs, etc. It adds no more complexity to the code than adding strict=false except that you are only allowed to take a "restricted" path that has a cost greater then 0. A -1 cost would still be forbidden.

[cvvergara]

His question is not about "how the restrictions table looks like" or what "should or should not have the restrictions table" for other topics not being "strict" parameter default value, please open a new issue.

I will close this issue, because from all our comments he took a decision about the default value he will be using.

[robe2]

I guess I'm late for this discussion. I would go with default strict = true

I agree with @cvvergara that in some cases like ambulance driving you are allowed to violate restrictions but still want to violate the least to prevent accidents.

[woodbri]

Reopened. This is a discussion and it is not clear what if any decisions have been made regarding these topics. @vidhan13j07 should summarize and close when he is comfortable that he has the answers he needs and summarize that.

[woodbri]

@robe2 strict=true is a bad way to deal with this case. read discussion about vehicle classes. You would not want to route a vehicle thru a restriction that had a physical barrier like concrete Jersey barriers and if you routed it that way and the drive followed that path, then the recovery route might be much longer than the alternative.

[cvvergara]

@woodbri
where is the discussion about vehicle classes?

[woodbri]

The case of an ambulance or other special vehicle is a vehicle class problem and should be handled by the user's input. This problem refers to the fact that different classes of vehicles have different restrictions that apply. The user needs to supply the appropriate set of restrictions for that vehicle class that it is routing. Lets say you have a no right turn restriction and you allow the ambulance to violate it, but the reason for the restriction is that there are concrete barriers preventing the turn. There are restrictions for logical reasons, legal reasons, physical reasons and restrictions by vehicle class like emergency, regular, over-sized, delivery, etc. Some data sets differentiate these and some do not. We should not make assumptions about them in the code. It is the users responsibility to select which apply for any given query.

[woodbri]

Copied from above.

[cvvergara]

Marking as invalid as the flag is not used on the new
pgr_trsp function.
And there is no such function pgr_dijkstraTRSP

[cvvergara]

Work has been done for TRSP on develop branch for version 3.4 (due to be released on September/October 2022:
#2238
Please check the documentation
https://docs.pgrouting.org/dev/en/TRSP-family.html
and the migration guide:
https://docs.pgrouting.org/dev/en/trsp_migration.html

For further similar problems with TRSP functions please open a new issue with the specific function name.