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

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

作　　者：王江晴[1] 康立山[2] 

机构地区：[1]中南民族大学计算机科学学院,武汉430074 [2]武汉大学软件工程国家重点实验室,武汉430072

出　　处：《武汉理工大学学报（交通科学与工程版）》2007年第1期46-49,共4页Journal of Wuhan University of Technology（Transportation Science & Engineering）

基　　金：国家自然科学基金项目(批准号:60133010);湖北省自然科学基金项目资助(批准号:2004ABA029)

摘　　要：分析了现有算法处理动态车辆路径问题时的缺陷,提出了一个动态网络环境下的实时路径评估模型,在此基础之上构造了一个改进的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.

关 键 词：最短路径 动态 实时 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]