时间依赖的网络中最小时间路径算法

Shortest Path Algorithm in Time-Dependent Networks

时间依赖的网络与传统网络模型相比更具有现实意义 ,具有广泛的应用领域 .交通网络和通信网络可以抽象为时间依赖的网络模型 .当模型中弧的长度是时间依赖的变量 ,最短路径问题的求解变得非常困难 ,早期的研究者通过具体的网络实例认识到传统最短路径算法在这种情况下是不正确的 ,因此给出限制性条件使得传统最短路径算法是有效的 .该文从最短路径算法的理论基础入手 ,从理论上证明了传统最短路径算法 ,如 Dijkstra算法和标号设置算法 ,在时间依赖的网络上不能有效地求解最短路径问题 ;并且 ,在没有任何限制性条件下 ,给出了时间依赖的网络模型、理论基础、求解最小时间路径的优化条件和 SPTDN算法 ,从理论上证明了 SPTDN算法的正确性 .算法的实验结果是正确的 .

The time dependent network shortest path problems are generalized from and more realistic than the classical shortest path problem, and are applicable in a wide range of fields. Many transportation and communication systems can be represented by networks with travel times that are time dependent, which has lead to a need for extensive research on path planning in time dependent networks. When the arc length of a system model is time dependent, the problem becomes considerably more difficult. Standard shortest path algorithms, such as the Dijkstra algorithm, are not valid in this circumstance, since travel times are now time dependent variables. Early researchers have found the incorrectness of the traditional shortest path algorithms by presenting examples in the time dependent networks and have afterwards given conditions to make the classical shortest path algorithms valid in the time dependent networks. In this paper, based on the theoretical foundations of traditional algorithmic approaches for solving shortest path problems, we theoretically prove that the traditional shortest algorithms, such as the label setting algorithms and the famous Dijkstra algorithm, can not find the least time path in time dependent networks; and by establishing the theoretical foundations and the algorithms we solve the shortest path problems in the time dependent networks without giving any conditions. We construct time dependent network models, describe shortest path problems in time dependent networks, give the properties of shortest path problems, and present theoretical foundations and the optimality conditions for solving the least time path problems in time dependent networks. Next, we present the SPTDN algorithm for solving least time path problems in various scenarios, and theoretically prove that the SPTDN algorithm is valid in time dependent networks. The SPTDN algorithm solves the shortest path problem with computational complexity O(nmM 2C) in time dependent networks. We then implement the SPTDN algorithm with micro computer and obtain the correct experimental results. Finally, we illustrate how the algorithm can be applied to solve real world problems with time dependent properties.