A diversity-enhanced memetic algorithm for solving electric vehicle routing problems with time windows and mixed backhauls

• Main Authors: XIAO, Jianhua, DU, Jingguo, CAO, Zhiguang, ZHANG, Xingyi, NIU, Yunyun
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2023
• Subjects: Electric vehicles; Vehicle routing problem; Memetic algorithm; Time windows; Mixed backhauls; Operations Research, Systems Engineering and Industrial Engineering; Theory and Algorithms; Transportation
• Online Access: https://ink.library.smu.edu.sg/sis_research/8193; https://ink.library.smu.edu.sg/context/sis_research/article/9196/viewcontent/1_s2.0_S1568494623000431_main.pdf
• Institution: Singapore Management University

The electric vehicle routing problem (EVRP) has been studied increasingly because of environmental concerns. However, existing studies on the EVRP mainly focus on time windows and sole linehaul customers, which might not be practical as backhaul customers are also ubiquitous in reality. In this study, we investigate an EVRP with time windows and mixed backhauls (EVRPTWMB), where both linehaul and backhaul customers exist and can be served in any order. To address this challenging problem, we propose a diversity-enhanced memetic algorithm (DEMA) that integrates three types of novel operators, including genetic operators based on adaptive selection mechanism, a selection operator based on similarity degree, and modification operators for tabu search. Experimental results on 54 new instances and two classical benchmarks show that the proposed DEMA can effectively solve the EVRPTWMB as well as other related problems. Furthermore, a case study on a realistic instance with up to 200 customers and 40 charging stations in China also confirms the desirable performance of the DEMA.(c) 2023 Elsevier B.V. All rights reserved.