mjjbell
commented
6 months ago Sub-issue 1 - Via routes that support u-turns don't need to force loops
As mentioned above, loop forcing is needed for multiple via-waypoint routes, where we need to consider the costs in the previous steps to calculate the optimal path for the subsequent step.
However, for via routes that support u-turns at waypoints, we can treat each sub-route independently and sum them together, which means only the consideration of negative cost paths is needed with regards to the downstream edge criteria.
This means we can remove the calculation of nodes requiring forced loops here. https://github.com/Project-OSRM/osrm-backend/blob/7ebd21f39e32640e0d40b893d228350f218085ad/include/engine/routing_algorithms/shortest_path_impl.hpp#L67-L68 I believe the loops are calculated currently because of the way this plugin was previously implemented, but is now redundant.
A bit of additional refactoring is required as the cost of the previous steps is being passed in when initializing the forward heap weights. However, this is a constant value for all source nodes, so can be pulled out and added later.
DennisOSRM
Issue
As part of investigating negative route durations discussed in #5855, I've discovered the logic around "forcing loops" during graph searches plays an important role, and requires some improvements.
I'll use this issue to describe the current behaviour and outline the changes needed.
Background
OSRM converts the OSM node-based graph (NBG) into an edge-based graph (EBG) for performing routing searches.
A node in the EBG represents a compressed edge from the NBG. An edge in the EBG represents a turn from one NBG compressed edge onto another.
OSRM also generates a reverse graph for searching backwards from the target (we'll ignore the algorithm optimization details for now).
The edge weight in the EBG is the cost of traversing the NBG source edge and the accompanying turn cost onto the NBG target. As an example, a simple one-way road loop would have the following edge-based search graph and edge weights.
Snapping Input Locations
OSRM takes the waypoint input locations and snaps them to a position on the OSM geometry.
The EBG nodes representing OSM edges that the locations were snapped to are set as the source and target of the graph search.
Running the search
To get the correct result when running the search, we have to consider that the EBG edges include the cost of the entire NBG edge geometry, whereas our input location will be snapped onto a position on the edge geometry, and so only performs a partial traversal of the first and last edge.
In the forward graph, we need to negatively offset the cost from the start of the geometry to the source position, as any search path from this EBG node will include the entire cost of the geometry traversal.
Conversely, the reverse graph needs to positively offset the cost from the start of the geometry to the target position, as none of the cost of the EBG geometry represented by the NBG node will be included in any reverse search path.
Making the current example more concrete, lets assign each OSM edge to have edge cost 10 and turn cost 1, The source is snapped to edge_1 with offset cost of 1, target snapped to edge_3 with offset cost 2.
Running the forward and reverse searches with the initial negative and positive offsets, will lead to the correct route cost being found.
Edge cases
For the most part, this use of source and target offsets works for calculating the correct route cost.
The main edge-case is when the source and target snap to the same edge geometry. If source is "downstream" from the target, we would compute a negative route cost.
Assuming we don't allow negative edge weights (OSRM doesn't), this is easy to handle. If the sum of forward and backward costs is negative, and we see this at a source or target node, we know we're dealing with this edge-case.
The solution: continue the search in both directions from this node.
Forcing loops
The more complicated edge-case is when dealing with routes with via-waypoints. In cases where we don't allow u-turns, we need to include the route cost up to the current waypoint to correctly identify the optimal route to the subsequent waypoint.
This means that even if the source is downstream of the target, the initial starting cost will most likely be positive, as the cost of the previous section of the route will be larger than the negative offset. Therefore, the negative search cost check is insufficient, we need something that "forces a search" at this node.
The criteria for identifying whether we need to "force a search" is simple enough
And this is what OSRM does. It identifies the nodes that match these critieria as a pre-search step
https://github.com/Project-OSRM/osrm-backend/blob/7ebd21f39e32640e0d40b893d228350f218085ad/src/engine/routing_algorithms/routing_base.cpp#L6-L18
and forces a search on these nodes during the search phase. https://github.com/Project-OSRM/osrm-backend/blob/7ebd21f39e32640e0d40b893d228350f218085ad/include/engine/routing_algorithms/routing_base_mld.hpp#L405-L409
https://github.com/Project-OSRM/osrm-backend/blob/7ebd21f39e32640e0d40b893d228350f218085ad/include/engine/routing_algorithms/routing_base_ch.hpp#L126-L130
https://github.com/Project-OSRM/osrm-backend/blob/7ebd21f39e32640e0d40b893d228350f218085ad/include/engine/routing_algorithms/routing_base.hpp#L86-L92
(The "force loop" name appears to come from the original solution for the Contraction Hierarchy algorithm, where in addition to continuing the search, you would need to consider loop edges back to the node. The name appears to have transferred to the MLD implementation, event though it has no edge loops.)
This concludes the background understanding. Next I'll outline the issues identified with the current implementation.