negative distances in matrix for points that are far away #7269
Description
We have recently noticed negative distances in matrix responses - i.e., in responses from table service. This is similar to #5855, which describes the issue for points that are close, but in this case (and why we are reporting it separately) the problem manifests for points that are far away (e.g., some 30 km).
It took us some time to prepare a reliable reproducer for the purposes of this bug report - for points A and B, which would give negative distances in one matrix request, OSRM would give proper (or at least non-negative) distances in another, so it very much depends on some specific (unknown) conditions.
In order to reproduce the problem, we have prepared the following simple Python script:
In this script, there is a list of 64 bad points, some with curb approach and others with opposite. They are located in the eastern part of Latvia:
These points are called bad points, because all of them belong to some bad pair of points (both points from the pair are included) for which a negative distance was reported in our system. However, when we run this script, the issue will manifest for only three pairs - not much, compared to the scale observed in our system, but it should be good enough for you to start the investigation.
Initially, the script uses Folium to visualize the points on a map (saving it to points.html) - you can comment that part out if you do not have Folium installed. After that, it sends two matrix requests.
The first request is sent in "full mode" - the script asks OSRM for the full 64x64 matrix. For this type of request, there will be no negative distances in the response.
The second request is sent in "half mode" - it divides all points into two halves (both with 32 points) and then it asks OSRM for a 32x32 matrix, putting the first half of the points into sources and the other half into destinations.
Obviously, since the matrix in "half mode" is a 1/4 submatrix of "full mode", the results in that submatrix are expected to be identical. However, for the "half mode" request, there will be three pairs of far-away points with negative distances. The output of the script is as follows:
number of points: 64
matrix request in full mode:
matrix request in half mode:
negative distance in cell (4, 18) between Point(latitude=57.007511041473684, longitude=27.137932637935975, approach='curb') and Point(latitude=57.12818857604232, longitude=27.28028119931873, approach='curb'): -0.1
negative distance in cell (8, 31) between Point(latitude=57.00751274625871, longitude=27.137927791691357, approach='curb') and Point(latitude=57.20665789896023, longitude=27.423785714977, approach='opposite'): -0.1
negative distance in cell (27, 2) between Point(latitude=56.8904672439558, longitude=27.10523303227006, approach='curb') and Point(latitude=57.1536428241892, longitude=27.662818595800243, approach='opposite'): -0.2
For the points from the third pair, there is a distance of some 60 km between them:
We have a conjecture that the issue only manifests with sources and destinations, but we leave that as an exercise for the reader. Also, if you play around with the order of points in BAD_POINTS list (e.g., by randomly shuffling it), then sometimes there will be three bad pairs in half mode, sometimes two, sometimes one or sometimes none at all. For this bug report, we chose the order with three bad pairs - the maximum we managed to find.
The script was tested on OSRM v6.0.0 with the default car.lua profile and MLD algorithm. The road network was a recent OSM download for Latvia from https://download.geofabrik.de/europe/latvia.html .