学习型蚁群算法求解绿色多车场车辆路径问题

doi:10.16182/j.issn1004731x.joss.20-0349

系统仿真学报 ›› 2021, Vol. 33 ›› Issue (9): 2095-2108.doi: 10.16182/j.issn1004731x.joss.20-0349

学习型蚁群算法求解绿色多车场车辆路径问题

胡蓉^1,2, 陈文博^1,2, 钱斌^1,2, 郭宁¹, 向凤红¹

1.昆明理工大学信息工程与自动化学院,云南昆明 650500;
2.昆明理工大学云南省人工智能重点实验室,云南昆明 650500

收稿日期:2020-06-15 修回日期:2020-08-07 出版日期:2021-09-18 发布日期:2021-09-17
作者简介:胡蓉(1974-)，女，博士，副教授，研究方向为智能优化调度，物流优化。E-mail：ronghu@vip.163.com
基金资助:
国家自然科学基金(61963022,51665025)

Learning Ant Colony Algorithm for Green Multi-depot Vehicle Routing Problem

Hu Rong^1,2, Chen Wenbo^1,2, Qian Bin^1,2, Guo Ning¹, Xiang Fenghong¹

1. Faculty of Information Engineering and Automation, Kunming University of Science and Technology, Kunming 650500, China;
2. Yunnan Key Laboratory of Artificial Intelligence, Kunming University of Science and Technology, Kunming 650500, China

Received:2020-06-15 Revised:2020-08-07 Online:2021-09-18 Published:2021-09-17

摘要/Abstract

摘要： 针对我国城市中心区域路况较拥堵的实际情况,设计基于车辆行驶路段的速度计算方法,同时考虑车辆行驶距离、载重和速度因素,建立以最小化总油耗费用为目标的绿色多车场车辆路径问题模型,提出一种融合蚁群优化算法(Ant Colony Optimization, ACO)与知识模型的学习型蚁群优化算法(Learning Ant Colony Optimization, LACO)进行求解。为提高算法全局搜索性能和鲁棒性,设计由不同ACO参数组合和各参数组合选取概率组成的参数知识,用于每代调整ACO参数;为增强算法局部搜索能力,设计由各邻域操作贡献率组成的局部操作知识,用于每代确定各邻域操作的执行次数。通过在不同规模问题上的仿真实验和算法对比,验证所提LACO的有效性。

关键词: 学习型蚁群算法, 绿色多车场, 车辆路径问题, 知识模型, 邻域搜索

Abstract: Considering the congested roads situation of urban central areas in China, a speed calculation method based on vehicle driving sections is designed, and a model for the Green Multi-Depot Vehicle Routing Problem with Total Fuel-Consumption cost Criterion (TFC-GMDVRP) is established, considering simultaneously the vehicle travel distance, load, and speed factors. A learning ant colony optimization algorithm (LACO), combining a knowledge model and an ant colony optimization algorithm (ACO), is proposed for solving the TFC-GMDVRP. In order to improve the performance and robustness of the algorithm's global search, the parameter knowledge that contains the different parameter combinations of ACO and the selection probability of each parameter combination is designed to adjust the ACO's parameters for each generation. In order to enhance the ability of algorithm's local search, the local operation knowledge that contains the contribution ratio of each neighborhood operation is designed to determine the execution times of each neighborhood operation for each generation. Simulation experiments on different instances and comparisons of algorithms show the effectiveness of the proposed algorithm.

Key words: learning ant colony optimization, green multi-depot, vehicle routing problem, knowledge model, neighborhood search

中图分类号:

TP391.9

胡蓉, 陈文博, 钱斌, 郭宁, 向凤红. 学习型蚁群算法求解绿色多车场车辆路径问题[J]. 系统仿真学报, 2021, 33(9): 2095-2108.

Hu Rong, Chen Wenbo, Qian Bin, Guo Ning, Xiang Fenghong. Learning Ant Colony Algorithm for Green Multi-depot Vehicle Routing Problem[J]. Journal of System Simulation, 2021, 33(9): 2095-2108.

参考文献

