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