No route found between points

[daudef]

OSRM cannot find a route between those two points:
http://router.project-osrm.org/route/v1/driving/2.343521,48.86589;2.344338,48.866283

It can also be seen on the OSM front:
https://www.openstreetmap.org/directions?engine=fossgis_osrm_car&route=48.86580%2C2.34347%3B48.86630%2C2.34427#map=19/48.86598/2.34397&layers=N

But if i try to insert a third point in between, it works:
https://www.openstreetmap.org/directions?engine=fossgis_osrm_car&route=48.86580%2C2.34347%3B48.86613%2C2.34366#map=19/48.86614/2.34379&layers=N
https://www.openstreetmap.org/directions?engine=fossgis_osrm_car&route=48.86613%2C2.34366%3B48.86630%2C2.34427#map=19/48.86614/2.34379&layers=N

I don't think this is the same issue as #5320 since there is no u-turn between the two previous routes, and adding continue_straight=false doesn't help:
http://router.project-osrm.org/route/v1/driving/2.343521,48.86589;2.344338,48.866283?continue_straight=false

also it works if i swap to the graphhopper backend:
https://www.openstreetmap.org/directions?engine=graphhopper_car&route=48.86580%2C2.34347%3B48.86630%2C2.34427#map=19/48.86612/2.34351&layers=N

I am using the OSRM backend with libosrm c++ API, is there a way to find the route between those two points or to snap the second point to closest way reachable ?

Thanks.

[datendelphin]

It is a partial routing island. The Rue d'Argout is a one way with motor_vehicle=yes, which is fine. But the only source for it is Rue Montmartre which is motor_vehicle=no. As a result, it can't be routed in that direction, which would require the car driving once around the block.

[daudef]

Thanks for your reply @datendelphin, I understand that Rue Montmartre is motor_vehicle=false in OSM so you can't get to the endpoint (which is not correct btw, cars are totally allowed in Rue Montmartre, but I don't think it matters here).

What I don't understand is why this works and this does not.

[datendelphin]

It snaps to different points. And it seems pretty random if it snaps onto the one way street or not, so definitely room for improvement. However, if this only occurs in this "impossible" case of a one way which can only be exited, it's not that bad I think.

Well you are right, Rue Montmartre is delivery @ (6:00-10:00,13:30-15:30) but the demo server can't use that information (it's time independent). The Problem arises because Rue d'Argout is mapped differently.

[mjjbell]

This is due to the way that the route endpoints are snapped to the road network.
OSRM will try to snap to roads that are strongly connected (each is reachable from the other).

The majority of the road network is strongly connected. But you’ll also get small strongly connected components (SCC) that are disconnected in some way from the main network. In this case, Rue d'Argout is treated as its own SCC due to being one-way and (according to current OSM tags) not being accessible from Rue Montmartre. You can see the small SCCs highlighted in pink on the debug map.

In the first case, the source snaps to Rue du Louvre and the target to Rue d’Argout. These roads are in different SCCs, so it will actually change the target to snap to the nearest position on same SCC as the source, which in this case means also on Rue du Louvre. Hence, a route is found.

In the second case, both endpoints snap to Rue d’Argout. This is fine as clearly they are in the same SCC by virtue of being on the same road. However, at the point of snapping it’s not considering the position on the road. Therefore, it fails at the routing step due to being one-way and otherwise inaccessible.

Ideally what should happen is if OSRM supports snapping to multiple locations, then an alternative route is found via Rue du Louvre as in case 1.

PR #5953 goes some way to supporting snapping to multiple source/targets, but only supports snap locations that are equidistant from the input location. The next step - to support multiple source/targets that are within a distance N of the input - would be needed to resolve the problem here.

[danpat]

However, at the point of snapping it’s not considering the position on the road. Therefore, it fails at the routing step due to being one-way and otherwise inaccessible.

I think this is the key - we're missing the "same edge" case handling for small component snapping.

[mjjbell]

I think this is the key - we're missing the "same edge" case handling for small component snapping.

Am I right in thinking this can only happen when the small component is a single edge?
Perhaps looking at the component size is the way to handle it.

[danpat]

I don't think we store the component size for nodes, only the component ID. I think you're right though - if this road was two one-way nodes and we had this situation spread over adjacent nodes, we wouldn't have a problem as they aren't strongly connected.

osrm-backend/include/engine/plugins/plugin_base.hpp

Lines 124 to 132 in 41dda32

	const auto fallback_to_big_component =
	[](const std::pair<PhantomNode, PhantomNode> &phantom_pair) {
	if (phantom_pair.first.component.is_tiny && phantom_pair.second.IsValid() &&
	!phantom_pair.second.component.is_tiny)
	{
	return phantom_pair.second;
	}
	return phantom_pair.first;
	};

is where the fix would need to go.

There, we'd want to check if the

1. PhantomNodes are on the same node
2. Determine if it's a oneway, and
3. If it is, make sure the coordinates are in a usable ordering

I'm not sure how easy (2) will be to determine at this phase - it's possible that the forward_segment_id or reverse_segment_id will not be set in the case of a oneway, but I'm not sure - it's been a while since I've looked at this code.

[github-actions]

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