编者按：

在应急物流场景中，需求的不确定性和地面交通基础设施的脆弱性一直是困扰物流系统的两大难题。本文研究了卡车-无人机协同配送中的随机需求路径规划问题（TDRP-SD），创新性地提出了卡车-无人机同步补货策略（TDS），使无人机不仅能够执行配送任务，还能在路径失败时协助补货。作者分析了所提补货策略的特性，推导了若干命题以解决期望成本动态规划计算带来的计算负担。在算法层面，作者提出了结合SISRs和贪婪插入的混合启发式算法，采用短路径深度搜索、上下界引导、模拟退火等机制确保算法性能。在两组基准实例上取得了新的最优解，并在最多302个客户的转换实例上验证了算法的有效性。敏感性分析进一步展示了TDS补货策略的优越性能。

关键词：车辆路径规划 • 卡车-无人机协同 • 随机需求 • 应急物流 • 启发式算法

1.引言

1.1 研究背景

2021年，全球共发生367起重大自然灾害（不含流行病），影响超过1.04亿人口。洪水、风暴和地震是三种最常见的灾害类型。由于自然灾害具有高度不可预测性，传统的以执行为中心的组织模式在人道主义救援行动中往往效率低下。一个有效的应急物流系统在灾害期间和灾后至关重要，因为食品、药品、医疗救助设备和血液等关键物资需要及时送达。然而，传统应急物流系统面临两大核心挑战：

挑战一：需求的高度不确定性。 在自然灾害期间或之后，各地点的物资需求几乎不可能事先确定，因为这种需求是动态变化的。今天某个安置点可能需要100份食品，明天可能变成300份，这种波动使得传统的确定性路径规划方法难以适用。

挑战二：地面交通基础设施的脆弱性。 道路、铁路等地面交通基础设施在灾害中极易受损，导致地面车辆需要大量绕行，甚至某些区域完全无法到达。2008年汶川地震后，通往震中的道路几乎全部中断，就是一个典型案例。

1.2 无人机技术的机遇

随着技术进步，无人机在应急物流系统中的应用变得越来越可行。根据配置不同，无人机可分为固定翼、旋翼等类型。由于旋翼持续转动，旋翼无人机可以在狭小场地垂直起降。随着无人机技术的进步，一些工业级旋翼无人机的载重能力显著提升。由于无人机对地面交通拥堵和中断不敏感，无人机技术为依赖地面交通网络的传统应急物流系统提供了极具吸引力的替代方案。目前，应急物流系统是旋翼无人机最有前景的应用领域之一。例如：

• 加州的应急服务部门已经使用无人机帮助探测森林火灾
• 医疗无人机被用于运送救命的自动体外除颤器和急救药品
• Verizon的THOR系统部署了卡车-无人机系统来应对自然灾害和紧急情况

除了应急物流，无人机还可以用于其他需求波动较大的场景，如药品、疫苗、检测试剂盒和血液的配送（需求随患者需要而变化），以及饮料或餐食等需求难以预测的配送场景。

1.3 研究现状与空白

运筹学界一直积极关注卡车与无人机协同配送所带来的同步路径规划挑战，以解决旋翼无人机续航和载重有限的问题。在假设卡车和无人机协同进行包裹配送的研究中，Li等(2020)和Zhou等(2023)研究的两级无人机车辆路径问题可以视为本研究的确定性版本。

然而，根据已有文献，目前大多数研究忽略了需求的随机性特征——即需求只有在车辆到达时才会揭示。 要将卡车-无人机组合应用于应急物流系统的实际场景，必须实现方法论上的创新。因此，本文正式定义了卡车-无人机随机需求路径规划问题（TDRP-SD），该问题涉及无人机快速响应随机需求，并在发生短缺时进行补货。

2.问题定义

2.1 问题描述

图1提供了TDRP-SD的一个描述性示例。场景中有13个需要服务的客户，每个客户的需求在卡车到达时才会揭示（图中用罗马数字表示）。卡车和无人机的最大容量分别为X和III单位。系统使用两辆各配备一架无人机的卡车和一架单机无人机来服务这13个客户。

图1 TDRP-SD的描述性示例

卡车1的配送过程：

• 从仓库满载出发，服务客户1和2后货物耗尽，返回仓库补货
• 从客户2前往客户3时，剩余货物为VIII单位
• 服务客户3后，剩余货物减少到II单位，不足以满足客户4的需求
• 因此在客户3处执行预防性补货，返回仓库补满后继续前往客户4
• 完成客户4和5的服务后无需额外补货

