卡车-无人机协同补救机制：随机扰动下的应急配送系统

论文题目：Truck–drone routing problem with stochastic demand

第一作者：王飞龙 北京航空航天大学在读博士生，研究方向包括组合优化、卡车-无人机协同路径问题以及城市空中出行。

E-mail：bhwfl@buaa.edu.cn。

通讯作者：李红启 北京航空航天大学长聘副教授，从事物流运输领域的数学规划建模与优化算法、低空技术运用与优化、无人机/无人车调度优化、商用飞机供应链技术等方面的科研和教学工作。E-mail：lihongqi@buaa.edu.cn。

卡车-无人机协同补救机制：随机扰动下的应急配送系统

论文摘要

在自然灾害、高度不确定的配送场景中，传统的车辆配送因道路中断和需求波动而效率低下。旋翼无人机具备垂直起降、抗路网阻断的优势，被引入应急物流以补充卡车配送。文章正式提出卡车–无人机随机需求路径问题（TDRP‑SD），在给定的一组客户中，卡车携带无人机同时执行配送，客户需求随机揭示，不足时需中途补货。作者针对现有研究忽视随机需求的局限，建立了三个补货策略：经典补货、预防性补货和卡车–无人机同步（TDS）补货策略，并证明了其期望成本的单调性，构建了动态规划框架。在算法方面，论文设计了一种两阶段混合启发式算法：先通过贪婪和大邻域搜索构造先验路线，再利用“字符串删除”与模拟退火等策略优化。算例结果显示，该算法在两个基准数据集上获取了多项新最优解，平均成本优于已有粒子群优化和自适应大邻域算法。最后，作者扩展出具有 302 个客户的新实例，敏感性分析表明提升单站点允许的无人机航线数可显著降低配送成本。

一、问题背景与研究意义

配送需求随机性和道路基础设施破坏是灾害场景中的两大挑战。为了快速将食品、药品和血液等物资送达灾区，研究者提出“卡车–无人机组合配送”概念：卡车携带旋翼无人机，卡车在客户处停靠时放飞无人机执行支线配送。已有工作主要关注确定性需求下的飞行员问题(FSTSP)和带无人机的旅行商问题(VRPD)，在随机需求环境下缺乏系统的补货策略。

研究意义在于：

• 应急场景真实模拟：引入随机需求和道路受阻，贴近自然灾害或医疗应急配送需求。
• 制度创新：首次提出TDRP‑SD并引入卡车–无人机同步补货策略，使无人机不仅配送，还用于补货提升系统抗风险能力。
• 算法价值：开发针对大型实例的启发式算法，可用于应急决策支持，在时间有限的情况下获得高质量方案。

二、问题定义与模型框架

2.1 任务描述

配送网络由一个仓库、多辆卡车与若干单架无人机组成。每辆卡车带一架容量为  的无人机，仓库另有若干单元容量的补货无人机。客户集合记为 ，每个客户需求  在车辆到达时随机揭示。

系统运作规则如下：

• 卡车路线：卡车按照先验路线访问一系列客户，离开仓库时携带初始货物 。在某客户处停靠时，可以放飞车载无人机执行单个客户的支线配送。

• 无人机路线：无人机从卡车起飞，服务指定客户后返回同一卡车。无人机必须在卡车停靠的客户位置（称为起降点）起飞和回收。

• 补货策略：若卡车剩余货物不足以满足下一客户需求，可采用三种策略：

1. 经典补货：卡车返回仓库装满货物后返回断点继续路线。
2. 预防性补货：在货物耗尽前主动返回仓库补货。
3. 卡车–无人机同步补货：仓库派出单元容量的无人机补充卡车货物，卡车同时回仓库装满后继续配送。

2.2 目标函数

设卡车路线为 ，定义  为车辆完成客户  服务后剩余货物为  时，从该节点到仓库的最小期望成本。对每个节点，三种补货策略对应的期望成本记为 、 和 。总体期望成本递推式为：

其中每项成本考虑了卡车行驶时间、无人机出动时间以及不同补货行为的代价（例如经典补货需往返仓库的距离），三种方案的递推方程在正文中分别列出。通过动态规划逆向迭代，可计算给定先验路线的期望总成本。

2.3 典型示例

论文给出了 TDRP‑SD 的示例：共有 13 个客户，两辆带无人机的卡车与一架单元容量无人机。卡车需根据随机需求决定是否回仓或通过无人机补货，示例展示了不同补货时机及无人机派遣的协同模式。以下图展示了该问题的示意结构，卡车与无人机的协同路线清晰呈现。

三、补货策略与动态规划方法

3.1 补货策略及其比较

• 经典补货（策略1）：当卡车货物用尽时，返回仓库装满货物再回到断点。
• 预防性补货（策略3）：在出现缺货之前主动回仓库补货，避免途中断货。
• 卡车–无人机同步补货（策略2）：仓库派出单元容量无人机直接补充卡车货物，卡车同时前往仓库补满后继续配送，多架无人机可并行出发。

为比较三种策略的成本，论文构建了分析框架并通过图示阐述：在车辆到达客户  时，若剩余货物  小于下一客户需求，将触发补货策略。下图展示了四种路线情形，用以说明在同等服务序列下，使用无人机支持的路径能明显降低行驶里程和补货次数。

