无人机﹣卡车协同配送场景：基于逻辑型Benders分解的鲁棒调度方法

一、研究背景与问题提出

随着电子商务的迅猛发展，无人机（UAV） 参与末端配送已从概念走向现实。亚马逊在2013 年启动的 Prime Air 项目致力于在 30 分钟内向客户投递重达 5 磅的包裹。随后奔驰、Siroop 与 Matternet 等公司推出无人机与卡车协作的同城配送服务；无人机从仓库出发，飞往预定会合点交货，再由卡车将商品送达用户。多家物流企业（如 Zookal、DHL、UPS、Walmart 等）也陆续引入无人机配送技术。

研究者对无人机与卡车协同配送模式进行了不同抽象，主要包括：

• 飞行副手旅行商问题（FSTSP）：卡车与无人机一起离开仓库，当卡车到达客户节点时，卸下无人机让其独立完成配送后再与卡车汇合。
• 并行无人机调度旅行商问题（PDSTSP）：无人机和卡车各自独立运行，无人机直接从仓库为部分客户派送，卡车则独自向其余客户配送。
• 支援无人机配送问题：奔驰等公司的合作项目提出了一种新模式，使用较大的支援无人机从仓库携带多件商品飞往会合节点，交给卡车，再由卡车完成最后一段运输。

上述系统描述在图 1 中展示：左图（a）为 FSTSP 模式，服务无人机直接为节点 2 和 6 客户配送；中图（b）为 PDSTSP 模式；右图（c）为支援无人机模式，其中支援无人机将节点 4、5、6 的商品送至会合节点 3 后由卡车配送。

随着同日配送和定制生产的需求增加，商品往往在配送期内陆续到达仓库。考虑到这一特性，文献提出了带发布时序并含支援无人机的并行无人机调度旅行商问题（PDSTSP‑DR）。在这一问题中：

• 仓库拥有一辆卡车、一架支援无人机和一组服务无人机。服务无人机重量限制为 2.3 kg，可一次携带一件商品；支援无人机体积较大，能同时携带多件商品。
• 部分客户位于无人机可达区域，服务无人机可直接送货；其余客户通过卡车配送。
• 新商品陆续到达仓库，可由服务无人机直接送达客户，或由支援无人机运到卡车在会合节点交接。
• 无人机的行驶时间受风向和风速等因素影响而不确定，需通过稳健优化处理。

问题的目标是最小化系统的完工时间（makespan），即卡车、支援无人机和所有服务无人机完成各自任务的最迟完成时刻。若不使用支援无人机，卡车必须等待所有商品到齐后一次出车，或多次返回仓库装货，效率显著降低。

二、研究贡献与文献概述

早期研究主要关注确定性设置下的 PDSTSP 及其扩展。已有工作通过约束规划、启发式算法或元启发式求解多卡车多无人机协同配送问题，但大多忽略了商品发布时序与飞行时间不确定性。此外，仅有少量工作考虑支援无人机的辅助作用。本研究的贡献体现在以下方面：

• 引入发布时序：考虑产品在配送期内陆续到达仓库，使调度更加贴近现实生产与生鲜配送情形。
• 引入支援无人机：支援无人机可以在仓库与会合节点之间往返运送多件商品，减少卡车等待时间并缩短系统完工时间。
• 引入飞行时间不确定性：基于稳健优化框架将风速等因素导致的飞行时间波动建模为区间不确定参数，并通过预算不确定性集加以控制。
• 提出改进的 MILP 模型与逻辑型 Benders 分解算法：通过利用最早释放时间（ERD）规则和动态规划简化模型，消除大  参数，从而提高求解效率。

三、问题建模与不确定性表示

3.1 系统描述与假设

在 PDSTSP‑DR 中，卡车、支援无人机和多架服务无人机停留在同一仓库。设客户集合为 ，其中有些客户可由服务无人机直接送货（记为 ），其余由卡车配送。会合节点集合  位于支援无人机可达但非客户的位置。基本假设如下：

• 服务无人机容量与作业：每架服务无人机一次只能携带一个商品，从仓库出发飞至客户节点 ，卸货并起飞，再返回仓库。每趟作业包括前向飞行 、卸货与起飞时间  以及返回飞行  。
• 支援无人机容量与作业：支援无人机体积较大，可携带多件商品；它将商品送至会合节点  并与卡车交接，然后返回仓库。其单趟作业包括前向飞行 、卸货与起飞时间  以及返回飞行 。
• 卡车作业：卡车可携带多件商品，可直接从仓库出发沿路径服务部分客户，也可在会合节点与支援无人机交接后继续配送。
• 发布时序：每件商品  有一个释放时间 ，表示商品可被装载的最早时刻；仓库在时刻  之前无法取得该商品。
• 飞行时间不确定：由于风速和风向等因素，服务无人机和支援无人机的飞行时间及卸货时间在区间内波动。

