Logistic Optimization for Multi Depots Loading Capacitated Electric Vehicle Routing Problem From Low Carbon Perspective
Xiaoning Zhu, Rui Yan, Zhaoci Huang, Wenchao Wei, Jiaqin Yang, Shamsiya Kudratova
Abstract
In this paper, a multi depots capacitated electric vehicle routing problem where client demand is composed of two-dimensional weighted items (2L-MDEVRP) is addressed. This problem calls for the minimization of the transportation distance required for the delivery of the items which are demanded by the clients, carried out by a fleet of electric vehicles in several depots. Since the 2L-MDEVRP is an NP-hard problem, a heuristic algorithm combined variable neighborhood search algorithm (VNS) and space saving heuristic algorithm (SSH) is proposed. The VNS algorithm is used to solve the vehicle routing problem (VRP) sub-problem, and the SSH algorithm is used to solve the bin packing problem (BPP) sub-problem. We propose the space saving heuristic to find the best matching solution between the next loading item and the feasible loading position. The SSH-VNS algorithm is tested by using benchmark instances available from the literature. The results show that the SSH-VNS algorithm has better performance compared with other published results for solving capacity vehicle routing problem (CVRP) and two-dimensional capacity vehicle routing problem (2L-CVRP). Some new best-known solutions of the benchmark problem are also found by SSH-VNS. Moreover, the effectiveness of the proposed algorithm on 2L-MDEVRP is demonstrated through numerical experiments and a practical logistic distribution case. In the last section, the managerial implications and suggestions for future research are also discussed.