Hybrid Variable Neighborhood Search algorithm for the Multi-trip and Heterogeneous-fleet Electric Vehicle Routing Problem

Authors

Weiquan Wang, 1.School of International Trade and Economics, University of International Business and Economics, Beijing 100029, China;3.Department of Information Management, University of International Business and Economics, Beijing 100029, China;Follow
Ding Ding, 1.School of International Trade and Economics, University of International Business and Economics, Beijing 100029, China;Follow
Shuyan Cao, 2.School of Statistics, University of International Business and Economics, Beijing 100029, China;

Abstract

Abstract: Based on the real business practice, the multi-trip and heterogeneous-fleet electric vehicle routing problem (MTHF-EVRP) with time windows in green logistics is studied. A path-based mixed-integer linear model is built for the precise solution to the small-scale instances. A hybrid variable neighborhood search algorithm (Hybrid VNS) combined the variable neighborhood search algorithm with the labeling algorithm is proposed for the large-scale instances. The algorithm generates a modified insertion heuristic with random factor to construct the initial solution, allows the time window and range violation, adopts the neighborhood operators for the local search, and applies a labeling algorithm to solve the fixed-route recharging problem precisely. The methods are tested on the real-world benchmark instances for MTHF-EVRP. The results on the small-scale instances show that Hybrid VNS can find the optimal solutions in a very short time. Compared with the state-of-the-art algorithm on the large-scale instances, the algorithm can significantly reduce the logistics cost and the great competitiveness of Hybrid VNS is showed.

Recommended Citation

Wang, Weiquan; Ding, Ding; and Cao, Shuyan (2022) "Hybrid Variable Neighborhood Search algorithm for the Multi-trip and Heterogeneous-fleet Electric Vehicle Routing Problem," Journal of System Simulation: Vol. 34: Iss. 4, Article 26.
DOI: 10.16182/j.issn1004731x.joss.21-1133
Available at: https://dc-china-simulation.researchcommons.org/journal/vol34/iss4/26

First Page

910

Revised Date

2021-12-23

DOI Link

https://doi.org/10.16182/j.issn1004731x.joss.21-1133

Last Page

919

CLC

TP391.9

Recommended Citation

Weiquan Wang, Ding Ding, Shuyan Cao. Hybrid Variable Neighborhood Search algorithm for the Multi-trip and Heterogeneous-fleet Electric Vehicle Routing Problem[J]. Journal of System Simulation, 2022, 34(4): 910-919.

Corresponding Author

Ding Ding,dingd@uibe.edu.cn

DOI

10.16182/j.issn1004731x.joss.21-1133