The multi-depot pickup and delivery problem with capacitated electric vehicles, transfers, and time windows. (May 2023)

• Record Type: Journal Article
• Authors: Agrali, Cansu; Lee, Seokcheon
• Is Part Of: Computers & industrial engineering. Volume 179(2023)
• Publication Date: 2023-05
• Subjects: Transportation -- Routing -- Pickup and delivery problem with transfers -- Electric vehicles -- Metaheuristic; Engineering -- Data processing -- Periodicals; Industrial engineering -- Periodicals; 620.00285
• DOI: 10.1016/j.cie.2023.109207
• Languages: English
• ISSNs: 0360-8352

Abstract

Abstract: 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. Highlights: Studies the multi-depot pickup and delivery problem with capacitated electric vehicles, transfers, and time windows. Formulates a mixed-integer linear programming model. Provides an efficient Simulated Annealing algorithm. Revises the transfer constraint given in the literature.