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

针对大规模时变网络中的最短路径问题，我们提出了一种新的时变A*算法框架。特别是，在传统的基于地标的ALT方法的基础上，提出了一种动态更新有效地标集合的快速A*算法来寻找最优解。该算法不依赖于网络的图结构，可以应用于任何类型的实例。

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.