随机选址﹣路径优化：面向灾害救援的卡车﹣无人机协同调度模型
一、研究背景与问题提出
自然灾害严重破坏道路基础设施，导致道路阻断、交通不畅和应急救援延迟。在人道主义援助场景中，及时将救援物资送达受灾群众比成本最小化更为关键。无人机（UAV）因机动灵活而在灾后配送中受到关注，但其航程有限且受天气影响，在规模较大的灾害场景中不能单独承担所有配送任务。卡车具有较高的运载能力，但在道路受损区域通行困难。平行卡车–无人机协同配送模式可以发挥两类车辆互补优势：卡车负责干线运输和远距离配送，无人机负责最后一公里快速派送，显著降低受灾群众等待时间。
本文针对具有随机道路损害及行驶时间不确定性的灾害物流构建“两阶段随机选址–路径模型”。第一阶段在灾前决定开设若干临时物资储备点（depots）；第二阶段在灾后根据道路状态为卡车与无人机构建配送路径。由于该问题是随机混合整数规划，采用商用求解器难以求解中等规模实例。为此，论文提出了基于局部搜索与变量邻域搜索（VNS） 的启发式算法，并在随机生成实例和2011年土耳其Van地震案例上验证了方法。
二、模型与数学形式化
2.1 网络扩展与决策变量
考虑一个包含灾后需求节点集合 、候选库点集合 与道路边集合 的连通网络。车辆包括卡车和无人机两种类型。为描述卡车在巡访多个节点时的流动过程，作者引入了一个扩展网络：在原网络基础上增加一个虚拟汇点，并为每个需求节点与虚拟汇点添加一条边，使得每个节点的流出流入量可以平衡，如图 1 所示。
主要决策变量包括：
：第一阶段变量，若在候选库点 开设救援仓库则 ，否则 。 ：随机场景 下无人机是否从库点 服务需求节点 。 ：随机场景 下卡车是否从库点 访问需求节点 。 ：随机场景 下卡车 是否沿着边 行驶。 ：扩展网络中的货物流变量，表示卡车沿边 输送的“商品流”。
此外，还定义了无人机到达需求节点的时间 ，以及表示节点被卡车访问次数的变量 、 等，这些与货物流变量一起用于计算各需求节点的到达时间与等待时间。
2.2 两阶段随机选址–路径模型
第一阶段目标是最小化期望平均到达时间。设 为随机场景， 为第二阶段模型的最优值，则总体目标函数为
第一阶段还要求开设的库点不超过给定数目 ：
随机场景下的第二阶段模型最小化各需求节点的到达时间平均值。假设每条边 的行驶时间为 ，则目标为
目标分子由三部分组成：前两项共同计算由卡车服务的需求节点的总到达时间，最后一项为由无人机服务的需求节点到达时间之和。
卡车与无人机分配约束：每个需求节点要么由无人机配送，要么由卡车配送：其中 是可以用无人机覆盖节点 的库点集合。 无人机覆盖约束：若 ，则卡车不允许访问该节点，其出入度为零。 库点与车辆一致约束：只有当库点 被选为开设点时（），卡车才可从该库点出发服务节点，且每个库点最多发出一辆卡车。 卡车路径连续性和流守恒：对每个库点，卡车不会访问其他库点并形成子环；对每个节点，流入和流出次数相等，保证生成一条回路。 到达时间计算：约束 (5) 计算无人机到达时间 ：累加库点 下在节点 之前访问的所有节点的往返飞行时间，并加上从库点到节点 的单程时间。卡车节点的到达时间由目标函数前两项体现。
模型还包括无人机航程约束、服务时限等。由于无人机的飞行时间远小于卡车，作者假设无人机的返回时间不计入等待时间。
2.3 随机场景与计算挑战
灾后道路的损坏程度具有显著不确定性。论文在每个随机场景下，根据节点所在的破坏等级对卡车在相关道路上的行驶时间进行随机放大，使受损区域的道路在该场景中表现为更高的通行时间成本。无人机不依赖道路网络，因此其飞行时间不受道路状况影响。
随着场景数量增加，每种库点选择方案都需要在多个损坏情境下重新规划卡车与无人机的路径，使得两阶段随机模型的规模迅速膨胀。论文指出，即使使用商业求解器，在中等规模实例上也难以在限定时间内获得收敛解，从而需要专门的启发式算法来提升求解效率。
三、求解算法：局部搜索与变量邻域搜索
为解决模型难以求解的问题，作者设计了基于局部搜索和变量邻域搜索（VNS） 的启发式算法，主要思想包括三部分：
3.1 贪婪构造与回溯调整
初始解采用贪婪路径构造：首先为每辆卡车生成服务顺序列表。为了确保覆盖所有需求节点，算法从每个库点出发，优先选择最近的未服务节点，将其插入路线；当所有节点被分配后再连接返回库点。若贪婪路径遇到死胡同（即剩余需求节点不与当前子路径相连），则触发回溯，撤销最近的一次选择并尝试替代路径。图 2 展示了在小型网络上的回溯示例：
3.2 局部搜索与改善算子
局部搜索阶段针对多个邻域结构反复改进，包括：在不同卡车路线之间移动节点、在卡车与无人机之间重新分配节点（同库点或异库点）、以及在给定库点下对卡车路线进行局部重构等。每次移动都根据目标函数的变化来决定是否接受。
3.3 变量邻域搜索框架
局部搜索往往停留在局部最优。为此，算法采用变量邻域搜索（VNS）框架，不断改变邻域结构以跳出局部最优。具体步骤：
定义若干邻域结构：例如改变库点选择、调整卡车路线、改变无人机分配等。 在每个邻域进行局部搜索：利用插入、交换等算子寻找改进。 邻域扩展：若当前邻域无法改进解，则扩大搜索范围或随机扰动重新启动。 终止条件：当连续多次邻域扩展未能改进解时终止，返回当前最优解。
这种面向问题的启发式兼顾选址、路径和车辆分配的集成优化，在大多数实例上能在几分钟内得到高质量解。
四、实验设计与案例研究
4.1 数据与场景设置
论文首先在随机生成的网络上评估算法，随后选取2011 年土耳其 Van 地震作为现实案例。地震发生在 Van 城北部，作者以受灾区域的道路网络作为图结构，选取 个需求节点和 个候选库点，如图 3a 所示。地图中三角形表示候选库点，圆点表示需求节点。
图 4 展示了论文用于生成灾害场景的强度区划分方法。以震中为圆心划分 destructive、damaging 和 strong 三个区域，其半径分别由基础距离（小规模实例为方形边长的 1/10 与 1/5，Van 案例为 5 km 与 10 km）乘以随机系数 或 得到。每条边的强度由其端点中破坏等级较高者决定。无人机飞行不受道路状况影响。
实验参数方面，卡车行驶时间由 Google Maps 的实际驾驶时间生成，无人机速度 km/h（ mph），无人机航程 min（含起降），无人机载重足以满足一次救援需求。为了兼顾设施建设成本与覆盖效率，限制开设 个库点。对每个案例实例生成 个地震场景，用于计算期望平均到达时间。
4.2 指标与对比方案
作者比较了以下几种方案：
卡车–无人机协同方案（本文提出）：使用上述模型和启发式同时优化库点选址、卡车路径与无人机分配。 仅卡车方案：无人机不可用，所有需求节点由卡车沿受损后的道路网络完成配送。 无道路损害评估方案：基于灾前期望行驶时间作出选址与路径决策。 K‑Means 聚类基线：先用 K‑Means 聚类选址，再用贪婪算法构建卡车和无人机路线。
评价指标为期望平均到达时间，以及各节点被分配给卡车或无人机的频次。
4.3 结果分析
图 5 展示了启发式算法在某一随机实例中的配送模式：紫色圆点、绿色圆点等代表需求节点，三角形为选定库点；实线表示卡车路线，虚线表示无人机飞行路线。红色圆圈为无人机航程所覆盖的范围。可以看到，大部分位于库点凸包内部的节点由无人机服务，而远离库点或位于道路端点的节点则由卡车负责。
图 6 至图 8 比较了不同方案的结果：
从结果可得出以下主要结论：
协同方案显著改善救援时效：与仅卡车方案相比，平均到达时间从 3.3 h 降至 1.5 h，改善率约为 55%。无人机在库点周围大范围服务，减少卡车的行驶距离，从而降低等待时间。 合理选址与分配不可忽视：K‑Means 基线在选址和分配上不如整体优化，导致平均到达时间略高于协同方案。因此选址、路径和分配的整体优化比简单的分步优化更有效。 无人机分配具有场景敏感性：图 5c 中，某些节点在超过 75% 的场景中由无人机服务，这些节点通常位于库点附近且道路易损；而远离库点或处于道路交汇处的节点则主要由卡车服务。
4.4 灵敏度分析
图 9 展示了平均到达时间与关键参数的关系。
库点数量：随着允许开设的库点数量由 3 增加到 9，平均到达时间快速下降；此后增益减弱，表明在成本受限的情况下，开设约 9 个库点即可获得较好效果。 无人机航程：当航程从 0.5 h 增加到 1 h 时，到达时间明显下降，之后延长航程的收益有限。说明合理增加无人机航程可显著提高效率，但超出某个阈值后效果递减。 无人机速度：无人机速度从 24 km/h 增加到 104 km/h 同样能减少平均到达时间，但提升速度对整体时效的影响小于增加库点或航程。
五、结论与管理启示
本文针对灾害援助中的平行卡车–无人机协同配送提出了两阶段随机选址–路径模型，以期望平均到达时间最小化为目标，考虑了灾后道路损害导致的行驶时间增加以及无人机航程限制。由于模型复杂且场景众多，作者设计了基于局部搜索和变量邻域搜索的启发式算法，能够在短时间内求解中等规模实例。通过大量随机实例和 Van 地震案例验证，研究得出如下启示：
协同运营显著提高时效。引入无人机后，期望平均到达时间从 3.3 h 降至 1.5 h，整体改善约 55%，在考虑多种灾害场景的情况下，卡车–无人机协同运营能显著提升整体救援时效。 灾前选址不可或缺。库点数量和位置对结果影响显著，合理的选址能够使无人机覆盖更大范围，减少卡车行驶路程。仅凭聚类或距离规则选址难以达到最优。 无人机航程比速度更关键。在资源有限的情况下，提高无人机航程比单纯提高速度能带来更大的时间节约。 应对不确定性的模型与算法。两阶段随机模型为灾前、灾后决策提供系统框架，启发式算法能够有效处理大规模场景，是实际部署可行的工具。
文章须知
推文编辑：单子叶
责任编辑：张仁义
原文链接：https://doi.org/10.1016/j.ejor.2025.08.057