为帮助理解调度过程，图 2 展示了一个五客户两会合节点的确定性 PDSTSP‑DR 示例，图 3 给出了对应调度甘特图。客户 4、5 由卡车服务，客户 1、2 由服务无人机 1 服务，客户 3 由服务无人机 2 服务。卡车和支援无人机在会合节点 7 汇合，支援无人机将客户 4 的商品交给卡车，卡车完成配送并返回仓库。根据图 3，卡车、支援无人机、服务无人机 1 和 2 的完成时间分别为 15.5、14.5、14 和 16.5 单位时间，因此系统完工时间为 16.5 单位。

现实中，风速变化等可能导致飞行时间和卸货时间同时偏大，进而影响调度可行性。图 4 展示了一个鲁棒 PDSTSP‑DR 实例，其中所有不确定参数取最大值，图 5 展示了相应的调度。与确定性调度相比，服务无人机 1 完成两次行程的总时间增加到 18 单位，系统完工时间上升至 18 单位。然而由于不确定性影响可能只出现在部分行程，文献采用预算不确定性集控制不确定行程的数量，并定义“鲁棒性价格”参数  （服务无人机）和  （支援无人机）。

当  时，服务无人机一次运行中至多有一趟行程受到不确定性的影响。图 6 对比了三种情况：全部确定、第一趟确定/第二趟不确定、第一趟不确定/第二趟确定；可见最坏情况下无人机的完工时间为 16.5 单位。

3.2 不确定性建模

为了刻画飞行时间和卸货时间的不确定性，文中采用区间不确定集并引入预算参数  和  来限制同时受到扰动的行程数量。以下给出相应集合的形式定义：

不确定支援无人机前向飞行时间集合

不确定支援无人机返航时间集合

不确定服务无人机前向飞行时间集合

不确定服务无人机返航时间集合

对于卸货与起飞时间，定义集合

其中  和  为不确定性权重， 和  表示最大偏差， 和  控制在支援无人机和服务无人机的行程中最多有多少次受到不确定扰动。

3.3 最坏情形完成时间与 ERD 规则

通过最早释放时间（Earliest Release Date，ERD）规则对服务无人机调度进行排序，可证明在排序好的客户序列上，计算最坏情形完成时间的递推关系式。当第  个客户由服务无人机  服务，并允许有  次行程受到不确定性的影响时，其最坏完成时间满足以下下界条件：

上述不等式（63–64）利用 ERD 规则替代了原模型中涉及大  和三维二进制变量的复杂时序约束，从而显著减少决策变量数量并消除了大  参数。

四、改进的 MILP 模型

4.1 决策变量与目标函数

为了统一描述卡车、支援无人机和服务无人机的调度，建立混合整数线性模型 (MILP‑2)。关键决策变量包括：

•  ——卡车从节点  驶向节点  的 0/1 变量；
•  ——支援无人机在会合节点  把客户  的商品交给卡车的 0/1 变量；
•  ——客户  由服务无人机  服务的 0/1 变量；
•  ——分别表示在第  个不确定预算下，卡车、支援无人机和服务无人机完成节点  相关作业的最坏完成时间。

目标函数是最小化系统完工时间 ：

其中  至少大于卡车、支援无人机和所有服务无人机的最坏完成时间。

4.2 主要约束

模型包括以下约束类别（仅列出改进模型中的关键约束，详见原文）：

• 客户分配：每个客户要么由卡车服务，要么由某一架服务无人机服务。
• 卡车路径与会合节点：卡车必须遵循有向巡回路径并满足流平衡；若卡车与支援无人机在会合节点相遇，则支援无人机必须抵达并返回。
• 服务无人机时序：利用 ERD 规则排序客户序列后，通过约束 (63)–(64) 计算 ，确保在确定性和不确定性情况下的作业时间。
• 支援无人机与卡车时间关系：卡车抵达会合节点后必须等待支援无人机卸货；当支援无人机返回时，卡车方可出发。
• 改进的有效不等式：约束 (66)–(71) 用于加强模型，例如保证当客户  在仓库装货时，所有释放时间小于  的客户可以直接由卡车在仓库装载。

通过引入上述约束并利用 ERD 规则，改进模型消除了大  参数并减少了决策变量数量，提高了 MILP 的求解效率。

五、逻辑型 Benders 分解算法

由于 PDSTSP‑DR 的复杂度高，直接求解 MILP‑2 在中等规模实例上耗时较长。论文采用 逻辑型 Benders 分解（LBBD） 技术将问题分解为主问题和多个辅助问题：

5.1 主问题

主问题以决策变量  和  为核心，确定每个客户是由卡车还是由哪一架服务无人机服务，并决定支援无人机在何处与卡车交接。确定了这些分配变量后，卡车的行驶顺序和各无人机的调度可在辅助问题中计算。

5.2 辅助问题

