[1]王朝,秦芳,刘蓉蓉,等.求解电动汽车车辆路径问题的双种群协同进化算法[J].智能系统学报,2024,19(2):438-445.[doi:10.11992/tis.202209007]
WANG Chao,QIN Fang,LIU Rongrong,et al.Dual-population co-evolutionary algorithm for solving electric vehicle route problems[J].CAAI Transactions on Intelligent Systems,2024,19(2):438-445.[doi:10.11992/tis.202209007]
点击复制
WANG Chao,QIN Fang,LIU Rongrong,et al.Dual-population co-evolutionary algorithm for solving electric vehicle route problems[J].CAAI Transactions on Intelligent Systems,2024,19(2):438-445.[doi:10.11992/tis.202209007]
求解电动汽车车辆路径问题的双种群协同进化算法
《智能系统学报》[ISSN 1673-4785/CN 23-1538/TP] 卷:
19
期数:
2024年第2期
页码:
438-445
栏目:
学术论文—人工智能基础
出版日期:
2024-03-05
- Title:
- Dual-population co-evolutionary algorithm for solving electric vehicle route problems
- Keywords:
- green logistics; electric vehicle routing problem; electricity constraint; two-population; evolutionary algorithm; distance adjacency matrix; denoising autoencoder; knowledge transfer
- 分类号:
- TP273
- 文献标志码:
- 2023-11-20
- 摘要:
- 绿色物流领域新兴的电动汽车车辆路径问题，由于需要对车辆路径和充电决策同时优化，搜索空间急剧增大，且需要同时满足容量和电量双重约束，现有方法难以快速找到质量较优的可行解。为此，提出一种基于双种群的协同进化算法，通过忽略电量约束构造简单带容量约束的车辆路径问题，辅助原始复杂问题的快速求解。为实现其间信息交互，设计一种基于改进距离邻接矩阵的解序列特征表示方法，旨在同时获取客户访问顺序和车辆指派信息；利用降噪自编码器构建2个问题解之间转换关系，以实现问题域间知识迁移。将该算法与目前常用的3种启发式算法和2种进化算法在不同规模测试集上进行对比，试验结果表明所提算法具有更快收敛速度且所获解集具有更好收敛性。
- Abstract:
- The emerging field of green logistics presents a challenge in the form of electric vehicle routing. This issue requires simultaneous optimization of routing and charging decisions, significantly expanding the search space. Moreover, solutions must comply with capacity and power constraints, making it difficult to quickly find feasible solutions using existing methods. To address these challenges, we propose a dual population-based co-evolutionary algorithm. This approach involves constructing a simpler problem to expedite the solution process for the original, more complicated problem. To facilitate information exchange between these two heterogeneous problems, we designed a solution representation method. This method, which is based on an improved distance adjacency matrix, allows to obtain information on customer visits and vehicle assignments. Subsequently, we employed a commonly used denoising autoencoder to establish the transformation relationship between solutions from these two problems. This step enables knowledge transfer between the two problem domains. Our proposed algorithm was tested against three heuristic methods and two evolutionary algorithms on test sets of different sizes. The experimental results show that the proposed algorithm not only converges faster but also yields solutions with superior convergence.
- 参考文献/References:
-
[1] 郭戈, 张振琳. 电动车辆路径优化研究与进展[J]. 控制与决策, 2018, 33(10): 1729–1739
GUO Ge, ZHANG Zhenlin. Status and development of electric vehicle routing optimization[J]. Control and decision, 2018, 33(10): 1729–1739
[2] SCHIFFER M, WALTHER G. The electric location routing problem with time windows and partial recharging[J]. European journal of operational research, 2017, 260(3): 995–1013.
[3] 刘蓉蓉. 基于进化算法的电动汽车物流调度问题研究[D]. 合肥: 安徽大学, 2021.
LIU Rongrong. Research on electric vehicle logistics scheduling problem based on evolutionary algorithms[D]. Hefei: Anhui University, 2021.
[4] 吴廷映, 孙灏. 考虑载重影响耗电率的电动车车辆路径问题[J]. 控制与决策, 2023, 38(2): 483–491
WU Tingying, SUN Hao. Electric vehicle routing problem with time window and linear weight related discharging[J]. Control and decision, 2023, 38(2): 483–491
[5] DESAULNIERS G, ERRICO F, IRNICH S, et al. Exact algorithms for electric vehicle-routing problems with time windows[J]. Operations research, 2016, 64(6): 1388–1405.
[6] DUMAN E N, TA? D, ?ATAY B. Branch-and-price-and-cut methods for the electric vehicle routing problem with time windows[J]. International journal of production research, 2022, 60(17): 5332–5353.
[7] OMIDVAR A, TAVAKKOLI-MOGHADDAM R. Sustainable vehicle routing: strategies for congestion management and refueling scheduling[C]//2012 IEEE International Energy Conference and Exhibition. Florence: IEEE, 2012: 1089-1094.
[8] PREIS H, FRANK S, NACHTIGALL K. Energy-optimized routing of electric vehicles in urban delivery systems[C]//Operations Research Proceedings 2012. Cham: Springer, 2014: 583-588.
[9] SCHNEIDER M, STENGER A, GOEKE D. The electric vehicle-routing problem with time windows and recharging stations[J]. Transportation science, 2014, 48(4): 500–520.
[10] KESKIN M, ?ATAY B. Partial recharge strategies for the electric vehicle routing problem with time windows[J]. Transportation research part C:emerging technologies, 2016, 65: 111–127.
[11] RISTO M, STEPHANIE F. A biological perspective on evolutionary computation[J]. Nature machine intelligence, 2021, 3(1): 9–15.
[12] 彭扬, 陈子侠, 吴承键. 定位-运输路线安排问题的改进离散粒子群优化算法[J]. 智能系统学报, 2010, 5(1): 74–79
PENG Yang, CHEN Zixia, WU Chengjian. Improved discrete particle swarm optimization algorithm for location-routing problems[J]. CAAI transactions on intelligent systems, 2010, 5(1): 74–79
[13] KIM G, ONG Y S, HENG C K, et al. City vehicle routing problem (city VRP): a review[J]. IEEE transactions on intelligent transportation systems, 2015, 16(4): 1654–1666.
[14] 葛斌, 韩江洪, 魏臻, 等. 最小最大车辆路径问题的动态自适应蚁群优化算法[J]. 模式识别与人工智能, 2015, 28(10): 930–938
GE Bin, HAN Jianghong, WEI Zhen, et al. Dynamic adaptive ant colony optimization algorithm for Min-max vehicle routing problem[J]. Pattern recognition and artificial intelligence, 2015, 28(10): 930–938
[15] 王舜, 赵燕伟, 冷龙龙, 等. 基于蚁群选择超启发算法的低碳选址-路径问题[J]. 计算机集成制造系统, 2020, 26(6): 1702–1716
WANG Shun, ZHAO Yanwei, LENG Longlong, et al. Low carbon location-routing problem based on evolutionary hyper-heuristic algorithm of ant colony selection mechanism[J]. Computer integrated manufacturing systems, 2020, 26(6): 1702–1716
[16] WANG Ling, LU Jiawen. A memetic algorithm with competition for the capacitated green vehicle routing problem[J]. IEEE/CAA journal of automatica sinica, 2019, 6(2): 516–526.
[17] BARCO J, GUERRA A, MU?OZ L, et al. Optimal routing and scheduling of charge for electric vehicles: a case study[J]. Mathematical problems in engineering, 2017, 2017: 1–16.
[18] HIERMANN G, HARTL R F, PUCHINGER J, et al. Routing a mix of conventional, plug-in hybrid, and electric vehicles[J]. European journal of operational research, 2019, 272(1): 235–248.
[19] GUO Zhenfeng, LI Yang, JIANG Xiaodan, et al. The electric vehicle routing problem with time windows using genetic algorithm[C]//2017 IEEE 2nd Advanced Information Technology, Electronic and Automation Control Conference. Chongqing: IEEE, 2017: 635-639.
[20] JIA Yahui, MEI Yi, ZHANG Mengjie. A bilevel ant colony optimization algorithm for capacitated electric vehicle routing problem[J]. IEEE transactions on cybernetics, 2022, 52(10): 10855–10868.
[21] FENG Liang, ONG Y S, JIANG Siwei, et al. Autoencoding evolutionary search with learning across heterogeneous problems[J]. IEEE transactions on evolutionary computation, 2017, 21(5): 760–772.
[22] YANG Jun, SUN Hao. Battery swap station location-routing problem with capacitated electric vehicles[J]. Computers & operations research, 2015, 55: 217–232.
[23] ZHANG Qingfu, LI Hui. MOEA/D: a multiobjective evolutionary algorithm based on decomposition[J]. IEEE transactions on evolutionary computation, 2007, 11(6): 712–731.
[24] CHIANG T C, HSU W H. A knowledge-based evolutionary algorithm for the multiobjective vehicle routing problem with time windows[J]. Computers & operations research, 2014, 45: 25–37.
[25] FELIPE ?, ORTU?O M T, RIGHINI G, et al. A heuristic approach for the green vehicle routing problem with multiple technologies and partial recharges[J]. Transportation research part E:logistics and transportation review, 2014, 71: 111–128.
[26] BEUME N, NAUJOKS B, EMMERICH M. SMS-EMOA: Multiobjective selection based on dominated hypervolume[J]. European journal of operational research, 2007, 181(3): 1653–1669.
备注/Memo
收稿日期:2022-09-06。
基金项目:国家自然科学基金项目（62106002, 62372001）
作者简介:王朝，副教授，博士，主要研究方向为计算智能方法及其物流调度应用。主持国家自然科学基金青年项目1项、安徽省自然科学基金青年项目1项，参与科技部重点研发项目1项，申请发明专利3项。发表学术论文近20篇。E-mail：wangchao8@ahu.edu.cn;秦芳，女，硕士研究生，主要研究方向为智慧物流调度。E-mail：2412733393@qq.com;江浩，副教授，博士，主要研究方向为智能计算方法与应用、群智能优化、车辆路径智能调度、社团检测。主持国家自然科学基金青年项目1项。近3年发表学术论文10篇。E-mail：haojiang@ahu.edu.cn
通讯作者:江浩. E-mail：haojiang@ahu.edu.cn
更新日期/Last Update:
1900-01-01