动态车辆路径问题中的实时最短路径算法研究

Shortest Path Algorithm with Real Time Traffic Information in Dynamic Vehicle Routing Problem

分析了现有算法处理动态车辆路径问题时的缺陷,提出了一个动态网络环境下的实时路径评估模型,在此基础之上构造了一个改进的Dijkstra双桶算法.该算法能根据静态和动态的交通信息找出客户之间的实时最短路径,并对车辆的旅行线路进行调整,具有对随机事件和突发事件进行实时处理的能力,已用于解决动态车辆路径问题.实验结果表明,该算法能在动态网络环境下找到实时的最短路径,减少车辆旅行的总成本.

Traditional shortest path algorithms can＇t directly be applied on real world situations because real time traffic information in dynamic network is not taken into consideration. This paper examines the value of real-time traffic information to find shortest paths in real world. It provides a real time route evaluation model for modeling the responses of vehicles, and develops a modified Dijkstra＇s double bucket algorithm for path finding in dynamic network. The experimental results show that the developed algorithm can find real time shortest paths for the vehicle routing problem in dynamic network effectively, and can reduce the total costs.