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:
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:
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:
Here’s the general idea for the so called Via-Method we implemented for finding alternative routes for a s -> t request:
s -> t
(s, c, t)
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.
Comment from Dalkeith on 29 May 2018 at 06:56
Brilliant work guys
Comment from 4004 on 30 May 2018 at 22:04
Candidate set size seems like something people might want to tweak (especially if they consider themselves to be better than the router).
Comment from Komяpa on 31 May 2018 at 07:53
So this means there are “beloved spots” that depend on how OSRM decides to process the graph?
Can these be tuned, or at least visualized, somehow? It may bring a tool that helps finding lost roads :)
Comment from daniel-j-h on 31 May 2018 at 08:48
There are “bottlenecks” in the road network which the partitioner detects. You can think of it as answering the question: which roads do I have to cut out of the road network to split it in half. Then we optimize for the minimum amount of roads to cut out and we balance the cuts to divide the road network “roughly” in half on every recursion level. This gives us roads we know cars have to go through when driving from one cell to the other.
Here are two maps from almost three years ago when I prototyped the partitioner and did these visualizations at a Geofabrik hack weekend in Karlsruhe. I remember we were wondering if the partitioner would cut old east and west Berlin in half.
The first one shows multiple cuts for Berlin. We run multiple cuts with a different slope in parallel and take the best cut on every level. Then we recurse down repeating the process in parallel for both sides.
Map - Berlin
And a single cut how to split California in half removing the minimum amount of roads.
Map - California
Note: this was from a prototype and probably does not match what you will currently get from our actual implementation in the Open Source Routing Machine.
Here is the current implementation:
You can definitely make use of these partitions for visualization or other purposes.
Also check out the Inertial Flow paper.