[OSRM-talk] Dynamic updates

Wed Jun 19 13:19:31 UTC 2013

When I was considering a similar approach, if I interpreted things
correctly, you'd have to do some kind of re-contraction of the affected
nodes, which could then cascade throughout the graph. Doing this in a way
that the contraction only ends up occurring in a small subset in the graph
when the updates are more significant and carefully enough that the
correctness of the hierarchy is preserved seems difficult to me, at least
assuming you want it to be an operation that occurs quickly. I don't
_think_ you'd have to reorder the nodes though for correctness.

I'm exploring other approaches right now because I'm not very optimistic
about the above.

James

On Wed, Jun 19, 2013 at 3:31 AM, Emil Tin <ZF0F at tmf.kk.dk> wrote:

>
> Thanks for looking into the paper. More work ahead then :-)
>
> Med venlig hilsen
>
> Emil Tin
> IT- og Processpecialist
> Trafikdesign
> _______________________________
> KØBENHAVNS KOMMUNE
> Teknik- og Miljøforvaltningen
> Center for Trafik
>
> Islands Brygge 37 Vær. 118
> Postboks 450
> 2300 København S
>
> Mobil
> +45 2369 5986
> Email
> zf0f at tmf.kk.dk
> EAN
> 5798009493149
>
>
> -----Oprindelig meddelelse-----
> Fra: Schieferdecker, Dennis (ITI) [mailto:dennis.schieferdecker at kit.edu]
> Sendt: 19. juni 2013 09:25
> Til: osrm-talk at openstreetmap.org
> Emne: Re: [OSRM-talk] Dynamic updates
>
> 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 Trafﬁc Data:
> > https://engineering.purdue.edu/~ychu/ee673/Projects.F12/comp2_rtengine
> > _final.pdf
> > <https://engineering.purdue.edu/%7Eychu/ee673/Projects.F12/comp2_rteng
> > ine_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
> >
>
>
> _______________________________________________
> OSRM-talk mailing list
> 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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstreetmap.org/pipermail/osrm-talk/attachments/20130619/925f6ffe/attachment.html>