There is an obviously passable route, but OSRM returns "NoRoute."

[qimj]

I am using OSRM for route. From the OpenStreetMap, there is clearly a passable road, but the OSRM's response to the query is "NoRoute."

here is my osm data after simplify(.osm file is not supported and i changed it's suffix to txt): map.txt and i preprocess osm file with osrm-extract bike.lua/osrm-contract

codes for calling OSRM: `

EngineConfig config;
config.algorithm = EngineConfig::Algorithm::CH;
config.use_shared_memory = false;
config.storage_config = storage::StorageConfig("map.osrm");

OSRM const osrm {config};
RouteParameters params;

params.coordinates.emplace_back(util::FloatLongitude{106.6963952}, util::FloatLatitude{10.7288943});
params.coordinates.emplace_back(util::FloatLongitude{106.6937228}, util::FloatLatitude{10.7287811});
params.exclude.emplace_back("toll");

engine::api::ResultT result = json::Object();
const auto status = osrm.Route(params, result);

my env: osrm: 5.27.1 MacOs 11.7.9

However, I've noticed a very peculiar phenomenon: if I remove any one of the roads mentioned in 1, 2, and 3, OSRM will return the expected result.It appears that the topological structure of the road network is affecting the results of OSRM.

[qimj]

i debug the OSRM codes and found some clues.

here is node of routing query_graph:

edges of routing query_graph:

• 2 - 0
• 2 - 1
• 3 - 5
• 3 - 11
• 4 - 7
• 5 - 9
• 6 - 9
• 7 - 10
• 8 - 4
• 8 - 5
• 8 - 6
• 10 - 9
• 11 - 6

Bidirectional Dijkstra search is like this: init forward(node 4) reverse(node 11, 6)

• forward: delete node 4, add node 7 -> delete node 7
• reverse: delete node 11 -> delete node 6, add node 9 -> delete node 9

it seemed that both forward and reverse searches access the road below, but were eventually prohibited due to a toll. Meanwhile, the path above was never accessed and this caused NoRoute

[mjjbell]

Does this work correctly if you remove the exclude=toll parameter?

[mjjbell]

Without that parameter, it does the right thing on the demo server: http://map.project-osrm.org/?z=18&center=10.728346%2C106.695517&loc=10.7288943%2C106.6963952&loc=10.7287811%2C106.6937228&hl=en&alt=0&srv=1

So I'm interested in what you're seeing in this case.

[qimj]

Does this work correctly if you remove the exclude=toll parameter?

yes，it gives below route result if i remove the 'exclude=toll' parameter

But my scenario is to bypass toll, and I also made the following settings in bike.lua:

classes = Sequence {
    'toll', 'motorway', 'ferry', 'restricted', 'tunnel'
},

excludable = Sequence {
    Set {'toll'},
    Set {'motorway'},
    Set {'ferry'},
    Set {'toll', 'motorway'},
    Set {'toll', 'ferry'},
    Set {'motorway', 'ferry'},
    Set {'toll', 'motorway', 'ferry'},
}

[mjjbell]

Thanks, I'm able to reproduce the problem. Will investigate further.

[mjjbell]

So far I can see that:

• It works as expected for the MLD algorithm
• It works as expected on your snippet (even if it doesn't for you).

This leads me to believe that it's a similar problem to #5969, where dynamic changes can expose random asymmetries in the contraction hierarchy forward/reverse graphs that can lead to routes not being found.

I didn't fully investigate this as I assumed I was only seeing it in hypothetical test scenarios, but now we have a real-world example, it's worth investigating further.

If feasible, you can switch to the MLD algorithm as an immediate workaround until a fix is available.