Fast algorithm for large-scale time-dependent shortest path problem

点击翻译按钮获取中文摘要

We developed a new time-dependent A* algorithm framework for finding a shortest path in a large-scale time-dependent network. In particular, based on the conventional ALT method that uses landmarks, we developed a fast A* algorithm for finding an optimal solution with dynamical updating of the set of the effective landmarks. This algorithm can be applied to any kind of instances since it does not dependent on the graph structure of the network.