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

作者：刘明; 徐寅峰; 杜源江; 肖鹏

来源：系统工程, 2006, (12): 16-20.

• 关键边
• 不完全信息
• 关键路径
• 算法 Most Vital Edge
• Incomplete Information
• Vital Path
• Algorithm

在交通运输中,车辆总是选择最短路径行驶。然而因各种突发事件(交通事故、自然灾害等)造成道路中断的现象普遍存在,车辆在行驶的过程中并不具有道路中断的完全信息,只有行进到中断处时才获得道路中断的信息,此时原来的最短路径就很可能失去其最优性,从而增加交通运输的成本。为了解决这一问题,本文提出了不完全信息下交通网络的关键路径问题,给出了相应的求解算法,并分析了其时间复杂性,然后结合实际交通网络给出算例,最后指出这对提高交通运输的效率更具有实际意义。

• 单位
  西安交通大学机械制造系统工程国家重点实验室; 西安交通大学