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

Daniel Patterson daniel at mapbox.com
Thu Oct 15 19:37:38 UTC 2015


Matthias,

  For small networks (city-sized), many algorithms can be used and have performance good enough for interactive queries.  OSRM aims to offer fast queries for *global* road networks, but the price is that a lot of pre-processing has to be done. If you're just looking at smaller regions (like city-sized networks), you can often fully re-process with OSRM in just a few minutes in most cases.  Scaling fast updates and fast queries to a global-scale road network is an active area of research.
  
  There is a very good overview paper (from April 2015) of general routing problems and known solutions here, and it's not too heavy on the math:

    http://arxiv.org/abs/1504.05140 <http://arxiv.org/abs/1504.05140>

  I would recommend spending some time reading it, it will really help you understand the state-of-the-art and the trade-offs in time/space.  There is also quite a lot of reading material in German here:  http://i11www.iti.uni-karlsruhe.de/teaching/sommer2015/routenplanung/index <http://i11www.iti.uni-karlsruhe.de/teaching/sommer2015/routenplanung/index>  

daniel


> On Oct 15, 2015, at 8:38 AM, Matthias Loeks <matthias at loeks.net> wrote:
> 
> Patrick,
> 
> thanks again for your explanations and opinions about dynamic updates to the graph.
> 
> Being aware of the complex scenario that dynamic updates introduce, I'd still like to think about the great features that it would allow for!
> Implementing per-request dynamics to some extent would enable use cases like traffic-based routing, disaster routing (avoiding locked down roads), truck routing ... and much more.
> Anything of these topics on the OSRM roadmap? ;-)
> 
> Of course, the "how" (to implement) is crucial here... Due to my lack of knowledge about both CH and C++, I cannot offer help unfortunately.
> I thought it has to be possible somehow, since GraphHopper offers this traffic data integration thing [1], which might show the way how to do this?
> 
> Best,
> Matthias
> 
> --
> [1] - https://github.com/karussell/graphhopper-traffic-data-integration
> 
> 
> On 14.10.2015 13:05, Patrick Niklaus wrote:
>>> certain edges in the contracted graph should have to be ignored
>> 
>> If that set of 'dynamic edges' is known in advance you could use a
>> technique that does not contract nodes adjacent to that edges. This
>> would mean for those edges you could update the weights without
>> re-contraction. On the pre-processing side adding support for this is
>> quite trivial, essentially it is a variation of partial contraction.
>> However adding an interface for
>> updating the graph would be new. The main problem there is that you
>> either add some sort of "override set" to the query graph, or have a
>> copy for each graph for each thread.
>> The first implementation will incur high penalties on query time (you
>> would need an additional check every time you read the edge weight),
>> the second approach would have a high memory usage.
>> 
>> Currently we don't plan to implement this. But if anyone likes to give
>> it a try, I will of course help were I can.
>> 
>> Best,
>> Patrick
>> 
>> On Wed, Oct 14, 2015 at 12:18 PM, Matthias Loeks <matthias at loeks.net> wrote:
>>> 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!
>>> 
>>> Cheers,
>>> Matthias
>>> 
>>> 
>>> 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
> 
> _______________________________________________
> OSRM-talk mailing list
> OSRM-talk at openstreetmap.org
> https://lists.openstreetmap.org/listinfo/osrm-talk

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstreetmap.org/pipermail/osrm-talk/attachments/20151015/47802f34/attachment.html>


More information about the OSRM-talk mailing list