[OSRM-talk] Dynamic updates

Schieferdecker, Dennis (ITI) dennis.schieferdecker at kit.edu
Tue Jun 18 15:35:49 UTC 2013


James Litton schrieb:
> Hello,
>
> I would like to modify OSRM so that it is capable of receiving dynamic
> updates to its edge weight (I have access to real time speed data).
> This is work we would like to contribute back to the project.
>
> So the first question is, is this feasible? 
>
> We have speed data on all of the major roads in the United States and
> it is updated once every few minutes. I read the paper, "Exact Routing
> in Large Road Networks Using Contraction Hierarchies" and there was
> some mention of accommodating dynamic updates, but my intuition is
> that this would potentially modify too much of the graph to be done
> reasonably quickly. I'm reluctant to do significant work figuring out
> how to shoehorn this capability into OSRM if it's a bad idea from the
> onset.
>
> It may make more sense to follow the approach in the the Minimum
> Time-Dependent Travel Times with CH by G. Veit Batz et al, but I'm
> still trying to make sense of it. In this case, if it were to be used
> in OSRM the TTF could perhaps make use of the lua extensions. To be
> honest I'm not very deep into understanding that paper yet.
>
> Anyway, if this is a capability that I could add to OSRM, does anyone
> have any pointers for where to start or what approach to take?
>
> Thanks
>
> James
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



More information about the OSRM-talk mailing list