基于改进蚁群算法的带时间窗废品收集车辆路径问题  

Waste Collection Vehicle Routing Problem with Time Windows Based on Improved Ant Colony Optimization

作　　者：刘琼[1] 刘秀城 张超勇[1] 饶运清[1] 

机构地区：[1]华中科技大学数字制造装备与技术国家重点实验室,武汉430074

出　　处：《中国机械工程》2015年第2期247-254,共8页China Mechanical Engineering

基　　金：国家自然科学基金资助重点项目(51035001);国家自然科学基金资助项目(51275190);国家科技重大专项(2011ZX04015-011-07);中央高校基本科研业务费专项资金资助项目(HUST:2013ZZGH002)

摘　　要：建立了以最小化燃油消耗为优化目标的带时间窗、司机休息时间以及多个中转处理中心的废品收集车辆路径问题模型。提出了一种改进最大最小蚁群算法,针对时间窗特点,设计了两类满足时间窗约束的动态候选列表以提高算法的搜索效率。在最大最小蚁群算法的概率状态转移规则中引入了带距离限制的最近邻域搜索。10个基准实例中的9个实例比当前文献的最优解更好,从而验证了该模型和算法的可行性和有效性。A mathematical model aiming at minimizing the fuel consumption for the waste collec-tion vehicle routing problem with time windows,driver rest period and multiple disposal facilities was set up.The main factors to affect the fuel consumption of a vehicle considered herein were the load of a vehicle and distance traveled.An improved MAX-MIN ant system algorithm was proposed.Based on characteristics of the time windows,two kinds of dynamic candidate lists were designed to improve the searching efficiency of the algorithm.A new probabilistic condition transition rule for the MAX-MIN ant system algorithm was proposed.The nearest neighborhood search with distance limitation was in-tegrated in the transition rule of proposed algorithm.The proposed model and algorithm were valida-ted by comparion with benchmark problems in literatures.

关 键 词：大规模带时间窗车辆 路径问题 蚁群算法 燃油消耗 

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