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 <[email protected]> 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 <[email protected]> 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
> [email protected]
> https://lists.openstreetmap.org/listinfo/osrm-talk
_______________________________________________
OSRM-talk mailing list
[email protected]
https://lists.openstreetmap.org/listinfo/osrm-talk
