混合最大最小蚁群算法在VRPTW中的应用  

Hybrid Max-Min Ant System for Vehicle Routing Problem with Time Windows

作　　者：苏红畏[1] 刘希玉[1] 王晓敏[2] 

机构地区：[1]山东师范大学管理与经济学院,山东济南250014 [2]山东师范大学信息科学与工程学院,山东济南250014

出　　处：《计算机技术与发展》2010年第2期90-94,共5页Computer Technology and Development

基　　金：国家自然科学基金项目(60873058);山东省自然科学基金项目(Z2007G03);"泰山学者"建设工程专项经费资助项目(2005-2010)

摘　　要：为解决有时间窗车辆路径问题,采用两个最大最小蚁群系统,一个蚁群最小化车辆数量,另一个蚁群最小化旅行距离。通过分析有时间窗车辆路径问题和旅行商问题的区别,改进了最大最小蚁群算法中状态转移策略,并增加与可用车辆相同数量的虚拟仓库,使这两个蚁群使用独立的信息素但通过分享全局最优解来协作,算法还结合了2-opt局部搜索,从而减少了算法的计算时间并避免过早收敛。仿真实验结果表明,该算法性能优良,能有效地求解有时间窗车辆路径问题。Two ant colonies employing max- min ant colony system, one minimizes the number of vehicles while the other minimizes the traveled distances, have been designed to tackle the VRPTW（vehiele muting problem with time window）. By analyzing the difference between the vehicle routing problem with time window and travehng salesman problem, the state transition strategy of the max - min ant colony system is improved and the depot is duplicated a number of times equal to the number of available vehicles. These two colonies work by using independent pheromone trails but collaborate by sharing the global best feasible solution, and integrating 2 - opt local search method in order to decrease computing time and overcome early convergence. Simulation results show that the algorithm present is feasible and valid for VRPTW.

关 键 词：最大最小蚁群算法 时间窗车辆路径问题 2-opt局部搜索 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]