摘要
因各种突发事件(交通事故、自然灾害等)造成道路中断的现象普遍存在,车辆在行驶的过程中并不具有道路中断的完全信息,只有行进到中断处时才获得道路中断的信息。本文就不完全信息(道路中断信息)下的交通网络最短路径关键边问题进行研究,首先定义了不完全信息下最短路径关键边的概念,其次给出了求解不完全信息下最短路径关键边的有效算法及其时间复杂性分析,然后结合城市道路网络给出了实际算例,比较分析了最短路径关键边、最长绕行路关键边和不完全信息下的最短路径关键边问题,指出了不完全信息下的最短路径关键边问题更具有实际意义。
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-Ⅱ）. Secondly, it presents an algorithm of computing the MVEP-Ⅱ 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-Ⅱ problem, the longest detour problem and the most vital edge problem, we conclude that MVEP-Ⅱ problem is more practically significant.
出处
《系统工程》
CSCD
北大核心
2006年第2期37-40,共4页
Systems Engineering
基金
国家杰出青年科学基金资助项目(70525004)
国家自然科学基金资助项目(70471035)
关键词
关键边
不完全信息
最短路径
算法
Most Vital Edge
Incomplete Information
Shortest Path
Algorithm
