The multi-depot pickup and delivery problem with capacitated electric vehicles, transfers, and time windows

The Pickup and Delivery Problem has received increasing attention as a result of the recent growth of third-party delivery companies, and electric vehicles (EVs) are becoming a preferable choice for such large delivery systems due to their environmental benefits. The EVs, however, have limited energy capacity; thus, intra-route facilities are required to recharge them. These facilities can also be visited to transfer requests to other vehicles. In this study, we introduce a novel pickup and delivery problem with electric vehicles and transfers. The traditional constraint that each request should be handled by a single vehicle, is relaxed in this problem with transfers, and additionally, we incorporate other practical considerations such as multi-depots, time-windows, and EVs’ battery and carrying capacity constraints. We develop a mixed-integer linear programming model encompassing all these constraints. To address the computational difficulty of the problem, we propose a hybrid heuristic combining Simulated Annealing (SA) and Large Neighborhood Search (LNS). Experimental results reveal that for small instances where CPLEX can find optimal solutions, our heuristic finds them about 90% faster.