Intra-Route Location Routing for the Pickup and Delivery Problem with Transfers

The development and increasing application area of electric vehicles (EVs) in city logistics has contributed to the necessity of intermediate stops for charging EVs. Due to the limited service range of these vehicles, charging facilities must be located at the same echelon as customers’ and differ from depots or hubs in that they are visited while serving customers. Thereby, these facilities allow vehicles to exchange requests and get recharged. In this study, we present the Intra-route Location Routing for the Pickup and Delivery Problem with Transfers that arises in this novel scenario. There are sets of requests, vehicles, and potential transfer locations (intra-route facilities). Each request consists of a pair of a pickup node and a delivery node. Vehicles start their routes from their respective origins, serve customers (pickup and delivery), and return to the origin nodes. In the generic Pickup and Delivery Problem, a request must be served by a single vehicle that picks and delivers the request. In our study, however, multiple vehicles can service a request collaboratively by transferring it to each other at a transfer facility. In this problem context, we decide vehicle schedules, transfer decisions, and which nodes should serve as intra-route facilities. We propose a mathematical model for this novel NP-Hard problem. Experimental results indicate the computational difficulty of the problem in practice. For several small instances, solving the mathematical model by using a commercial solver does not even find the optimal solutions in six hours, and given the importance of this problem, it must be addressed in future works.