Better Map Matching rerouting

[ianthetechie]

The existing getRoutes method will "just work" for map matching if it has a request generator. I know of some Ferrostar users doing map matching without re-routing. But there's probably a bigger discussion to be had around how to handle rerouting for cases where that's needed.

The key question is at which point(s) should we try to put the user back on the original route? We currently try to reroute through all waypoints that have not yet been "visited." But in the case of map matching, we often have hundreds of waypoints, and we probably shouldn't treat all of them as the same for rerouting on map matched routes.

Map matching engines turn the raw points into maneuvers. We could theoretically use this to identify breaks and reroute the user from the current position to the next break and then map match the rest. An open question is whether the map matching engine will be able to handle a (potentially large) jump. So maybe we need to make multiple backend requests?

Feedback, ideas, and opinions welcome!

[bjtrounson]

Thought I should put my 2¢ here since our app is completely driven off of map-matched routes. I know we have talked about it in our weekly calls but thought it would be good to have this written down somewhere.

I will put how our app current handles the routes currently here for some context. We currently are storing all of our map-matched responses in a SQLite DB on device and using the extension method on the Route class fromOsrm to convert these responses into Ferrostar route objects. We also do some extra processing for hand to make sure the whole route was processed as there are quite a few missing farm driveways in OSM in New Zealand. I generate what I call dummy instruction for these and append them to the start and end of the map matched routes.

With that in mind here is some questions and thoughts I have on the above.

The key question is at which point(s) should we try to put the user back on the original route? We currently try to reroute through all waypoints that have not yet been "visited." But in the case of map matching, we often have hundreds of waypoints, and we probably shouldn't treat all of them as the same for rerouting on map matched routes.

This one is a tricky one, in our case we would want to get back on to the map matched route as soon as possible. But we wouldn't want to be doing weird maneuvers that require u-turns. Maybe having different modes of re-route map-matching might be needed here or an interface for implementing a custom one. Not sure what this would look like at the moment.

Map matching engines turn the raw points into maneuvers. We could theoretically use this to identify breaks and reroute the user from the current position to the next break and then map match the rest.

I do have a question about this part, with our map-matched routes we only have two breaks one at the start and another at the end. We split all of our map matched responses to be per-pickup so I don't know if this approach would work to well in that scenario. For this we might need to keep track of the closest waypoint the user has pasted, then if we deviate we turn the next waypoint into the starting break and continue from there. This might cause some weird u-turn scenarios though so not 100% sure about this. Another way to maybe go about this is to skip to the next step and consider the start point of that step to be the next break waypoint.

A bit of a brain dump but let me know if something doesn't make sense.

[ianthetechie]

Thanks for the comments!

This one is a tricky one, in our case we would want to get back on to the map matched route as soon as possible. But we wouldn't want to be doing weird maneuvers that require u-turns. Maybe having different modes of re-route map-matching might be needed here or an interface for implementing a custom one. Not sure what this would look like at the moment.

Makes sense. Yeah, U-turns were actually the first undesirable behavior that popped into my head too as I was thinking about this. I think there are ways to minimize that, but it'd require some careful tuning of the request generation, and I think this would necessarily be specific to the backend. For example, with Valhalla, we could tell it to start with the user's last known heading. This won't eliminate all U-turns per se, but if you're routing with a profile like truck or bus which heavily penalizes u-turns already, I think this would generate acceptable routes in most scenarios.

Another way to maybe go about this is to skip to the next step and consider the start point of that step to be the next break waypoint.

Ahh, yes! I think that is what I meant to say 😅 I was careless in my choice of "break" and was not intending that to mean the Valhalla break waypoint type. Just the next logical step division in the route. Basically, we already track remaining steps. So when the user goes off the matched route, I think a (simplistic first pass) heuristic would be to route from the user to the end of the "current" step (or start of the next step; same thing) first. Then join that set of instructions with map matching that starts from that point and continues through the rest of the points as normal.

Is that what you had in mind?

[bjtrounson]

Yes that basically what I had in mind. I can provide some routes we can play around with this idea if need be and see if the u-turn stuff is going to much of an issue at all. But you logic makes sense and I don't think it will be a big deal.