[OSRM-talk] State of the Art - Dynamic Routing

Matthias Loeks matthias at loeks.net
Wed Oct 14 10:18:48 UTC 2015

HI Patrick,

many thanks for your extensive answer and your interesting insights into 
the possibilities of achieving dynamic routing with CH.

While partial graph contraction may be an option for adding traffic data 
e.g. every 15 minutes, I'm afraid that it is still not an option if each 
individual request has to deal with e.g. different avoid areas.
Each request would then need a differently contracted/pre-processed 
graph... (impossible to pre-process on the fly)

Do you think there is any possibility to add some sort of "dynamic 
layer" on top of the contracted graph? Based on the information in this 
layer, certain edges in the contracted graph should have to be ignored 
by the routing algorithm.
Is such a thing possible and are there any plans to incorporate this (or 
similar concepts) into OSRM? Or is this just contrary to the CH approach 
and only solveable with a usual (slow) Dijkstra?

Thanks a lot for your help!


On 09.10.2015 15:37, Patrick Niklaus wrote:
> If you want to ingest dynamic data like traffic information into the
> routing, the main objective is to reduce pre-processing times so that
> the data will not be stale before you can actually serve requests from
> it.
> There are several ways you can achieve this:
> 1. Don't do any pre-processing.
>       In that case you just use a normal Dijkstra based search.
> 2. Do pre-processing but don't update it on traffic updates.
>      For example if you use something ALT-based you can calculate the
> heuristic using the average value and still yield good performance.
> 3. Re-run pre-processing and make it fast enough for your given update cycle.
>      The primary knobs you can turn there are:
>      - reduce the size of your dataset
>      - reduce the quality of the pre-processing
> We have been working on supporting 3 in OSRM with CH. We added a
> parameter to now contract the graph completely but only partially.
> This as dire consequences for query times however, depending on which
> quality factor you pick. If you contract the graph only 95% you will
> half your pre-processing time and increase the runtime 100x depending
> on your dataset size. Features like alternative searches, distance
> tables and similar will not work with this approach since it is much
> too slow.
> You can try partial contraction with `4.8.1` by using the `-k`
> parameter like `-k 0.95` will contract the graph only to 95%.
> Supporting real time traffic updates while still supporting
> continental sized networks is not exactly trivial, even more so if you
> support advanced features like turn restrictions. Consider the fact
> that just reading/writing such a graph from/to disk might take longer
> than your usual update cycle.
> We are working on making it easier to support this for smaller
> datasets though (like countries). Of course CH is really not suited
> that well for this task, but it enables you to use the same platform
> and process until CH can be replaced with alternative approaches.
> Best,
> Patrick
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstreetmap.org/pipermail/osrm-talk/attachments/20151014/767765a4/attachment.html>

More information about the OSRM-talk mailing list