联营
排队论
计算机科学
调度(生产过程)
二部图
数学优化
作业车间调度
计算复杂性理论
皮卡
分布式计算
布线(电子设计自动化)
排队
分层排队网络
作业调度程序
运筹学
瓶颈
时间复杂性
作者
Tianyu Wang,Desheng Wu,David L. Olson
出处
期刊:Operations Research
[Institute for Operations Research and the Management Sciences]
日期:2026-11-13
标识
DOI:10.1287/opre.2026.2625
摘要
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.
科研通智能强力驱动
Strongly Powered by AbleSci AI