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

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