从理论分析可知，当单架无人机能力不足或客户间距离较大时，过多使用无人机可能反而增加成本。因此论文在补货策略选择中提供一个优先级准则：只有当同步补货的成本小于经典补货时才调用策略2，并证明了无人机补货次数的上界。

3.2 动态规划与单调性

文章推导了基于补货策略的动态规划递推公式（公式2–4），描述了车辆在节点  和下一节点  之间的期望成本演化，并考虑三种可能情形（无需补货、经典补货、同步补货）。由于随机需求导致期望成本不一定单调增加，直接求解递推过程计算量大。作者首先证明了若固定补货策略，递推函数  对库存  单调递减，从而可以剪枝降低计算复杂度。随后采用分解思想，将总体函数拆分为三种策略的子问题独立求解。

为了提高动态规划效率，算法在求解期望成本时采用短路径深度搜索：对包含客户数最少的卡车路线优先计算期望成本，因为短路线使得状态空间较小，缺货概率较低。这种设计减少了大量无效计算。

四、混合启发式算法设计

TDRP‑SD 属 NP 难问题， exact 方法只能解决几十个节点的小规模实例。为此，论文提出两阶段混合启发式算法：

4.1 初始解构造

算法先在确定需求假设下构造先验路线：假设每个客户需求为 （卡车服务）或 （无人机服务），保证无人机航线在随机需求下仍可行。具体步骤如下：

• 初始化无解集 ，选择距离最近的客户加入当前路线。
• 若当前客户的半负载需求超过卡车剩余容量，则新建一条卡车路线。
• 判断潜在的无人机航线是否满足容量及飞行距离约束，满足则构造无人机航线。
• 更新卡车装载并循环，直到覆盖全部客户。
• 最后调用大邻域搜索（LNS）进一步优化。

4.2 “字符串删除”与重构

为摆脱局部最优，作者将Slack induction by string removals (SISRs) 融入破坏–重建框架中：

• 破坏阶段：根据参数决定需要破坏的路线数和需要删除的客户数，从现有解中随机选定“种子客户”，删除其邻近的一串客户，若选中起降点则相应无人机航线一起删除。
• 重建阶段：按需求大小、随机性和距离对被删客户排序，引入“眨眼”策略以概率跳过部分插入位置，仅在成本较优的位置尝试插入。对于每个候选插入位置，首先使用确定性成本筛选，再在少量优秀位置上调用动态规划计算期望成本，选择最小者。

4.3 搜索增强策略

为提高搜索质量，算法集成了下列机制：

• 短路线深度搜索：优先在客户较少的路线中评估期望成本；
• 模拟退火：按概率接受非改进解，避免陷入局部最优，温度逐渐下降；
• 上下界剪枝：记录当前最佳解作为上界，重建阶段若估计的下界成本不优于上界则提前终止。

这些策略组合形成了高效的混合启发式算法，其流程如图所示（由于篇幅原因，此处略去伪代码）。

五、数值实验与结果分析

文章使用 C++ 实现算法，在 i5‑10400F/16GB 环境下运行。测试数据包括两个标准数据集及一批扩展实例。基准数据集 DATA I 来源于 Christofides(1979)，DATA II 来源于 Augerat(1995)，客户数从 51 到 199。实验中将卡车容量取 10，单元无人机容量取 1，需求随机服从离散分布。

主要结果：

• 与文献中的粒子群优化(PSO)和自适应大邻域搜索(ALNS)算法相比，混合算法在 DATA I 上平均成本分别降低 3.22% 和 4.18% ，21个实例中有18个获得了新的最优解。平均计算时间约 69.27 s。
• 在 DATA II 上，分支定价算法能解决 38 个实例，混合算法在 53.41 s 平均时间内获得其中 37 个实例的同等最优解，同时为 6 个实例提供了更优解。
• 作者构建了 302 个客户的大规模扩展实例，通过敏感性分析发现：随着单个起降点可布置的无人机航线数增加，总成本显著下降，说明同步补货策略充分发挥了无人机支援作用。

下图给出了不同补货策略下的成本比较示意，可看出当无人机补货速度快于卡车时，同步补货显著优于经典补货。

六、结论与展望

本文针对随机需求环境下的卡车–无人机联合配送问题提出了 TDRP‑SD 模型，首次引入卡车–无人机同步补货策略，对比经典和预防性补货展示了其在应急物流中的优势。利用递推方程与单调性分析，构建了期望成本动态规划框架，并在此基础上开发了含 SISRs 的混合启发式算法。实验结果表明，该算法在中大型实例上超越了现有方法并能解决 300+ 客户规模问题。

未来研究可在以下方向继续拓展：

• 研究多无人机携带、异质无人机等复杂设置，提高系统弹性。
• 探索更高效的精确算法或近似算法解决 TDRP‑SD，提高理论深度。
• 将模型推广到动态需求、实时交通信息等情形，开发实时调度策略。

综上，该研究为应急物流和不确定需求下的配送优化提供了新的模型和算法框架，为实际应用提供了参考价值。

原文链接见文末，或扫下方交流群二维码。群内实时更新推文及原文 pdf，方便专家学者随时获取（若二维码失效，请翻阅扫描最新文章的二维码）。