The Complexity of Scheduling Pickup and Delivery Jobs
Operations Research · 13.11.2026
DOI: 10.1287/opre.2026.2625 ↗Kurz gefasst
Fachartikel in der Zeitschrift Operations Research, online erschienen am 13.11.2026. Verfasst von Tianyu Wang und 2 weiteren Autor:innen.
Abstract (Originalsprache)
Scheduling pickup and delivery jobs stands as a critical and challenging problem commonly encountered in time-sensitive logistics and transportation. Often, a large number of requests involving shipments from the same location are aggregated into either a fixed number of job queues, referred to as the queueing mode, or into a fixed number of sets, referred to as the pooling mode. Due to the time-sensitive nature, the objective of scheduling jobs by location and routing drivers is to minimize customers’ waiting times. While request aggregation is widely observed in platform economies and related research, the computational complexity of scheduling pickup and delivery jobs has not been studied. This paper presents a comprehensive complexity analysis of this problem. We prove that the problem is strongly NP-hard in the queueing mode, but is polynomially solvable in the pooling mode. Furthermore, we prove that both modes become polynomially solvable when minimizing total distance, as does the queueing mode with fixed number of drivers or scaled-length edges. Finally, we provide approximation guarantees and extend the analysis to bipartite graphs, identifying solvable variants with relaxed map-size constraints to enhance the applicability.
Zitieren
APA
Wang, T., Wu, D., & Olson, D. L. (2026). The Complexity of Scheduling Pickup and Delivery Jobs. Operations Research. https://doi.org/10.1287/opre.2026.2625
Vancouver
Wang T, Wu D, Olson DL. The Complexity of Scheduling Pickup and Delivery Jobs. Operations Research. 2026. doi:10.1287/opre.2026.2625
BibTeX
@article{Wang2026,
author = {Wang, Tianyu and Wu, Desheng and Olson, David L.},
title = {The Complexity of Scheduling Pickup and Delivery Jobs},
journal = {Operations Research},
year = {2026},
doi = {10.1287/opre.2026.2625}
}
EUVIMED