[OSRM-talk] Dynamic updates

[James Litton]

Thanks. Their approach does seem to deal with particular incidents and then
scale the edge weight based on their relative severity. I wonder if those
changes are limited enough (compared to overall road speeds) that the CH is
able to work without as much adverse effect. That or something like that
was the approach I was originally thinking of taking (updating the graph in
memory with updated speed/weights) but I had some doubts about it. I'm
really appreciative that I can run this by the list before going full tilt.

James


On Tue, Jun 18, 2013 at 1:49 PM, Emil Tin <emil at tin.dk> wrote:

>
> 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
>
>
> -Emil
>
>
>
> On Jun 18, 2013, at 18:20 , James Litton <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
> http://lists.openstreetmap.org/listinfo/osrm-talk
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstreetmap.org/pipermail/osrm-talk/attachments/20130618/b0cf8416/attachment-0001.html>