search

Project-OSRM / osrm-backend

Open Source Routing Machine - C++ backend
http://map.project-osrm.org
BSD 2-Clause "Simplified" License
6.29k stars 3.32k forks source link

Alternatives: take road importance into account for via candidates #4265

Closed daniel-j-h closed 1 month ago

daniel-j-h commented 7 years ago

Splitting out into a ticket from https://github.com/Project-OSRM/osrm-backend/pull/4047 (please read for context).

The alternatives feature on mld generates a lot of via candidates and then filters them based on cheap filtering first and more and more expensive filtering following.

What we should do is take the road importance into account early on in the filtering to discard via candidate nodes that are unimportant roads (edge-based graph: nodes are roads):

https://github.com/Project-OSRM/osrm-backend/blob/c1cb3ebff7471d6f34ac8a345115717e955a7554/src/engine/routing_algorithms/alternative_path_mld.cpp#L92-L112

Even though we use the mld stepping to walk over border nodes filtering by road importance would be a cheap filter and discard unluckily picked via candidates already early on.

What we need to do is serialize out a bit vector which tells us for every node if the road passes RoadClassification::IsImportantRoad(node) or not. Serlialization need to happen in osrm-extract then deserialization and exposing road importance per node in the datafacades again.

github-actions[bot] commented 2 months ago

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