search

Project-OSRM / osrm-backend

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

Incorrect route calculation #633

Closed MaartenDeen closed 11 years ago

MaartenDeen commented 11 years ago

Have a look a these two routes: http://osrm.at/3hX and http://osrm.at/3hY

The second has the destination set slightly lower and then the route calculation gives a long detour via Piracanjuba. Why?

I have uploaded screenshots of the two routes.

3hx 3hy

erickdeoliveiraleal commented 11 years ago

I think I got a misrouting here too: osrm.at/3iF

MaartenDeen commented 11 years ago

I see nothing wrong in that route. But my two routes are now correct too. I am curious what change was made. It is strange that the time via the detour is the same as the direct route. So for some reason the routing engine thinks it can go (a lot) faster on primary and secondary roads than on motorways. 40km extra took no time extra. The direct route is between the two junctions is 17 minutes, with the detour it's 57 km, that would make 201 km/h average.

erickdeoliveiraleal commented 11 years ago

My route are fine now too, someone has changed something on the algorythm.

2013/5/21 MaartenDeen notifications@github.com

I see nothing wrong in that route. But my two routes are now correct too. I am curious what change was made. It is strange that the time via the detour is the same as the direct route. So for some reason the routing engine thinks it can go (a lot) faster on primary and secondary roads than on motorways. 40km extra took no time extra. The direct route is between the two junctions is 17 minutes, with the detour it's 57 km, that would make 201 km/h average.

— Reply to this email directly or view it on GitHubhttps://github.com/DennisOSRM/Project-OSRM/issues/633#issuecomment-18191630 .

MaartenDeen commented 11 years ago

That's why a screenshot is helpful. Last time I reported something like this I did not include the screenshot and then when the problem corrected itself the issue was closed with a comment that there was no problem.

emiltin commented 11 years ago

it's more likely that the data changed, than the code. but the bug might still be in the code.

emiltin commented 11 years ago

perhaps it would be possible to investigate how the data for the area changed?

MaartenDeen commented 11 years ago

I would be interested to know what kind of data problem would trigger this error. To make it clear: the route is correct when the destination is at A on a way, but if you move the destination a few 100 meters further on the same way, the route changes in a different area. Also take into account that the traveltime is supposed to be the same but the distance is a lot more. That is no data error, that is a routing error.

Anyway, I downloaded the area between minlat='-17.4332003' minlon='-49.2963409' maxlat='-17.1539129' maxlon='-48.9935303' and the newest item there is from may 10th and that is a relation. Ways and nodes are january 2013 and older. So no changes in the data in that area.

DennisOSRM commented 11 years ago

The algorithm did not change. OSRM is optimizing someting like expected travel time and if two paths have equal travel time, then either is chosen. This is not error from a routing point of view, just not what you expected.

tyrasd commented 11 years ago

Actually, there is an error: OSRM produced the wrong travel time for the detour via Pircanjuba. http://osrm.at/3ju is 2 h 7 min now (seems reasonable), but was 1 h 29 min 3 days ago. (And neither the data nor the algorithm changed in the meantime.)

MaartenDeen commented 11 years ago

I was just typing the same as tyrasd.

When you limit the route from junction to junction (where it branches off in the second screenshot) you currently get 26.8 km 17 min direkt and 56.4 km 55 min via Piracanjuba.

Please explain how OSRM can make an optimization with expected travel time enabling it to cut the expected traveltime to a third. If this is an algorithm that is conciously put in then it is clearly malfunctioning. Obviously algorithms do not work like we humans think, but it has to be clear too that a route 3 times longer in distance over lesser roads can never be similar in time than a direct route via a motorway.

DennisOSRM commented 11 years ago

Perhaps something with the underlying data feed on the server went wrong. Cannot reproduce the error, though. Feel free to reopen the ticket if the error reoccurs.

MaartenDeen commented 11 years ago

The problem I have now is the same as with issue #409. If you wait long enough it will go away. At least I made screenshots so that it is clear now that there is a bug.

And again: this can not be a data problem. As I stated before and as you can see in the screenshots: the route is correct when you go to point A, it changes to incorrect when you move the destination to point B and the area where the fault occurs has nothing to do with the destination. Also supported by the fact that the travel time on the incorrect route is suspiciously low. NOFI, but you are closing your eyes for a clear bug. I do agree though that it might be hard to pinpoint the bug, especially when it does not occur consistently.

tyrasd commented 11 years ago

Issue 311 sounds also very familiar.

Quoting Dennis:

The problem has been identified and fixed. It has been caused by a broken planet.osm.pbf file that was updated with osmosis.

DennisOSRM commented 11 years ago

As I said before, it may have been an issue with the update feed.

MaartenDeen commented 11 years ago

Please explain how that can cause the effect that a very high average speed is calculated and that a route to point A is correct but when the route passes point A and terminates at point B it is incorrect. It is not a problem of being unable to route over the correct way, the first example disproves that theory. It is not a problem of being unable to route from A to B because the second example disproves that theory.

Of course an update can make certain ways disappear, but I can not see how that is the case. Moreover: there were no changes in this area. The last change to any object (a relation) was 9 days before I made the route (I don't know what the update frequency of OSRM is) and the last change to other objects was 5 months ago.

DennisOSRM commented 11 years ago

I can only speculate at this point, but it looks like the planet file may have been in an inconsistent state.

MaartenDeen commented 11 years ago

That does not explain anything.

tyrasd commented 11 years ago

@DennisOSRM: as you can see, people really care about this issue(s)... So, can you please be more verbose in your comments? It doesn't really help when you close issues early only because you don't know the exact source of the bugs.

Ontopic: Would it make sense to implement some kind of consistency check for the base data?

ZupoLlask commented 11 years ago

Bump!

Can someone help us with this? This is a serious issue that must be sorted out but we need some developer to guide us so we can contribute for the solution!

emiltin commented 11 years ago

if someone can write a failing cucumber test, that would be a big step towards solving this: https://github.com/DennisOSRM/Project-OSRM/wiki/Cucumber-Test-Suite

DennisOSRM commented 11 years ago

Indeed, it would be of great help