近日,我院王天宇副教授(第一作者)与中国科学院大学经济与管理学院吴德胜教授、美国内布拉斯加大学林肯分校David L. Olson教授合作完成的研究论文《The Complexity of Scheduling Pickup and Delivery Jobs》,在运筹学与管理科学领域国际顶级期刊《Operations Research》在线发表。(论文DOI:10.1287/opre.2026.2625)

在共享出行、外卖配送和同城快递等平台服务中,大量需求往往集中于相同的出发地点。平台需要在安排车辆行驶路线的同时,协调各地点订单的服务顺序,以降低用户等待时间。实际运营中,有的场景需要按照下单时间或服务优先级依次处理订单,有的场景则允许从待服务订单中灵活选取。服务规则的差异,使取送调度同时涉及空间上的车辆移动与时间上的任务安排。
论文在订单信息已知、服务地点数量固定的条件下,比较按既定顺序服务的排队模式与可灵活排序的任务池模式。研究发现,最小化总等待时间时,前者为强NP难问题,后者可在多项式时间内求解;若最小化总行驶距离,两者均可在多项式时间内求解。论文进一步提出动态规划与具有性能保证的近似算法,识别固定司机数量、特定路段长度尺度等可解条件,拓展至取货地点固定、送达地点增长的配送场景,并揭示就近服务队首订单可能偏离全局最优。
该研究从计算复杂性角度厘清了聚合取送调度的可解边界,丰富了车辆路径与任务调度领域的理论研究,为平台识别调度难点、评估服务规则及选择优化算法提供了依据。相关成果可为共享交通、即时配送等场景下的运力组织和服务效率优化提供理论参考。
《Operations Research》是运筹学与管理科学领域的国际顶级学术期刊,创刊于1952年,由美国运筹学与管理科学学会(INFORMS)出版,与《Management Science》同为该学会的旗舰期刊。该刊入选UTD24和FT50期刊目录,是英国商学院协会ABS(AJG)4*级期刊、中国管理科学学会联合体(FMS)A类期刊,并被SCIE和SSCI收录。期刊强调数学理论与方法的严谨性,重视通过创新模型和分析方法解决复杂运营与管理决策问题,推动运筹学基础理论与实际应用的发展。
