Triangle inequality violations

[cssartori]

I'm using OSRM to get data related to distance/duration between a set of coordinates, in order to create a graph with which my application will later work. I'm using the C++ API on my local machine.

However, when obtaining this matrix there appears to be certain points that do not hold the triangle inequality. In other words, there are coordinates A, B and C, where

d(A,B) + d(B,C) < d(A,C) , where d(X,Y) is the distance between coordinates X and Y.

This does not seem right to me, because if going A-B-C is faster/shorter than directly A-C, OSRM should return route A-B-C as the one to go from A to C. This effect happens even if I allow alternative paths to be considered (alternative = true) and I take the faster/shorter path between each pair of coordinates. This effect happens for both distance and duration data, though with distance the number of violations is usually bigger (I have no clue why).

Is there anything I should know about this issue? Or is anyone else experiencing this? I've tried searching for related problems, but all I could find were two issues a couple of years old, which I'm not sure are still valid considering the current updates to OSRM. Also, is there a way to overcome this, besides making the adjustments by hand (as in d(A,C) = d(A,B)+d(B,C))?

An example with three points is (my input data is OSM Berlin from Geofabrik):
A = ( 52.561346 , 13.504229 )
B = ( 52.492262 , 13.321100 )
C = ( 52.491818 , 13.321137 )

The distance data returned by OSRM is the following:
d(A,B) = 16278.20
d(B,C) = 84.10
d(A,C) = 16430.30
And: 16278.20 + 84.10 = 16362.30 < 16430.30
I would expect it to provide d(A,C) = 16362.30 instead.

[danpat]

Can you check if the equality is violated with durations as well?

There are some bugs in the distance calculation for the /table plugin, it's possible this is what you're seeing:

#5151

[cssartori]

Unfortunately duration is violated as well.
For the same example I gave, OSRM gives me the following information on duration (I'll refer as t(X,Y)):
t(A,B) = 1676.00
t(B,C) = 15.00
t(A,C) = 1698.10
And: 1676.00 + 15.00 = 1691.00 < 1698.10

Note: Although as I mentioned before, the total number of violations in a N x N matrix is smaller when considering durations instead of distances.

Note2: I've read issue #5151 as you mentioned. However, this issue happens to me whether I'm calling the Table or Route method.

[jcoupey]

Given that OSRM provides optimal routes, we should expect the triangle inequality to hold on the underlying metric, which is neither duration, nor distance, but weight.

Weights are derived from speed/duration in the profile, this is probably why you experience a lower number of violations with duration than with distance.

[cssartori]

Thank you for the clarification @jcoupey regarding this weight issue, I was actually not entirely aware of that.

Is there anyway to overcome this? Or anyway I could tell the router to use the best metric for my purpose?

On a side question: when I ask for alternative paths between two points, OSRM returns alternative paths that are somehow equally optimal based on this weight metric? Or does it return some paths that may be "more optimal" regarding distance, or duration?

[jcoupey]

@cssartori you can adjust the routing metric in the profile here: https://github.com/Project-OSRM/osrm-backend/blob/v5.18.0/profiles/car.lua#L18-L23.

[cssartori]

@jcoupey I have run some tests after changing the profile configuration and it appears to be working all right now. All matrices respect the triangle inequality in its appropriate metric.

Thank you for the useful information and guidance :)

[TheMarex]

This is an interesting side-effect, I guess that means for a few VRP related algorithms the durations of the minimal-weight routes might cause problems. Good catch @jcoupey! Closing as "solved".