[1] 王坤, 王广翔. 基于GIS和MDVRP的成都市城乡配送网络仿真[J]. 综合运输, 2019, 41(3): 99-104.
Wang Kun, Wang Guangxiang.Simulation Research of Urban and Rural Distribution Network in Chengdu Based on GIS and MDVRP[J]. China Transportation Review, 2019, 41(3): 99-104.
[2] 鲍春玲, 张世斌. 考虑碳排放的冷链物流联合配送路径优化[J]. 工业工程与管理, 2018, 23(5): 95-100.
Bao Chunling, Zhang Shibin.Route Optimization of Cold Chain Logistics in Joint Distribution with Consideration of Carbon Emission[J]. Industrial Engineering and Management, 2018, 23(5): 95-100.
[3] Carotenuto P, Giordani S, Massari S, et al.A Multi-depot Periodic Vehicle Routing Model for Petrol Station Replenishment[C]// Advances in Intelligent Systems and Computing. Cham: Springer International Publishing, 2018: 421-437.
[4] Dantzig G B, Ramser J H.The Truck Dispatching Problem[J]. Management Science (S0025-1909), 1959, 6(1): 80-91.
[5] Tavares G, Zsigraiova Z, Semiao V, et al.Optimisation of MSW Collection Routes for Minimum Fuel Consumption Using 3D GIS Modelling[J]. Waste Management (S0275-6196), 2009, 29(3): 1176-1185.
[6] 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 (S0305-0548), 2012, 39(7): 1419-1431.
[7] 饶卫振, 金淳, 王新华, 等. 考虑道路坡度因素的低碳VRP问题模型与求解策略[J]. 系统工程理论与实践, 2014, 34(8): 2092-2105.
Rao Weizhen, Jin Chun, Wang Xinhua, et al.A Model of Low-carbon Vehicle Routing Problem Considering Road Gradient and its Solving Strategy[J]. Systems Engineering Theory & Practice, 2014, 34(8): 2092-2105.
[8] Wang R, Zhou J, Yi X, et al.Solving the Green-fuzzy Vehicle Routing Problem Using a Revised Hybrid Intelligent Algorithm[J]. Journal of Ambient Intelligence and Humanized Computing (S1868-5145), 2019, 10(1): 321-332.
[9] Hooshmand F, Mirhassani S A.Time Dependent Green VRP with Alternative Fuel Powered Vehicles[J]. Energy Systems (S1868-3975), 2019, 10(3): 721-756.
[10] Jabir E, Panicker V V, Sridharan R.Design and Development of a Hybrid Ant Colony-variable Neighborhood Search Algorithm for a Multi-Depot Green Vehicle Routing Problem[J]. Transportation Research Part D: Transport and Environment (S1361-9209), 2017, 57: 422-457.
[11] Li J, Wang R, Li T, et al.Benefit Analysis of Shared Depot Resources for Multi-depot Vehicle Routing Problem with Fuel Consumption[J]. Transportation Research Part D-transport and Environment (S1361-9209), 2018, 59: 417-432.
[12] Li Y, Soleimani H, Zohal M.An Improved Ant Colony Optimization Algorithm for the Multi-depot Green Vehicle Routing Problem with Multiple Objectives[J]. Journal of Cleaner Production (S0959-6526), 2019, 227: 1161-1172.
[13] Wang Y, Assogba K, Fan J, et al.Multi-depot Green Vehicle Routing Problem with Shared Transportation Resource: Integration of Time-dependent Speed and Piecewise Penalty Cost[J]. Journal of Cleaner Production (S0959-6526), 2019, 232: 12-29.
[14] Dorigo M, Maniezzo V, Colorni A.Ant System: Optimization by a Colony of Cooperating Agents[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics)(S1083-4419), 1996, 26(1): 29-41.
[15] Bell J E, Mcmullen P R.Ant Colony Optimization Techniques for the Vehicle Routing Problem[J]. Advanced Engineering Informatics (S1474-0346), 2004, 18(1): 41-48.
[16] Yu B, Yang Z, Yao B.An Improved Ant Colony Optimization for Vehicle Routing Problem[J]. European Journal of Operational Research (S0377-2217), 2009, 196(1): 171-176.
[17] Goel R, Maini R.A Hybrid of Ant Colony and Firefly Algorithms (HAFA) for Solving Vehicle Routing Problems[J]. Journal of Computational Science (S1877-7503), 2018, 25: 28-37.
[18] Sandhya Goel R.Fuzzy Based Parameter Adaptation in ACO for Solving VRP[J]. International Journal of Operations Research and Information Systems (IJORIS)(S1947-9328), 2019, 10(2): 65-81.
[19] 邢立宁, 陈英武, 向尚. 学习型智能优化算法及其应用[M]. 北京: 清华大学出版社, 2018.
Xing Lining, Chen Yingwu, Xiang Shang.Learnable Intelligent Optimization Algorithm and its Application[M]. Beijing: Tsinghua University Press, 2018.
[20] 邢立宁, 姚锋. 求解双层CARP优化问题的演化学习型遗传算法[J]. 系统工程与电子技术, 2012, 34(6): 1187-1192.
Xing Lining, Yao Feng.Learnable Genetic Algorithm to Double-layer CARP Optimization Problems[J]. Systems Engineering and Electronics, 2012, 34(6): 1187-1192.
[21] Yang H, Yang S, Xu Y, et al.Electric Vehicle Route Optimization Considering Time-of-Use Electricity Price by Learnable Partheno-Genetic Algorithm[J]. IEEE Transactions on Smart Grid (S1949-3053), 2015, 6(2): 657-666.
[22] Ehsani M, Ahmadi A, Fadai D.Modeling of Vehicle Fuel Consumption and Carbon Dioxide Emission in Road Transport[J]. Renewable & Sustainable Energy Reviews (S1364-0321), 2016, 53: 1638-1648.
[23] 高德交通-中国主要城市交通分析报告[EB/OL]. (2019-10-08). [2020-06-13]. https://report.amap.com/ download_city.do.
Amap Traffic-Analysis Report of Major Cities in China[EB/OL]. (2019-10-08) [2020-06-13]. https://report. amap.com/download_city.do.
[24] Clarke G, Wright J W.Scheduling of Vehicles from a Central Depot to a Number of Delivery Points[J]. Operations Research (S0030-364X), 1964, 12(4): 568-581.
[25] Multiple Depot VRP Instances Vehicle Routing Problem [EB/OL]. [2020-06-13]. http://neo.lcc.uma.es/vrp/vrp- instances/multiple-depot-vrp-instances/.

