Route calculation is dependant on route changes in unrelated area

[MaartenDeen]

I apologise for the maybe cryptic subject. I am noticing a change in the route calculation in unrelated areas when you change the parameters of the route in other areas.
Consider these two routes (screenshots are also attached):

1. http://www.osrm.at/bDs

2. http://www.osrm.at/bDt

3. is the route that osrm calculates without intermediate points and takes a shortest path in the village Lierop. For 2) I added an intermediate point in an area that is not related to the route in the village (it is not on a track that should be affected by the new point) and the new route calculates a different route in the village Lierop which is about 500 meter longer.
   Looking at the speed information from the point of change, 1) is about 340 meters @ 30 km/h, 2) is about 145 m @ 50 km/h and 680 m @ 30 km/h. This can never be a faster route.

Why does the route calculation change when I put an intermediate point in a non-related area?

[danpat]

Possibly related test case. Here, the intermediate marker is moved around a corner that is on the path in both cases. In the second case, the routing seems reasonable, in the first case, the routing does a complete lap of the block to arrive at the point.

[woodbri]

Please supply links from the [Generate Link] link so we can have a link example of these last two. Thanks.

[danpat]

Here you go:

http://osrm.at/bOG
http://osrm.at/bOF

[danpat]

Here's a minimal case from the original report. By moving the intermediate marker slightly, the route changes in unexpected ways.

I loaded a 10x10km OSM extract for this region of the Netherlands into a local OSRM install, and I can't reproduce the problem based on HEAD from master. If I place markers in the same spots, the routing does not jump around like it does on http://map.project-osrm.org/.

http://osrm.at/bPo

http://osrm.at/bPp

[danpat]

While I can't reproduce it in master, it is reproducable in develop as of 61dca4a

[danpat]

Looks like this behaviour appeared in 11c6713

[danpat]

Reversing the route often does not produce the same path, even when there are no one-way streets involved. Examples above demonstrate this behaviour.

[TheMarex]

Seems related to #1474 Can also reproduce this with develop.

[TheMarex]

@danpat just double checked: Reverting that commit fixes this problem. Awesome work tracking that down! Going to cross verify with the other issues that have cropped up.

[emiltin]

the branch fix/looping contains a failing cucumber test. it's a small extract of a location in copenhagen. to run:
cuke -p all features/testbot/bugs.feature:8

there are two wrong cases:

http://map.project-osrm.org/?hl=en&loc=55.664913,12.601698&loc=55.665016,12.602199&loc=55.665302,12.603515&z=18&center=55.664711,12.602324&alt=0&df=0&re=0&ly=-1171809665

http://map.project-osrm.org/?hl=en&loc=55.664913,12.601698&loc=55.664948,12.601887&loc=55.665302,12.603515&z=18&center=55.664711,12.602324&alt=0&df=0&re=0&ly=-1171809665

[TheMarex]

Just reverted 11c6713 on develop tomorrow we will see if that fixes the problems that have cropped up recently. Still this code has bugs that need to be fixed.

[woodbri]

I just built and tested develop and it fixed this case:
http://map.project-osrm.org/?hl=en&loc=-34.86688,-56.20764&loc=-34.86639,-56.20818&loc=-34.86563,-56.20894

[woodbri]

My example above is working correctly now on map.project-osrm.org.

[TheMarex]

This was fixed by #1503