Title: An adaptive large neighbourhood search for multi-depot electric vehicle routing problem with time windows

Authors: Yucong Wang; Ping Chen

Addresses: College of Management and Economics, Tianjin University, Tianjin 300072, China ' Business School, Nankai University, Tianjin 300071, China

Abstract: The multi-depot electric vehicle routing problem with time windows (MDEVRPTW) is an extension of the electric vehicle routing problem with time windows (EVRPTW). Due to the driving range limit, the EVs need to recharge at some charging stations en route. In the MDEVRPTW, the EVs depart from different depots, visit the assigned customers for delivery, and finally return to the depot where they leave. The EVs could recharge at any depot or public charging station whenever necessary. This problem is formulated as a mixed-integer linear programming model, and an adaptive large neighbourhood search algorithm is proposed for solving it. In the proposed approach, both general and problem-specific destroy and repair operators are applied to improve solution quality. Numerical results show that the proposed approach can obtain high-quality solutions within less computing time and an elite version of the proposed ALNS could perform better than the complete version. [Received: 20 August 2021; Accepted: 25 April 2023]

Keywords: electric vehicle routing problem; multi-depot; time windows; charging station; adaptive large neighbourhood search.

DOI: 10.1504/EJIE.2024.139327

European Journal of Industrial Engineering, 2024 Vol.18 No.4, pp.606 - 636

Accepted: 25 Apr 2023
Published online: 01 Jul 2024 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article