[1]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]
Copy

Dual-population co-evolutionary algorithm for solving electric vehicle route problems

CAAI Transactions on Intelligent Systems[ISSN 1673-4785/CN 23-1538/TP] Volume: 19 Number of periods: 2024 2 Page number: 438-445 Column: 学术论文—人工智能基础 Public date: 2024-03-05
Title:
Dual-population co-evolutionary algorithm for solving electric vehicle route problems
Author(s):
WANG Chao;  QIN Fang;  LIU Rongrong;  JIANG Hao
School of Artificial Intelligence, Anhui University, Hefei 230601, China
Keywords:
green logistics; electric vehicle routing problem; electricity constraint; two-population; evolutionary algorithm; distance adjacency matrix; denoising autoencoder; knowledge transfer
CLC:
TP273
DOI:
10.11992/tis.202209007
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.
Similar References:

Memo

-

Last Update: 1900-01-01

Copyright © CAAI Transactions on Intelligent Systems