[OSRM-talk] Dynamic updates

[Schieferdecker, Dennis (ITI)]

Thank you for the link. I took at look at the paper. The authors seem to
simply flag nodes has having an incident and then scaling all adjoined
edges by a weight function when relaxing them during a query.
First, it should be noted that the graph representation of OSRM is an
edge-expanded graph where nodes correspond to OSM way segments and edges
to transitions between these segments (implicitly modelling turns).
Thus, flagging nodes as the authors do actually flags roads - which is
nice, but probably not intended by them.
Second and quite severe, by simply changing the edge weights of
precomputed Contraction Hierarchy you lose correctness. The resulting
route no longer has to represent a shortest path (even with respect to
the changed edge weights). This should not be that severe for local
streets -at least when increasing weights-, bu for main rodas the erros
can become huge.
To give a small example of what breaks: In a CH mutliple edges are
combined into a long shortcut. When the edge weight of one of the
constituting edges of the shortcut is changed, the shortcut is not
automatically changed, and still holds its original weight. Thus, you
would  have to keep track of which edges are shortcuts and whether they
have some flagged nodes. Doing this online during each query is too time
consuming. But you could do it offline in little time. Though then, the
quality of the hierarchy deteriortes and queries can become slow.
Furthermore, the results can still be faulty as the Contraction
Hierarchy is tuned to only contain required shortcuts (this is important
for performance!). But with changed edge weights some omitted shortcuts
might become necessary again and there is no easy way to repair this
problem.

So, to conclude. The results in the paper might seem reasonable to the
end user, but when you actually look at the numbers, you see them to be
wrong.

best regards
dennis schieferdecker

Emil Tin schrieb:
>
> This might be useful:
>
> Enhancing the OSRM Route Engine by Incorporating Real-Time Traffic Data:
> https://engineering.purdue.edu/~ychu/ee673/Projects.F12/comp2_rtengine_final.pdf
> <https://engineering.purdue.edu/%7Eychu/ee673/Projects.F12/comp2_rtengine_final.pdf>
>
>
> -Emil
>
>
>
> On Jun 18, 2013, at 18:20 , James Litton <litton.james at gmail.com
> <mailto:litton.james at gmail.com>> wrote:
>
>> > Hi James,
>> > 
>> > the basic Contraction Hierarchies approach is not well suited for
>> > dynamic updates unless they remain few before a complete
>> reprocessing is
>> > done. By now, there exist better algorithms to deal with changing edge
>> > costs like "Customizable Route Planning", though they face their own
>> > difficulties. You would have to replace the complete algorithmic
>> core of
>> > OSRM to incorporate these dynamic updates - and introducing dynamic
>> > updates that can also cope with addition/deletion of edges is still on
>> > another page.
>> > 
>> > Regarding the paper of Veit Batz, there seems to be available a much
>> > extended journal version as of recently. But using that method you
>> would
>> > still have to replace a lot of the OSRM algorithmic core. Also, memory
>> > consumption would likely be prohibitive high for the OSM world graph.
>> > That said time-dependent CH and your dynamic updates are two different
>> > problems. The first has average edge weights for each hour (or whatever
>> > granularity) of the day but does not allow for changing these weights
>> > for example when there is a traffic jam due to an accident. Slow
>> traffic
>> > due to rush hours can be modelled with time-dependency but not
>> irregular
>> > events.
>> > 
>> > By the way, what kind of traffic data do you have? Does this only
>> > include highways or inner city streets, too? And did you already try to
>> > aggregate travel-time functions from your data?
>> > 
>> > best regards
>> > 
>> > Dennis Schieferdecker
>>
>> Thanks, that's helpful. I now have a better understanding of what
>> challenges we would have to overcome with these two approaches.
>>
>> Our traffic data includes most of the road network that gets
>> significant traffic. So for a major city, it includes the inner city
>> streets, but in the suburbs the coverage is more sparse.
>>
>> We haven't created aggregate travel time functions yet, though we
>> have the historic data to do so. 
>>
>> I will read through the paper you mentioned.
>>
>> Thanks again,
>>
>> James 
>> _______________________________________________
>> OSRM-talk mailing list
>> OSRM-talk at openstreetmap.org <mailto:OSRM-talk at openstreetmap.org>
>> http://lists.openstreetmap.org/listinfo/osrm-talk
>
> ------------------------------------------------------------------------
>
> _______________________________________________
> OSRM-talk mailing list
> OSRM-talk at openstreetmap.org
> http://lists.openstreetmap.org/listinfo/osrm-talk
>