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

中国机械工程 ›› 2015, Vol. 26 ›› Issue (2): 247-244.

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

刘琼;刘秀城;张超勇;饶运清

华中科技大学数字制造装备与技术国家重点实验室，武汉，430074

出版日期:2015-01-25 发布日期:2015-01-23
基金资助:
国家自然科学基金资助重点项目(51035001);国家自然科学基金资助项目（51275190);国家科技重大专项(2011ZX04015-011-07）；中央高校基本科研业务费专项资金资助项目(HUST:2013ZZGH002)

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

Liu Qiong;Liu Xiucheng;Zhang Chaoyong;Rao Yunqing

State Key Laboratory of Digital Manufacturing Equipment & Technology,Huazhong University of Science and Technology,Wuhan,430074

Online:2015-01-25 Published:2015-01-23
Supported by:
National Natural Science Foundation of China（No. 51035001, 51275190）; National Science and Technology Major Project（No. 2011ZX04015-011-07）;Fundamental Research Funds for the Central Universities（No. HUST:2013ZZGH002）

摘要/Abstract

摘要：

建立了以最小化燃油消耗为优化目标的带时间窗、司机休息时间以及多个中转处理中心的废品收集车辆路径问题模型。提出了一种改进最大最小蚁群算法,针对时间窗特点,设计了两类满足时间窗约束的动态候选列表以提高算法的搜索效率。在最大最小蚁群算法的概率状态转移规则中引入了带距离限制的最近邻域搜索。10个基准实例中的9个实例比当前文献的最优解更好,从而验证了该模型和算法的可行性和有效性。

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

Abstract:

A mathematical model aiming at minimizing the fuel consumption for the waste collection 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 integrated in the transition rule of proposed algorithm.The proposed model and algorithm were validated by comparion with benchmark problems in literatures.

Key words: large scale vehicle with time windows, routing problem, ant colony optimization, fuel consumption

中图分类号:

TP391

刘琼, 刘秀城, 张超勇, 饶运清. 基于改进蚁群算法的带时间窗废品收集车辆路径问题[J]. 中国机械工程, 2015, 26(2): 247-244.

Liu Qiong, Liu Xiucheng, Zhang Chaoyong, Rao Yunqing. Waste Collection Vehicle Routing Problem with Time Windows Based on Improved Ant Colony Optimization[J]. China Mechanical Engineering, 2015, 26(2): 247-244.

参考文献

[1]Sahoo S,Kim S,Kim B I,et al.Routing Optimization for Waste Management[J].Interfaces，2005，35(1)：24-36.
[2]Angelelli E,Speranza M G.The Application of a Vehicle Routing Model to a Waste-collection Problem:Two Case Studies[J]. The Journal of the Operational Research Society,2002,53(9):944-952.
[3]Baldacci R,Hadjiconstantionou E,Mingozzi A.An Exact Algorithm for the Capacitated Vehicle Routing Problem Based on a Two-commodity Network Flow Formulation[J]. Operations Research,2004,52(5):723-738.
[4]Xiao Y,Zhao Q,Kaku I,et al.Development of a Fuel Consumption Optimization Model for the Capacitated Vehicle Routing Problem[J].Computers & Operations Research,2012,39(7):1419-1431.
[5]Tavares G,Zdena Z,Viriato S,et al.A Case Study of Fuel Savings through Optimization of MSW Transportation Routes[J]. Management of Environmental Quality:An International Journal，2008,19(4):444-454.
[6]Zsigraiova Z,Semiao V,Beijoco F.Operation Costs and Pollutant Emissions Reduction by Definition of New Collection Scheduling and Optimization of MSW Collection Routes Using GIS.The Case Study of Barreiro,Portugal[J].Waste Management, 2013,33(4):793-806.
[7]Stützle T,Hoos H.The Max-min Ant System and Local Search for Combinatorial Optimization Problems[C]//1997 IEEE International Conference on Evolutionary Computation.Indianapolis,1997:309-314.
[8]Bullnheimer B,Hartl R F,Strauss C.An Improved Ant System Algorithm for the Vehicle Routing Problem[J].Annals of Operations Research,1999,89:319-328.
[9]Kim B I,Kim S,Sahoo S.Waste Collection Vehicle Routing Problem with Time Windows[J].Computers & Operations Research, 2006,33(12):3624-3642.
[10]Benjamin A M,Beasley J E.Metaheuristics with Disposal Facility Positioning for the Waste Collection VRP with Time Windows[J]. Optimization Letters,2013,7(7):1433-1449.
[11]Buhrkal K,Larsen A,Ropke S.The Waste Collection Vehicle Routing Problem with Time Windows in a City Logistics Context[J]. Procedia Social and Behavioral Sciences,2012,39:241-254.
[12]Islam R,Rahman M S.An Ant Colony Optimization Algorithm for Waste Collection Vehicle Routing with Time Windows, Driver Rest Period and Multiple Disposal Facilities[C]//2012 International Conference on Informatics, Electronics & Vision. Dhaka,2012:774-779.

[1]	辜勇, 袁源乙, 张列, 段晶晶. 带时间窗的多中心半开放式车辆路径问题[J]. 中国机械工程, 2020, 31(14): 1733-1740.
[2]	乔东平, 裴杰, 文笑雨, 肖艳秋, 焦建强, . [车间调度]一种求解单机总加权延迟调度问题的改进蚁群算法[J]. 中国机械工程, 2018, 29(22): 2703-2710.
[3]	周蓉, 沈维蕾. [供应链调度]装卸一体化车辆路径问题的自适应并行遗传算法[J]. 中国机械工程, 2018, 29(22): 2740-2749.
[4]	邓涛;韩海硕;罗俊林. 基于动态规划算法的混合动力汽车改进型ECMS能量管理控制研究[J]. 中国机械工程, 2018, 29(03): 326-332.
[5]	陈呈频;韩胜军;鲁建厦;陈青丰;王成. 多车场与多车型车辆路径问题的多染色体遗传算法[J]. 中国机械工程, 2018, 29(02): 218-223.
[6]	侯仰强1;王天琪1;李亮玉1;张志臣1;赵娜2. 基于蚁群算法-粒子群算法的白车身侧围点焊机器人路径规划[J]. 中国机械工程, 2017, 28(24): 2990-2994.
[7]	张铁, 苏杰汶. 基于改进蚁群算法的机器人末端路径排序优化[J]. 中国机械工程, 2016, 27(19): 2624-2629.
[8]	王恒升, 陈伟锋, 王思远. 基于末端杆件螺旋运动的凿岩机械臂孔序规划[J]. 中国机械工程, 2016, 27(13): 1748-1754.
[9]	阚萍, 邱利宏, 钱立军, 王金波. 基于Willans Line的双轴驱动混合动力越野车实时能量管理[J]. 中国机械工程, 2016, 27(11): 1546-1553.
[10]	方清华, 倪丽萍, 李一鸣. 求解物流Web服务组合问题的两阶段多目标蚁群算法[J]. 中国机械工程, 2016, 27(10): 1327-1336.
[11]	黄风立, 顾金梅, 张礼兵, 徐春光, 王海燕. 基于禁忌制造特征动态调整的STEP-NC工艺路线蚁群优化方法[J]. 中国机械工程, 2016, 27(05): 596-602.
[12]	周蓉, 沈维蕾, 刘明周, 赵韩. 带时间窗装卸一体化车辆路径问题的混合离散粒子群优化算法[J]. 中国机械工程, 2016, 27(04): 494-502.
[13]	吴长友, 戴宁, 刘浩, 程筱胜, 李大伟, 沈振宏, 孙登广. 基于改进蚁群算法的分形刀轨连接技术[J]. 中国机械工程, 2016, 27(01): 58-65.
[14]	谢志江, 梁欢, 宋代平. 基于连续蚁群算法的3-RPS并联机构正解[J]. 中国机械工程, 2015, 26(6): 799-803.
[15]	姜康, 胡龙. 复杂环境下的装配路径求解与优化[J]. 中国机械工程, 2015, 26(5): 632-636.