Implementing an alt algorithm for large-scale time-dependent networks

ALT algorithms have been successfully applied to time-independent transportation networks but applying it to time-dependent transportation networks is not straightforward. The difficulty arises when a driver has to recalculate the shortest path to his/her destination at the time of hisÆer departure by considering the effect of other vehicles on the travel time. While this doesn't pose a substantial negative computational effect when the number of drivers is small, this is crucial when simulating large-scale time-dependent transportation networks with millions of vehicles and a very large time horizon. This is called the time-dependent shortest path (TDSP) problem. Hence, we are motivated in reducing the shortest path query times. By explicitly choosing a region in the network to select a landmark from using a weighted variant of the avoid landmark selection algorithm, we are able to reduce the shortest path query times without increasing the landmark generation times and space (memory) consumption.