Router choosing longer route due to taking smallest gap between point and road

[answerquest]

Hello, big thanks to the developers of this project for a fantastic amount of work. I have built osrm-backend for pedestrian routing using profiles/foot.lua , and am running osrm-frontend on it.

Please notice the translucent gap in these screenshots:

What is the offiical / code term for this gap? I want to find a way to prevent the router from choosing much longer go-around routes and tolerate an increased gap instead.

That fits the use case for pedestrian routing : We want them to get into the building/premises with the shortest possible road distance. We don't want to send them running around the building in circles just to have them end up on a road point that is closest possible to the exact lat-lon inside the premises. In the real world, the destination/origin lat-long may be well inside a premises but the commuter will obviously go from/to an entry point. The entry points are marked by the points where the roads touch the polygon of the premises.

My guesswork right now is that the router is first finding the closest road point from the location, and then doing routing. But for pedestrian profile it would make sense to check out multiple points and then choose the one that returns least on-road distance. (I have set weight_name = 'distance' in my foot.lua profile to keep distance as priority)

Regarding the building in screenshot, I had added highway=pedestrian,area=yes tags to it as per this in the hopes that OSRM would not run around the roads, but it now it's treating the outer walls as paths instead of cuttng across the area. If I can get the gap tolerance increased, then i'll rollback those tags.

[systemed]

Ultimately this is because OSRM does not support area routing (see #64).

[answerquest]

@systemed sorry, but my issue is not about area routing at all. I have recognized (albeit late!) that it wasn't the real requirement/problem here. I would rather not have OSRM do routing in an area in my use case. The issue is about how OSRM decides which route is best when the destination/origin point is off the road. Let me try and explain it better:

Simplified Scenario

Problem Statement

Please see the diagram. So this is how I believe the current decision-making seems to be happening:

1. Figure out which on-road node (P or Q) is closest to the origin, irrespective of everything else
2. Adopt the closest on-road node (Q) as the pseudo-origin
3. Start routing between Q and destination. There go ahead and use weightage, consider factors etc.
4. Pick the best routes from Q to destination, set those as the router's solutions.
5. Ignore P completely, because it failed the gap test by 2 meters. Don't even bother checking if there was a better route from P to destination (which, it turns out, there was : a 9km shorter route).

So because all the routing decision-making process only begins long after Q has been chosen and P has been rejected, we never get to see Path A even in the alternative path suggestions.

Proposed alternative algorithm

1. Figure out the top 3 or so closest road nodes, so pick both P and Q
2. Do routing for all the chosen nodes, choosing the best path from each node to destination. So we have a best path for Q and a best path for P too.
3. Compare the best paths, find out which is the most viable one (accoring to weightage like distance, duration etc).
4. Here, router realizes that P, despite being 2 meters further away from origin than Q, is giving a path to destination which is 9 km shorter than what Q was offering.
5. Hence, router favors P and Path A over Q and Path B, and we all live happily ever after.

Secondary proposal

If we can't reach that level of choosiness, then the least we can do is not discard the P option out of hand and include it in the alternative path suggestions. If it comes at least mentioned as an alternative path in the API callback then I can evaluate the distances and choose the more sensible option at my end.

Proverbial Carrot

I have a feeling that working on this would benefit the driving and transit directions efforts too. If the car is inside a premises, you want to point it to the better gate, not necessarily the closest one. Or if a commuter needs to take a bus to someplace, then you might want to suggest a better stop even if it's a few meters farther away.

Please point to code

At least let me know where exactly in the code is Q being chosen over P, and maybe I can do some tinkering over there at my own end. Apologies - I'm more into Python than Java at the moment; am not being able to trace it myself. Please just tell me which file / section / function / class is involved in this matter.

[danpat]

This related to #4465 - OSRM snaps to the nearest edge, and routes from that point only. An alternative approach would be to find the nearest N matches, route from all of them, and come up with a heuristic to select which combination is the most desirable. @emiltin suggested a possible heuristic for this back in #605 (comment) when considering the "which 'bearing' matches the user's request best".

There are two major changes that would need to be made:

1. Make the RTree search return multiple results, out to some kind of limit.
2. Modify the route search algorithm to route between all pairs of sources/destinations (the /table code could be re-used here).
3. Rank the results and select the one that best fits the desired output - getting this right may be difficult.

[answerquest]

@danpat thanks so much for interpreting this correctly. Please feel free to rename the issue to another appropriate title.

3. Rank the results and select the one that best fits the desired output - getting this right may be difficult.

I think the "weight" parameter is quite good. Simply compare weights of all results thrown up and rank as you have been. In my use case I've set weight_name = 'distance' in my .lua profile, so that one should work out fine.

One added operation could be: Final distance = route distance + gap distance.
And then weigh accordingly. In my use case that would make:

• Path A : (1000 + x + 2) m
• Path B : (10000 + x) m

And A would win. But if somebody's in a forest and all the nearest road nodes are a long distance away, then it might be worthwhile to just get them on to the nearest road first and worry about other things later. For that, the weight_name would have to be something besides 'distance'.

[answerquest]

If I zoom in to my first screenshot,

It does look like osrm is entertaining two gaps / snap-to-nodes simultaneously, and judging between them passing on judgement to the user. How about trying to increase the tolerance so it entertains more gaps?

[github-actions]

This issue seems to be stale. It will be closed in 30 days if no further activity occurs.