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.