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. © 2009 Springer Science+Business Media, LLC.
https://doi.org/10.1007/s00453-009-9341-0Cite as:
@article{Delling_2009,
doi = {10.1007/s00453-009-9341-0},
url = {https://doi.org/10.1007%2Fs00453-009-9341-0},
year = 2009,
month = {jul},
publisher = {Springer Science and Business Media {LLC}},
volume = {60},
number = {1},
pages = {60--94},
author = {Daniel Delling},
title = {Time-Dependent {SHARC}-Routing},
journal = {Algorithmica}
}