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 <matth...@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 <matth...@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@openstreetmap.org > https://lists.openstreetmap.org/listinfo/osrm-talk
_______________________________________________ OSRM-talk mailing list OSRM-talk@openstreetmap.org https://lists.openstreetmap.org/listinfo/osrm-talk