The Complexity of Scheduling Pickup and Delivery Jobs

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.

Authors

Institutions

Publication Details

Journal
Operations Research
Published
2026-11-13
DOI
https://doi.org/10.1287/opre.2026.2625
Primary Topic
Vehicle Routing Optimization Methods
Type
article
Field-Weighted Citation Impact
0.00
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
article

The Complexity of Scheduling Pickup and Delivery Jobs

David L. Olson, Tianyu Wang, Desheng Wu
Operations Research
Vehicle Routing Optimization Methods
article

The Complexity of Scheduling Pickup and Delivery Jobs

David L. Olson, Tianyu Wang, Desheng Wu
article en

Abstract

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.

Operations Research
University of Chinese Academy of Sciences (CN), Beihang University (CN)
Vehicle Routing Optimization Methods
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon