OSRM drives past a waypoint and reaches it after a U-turn

[asaveljevs]

Consider the following example with a starting point, an intermediate point, and an end point:

It can be seen that OSRM first drives past the gray waypoint, makes a U-turn, and only then arrives at the gray marker.

Of course, it does not make a difference on the overall trip length, but it would be expected to arrive at the gray marker on the first occasion, before the U-turn.

Would that classify as a bug, a feature request or there is some rationale behind it?

[danpat]

You can change this behaviour by adding the continue_straight=false parameter to the API request - it defaults to true, which leads to the behaviour you're seeing (not doing u-turns at the waypoint itself).

The behaviour you're seeing is intended.

[asaveljevs]

Yes, we are aware of the continue_straight=false parameter. However, that parameter does not have to do with the issue described here, because we do not wish to do U-turns at waypoints.

If we look closely at the picture on the right-hand side, we can see that "Make a U-turn" comes before "You have arrived at your destination, on the left". That is, it first drives past the waypoint, makes a U-turn, and then stops at the waypoint.

Our question is that an alternative expected behavior would be to first stop at the waypoint, then continue straight, make a U-turn, and then continue on to the red marker. In other words, the expected instructions for the gray marker would be "You have arrived at your destination, on the right" first and then "Make a U-turn".

[danpat]

Oh, I see, sorry I misunderstood.

Take a look at the approaches= parameter - if you use this, you can force the route to approach your waypoint on the curb side (i.e. don't require crossing the road to visit it).

[asaveljevs]

Yes, the approaches parameter works. For instance, using approaches=curb:

Or, using approaches=opposite with our implementation of #5616 (implemented just the functionality without documentation or tests, so not submitting a pull request at this point):

However, our real question is about the default approaches=unrestricted parameter in the initial issue description. Why does it choose the longer route to the gray waypoint? Is it possible to make it prefer the shorter route, because it may not be always possible to know the approach side in advance?

[danpat]

As long as continue_straight=true, then you'll find that both routes:

• A->B->uturn->C
• A->uturn->B->C

are actually identical duration and distance-wise - which one you get is randomly determined by the order of edges in the graph (which ones get found first). They are otherwise equivalent, so whichever is discovered first by the routing algorithm will be returned. It should be consistent for a dataset, but if you regenerate your routing data, it might flip.

In your current data, it's longer to get from the startpoint to the waypoint, but shorter from the waypoint to the destination. The alternative is that it's shorter from the startpoint to the waypoint, but longer from the waypoint to the destination. The approaches and continue_straight behaviours determine which solution you prefer, otherwise it's a tie (both routes are equivalent) and randomly selected.

[asaveljevs]

OK, so let me try to paraphrase that. When we make a single request with five points A-B-C-D-E, it optimizes the route between A and E, ensuring that we visit B, C, D in sequence.

This is in contrast to and better than making four separate requests A-B, B-C, C-D, D-E, where in the next request we start in the direction of the arrival in the previous request (e.g., the result of A-B request says that we arrive at B on the curb side, so in the B-C request we also make it start on the curb side).

The reason making a single request with five points is better than making four separate requests is not just about efficiency, but also because four separate requests may yield a longer route from A to E (e.g., the result of A-B request says that we arrive at B on the curb side, but then driving to C from the curb of B gives a much larger total distance than if we would arrive at B on the opposite side).

Or, in other words, it is wrong to think that a single request A-B-C-D-E first optimizes the route A-B, then B-C, then C-D, and finally D-E. Rather, it optimizes the trip from A to E.

Is this understanding correct?

[danpat]

You can simplify your thinking here a bit I think:

• OSRM finds the shortest path that visits a list of waypoints, considering constraints you've supplied (approaches and continue_straight).

The loop that actually implements this can be found here - it's a dynamic programming approach that finds the shortest overall path:

https://github.com/Project-OSRM/osrm-backend/blob/82b5648c97edf1d2edec7aecebc35aa8a8033c82/include/engine/routing_algorithms/shortest_path_impl.hpp#L266

In your case, as I pointed out, both paths are the same in terms of time/distance, so whether you do a u-turn before the waypoint or not is randomly decided.

[asaveljevs]

Thank you for your prompt answers! It became much more clear for us now.