An exact pruned route-enumeration and set-partitioning approach for the multi-pickup and delivery problem with time windows

The multi-pickup and delivery problem with time windows (MPDPTW) arises in on-demand logistics applications where each delivery corresponds to one or more pickups, all of which must be completed before the delivery. Existing exact methods for the MPDPTW typically rely on large mixed-integer programming formulations with extensive branching and cutting. This paper proposes PRE-SP, an exact pruned route-enumeration and set-partitioning framework that evaluates candidate single-vehicle request subsets a priori , discards infeasible subsets using pruning rules that preserve exactness, and then solves a set-partitioning master problem over the resulting feasible routes. Computational results on the 120 classical MPDPTW benchmark instances show that PRE-SP solves 116 instances to proven optimality within a 1-hour time limit, and all 120 when the time limit is extended to 24 hours for the remaining four cases, outperforming existing exact approaches on this benchmark set. Additional analysis of the explored search space shows how instance size, request length, and time-window structure affect the practical behaviour of the enumeration procedure. Experiments on 30 larger 200-node instances provide additional insight into the scalability limits of the framework. Overall, the results show that route enumeration with exactness-preserving pruning, combined with set partitioning, is a competitive exact solution framework for the MPDPTW on the benchmark classes studied.