An Efficient Threshold Acceptance-Based Multi-Layer Search Algorithm for Capacitated Electric Vehicle Routing Problem
- 5 January 2024
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Intelligent Transportation Systems
- Vol. 25 (6) , 5867-5879
Abstract
The capacitated electric vehicle routing problem (CEVRP) extends the traditional vehicle routing problem by simultaneously considering the service order of the customers and the recharging schedules of the vehicles. Due to its NP-hard nature, we decompose the original problem into two sub-problems: a capacitated vehicle routing problem (CVRP) and a fixed route vehicle charging problem (FRVCP). A highly effective threshold acceptance based multi-layer search (TAMLS) algorithm is proposed to quickly obtain high-quality solutions. TAMLS consists of three layers. An iterated thresholding search procedure and a thresholding selection procedure are employed to produce diversified CVRP solutions in the first layer and to screen out high quality ones in the second layer, respectively. In the third layer, a removal heuristic coupling with an enumeration method is adopted to solve FRVRP, which produces optimized charging schedules. Extensive computational results show that TAMLS outperforms the state-of-the-art algorithms in terms of both solution quality and computation time. In particular, it is able to obtain new best results for 11 out of 17 benchmark instances, and reach the best known results on the remaining 6 instances. Additional experimental analyses are performed to better understand the contributions of key algorithmic components.Keywords
Funding Information
- National Natural Science Foundation of China (72271240, 72371157, 72122006)
- Natural Science Foundation of Hunan Province (2022JJ30671)
- High-Level Young Talents Project of National University of Defense Technology
This publication has 41 references indexed in Scilit:
- A fast tri-individual memetic search approach for the distance-based critical node problemEuropean Journal of Operational Research, 2022
- A hybrid genetic algorithm for the electric vehicle routing problem with time windowsControl Theory and Technology, 2022
- Iterated dynamic thresholding search for packing equal circles into a circular containerEuropean Journal of Operational Research, 2022
- A threshold search based memetic algorithm for the disjunctively constrained knapsack problemComputers & Operations Research, 2021
- A simulated annealing heuristic for the hybrid vehicle routing problemApplied Soft Computing, 2017
- New benchmark instances for the Capacitated Vehicle Routing ProblemEuropean Journal of Operational Research, 2017
- Iterated responsive threshold search for the quadratic multiple knapsack problemAnnals of Operations Research, 2014
- An adaptive large neighborhood search heuristic for the Pollution-Routing ProblemEuropean Journal of Operational Research, 2012
- Particle swarm optimization algorithm for a vehicle routing problem with heterogeneous fleet, mixed backhauls, and time windowsJournal of Intelligent Manufacturing, 2012
- Active guided evolution strategies for large-scale vehicle routing problems with time windowsComputers & Operations Research, 2005