In the following I describe how we implemented reasonable alternative routes in the Open Source Routing Machine’s Multi-Level Dijkstra mode.

Final result: generating reasonable alternative routes incredibly efficiently

Our main goals when designing and implementing reasonable alternative routes were two-fold:

• provide reasonable alternative routes for end-users and use-cases such as generating many alternative routes letting users or developers decide between them (e.g. runner’s app, start and end is the same but provide different route each day), and
• guarantee for fast query times in the tens to lower hundreds of milliseconds to fit the Open Source Routing Machine’s trade-off of doing heavy pre-processing and then get incredibly fast exact responses

But what exactly do we mean by “reasonable” alternative routes? When we find a fastest route and compute alternatives these are the criteria we try to optimize for:

• the alternative route must not be x% longer than the fastest route; it also depends on the route’s length (think: 10 minutes vs 13 minutes is fine, 10 hours vs 13 hours is not)
• the alternative route must be x% different than the fastest route
• the alternative route must be “locally optimal”: x% of the detour is a fastest route itself (think: if the alternative route takes a different highway than the fastest route then you’re on the fastest route to your destination on this highway)

We can tune these thresholds to either make the alternatives look better or return more alternatives to the user.

There are subtle but essential differences in what we implemented compared to what users might expect:

• we do not specifically return a route e.g. using highways and a route avoiding highways. The avoid-x feature works indepedently of the alternatives implementation and users can make two requests: one avoiding highways and one using highways.
• we do not return a route e.g. based on fastest time and a route based on shortest distance. Our alternative routes are fastest routes taking traffic and other penalties into account. Different metrics still need different graphs (profiles) until support for multi-metric lands.

Here’s the general idea for the so called Via-Method we implemented for finding alternative routes for a s -> t request:

• start bi-directional Dijkstra forward search from s. Save all vertices
• start bi-directional Dijkstra reverse search from t. Save all vertices
• when both search spaces meet (and you usually would stop and reconstruct the shortest path) continue both searches “for a bit”
• intersect both vertex sets: these are the candidate vertices
• for all candidate vertices c a (potentially arbitrarily bad) alternative route is (s, c, t)
• evaluate and filter alternative routes based on stretch, overlap, how “reasonable” it is

Note: for different techniques check the extensive list of resources linked at the end.

Here is an example for the set of alternative routes you get initially without any pruning:

The main problem here is: the candidate set is huge and needs to be pruned for reasonable candidates.

In addition the filtering needs to be fast and happen gradually: to stay within the time bounds we can not e.g. extract and evaluate the detailed path of every single alternative candidate. We need to filter alternative candidates down step by step, with cheap high-level criteria first, and expensive detailed criteria last.

For the initial via-vertices we make use of the Inertial Flow graph partition (osrm-partition). The graph partitioner recursively (and fully in parallel) cuts the graph “in half” using Dinic’s algorithm for the min-cuts.

Here is the search space we then take via-vertices from to construct alternative route candidates. We know all routes from s to t have to go through these candidate nodes due to the partition:

When we then use the partitioner’s lowest level cells to filter out alternative route candidates that are “too similar” we already can see improvements:

We then focus on local optimality. The overall problem we try to solve is as follows: we could pick a via node for which the alternative path would make an unreasonable detour. Think of picking a via node which leads to a route leaving the highway and then immediately going onto it again.

To guarantee for local optimality around the via-vertices we take a look at the two sub-paths around a via node and use the forward and reverse heaps to check if they are optimal.

Local sub-path is optimal:

Only then we unpack the remaining alternative candidates for their detailed paths and run extensive high-quality evaluation checks resulting in these results:

Last but not least all of the above has to happen on all pair-wise alternative routes: when we return multiple alternative routes they not only have to be reasonable compared to the shortest path but to all other alternative routes themselves, too.

Give it a try, happy to hear your feedback!

I would like to thank Moritz Kobitzsch who literally has a PhD in alternative routes and was sitting across my desk guiding this adventure!

If you are interested I encourage you to take a look at the original ticket, pull request and implementation. Also check out the extensive list of resources below for further details.

Resources:

• Original ticket
• Original pull request
• Alternative Route Techniques, Moritz Kobitzsch
• Candidate Sets for Alternative Routes in Road Networks
• Algorithmen für Routenplanung: Alternativrouten (requires learning German first)
• Intertial Flow
• Interactive search space exploration