• 卡车与支援无人机调度子问题：固定客户分配后，此子问题通过动态规划计算卡车和支援无人机的最坏完成时间  和 。
• 服务无人机调度子问题：每个服务无人机独立解决一个按 ERD 规则排序的单机调度问题，利用公式 (63)–(64) 递推计算 。

在求解辅助问题后，如果发现某个分配不可行或取得的完工时间超过当前上界，则将相应的可行性割或最优性割添加回主问题以剪枝；其中包含针对卡车、支援无人机和服务无人机的多种割类型。

算法总体流程如图 7 所示，其中先在主问题层面生成客户分配并求解辅助问题，然后根据求得的上下界迭代改进分配直至收敛。

六、数值实验与敏感性分析

6.1 算法性能比较

作者通过随机生成包含 5 至 22 个客户的实例验证 LBBD 算法与改进 MILP 的性能。在基准设置下，LBBD 算法在 5 秒内就能求解大部分实例，而 MILP‑2 平均需要 2700 秒才能求解同样规模问题。表格结果显示，LBBD 在所有实例中都能找到最优解，而 MILP‑2 仅在部分实例达到最优并且耗时更长。图 9 描绘了动态规划算法求解辅助问题所需时间随客户数量的增长趋势，可以看到随着客户数增加，辅助问题的平均求解时间呈幂次上升，但在 22 个客户时仍在可接受范围内。

6.2 支援无人机与客户覆盖的敏感性分析

作者进一步研究支援无人机存在与否、服务无人机覆盖比例等参数对目标值的影响。图 10 比较了在不同问题规模下（10、12、15 个客户）使用支援无人机与否的平均完工时间节省率；可见支援无人机显著缩短了完工时间，且客户覆盖率越高（）节省越明显。

图 11 分析了服务无人机覆盖比例  的变化对系统完工时间的影响。随着  增加（代表能由服务无人机服务的客户比例降低），系统完工时间明显上升，且客户数量越多这种趋势越显著。。

图 12 总结了在不同客户数量下，平均完工时间的变化趋势；当客户数从 8 增加到 22 时，完工时间呈现先上升后趋缓的规律。

6.3 不确定性预算  的影响

不确定性预算  表示在服务无人机的客户序列中最多有多少次行程受到不确定性影响。图 13 展示了当客户数量一定时，增加  对完工时间的影响。结果表明：

• 当  较小（例如 1 至 2）时，完工时间随  增加而明显上升，因为更多行程受不确定性影响。
• 当  增长到某一阈值后，完工时间可能先下降再上升；这种现象与风速方向相关，当无人机与风向一致时，不确定性可能反而缩短飞行时间。

6.4 服务无人机调度示例与释放时间多样性分析

图 14 给出了一个服务无人机调度示例，其中客户 1 和 2 的释放时间为 0，而客户 3 和 4 的释放时间较大。可见当释放时间分布差异较大时，服务无人机的待机时间也显著增加，需要充分利用 ERD 规则排序客户。

图 15 – 图 17 讨论了释放时间分散度对支援无人机与卡车载荷的影响。图 15 显示随着释放时间多样性的增加，服务无人机待机时间增长。图 16 表明释放时间多样性提高时，支援无人机在会合节点交付的商品数量也增加；图 17 则展示卡车在仓库直接装载的商品数量随释放时间多样性增大而减少。这些结果说明在存在释放时间差异时，应利用支援无人机主动外送，以避免卡车在仓库等待。

七、结论与管理启示

本文提出的 PDSTSP‑DR 模型及算法为多车辆协同配送问题提供了新的理论与实践工具。主要结论与启示包括：

• 支援无人机显著提高效率：使用支援无人机可以将新到达商品及时送到卡车，减少卡车等待时间，从而缩短系统完工时间。
• 释放时间排序与不确定性预算相结合：通过 ERD 规则排序客户并利用预算不确定性集限制受扰行程数量，可以在保证鲁棒性的前提下提高模型可解性。
• LBBD 算法优于直接求解：与改进 MILP 模型相比，逻辑型 Benders 分解算法能在较短时间内求解更大规模实例，并能通过割加强化大幅缩小求解空间。
• 敏感性分析的管理启示：增加服务无人机覆盖比例和支援无人机数量可以有效降低完工时间；不确定性预算过大或过小都可能导致效率下降；释放时间分散度增大时应灵活使用支援无人机以避免卡车等待。

综上所述，本文通过构建鲁棒的并行无人机调度模型、提出改进的 MILP 和逻辑型 Benders 分解算法，以及深入的数值分析，为城市配送中无人机与卡车协同调度提供了新的思路。未来研究可考虑更复杂的能耗模型、多仓库设置或实景天气数据驱动的不确定性建模，以进一步提升模型的实用性。

文章须知 

推文编辑：单子叶 

责任编辑：张仁义

原文链接：https://doi.org/10.1016/j.tre.2024.103877