卡车2的配送过程（涉及TDS策略）：

• 从仓库满载出发，到达客户7时剩余货物为III单位
• 这不足以同时满足客户7和12的需求，但足够满足客户12
• 因此无人机2从卡车2发射去服务客户12
• 无人机返回后，卡车将剩余的I单位货物配送给客户7，然后绕道去仓库补货
• 客户7未满足的II单位需求由从仓库派出的单机无人机完成
• 此外，从客户8出发有两条无人机路径
• 当卡车2从客户8出发时，剩余VI单位货物，恰好满足客户9和10的需求

2.2 需求特性

每个客户$ i（i \in N）$的需求$\xi_i$是随机的，只有在卡车-无人机组合或无人机到达该客户时才能知道。需求服从独立分布，具有已知的分布和$m$个可能的取值（按升序排列）：$\xi^1, \xi^2, \ldots, \xi^m$。

令$\text{E}[{\xi }_i]$和$\text{Var}[{\xi }_i]$分别表示${\xi }_i$的期望值和方差，两者均为正数。概率质量函数p(ξik)，k∈M={1,…,m}p(\xi_i^k)，k \in M = \{1, \ldots, m\}p(ξik​)，k∈M={1,…,m}表示${\xi }_i$等于${\xi }^k$的概率。最大需求${\xi }_i$设定为小于卡车容量，但可以大于无人机容量。

2.3 车辆配置

卡车-无人机组合： 仓库配备足够的卡车和旋翼无人机，不考虑固定成本（这是随机需求VRP文献中的常见假设）。每辆卡车容量为 $Q^K$，速度为$v^K$；每架无人机容量为$Q^U（Q^U<Q^K）$，速度为$v^U$。每架无人机单次飞行有最大飞行时间$\Phi$（后文称为"最大航程"）。

作为唯一的配送车辆类型，每个卡车-无人机组合包括一辆卡车搭载一架无人机，两者都可以服务客户。卡车可以服务任何客户，而无人机只能服务满足容量和航程约束的客户子集。每次从卡车发射，无人机只能服务一个客户。卡车和搭载的无人机以配对模式工作，要求搭载的无人机从卡车发射、服务一个客户、然后被卡车回收。

单机无人机： 考虑到无人机的经济可承受性，假设仓库有充足的单机无人机供应。使用仓库的单机无人机进行补货预计是高效且经济的。进行补货时，一架或多架单机无人机必须从仓库出发并返回仓库。

2.4 无人机发射/回收站点（LRS）

在许多开发卡车-无人机配送模式的公司资料中，每架无人机都需要卡车的介入，卡车司机可以同时担任飞手。TDRP-SD要求：

1. 只有当卡车停在客户位置时，搭载的无人机才能从卡车发射
2. 当搭载的无人机被派去服务指定客户时，卡车不能移动（这是一种基于卡车等待的相对简单的同步模式）

也就是说，只有在卡车停好后，搭载的无人机才能发射去服务一个客户。随后，无人机必须飞回停放的卡车降落。当无人机被派出时，卡车在其返回之前不能访问其他客户。停有卡车的客户位置作为无人机发射/回收站点（LRS）。在LRS，无人机可以多次发射和回收。假设在LRS，货物转运和电池更换是完全自动化的，相关时间可忽略不计。

2.5 路径类型

确定性规划的路径称为先验路径。在TDRP-SD中，先验路径分为：

• 卡车路径： 由卡车-无人机组合行驶，无论搭载的无人机是否使用；
• 无人机路径： 由从卡车发射的无人机行驶；

如图2(a)所示，路径0-1-2-3-4-5-0是一条不使用无人机的卡车路径；路径0-6-7-8-9-10-0是另一条多次使用无人机的卡车路径；7-12-7、8-11-8和8-13-8是从卡车发射的无人机路径。客户7和8同时作为LRS。

由于需求是随机的，执行先验路径时可能发生路径失败，需要实施补货策略。图2(b)展示了补货策略的示例。

图2 路径说明性示例

2.6 优化目标

