Avoid "No Route" error in case of unreachable destination

[datwelk]

For whatever reason, it could sometimes happen that a destination is unreachable. E.g. when the destination is on the premises of a theme park or campground, which are usually blocked off by gates that are not passable.

Instead of sending the user to the nearest gate, OSRM in this case will return a "No Route" error. It would be great if it could try to route as closely to the destination as possible instead of not suggesting a route at all. OSRM already does this when you route to a destination outside the OSM area covered by the OSRM instance.

Is there a setting that I could use to enable this desired behaviour? If not, any pointers to files or functions where I could possibly implement a solution to this problem would be extremely helpful. Thanks!

[danpat]

This will only happen if the destination and sources are on disconnected networks that are also quite large.

When initial import the map, we scan every edge to determine how connected to the road network it is, using https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm

When snapping coordinates, if the closest point is on a "small component" (<1000 strongly connected edges), then a second point will be chosen on the nearest "large component" (>= 1000 strongly connected edges). OSRM then tries to ensure that either both the start/end coordinates are on the same small component, or that they are at least on a "large component".

If you request a route where the locations snap to two "large components" that are not actually connected, you'll get a NoRoute response.

There are thousands of small components on the global map. There are a much smaller number of large components - if an edge is connected to >1000 other edges, it tends to be part of the main road network for a country/continent. The few large components that aren't connected to the main road network tend to be things like Disneyland, and other very large, private-but-mapped areas. There aren't many of them, and when people request routes involving them, those routes tend to be within those areas.

You can tweak the 1000 node size with osrm-extract --small-component-size N - replace N with a value of your preference. Increasing it for your case is probably fine, maybe try using 10000. This will cause some of these larger disconnected areas to be flagged as "small components", which will cause OSRM to shift the snapping points onto the larger nearby road network. No guarantee it'll be the gate location - we use the straight-line closest distance to your input coordinate.

[datwelk]

Many thanks Daniel!

[xuruiray]

@danpat I think the snap according to the components size is not reasonable, the territory of some countries contains small islands, and when doing navigation between small islands and land, it will snap to land and become navigation on land, but in fact it is not navigable, even though component-size can be adjusted to solve the problem, I think this logic should not exist

[nilsnolde]

what'll happen if that logic wouldn't exist: the algorithm would traverse all edges inside each component and would likely never find a connection. it's a very reasonable measure and the fact that osrm gives you control over what's considered a small component is quite good.

in the case of islands: if there's a ferry connection, then they're part of the same component. if there isn't.. well, then a route won't be possible and it's correct to fail early instead of exhausting each network component to finally realize there's no route. it's a safe-guard for the server with little impact on the behavior for the user.

[xuruiray]

thanks nilsnolde, i figured it out

[xuruiray]

@nilsnolde I see the importance of this logic, but in the case of navigation between the island and the land, it did not fail quickly, but returned a misleading route, I think this scene is still in trouble

[mjjbell]

Currently there's no understanding of geographic barriers in OSRM. Some alternatives:

You can limit the distance the snapped location is from the input location by specifying the radiuses parameter in your request: https://github.com/Project-OSRM/osrm-backend/blob/master/docs/http.md If there's no snapped location within the radius, you'll get an immediate error response.

In the response you can look at the distance between input/snapped positions and the geo-location of the snapped location, and make an informed decision about whether you want to use the route.

[xuruiray]

thanks mjjbell, now I am using radiuses to handle this scene