首页 | 本学科首页   官方微博 | 高级检索  
     

时间依赖的网络中最小时间路径算法
引用本文:谭国真,高文.时间依赖的网络中最小时间路径算法[J].计算机学报,2002,25(2):165-172.
作者姓名:谭国真  高文
作者单位:1. 大连理工大学计算机科学与工程系,大连,116024
2. 中国科学院计算技术研究所,北京,100080,哈尔滨工业大学计算机科学与工程系,哈尔滨,150001
基金项目:教育部科学技术重点项目 (990 2 5 ),全国高等学校骨干教师基金项目,辽宁省自然科学基金项目 (9810 2 0 0 10 4)资助
摘    要:时间依赖的网络与传统网络模型相比更具有现实意义,具有广泛的应用领域,交通网络和通信网络可以抽象为时间依赖的网络模型,当模型中弧的工度是时间依赖的变量,最短路径问题的求解变得非常困难,早期的研究者通过具体的网络实例认识到传统最短路径算法在这种情况下是不正确的,因此给出限制性条件使得传统最短路径算法是有效的。该文从最短路径算法的理论基础入手,从理论上证明了传统最短路径算法,如Dijkstra算法和标号设置算法,在时间依赖的网络上不能有效地求解最短路径问题,并且,在没有任何限制性条件下,给出了时间依赖的网络模型,理论基础,求解最小时间路径的优化条件和SPTDN算法,从理论上证明了SPTDN算法的正确性,算法的实验结果是正确的,最后给出了时间依赖的网络应用实例。

关 键 词:网络优化  时间依赖  最小时间路径算法  计算机网络
修稿时间:2000年9月13日

Shortest Path Algorithm in Time-Dependent Networks
TAN Guo Zhen GAO Wen ,.Shortest Path Algorithm in Time-Dependent Networks[J].Chinese Journal of Computers,2002,25(2):165-172.
Authors:TAN Guo Zhen GAO Wen  
Affiliation:TAN Guo Zhen 1) GAO Wen 2),3) 1)
Abstract: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.
Keywords:network optimality  shortest paths  time  dependent networks  algorithms
本文献已被 CNKI 维普 万方数据 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号