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.