令$r$表示一条卡车路径，节点访问序列为$(0,1,\dots ,j,j+1,\dots )$。$S_j$表示卡车在客户$j$完成配送后所有可能的剩余货物集合。函数$f_j(q)，q\in S_j$，表示从客户$j$到仓库的最小期望成本，而fjℓ(q)，ℓ∈{1,2,3}f_j^\ell(q)，\ell \in \{1, 2, 3\}fjℓ​(q)，ℓ∈{1,2,3}分别表示在补货策略${{\rm Y}}_1、{{\rm Y}}_2、{{\rm Y}}_3$下该路段的总期望成本。

因此，$f_j(q)$可以计算为：
fj(q)=min⁡ℓ∈{1,2,3}{fjℓ(q)}f_j(q) = \min_{\ell \in \{1,2,3\}} \{f_j^\ell(q)\}fj​(q)=ℓ∈{1,2,3}min​{fjℓ​(q)}

给定路径r的期望成本计算为$f_0(Q^K)$。对于服务$\omega$个客户的路径，期望需求受卡车容量$Q^K$约束： $$\sum _{i=0}^{\omega }\text{E}[{\xi }_i]\le Q^K$$

TDRP-SD的目标是设计一组卡车路径，在满足容量约束和无人机最大航程约束的同时，最小化期望成本。

2.7 默认假设

值得一提的是，默认假设无人机速度$v^U > $卡车速度$v^K$以确保无人机能有效帮助降低先验路径的成本。

引理1： 当$v^K\ge v^U$时，最优解中不会采用无人机路径。

这一引理的证明基于三角不等式，说明当卡车速度不低于无人机时，使用无人机反而会增加成本。因此，只有当无人机速度显著快于卡车时，卡车-无人机协同配送才有意义。

3.补货策略

3.1 传统补货策略回顾

随机需求VRP的文献通常考虑两种补货策略：

经典补货策略（${{\rm Y}}_1$）： 当车辆货物耗尽时，返回仓库补货，然后回到发生缺货的客户处继续计划路径（反应式补货）。

预防补货策略（${{\rm Y}}_3$）： 车辆可以在服务每个客户后返回仓库补货，以避免缺货发生。

3.2 TDS补货策略详解

考虑到应急物流系统中卡车-无人机组合的使用，本文引入了卡车-无人机同步（TDS）补货策略（${{\rm Y}}_2$），旨在利用无人机减轻随机需求VRP中卡车的补货负担。文章对补货策略进行了创新。

在TDS补货策略下，当卡车货物耗尽时：

1. 一架或多架单机无人机可以从仓库出发进行补货
2. 同时卡车实施预防补货策略，前往下一个客户
3. 两者同步进行，实现时间节约

三种补货策略的特征对比如下表所示：

关键引理： 作者证明了在TDS策略下，单机无人机最多可为某客户补货 $\lfloor v^U/v^K\rfloor$ 次。这一结论为策略选择提供了理论依据。

策略选择规则： 当满足以下条件时，TDS策略优于经典策略：

• 客户可被无人机从仓库直接到达（$2\cdot d_{0,j+1}/v^U\le \Phi$）
• 缺货量在无人机补货能力范围内

4. 期望成本计算

4.1 动态规划递推

作者针对三种补货策略分别建立了动态规划递推方程。设$f_j(q)$表示从客户$j$出发、剩余货物为$q$时到达仓库的最小期望成本：
fj(q)=min⁡ℓ∈{1,2,3}{fjℓ(q)}f_j(q) = \min_{\ell \in \{1,2,3\}} \{f_j^\ell(q)\}fj​(q)=ℓ∈{1,2,3}min​{fjℓ​(q)}
其中$f_j^1(q)、f_j^2(q)、f_j^3(q)$分别对应经典策略、TDS策略和预防策略下的期望成本。

4.2 单调性命题

命题1： $f_j^1(q)$对所有$q\in S_j$单调不增。

命题2： $f_j^2(q)$对所有$q\in S_j$单调不增。

这两个命题的证明为算法设计提供了重要基础——利用单调性可以避免大量冗余计算，显著降低期望成本计算的时间复杂度。

5.求解算法

5.1 算法设计思路

在一些研究中，随机需求VRP使用随机规划框架求解。当流变量形成整数解时，可以精确计算期望成本。例如，De La Vega等(2023)提出的整数L-shaped算法在5小时内能求解的最大规模为34个客户；Florio等(2023)提出的分支-定价-割算法只能在5小时内最优求解一小部分中等规模实例。

