不完全信息下交通网络的关键路径问题  

Most Shortest Vital-path Problem with Incomplete Information on Traffic Network

作　　者：刘明[1] 徐寅峰[1] 杜源江[1] 肖鹏[1] 

机构地区：[1]西安交通大学管理学院,陕西西安710049

出　　处：《系统工程》2006年第12期16-20,共5页Systems Engineering

基　　金：国家杰出青年科学基金资助项目(70525004)

摘　　要：在交通运输中,车辆总是选择最短路径行驶。然而因各种突发事件(交通事故、自然灾害等)造成道路中断的现象普遍存在,车辆在行驶的过程中并不具有道路中断的完全信息,只有行进到中断处时才获得道路中断的信息,此时原来的最短路径就很可能失去其最优性,从而增加交通运输的成本。为了解决这一问题,本文提出了不完全信息下交通网络的关键路径问题,给出了相应的求解算法,并分析了其时间复杂性,然后结合实际交通网络给出算例,最后指出这对提高交通运输的效率更具有实际意义。Usually, the vehicles take the shortest path as their optimum way when dealing with transportation. However, due to the various outbursts of the traffic jams and natural disasters leading to blockages on the roads, the vehicles don＇t have the complete information about the blockages until they arrive at the blocked sites. On this occasion, the original optimum path will not be the optimum one any longer, leading to the increase in the transportation cost. In order to solve this problem caused by the happening of the unknown traffic jams, this paper puts forward th.e vital-path problem under incomplete information ,and gives the Algorithm to .solve it. Meanwhile,this paper analyzes the time complexity of the Algorithm. The problem this paper concerning is of great significance to deal with the practical transportation problems.

关 键 词：关键边 不完全信息 关键路径 算法 

分 类 号：C931[经济管理—管理学] O221[理学—运筹学与控制论]