Incorrect map matching onto motorway link


#1

Hi,

I am looking into an incorrect map matching issue where points are routed onto a motorway link rather than taking the fastest path along the motorway (see attached images).

I can reproduce the result with a very small number of points. One difference I found is that when an additonal point (point 5) is added to the data set, it seems to change the candidate snaps for the first GPX entry. This is odd, since I though “lookupGPXEntries” in MppMatching only performs a spatial lookup of individual points against the graph.

Example of inconsistent snapping for first GPX entry on a data set with 5 points:
2019-03-08 19:16:50 DEBUG MapMatching:197 - Query results for GPX entry 1
2019-03-08 19:16:50 DEBUG MapMatching:199 - Node id: 860650, virtual: true, snapped on: EDGE, pos: 47.57972372482106,-122.15710284583339, query distance: 25.95785110107895
2019-03-08 19:16:50 DEBUG MapMatching:199 - Node id: 860647, virtual: true, snapped on: EDGE, pos: 47.57930736385753,-122.15714929920928, query distance: 20.470656046719654
2019-03-08 19:16:50 DEBUG MapMatching:199 - Node id: 860662, virtual: true, snapped on: EDGE, pos: 47.57955285654165,-122.15712281216719, query distance: 6.899231983948782
2019-03-08 19:16:50 DEBUG MapMatching:199 - Node id: 860659, virtual: true, snapped on: EDGE, pos: 47.57978394180499,-122.15709618466602, query distance: 32.672245827019104

Snap candidates for first GPX entry on same dataset with last point removed:
2019-03-08 19:31:34 DEBUG MapM

atching:195 - ================= Query results =================
2019-03-08 19:31:34 DEBUG MapMatching:197 - Query results for GPX entry 1
2019-03-08 19:31:34 DEBUG MapMatching:199 - Node id: 860649, virtual: true, snapped on: EDGE, pos: 47.57972372482106,-122.15710284583339, query distance: 25.95785110107895
2019-03-08 19:31:34 DEBUG MapMatching:199 - Node id: 860660, virtual: true, snapped on: EDGE, pos: 47.57955285654165,-122.15712281216719, query distance: 6.899231983948782
2019-03-08 19:31:34 DEBUG MapMatching:199 - Node id: 860647, virtual: true, snapped on: EDGE, pos: 47.57930736385753,-122.15714929920928, query distance: 20.470656046719654
2019-03-08 19:31:34 DEBUG MapMatching:199 - Node id: 860658, virtual: true, snapped on: EDGE, pos: 47.57978394180499,-122.15709618466602, query distance: 32.672245827019104

Points:
“trip_id”,“point_id”,“capture_time”,“lat”,“lon”
“8422ac2e878c49ca97535f17dbc5ac57”,“0”,“2018-11-10T17:58:28.000Z”,“47.579491”
“8422ac2e878c49ca97535f17dbc5ac57”,“1”,“2018-11-10T17:59:12.000Z”,“47.578704”
“8422ac2e878c49ca97535f17dbc5ac57”,“2”,“2018-11-10T17:59:23.000Z”,“47.578519”
“8422ac2e878c49ca97535f17dbc5ac57”,“3”,“2018-11-10T17:59:27.000Z”,“47.578472”
Adding this point changes the list of snapped candidates for point “0”
“8422ac2e878c49ca97535f17dbc5ac57”,“4”,“2018-11-10T18:00:28.000Z”,“47.573102”

Any help would be appreciated.

Thanks,
Trang


#2

We are seeing many examples of incorrect routing onto a motorway_link. It is commonly seen where the main “motorway” class is tagged with a maxspeed restriction where the motorway link is not.
However, even after reducing the default speed of “motorway_link” in my CustomCarFlagEncoder to a 10 (for testing purposes), I don’t see a change in map matching behavior.
Above, with 2 data sets (one with 4 points and one with 5), the one with 4 points selects the correct route where the 5-point dataset doesn’t. I’ve verified that snap candidates are identical between the two. The issue occurs somewhere in the assignment of weights as part of the routing call performed by DijkstraBidirectionRef.

I’ve tried other approaches - using PriorityWeighting. I can only get the correct route by adding “motorway_link” to an avoidSet at worst priority, but this is non-ideal and will cause issues for other datasets.

We have many examples of this behavior. Here are some of them where the wrong road is chosen after the road is split:

Why is this occurring and how best to influence the correct behavior?


#3

This is really strange. Usually those problems occur if the weight on the motorway_link is lower. And so it should be fixed if you set the speed of the motorway_link to a lower speed (i.e. higher weight) compared to the maxspeed of the motorway.

Above, with 2 data sets (one with 4 points and one with 5), the one with 4 points selects the correct route where the 5-point dataset doesn’t. I’ve verified that snap candidates are identical between the two.

Are you able to reproduce the issue with the latest master? Then you could build a failing test and send us a link to your fork so we could investigate this on our side.


#4

Hallo Peter,

vielen Dank fuer Ihre Antwort :slight_smile:

Yes, the roads which are impacted typically have a maxspeed restriction that is lower than the motorway_link speed, but to get around this, in our custom implementation of CarFlagEncoder, we are setting the default motorway_link speed purposely to a very low value:
// autobahn
defaultSpeedMap.put(“motorway”, 100);
defaultSpeedMap.put(“motorway_link”, 30);
// using priority weighting
preferSet.add(“motorway”);
// avoided road classifications wiith priority level set to “AVOID_IF_POSSIBLE”
avoidSet.add(“motorway_link”);

In addition, for our custom implementation of PriorityWeighting, we’ve changed slightly the implementation to increase the routing penalty for motorway link:
@Override
public double calcWeight(EdgeIteratorState edgeState, boolean reverse, int prevOrNextEdgeId) {
double weight = super.calcWeight(edgeState, reverse, prevOrNextEdgeId);
if (Double.isInfinite(weight))
return Double.POSITIVE_INFINITY;
Double factor = edgeState.get(priorityEnc);
return weight / (0.001 + factor);
}

As to your question, I’ve merged code from master onto a local branch and still am observing the same results.
A colleague of mine was also able to repro strange routing behavior with this request:
https://graphhopper.com/maps/?point=47.579491%2C-122.15713&point=47.578691%2C-122.140042&point=47.578529%2C-122.136217&point=47.573102%2C-122.118426&locale=en-us&vehicle=car&weighting=fastest&elevation=true&use_miles=false&layer=Omniscale

I’ve attached the lat, lon coordinates in a separate file.BadRouting_Trip_8422ac2e878c49ca97535f17dbc5ac57.txt (96 Bytes)

Thanks,
Trang


#5

Thanks!

The GraphHopper maps demo uses the Routing API under the hood and just snaps to the wrong road for point 2. So, if you send the same points to the Map Matching API you’ll get them snapped:

But as you can see I can reproduce the same problem that you mentioned with our hosted Directions API (snapping to the motorway_link). Was able to reproduce this for the open source routing engine even when setting the speed of motorway_link to 5km/h. Have created an issue to track the progress of this bug: https://github.com/graphhopper/map-matching/issues/147


#6

Will reducing the GPS accuracy work in your case? (see also the discussion in the issue)