OpenStreetMap

Alternative Routes

Posted by daniel-j-h on 25 May 2018 in English (English)

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:

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). Great work!

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.

Cuts in Berlin

Map - Berlin

And a single cut how to split California in half removing the minimum amount of roads.

Cuts in California

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.

Login to leave a comment