search

Project-OSRM / osrm-backend

Open Source Routing Machine - C++ backend
http://map.project-osrm.org
BSD 2-Clause "Simplified" License
6.29k stars 3.32k forks source link

error with self-loops #2016

Open ivantrouvetout opened 8 years ago

ivantrouvetout commented 8 years ago

I think there is a problem with U-turns http://map.project-osrm.org/?z=18&center=46.301289%2C4.870076&loc=46.302107%2C4.869497&loc=46.301803%2C4.870875&loc=46.301892%2C4.870575&loc=46.300331%2C4.869229&hl=en&ly=&alt=&df=&srv=

MoKob commented 8 years ago

This is only partly related to u-turns. Since your query does not allow them at the intermediate vertices, the route is computed without u-turns at via nodes. However, the routing fails to find the (very long) loop in this case. I've updated the ticket accordingly.

MoKob commented 8 years ago

reopening as the basic problem is not yet fixed

TheMarex commented 8 years ago

Looking at the route again, I don't see a faster alternative. Was this fixed? As @MoKob already outlined this is the expected behavior as uturns in the middle of the street are not allowed.

MoKob commented 8 years ago

The route here is found randomly based on the contraction order. The general problem should still exist. I will have a look tomorrow and see whether I can find a reason that results in the omission of some required self-loops

MoKob commented 8 years ago

After some investigation we found the issue to be the following:

A prerequisite for this issue is the request of a route of the form s -- v -- t with v and t on the same segment (in the reported case, this was the two via-nodes, the final destination is not required to trigger it).

Next to this, the optimal path has to be a self-loop (required due to the forbidden u-turn in the middle of the street) -- that is it has to start and end at the same road segment.

OSRM assumes a self-loop to be only necessary for one-way streets or if the direct connection is slower than the loop around (think very slow forrest road, for example). In the described case, the forbidden u-turn translates the normal road into a implied oneway street. This results in the connection to be missed.

If, in addition, the street is higher up in the hierarchy than connecting other roads, we will not be able to find a path at all.

Potentially we could make sure to at least find a path if we allow u-turns with a very high penalty.

Due to the specific edge-case, we are postponing this issue to at least 5.1