Pickup & Delivery with Time Windows and Transfers: combining decomposition with metaheuristics
This addresses a logistics optimization problem for routing with load exchanges, offering incremental improvements in solution quality and scalability.
The paper tackles the Pickup and Delivery Problem with time windows and transfers by proposing a Logic-Based Benders Decomposition that improves optimality gaps for all benchmarks and scales to larger instances, and a refined Large Neighborhood Search algorithm that provides near-optimal solutions and enhances scalability.
This paper examines the generalisation of the Pickup and Delivery Problem that allows mid-route load exchanges among vehicles and obeys strict time-windows at all locations. We propose a novel Logic-Based Benders Decomposition (LBBD) that improves optimality gaps for all benchmarks in the literature and scales up to handle larger ones. To tackle even larger instances, we introduce a refined Large Neighborhood Search (LNS) algorithm that improves the adaptability of LNS beyond case-specific configurations appearing in related literature. To bridge the gap in benchmark availability, we develop an instance generator that allows for extensive experimentation. For moderate datasets (25 and 50 requests), we evaluate the performance of both LBBD and LNS, the former being able to close the gap and the latter capable of providing near-optimal solutions. For larger instances (75 and 100 requests), we recreate indicative state-of-the-art metaheuristics to highlight the improvements introduced by our LNS refinements, while establishing its scalability.