精确算法对随机需求VRP提供了有价值的方法论贡献，但其求解能力受限于计算效率。当灾害或紧急情况发生时，关键站点数量可能从几十到数百甚至数千，而快速响应总是必要的。因此，决定应急物流系统的计算时间非常有限，启发式算法比精确算法更适合快速响应场景。

5.2 两阶段求解框架

TDRP-SD分两阶段求解：

第一阶段： 构造初始路径（先验路径）；

第二阶段： 当达到或超过车辆容量时，选择补货策略使车辆沿先验路径恢复载货量；

算法的核心是结合SISRs（Slack Induction by String Removals） 和贪婪插入的ruin-and-recreate框架。

5.3 关键技术

SISRs破坏策略： 通过字符串移除的方式破坏当前解，具有以下特点：

• 移除"足够多"、“相邻”、"连续"的客户；
• 支持字符串移除和分割字符串移除两种模式；

混合重建策略： 整合多种机制提升算法性能：

• 短路径深度搜索： 优先在客户数最少的路径中进行期望成本评估；
• 上下界引导： 基于分支定界的剪枝思想，避免无效计算；
• 模拟退火： 帮助跳出局部最优；

贪婪插入与闪烁规则： 引入概率$\beta$随机跳过某些插入位置，增加解的多样性。

6. 数值实验

6.1 基准测试

作者在两组经典的VRP随机需求基准实例上验证了算法有效性：

DATA I（来自Christofides数据）：

• 21个实例，最多200个客户；
• 与文献最优解相比，平均成本降低3.22%-4.18%；
• 18个实例获得新的最优解；

DATA II（来自Augerat数据）：

• 40个实例；
• 匹配39个实例的最优解；
• 平均计算时间53.41秒；

6.2 TDRP-SD实例测试

作者设计了44个新实例（100-302个客户），分为四组进行测试。主要发现：

1. 需求扰动对成本的影响：

随着扰动幅度增加，补货概率上升，成本和计算时间均增加。

2. TDS策略的效果：

移除TDS策略后，平均成本增加0.27%-0.36%，而计算时间未显著增加，说明TDS策略能以较低的计算代价实现成本节约。

3. 无人机配送的价值：
禁用无人机后，平均成本增加约0.95%，验证了无人机在协同配送中的积极作用。

4. 单点发射无人机数量的影响：
允许更多无人机从同一发射点起飞可进一步降低成本（最多约0.29%），但计算负担也随之增加。

7. 结论

本文的主要贡献包括：

(1) 首次定义了卡车-无人机协同配送的随机需求路径规划问题（TDRP-SD），填补了该领域的研究空白。

(2) 提出了创新的TDS补货策略，利用无人机实现卡车-无人机同步补货，有效减少补货成本。

(3) 证明了期望成本函数的单调性命题，为高效计算奠定理论基础。

(4) 开发了基于SISRs的混合启发式算法，在基准实例上取得新的最优解，并能在合理时间内求解302客户规模的实例。

未来研究方向：

• 卡车携带多架无人机的场景
• TDRP-SD的精确算法设计

参考文献：

Wang, F., Li, H., & Xiong, H. (2025). Truck-drone routing problem with stochastic demand. European Journal of Operational Research, 322, 854–869.

Li, H., Wang, H., Chen, J., & Bai, M. (2020). Two-echelon vehicle routing problem with time windows and mobile satellites. Transportation Research, Part B (Methodological), 138, 179–201.

Zhou, H., Qin, H., Cheng, C., & Rousseau, L.-M. (2023). An exact algorithm for the two-echelon vehicle routing problem with drones. Transportation Research Part B: Methodological, 168, 124–150.

De La Vega, J., Gendreau, M., Morabito, R., Munari, P., & Ordóñez, F. (2023). An integer L-shaped algorithm for the vehicle routing problem with time windows and stochastic demands. European Journal of Operational Research, 308(2), 676–695.

Florio, A. M., Gendreau, M., Hartl, R. F., Minner, S., & Vidal, T. (2023). Recent advances in vehicle routing with stochastic demands: Bayesian learning for correlated demands and elementary branch-price-and-cut. European Journal of Operational Research, 306(3), 1081–1093.

Christofides, N. (1979). The vehicle routing problem. In Combinatorial optimization. John Wiley & Sons Ltd.

Augerat, P. (1995). Approche polyèdrale du problème de tournées de véhicules (Ph.D. thesis), Institut National Polytechnique de Grenoble-INPG.