学习型蚁群算法求解绿色多车场车辆路径问题

Learning Ant Colony Algorithm for Green Multi-depot Vehicle Routing Problem

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 14

编辑推荐

Metrics

本文评价

[1]	张凯庆, 嵇启春. 速度时变的多中心半开放式车辆路径问题研究[J]. 系统仿真学报, 2022, 34(4): 836-846.
[2]	王伟权, 丁鼎, 曹淑艳. 混合变邻域搜索算法求解大规模电动车辆路径优化问题[J]. 系统仿真学报, 2022, 34(4): 910-919.
[3]	宁涛, 苟涛, 刘向东. 考虑低碳约束的生鲜农产品冷链物流策略仿真研究[J]. 系统仿真学报, 2022, 34(4): 797-805.
[4]	王伟权, 丁鼎, 颜林莎. 线性充电策略下多车型电动车辆路径模型研究[J]. 系统仿真学报, 2022, 34(3): 614-623.
[5]	李珍萍, 杨光, 韩倩倩. 考虑工作量均衡的成品油二次配送车辆路径问题[J]. 系统仿真学报, 2022, 34(2): 221-233.
[6]	陈魁, 毕利. 改进粒子群算法在考虑运输时间下的FJSP研究[J]. 系统仿真学报, 2021, 33(4): 845-853.
[7]	陈芮莹, 王承涛, 刘振元. 考虑服务水平的IT运维人员调度的智能遗传算法[J]. 系统仿真学报, 2021, 33(3): 732-744.
[8]	蔡敏, 王艳, 纪志成. 基于多策略融合量子粒子群算法的MOFFJSP研究[J]. 系统仿真学报, 2021, 33(11): 2615-2626.
[9]	李珍萍, 赵雨薇, 张煜炜, 邢立宁, 任腾. 共同配送选址-路径问题及大邻域搜索算法[J]. 系统仿真学报, 2021, 33(10): 2518-2531.
[10]	孙灿, 周新宇, 王明文. 一种融合邻域搜索的多策略差分进化算法[J]. 系统仿真学报, 2020, 32(6): 1071-1084.
[11]	董泽, 马宁. 差分量子粒子群算法的分数阶混沌系统参数估计[J]. 系统仿真学报, 2019, 31(8): 1664-1673.
[12]	邢志伟, 唐云霄. 枢纽机场航班保障服务时间估计[J]. 系统仿真学报, 2017, 29(11): 2856-2865.
[13]	马向国, 刘同娟, 杨平哲, 蒋荣芬. 基于随机需求的冷链物流车辆路径优化模型[J]. 系统仿真学报, 2016, 28(8): 1824-1833.
[14]	宁涛, 郭晨, 陈荣, 金花. 一种动态车辆路径问题解决策略仿真研究[J]. 系统仿真学报, 2015, 27(12): 2942-2947.