A Hybrid Genetic Search Algorithm for Capacitated Electric Vehicle Routing Problem

Authors

Dongyao Jin, School of Computer Science and Engineering, Hunan University of Science and Technology, Xiangtan 411201, China; Hunan Key Laboratory for Service Computing and Novel Software Technology, Xiangtan 411201, China
Mi Liu, School of Computer Science and Engineering, Hunan University of Science and Technology, Xiangtan 411201, China; Hunan Key Laboratory for Service Computing and Novel Software Technology, Xiangtan 411201, China
Yena Zhu, School of Computer Science and Engineering, Hunan University of Science and Technology, Xiangtan 411201, China; Hunan Key Laboratory for Service Computing and Novel Software Technology, Xiangtan 411201, China
Yijiang Zhao, School of Computer Science and Engineering, Hunan University of Science and Technology, Xiangtan 411201, China; Hunan Key Laboratory for Service Computing and Novel Software Technology, Xiangtan 411201, China

Abstract

Abstract: The capacitated electric vehicle routing problem (CEVRP) is an NP-hard combinatorial optimization problem in logistics distribution, aiming to minimize the total delivery distance of electric vehicles while satisfying carrying capacity and battery charge constraints. A hybrid genetic search algorithm is proposed to solve CEVRP by decomposing it into two subproblems: capacitated vehicle routing problem (CVRP) and fixed-route vehicle charging problem (FRVCP). A coding scheme with a two-layer chromosome structure is designed to represent the decision variables of these two subproblems. A Split operation is employed to generate vehicle routes for solving CVRP, and five neighborhood search operators, including Relocate, 2-Opt, 2-Opt*, SWAP, and SWAP*, are adopted to perform local optimization on the routes. To solve the FRVCP, a backtracking-based charging strategy is proposed to insert the appropriate charging station number into the routes. The proposed algorithm is compared with five methods on CEVRP benchmark instances. Experimental results show that the proposed algorithm can find better solutions than the other methods in most instances and is especially suitable for solving large-scale CEVRP.

Recommended Citation

Jin, Dongyao; Liu, Mi; Zhu, Yena; and Zhao, Yijiang (2024) "A Hybrid Genetic Search Algorithm for Capacitated Electric Vehicle Routing Problem," Journal of System Simulation: Vol. 36: Iss. 11, Article 3.
DOI: 10.16182/j.issn1004731x.joss.23-0863
Available at: https://dc-china-simulation.researchcommons.org/journal/vol36/iss11/3

First Page

2528

Last Page

2541

CLC

TP391.9

Recommended Citation

Jin Dongyao, Liu Min, Zhu Yena, et al. A Hybrid Genetic Search Algorithm for Capacitated Electric Vehicle Routing Problem[J]. Journal of System Simulation, 2024, 36(11): 2528-2541.

Corresponding Author

Liu Min

DOI

10.16182/j.issn1004731x.joss.23-0863