caa a22 4500 445804254 CHVBK 20180317145152.0 cr unu---uuuuu 170323e20110501xx s 000 0 eng 10.1007/s00453-009-9341-0 doi (NATIONALLICENCE)springer-10.1007/s00453-009-9341-0 Delling Daniel Universität Karlsruhe (TH), 76128, Karlsruhe, Germany aut Time-Dependent SHARC-Routing [Elektronische Daten] [Daniel Delling] In recent years, many speed-up techniques for Dijkstra's algorithm have been developed that make the computation of shortest paths in static road networks a matter of microseconds. However, only few of those techniques work in time-dependent networks which, unfortunately, appear quite frequently in reality: Roads are predictably congested by traffic jams, and efficient timetable information systems rely on time-dependent networks. Hence, a fast technique for routing in such networks is needed. In this work, we present an efficient time-dependent route planning algorithm. It is based on our recently introduced SHARC algorithm, which we adapt by augmenting its basic ingredients such that correctness can still be guaranteed in a time-dependent scenario. As a result, we are able to efficiently compute exact shortest paths in time-dependent continental-sized transportation networks, both of roads and of railways. It should be noted that time-dependent SHARC was the first efficient algorithm for time-dependent route planning. Springer Science+Business Media, LLC, 2009 Algorithm engineering nationallicence Graph algorithms nationallicence Time-dependent shortest paths nationallicence Timetable information nationallicence Algorithmica Springer-Verlag 60/1(2011-05-01), 60-94 0178-4617 60:1<60 2011 60 453 https://doi.org/10.1007/s00453-009-9341-0 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-009-9341-0 text/html Onlinezugriff via DOI NATIONALLICENCE 100 1- Delling Daniel Universität Karlsruhe (TH), 76128, Karlsruhe, Germany aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 60/1(2011-05-01), 60-94 0178-4617 60:1<60 2011 60 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer