Difference in distance when using route and table

[rgugliel]

Hi, I'm playing a bit with the table service and the distance it can now return (thanks for that, it is awesome!).

I noticed that there exists pairs of coordinates that are such that the distance returned by the table service is different that the one returned by the route service although the durations are the same.

As an example, I took the Lyon map (http://download.bbbike.org/osm/bbbike/Lyon/), and ran the following two queries on a local instance:

curl "http://localhost:5051/route/v1/driving/4.827889,45.759704;4.842888,45.755310"
curl "http://localhost:5051/table/v1/driving/4.827889,45.759704;4.842888,45.755310?sources=0&destinations=1&annotations=distance,duration"

What I get are the following two:

{"code":"Ok","routes":[{"geometry":"emhvGi}m\\`A}Ej@mAVD~FtGnBgInCeVh@k@~AoKQa@aGcD[?lFkW|C_MBk@","legs":[{"steps":[],"distance":1691.9,"duration":237.6,"summary":"","weight":237.6}],"distance":1691.9,"duration":237.6,"weight_name":"routability","weight":237.6}],"waypoints":[{"hint":"NxUAgP___38UAAAAGAAAADIAAAAAAAAAZ7JhQaCeAUCSwwVCAAAAABQAAAAYAAAAMgAAAAAAAAAIAQAA8apJANo8ugLxqkkA2Dy6AgEAbwXhRjDc","name":"Avenue Adolphe Max","location":[4.827889

{"code":"Ok","sources":[{"hint":"NxUAgP___38UAAAAGAAAADIAAAAAAAAAZ7JhQaCeAUCSwwVCAAAAABQAAAAYAAAAMgAAAAAAAAAIAQAA8apJANo8ugLxqkkA2Dy6AgEAbwXhRjDc","name":"Avenue Adolphe Max","location":[4.827889,45.759706]}],"destinations":[{"hint":"GRIAgP___38GAAAACgAAAAkAAAADAAAAIY7sQMoEdECQgxlBEv3JQAYAAAAKAAAACQAAAAMAAAAIAQAAiOVJAK4rugKI5UkAriu6AgIAvwXhRjDc","name":"Cours Gambetta","location":[4.842888,45.75531]}],"durations":[[237.6]],"distances":[[1694.2]]}%      

The two durations are the same, 237.6 but the distances differ. I found other examples on other maps, too.

Is that normal?

Thanks a lot.

[chaupow]

I know that sometimes, when two routes have the same duration, it is possible that matrix requests unpack a route that is different from the one that you get with route. That would explain the different distances.

We decided to not to bother too much because in our experience the distances did not differ much. Unpacking all possible routes would probably affect performance even more.

I am currently still searching for the bit of code where we pick a random route to unpack because I don't quite remember anymore. I'll post it for more context if I can find it.

[rgugliel]

Hi @chaupow , Thanks for your answer.

I did a second try with a pair for which an alternative route which has similar distance is unlikely and I still get a difference.

[danpat]

In this case, I'd suspect a bug in the distance unpacking for the table plugin. The fact that the durations are the same is a strong hit that both the table and route plugins found the same path. However, the distance calculation code is different between table and route, and as the table code is quite new, I suspect there's an edge case here that's got a bug.

[chaupow]

Yea. That route looks pretty umambiguous 🤔 I'm still unable to find the line of code where @oxidase hinted at getting different distances when the duration is the same.

Another thing is that we have a mixed usage of haversine or fcc calculations to calculate distances. Not sure if that could cause differences as well.

@rgugliel are the distance differences you see big?

[chaupow]

Also, @rgugliel are you using CH or MLD algorithm? (= do you use contract or partitions/customize to preprocess the data).

[rgugliel]

@chaupow No, usually it is pretty small, typically around 0.1 - 0.2% But we use the two on a simulation context and it creates some discrepancies.

I use CH.

[barqshasbite]

I have also seen these differences. I filed issue #5106 when I noticed the distances could actually be returned as negative values. I suspect they are related somehow, but cannot be certain.

[rgugliel]

@barqshasbite Thanks for the update. I'll redo my test when 5.18.1 will be there, then!

[rgugliel]

A colleague did a test using master and it seems that the fix of #5060 decrease some of the discrepencies but not completely.

[rgugliel]

I get the same result (as in the initial post) with osrm-backend 5.20.0

Any idea?

[and7000]

Hi there, Still now there is differences in TABLE and ROUTE calls. Although the waypoints are exactly the same, in the legs part: the durations are exactly the same, but the distance differs a bit... this looks like a bug. I have the same opinion of @danpat : same durations 'strongly implies' that both TABLE and ROUTE calls found the same path, but the distance calculation code looks different between TABLE and ROUTE.

[danpat]

@and7000 Are the differences large or small? @chaupow 's comment here is still true, so if the differences are small, I'd point at use of different distance calculation algorithms as a strong candidate for the sources.

[and7000]

Using (SouthAmerica Map), in a localost, checking these 3 points:

curl "http://localhost:5001/route/v1/driving/-46.5566239,-23.5315259;-46.5822486,-23.508798;-46.612311,-23.508052?overview=false"
curl "http://localhost:5001/table/v1/driving/-46.5566239,-23.5315259;-46.5822486,-23.508798;-46.612311,-23.508052?annotations=duration,distance"

All waypoints (for Route), sources and destinations (for Table) returned had exactly the same data.

Diferences in distance and duration: Route vs Table :

1. leg1: distance: 6191.7 vs 6181.3 Diff: +10.4 (0.2%) duration: 694.2 vs 694.2 OK
2. leg2: distance: 4326.5 vs 4858.6 Diff: -532,1 (11%) duration: 506.3 vs 504.4 Diff: +1,9 (0.4%)

[danpat]

You should add continue_straight=false to your /route request. By default, it's set to true for the car.lua profile. It will prevent doing a u-turn at the middle waypoint. If you route with a middle waypoint, this can lead to different paths being used compared to when you do separate A->B, and B->C (i.e. ABC != AB+BC) requests (which is what the /table request effectively does).

[and7000]

Perfectly, I missed that: continue_straight=false . Thanks. Once fixed, the duration now match on both legs, but still a small difference in distance remains:

1. leg1: distance: 6191.7 vs 6181.3 Diff: 10.4 (0.2%) duration: 694.2 vs 694.2 OK
2. leg2: distance: 4863.3 vs 4858.6 Diff: 4.7 (0.1%) duration: 504.4 vs 504.4 OK

[danpat]

Yeah, I'd say those small differences can probably be entirely explained by the inconsistent use of different length calculation algorithms across the OSRM codebase.

For example, the table plugin uses distances that are stored as edge properties, created here:

https://github.com/Project-OSRM/osrm-backend/blob/master/src/extractor/extraction_containers.cpp#L385-L399

using a weird combination of Great Circle distance, and the fast FCC approximation method.

The the route plugin re-calculates distances using the coordinates in the response using the Haversine equation, here:

https://github.com/Project-OSRM/osrm-backend/blob/master/include/engine/guidance/assemble_geometry.hpp#L66-L71

It's a bit of an inconsistent mess. It's come about because over time, we've done incremental performance improvements in critical loops. IIRC, we avoided touching all of the codebase because a) changing lengths would've invalidated many of the carefully constructed tests, and b) the error sizes were quite small - well below the precision of the map data we're operating with.

e.g. in the real world, can you prove whether leg1 is actually 6191.7 or 6181.3?

I definitely agree we should be consistent internally, but it's a bit of work to clean up.

[gabriel-munteanu]

Hi! I have another issue related to this: https://router.project-osrm.org/table/v1/driving/20.996883,52.157196;20.932394,52.150704?skip_waypoints=true&sources=0&destinations=1&annotations=distance,duration https://router.project-osrm.org/route/v1/driving/20.996883,52.157196;20.932394,52.150704?overview=false&skip_waypoints=true&alternatives=2

The first(default) route from Routes Api is not the one picked by Table Api. Computing alternatives I see that the second route is the one Table is returning/computing. Why is this happening and can it be fixed? OSRM version: 5.26

[danpat]

@gabriel-munteanu that is a very interesting case, thank you for the example.

This highlights one of the underlying issues pretty clearly - graph exploration order.

The weight of the two routes is equal in your /route request. What's very likely happening is that the order of edge exploration for /route finds the 12km route first by chance, but the /table algorithm finds the 8.7km route first, by chance. The difference will come down to the order that equal-cost edges are explored by the two different algorithms.

The many-to-many (table) algorithm and the routing algorithm (route) are different. I'm not sure if it'd be possible to write them to guarantee they discover paths in the same order, they have some deep differences that might make that pretty hard.

Ultimately, when there are multiple equal cost paths from point A to point B, you can't even say which algorithm is right. If you do have an opinion on which is right and which is wrong (e.g. take the shorter route when durations are equal), then that idea needs to get codified in your edge cost.

[ilibar-zpt]

I've been thinking about whether table uses continue_straight or not, which is absolutely not clear given that:

1. route API description states that there's a default value for that option
2. table always uses false (according to this thread) and not the default

Can we have the documentation somehow updated to reflect that table always does u-turns disregarding the default? (or whatever the correct implementation here)

[danpat]

@ilibar-zpt the table service doesn't do u-turns at waypoints (which is what continue_straight affects), because it does not perform multi-leg routes. continue_straight only means something for 3 or more coordinate route requests, it's a behaviour specific to multi-leg /route, and has no impact on a 2-coordinate /route request.

[ilibar-zpt]

Had to re-read the description of continue_straight. Right, I thought it affects all possible uturns (within steps) from A to B, but it's only for input waypoints. Thanks

[danpat]

Yeah - if you place a coordinate on a street with a dead-end, then the routing algorithm will explore both directions from the point, but the dead-end path with a u-turn will never be the best, because it ends up turning around and passing the origin point again.

The only caveat to that is if you force the departure/arrival direction with approaches or bearings.