| 不完全信息下交通网络最短路径关键边问题 |
| |
| 引用本文： | 闫化海,徐寅峰. 不完全信息下交通网络最短路径关键边问题[J]. 系统工程, 2006, 24(2): 37-40 |
| |
| 作者姓名： | 闫化海 徐寅峰 |
| |
| 作者单位： | 1. 西安交通大学,管理学院,西安,陕西,710049
2. 西安交通大学,管理学院,西安,陕西,710049;机械制造系统工程国家重点实验室,西安,陕西,710049 |
| |
| 基金项目： | 国家杰出青年科学基金;中国科学院资助项目 |
| |
| 摘 要： | 因各种突发事件（交通事故、自然灾害等）造成道路中断的现象普遍存在，车辆在行驶的过程中并不具有道路中断的完全信息，只有行进到中断处时才获得道路中断的信息。本文就不完全信息（道路中断信息）下的变通网络最短路径关键边问题进行研究，首先定义了不完全信息下最短路径关键边的概念．其次给出了求解不完全信息下最短路径关键边的有效算法厦其时间复杂性分析，然后结合城市道路网络给出了实际算例，比较分析了最短路径关键边、最长绕行路关键边和不完全信息下的最短路径关键边问题，指出了不完全信息下的最短路径关键边问题更具有实际意义。
|
| 关 键 词： | 关键边 不完全信息 最短路径 算法 |
| 文章编号： | 1001-4098（2006）02-0037-04 |
| 收稿时间： | 2005-12-28 |
| 修稿时间： | 2005-12-28 |
The Most Vital Edge of the Shortest Path with Incomplete Information in Traffic Networks |
| |
| YAN Hua-hai,XU Yin-feng. The Most Vital Edge of the Shortest Path with Incomplete Information in Traffic Networks[J]. Systems Engineering, 2006, 24(2): 37-40 |
| |
| Authors: | YAN Hua-hai XU Yin-feng |
| |
| Abstract: | There are always many road blockages caused by unexpected events such as accident or disasters in traffic networks.The vehicle can not get the information of edge failure until it travels to the blockage edge.This paper aims at the most vital edge of the shortest path problem with the incomplete information.Firstly,this paper states the concept of the most vital edge of the shortest path with incomplete information(MVEP-II).Secondly,it presents an algorithm of computing the MVEP-II and analyses its time complexity,and then a numerical result of urban traffic networks is given.In the end,by comparing the realistic result of MVEP-II problem,the longest detour problem and the most vital edge problem,we conclude that MVEP-II problem is more practically significant. |
| |
| Keywords: | Most Vital Edge Incomplete Information Shortest Path Algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
