CALT with turn restrictions enabled might fail to find optimal route

[aoles]

There are cases when CALT with turn restrictions doesn't find the optimal route in terms of the given weighting. Consider the following examples where the first route is returned by CALT and the second one by A* (forced by providing some polygons to avoid).

1. Berlin

CALT fails to find the faster and shorter route through a gas station ORS maps

2. Heidelberg

Faster route through a roundabout not found ORS maps

The problem seems to originate from the graph contraction which currently uses pure node-based approach without any additional adaptations accounting for turn restrictions. These seem to be necessary despite the fact that all nodes and edges involved in turn restriction relations are marked and included in the core. Apparently some modifications to the contraction procedure outside of the core are needed in order to allow the creation of some sort of "loop shortcuts". These are shortcuts which start and end at the same node but lead through different edges.

[sfendrich]

Berlin: The route through the gas station is tagged access=customers and should therefore not be used as a drive through shortcut. Heidelberg: Using an additional waypoint in the roundabout "Im Bieth", both variants take two minutes, so it might be a matter of seconds? Also I noticed that the roundabout is not tagged as roundabout in OSM and ORS incorrectly uses the same lane for both directions.

[HendrikLeuschner]

Here's an example where CALT uses a loop edge to circumvent a no left turn restriction directly after the turn from Berliner Straße. Heidelberg route Core-ALT

CH

[aoles]

Thanks for your feedback @sfendrich and @HendrikLeuschner.

The examples I've provided might not be entirely representative. My point was that there are cases when there is a difference between the route found by CALT and A* the former being always worse (I've updated my original comment). Have a look at the confluence page listing a few more real-life examples which came up during testing.

@HendrikLeuschner even though the route in your example makes a loop to bypass the turn restriction, I'm not sure there is actually any loop shortcut in play. AFAIK these are currently not created when contracting the graph.

It would be the best to come up with a toy graph example reproducing the issue, just haven't had the opportunity to look into it properly yet.

[aoles]

I've created a toy graph example which illustrates one of the possible problems. Consider the following graph. https://github.com/GIScience/openrouteservice/blob/dd54273b6041329b60b81608c4af70ce8832b265/openrouteservice/src/test/java/org/heigit/ors/util/ToyGraphCreationUtil.java#L354-L359 All edges are bidirectional and of length 1 except edge 3-6 which has length 9. Turn 1-2-5 is forbidden, but apart from that there are no further constrains or restrictions in the graph.

The test case is the shortest path from 0 to 6. Taking the turn restriction into account the expected path is 0-1-2-3-4-2-5-6 which is found by Dijkstra. CoreDijkstra, however, fails to find this looping path of length 7. Instead it takes the direct connection 3-6 resulting in a path of length 12.

[shivam2893]

Hi @aoles @HendrikLeuschner, we are facing this issue in an older version of ORS (6.6.1). May I know if this was fixed in a newer release or if you found out some information which might be helpful for anyone who comes across this issue in the future? Thanks in advance!

[aoles]

Thanks @shivam2893 for your feedback. Unfortunately, this issue has not been fixed yet. We hope to get back to it soon. In the meantime, it would be great if you could provide your failing example. Cheers!

[MichaelsJP]

Closing bc fixed. Both examples work now as expected.

[aoles]

Even if the examples seem to produce reasonable results, it's highly unlikely that the underlying issue has been actually addressed. Needs to be followed up, in particular with the unit test mentioned above.