<html><head><meta http-equiv="Content-Type" content="text/html charset=us-ascii"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><div class="">Matthias,</div><div class=""><br class=""></div><div class="">  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.</div><div class="">  </div><div class="">  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:</div><div class=""><br class=""></div><div class="">    <a href="http://arxiv.org/abs/1504.05140" class="">http://arxiv.org/abs/1504.05140</a></div><div class=""><br class=""></div><div class="">  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:  <a href="http://i11www.iti.uni-karlsruhe.de/teaching/sommer2015/routenplanung/index" class="">http://i11www.iti.uni-karlsruhe.de/teaching/sommer2015/routenplanung/index</a>  </div><div class=""><br class=""></div><div class="">daniel</div><div class=""><br class=""></div><br class=""><div><blockquote type="cite" class=""><div class="">On Oct 15, 2015, at 8:38 AM, Matthias Loeks <<a href="mailto:matthias@loeks.net" class="">matthias@loeks.net</a>> wrote:</div><br class="Apple-interchange-newline"><div class="">Patrick,<br class=""><br class="">thanks again for your explanations and opinions about dynamic updates to the graph.<br class=""><br class="">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!<br class="">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.<br class="">Anything of these topics on the OSRM roadmap? ;-)<br class=""><br class="">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.<br class="">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?<br class=""><br class="">Best,<br class="">Matthias<br class=""><br class="">--<br class="">[1] - <a href="https://github.com/karussell/graphhopper-traffic-data-integration" class="">https://github.com/karussell/graphhopper-traffic-data-integration</a><br class=""><br class=""><br class="">On 14.10.2015 13:05, Patrick Niklaus wrote:<br class=""><blockquote type="cite" class=""><blockquote type="cite" class="">certain edges in the contracted graph should have to be ignored<br class=""></blockquote><br class="">If that set of 'dynamic edges' is known in advance you could use a<br class="">technique that does not contract nodes adjacent to that edges. This<br class="">would mean for those edges you could update the weights without<br class="">re-contraction. On the pre-processing side adding support for this is<br class="">quite trivial, essentially it is a variation of partial contraction.<br class="">However adding an interface for<br class="">updating the graph would be new. The main problem there is that you<br class="">either add some sort of "override set" to the query graph, or have a<br class="">copy for each graph for each thread.<br class="">The first implementation will incur high penalties on query time (you<br class="">would need an additional check every time you read the edge weight),<br class="">the second approach would have a high memory usage.<br class=""><br class="">Currently we don't plan to implement this. But if anyone likes to give<br class="">it a try, I will of course help were I can.<br class=""><br class="">Best,<br class="">Patrick<br class=""><br class="">On Wed, Oct 14, 2015 at 12:18 PM, Matthias Loeks <<a href="mailto:matthias@loeks.net" class="">matthias@loeks.net</a>> wrote:<br class=""><blockquote type="cite" class="">HI Patrick,<br class=""><br class="">many thanks for your extensive answer and your interesting insights into the<br class="">possibilities of achieving dynamic routing with CH.<br class=""><br class="">While partial graph contraction may be an option for adding traffic data<br class="">e.g. every 15 minutes, I'm afraid that it is still not an option if each<br class="">individual request has to deal with e.g. different  avoid areas.<br class="">Each request would then need a differently contracted/pre-processed graph...<br class="">(impossible to pre-process on the fly)<br class=""><br class="">Do you think there is any possibility to add some sort of "dynamic layer" on<br class="">top of the contracted graph? Based on the information in this layer, certain<br class="">edges in the contracted graph should have to be ignored by the routing<br class="">algorithm.<br class="">Is such a thing possible and are there any plans to incorporate this (or<br class="">similar concepts) into OSRM? Or is this just contrary to the CH approach and<br class="">only solveable with a usual (slow) Dijkstra?<br class=""><br class="">Thanks a lot for your help!<br class=""><br class="">Cheers,<br class="">Matthias<br class=""><br class=""><br class="">On 09.10.2015 15:37, Patrick Niklaus wrote:<br class=""><br class="">If you want to ingest dynamic data like traffic information into the<br class="">routing, the main objective is to reduce pre-processing times so that<br class="">the data will not be stale before you can actually serve requests from<br class="">it.<br class=""><br class="">There are several ways you can achieve this:<br class="">1. Don't do any pre-processing.<br class="">      In that case you just use a normal Dijkstra based search.<br class="">2. Do pre-processing but don't update it on traffic updates.<br class="">     For example if you use something ALT-based you can calculate the<br class="">heuristic using the average value and still yield good performance.<br class="">3. Re-run pre-processing and make it fast enough for your given update<br class="">cycle.<br class="">     The primary knobs you can turn there are:<br class="">     - reduce the size of your dataset<br class="">     - reduce the quality of the pre-processing<br class=""><br class="">We have been working on supporting 3 in OSRM with CH. We added a<br class="">parameter to now contract the graph completely but only partially.<br class="">This as dire consequences for query times however, depending on which<br class="">quality factor you pick. If you contract the graph only 95% you will<br class="">half your pre-processing time and increase the runtime 100x depending<br class="">on your dataset size. Features like alternative searches, distance<br class="">tables and similar will not work with this approach since it is much<br class="">too slow.<br class=""><br class="">You can try partial contraction with `4.8.1` by using the `-k`<br class="">parameter like `-k 0.95` will contract the graph only to 95%.<br class=""><br class="">Supporting real time traffic updates while still supporting<br class="">continental sized networks is not exactly trivial, even more so if you<br class="">support advanced features like turn restrictions. Consider the fact<br class="">that just reading/writing such a graph from/to disk might take longer<br class="">than your usual update cycle.<br class=""><br class="">We are working on making it easier to support this for smaller<br class="">datasets though (like countries). Of course CH is really not suited<br class="">that well for this task, but it enables you to use the same platform<br class="">and process until CH can be replaced with alternative approaches.<br class=""><br class="">Best,<br class="">Patrick<br class=""></blockquote></blockquote><br class="">_______________________________________________<br class="">OSRM-talk mailing list<br class=""><a href="mailto:OSRM-talk@openstreetmap.org" class="">OSRM-talk@openstreetmap.org</a><br class="">https://lists.openstreetmap.org/listinfo/osrm-talk<br class=""></div></blockquote></div><br class=""></body></html>