Logistic Optimization for Multi Depots Loading Capacitated Electric Vehicle Routing Problem From Low Carbon Perspective

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.

Keywords

• Vehicle routing problem
• two-dimensional loading
• electric vehicle
• variable neighborhood search
• space saving heuristic