论文题目：Robust optimization for truck-and-drone collaboration with travel time uncertainties
第一作者：Wenbo Sun 香港大学博士毕业生，现就职于香港理工大学，研究聚焦：城市物流系统优化、卡车与无人机协同鲁棒优化、网联自动驾驶车辆控制及传动系统设计等相关领域。
E-mail：sunwb@connect.hku.hk
通讯作者：Fangni Zhang 香港大学工业与制造系统工程系助理教授，研究涵盖交通领域的基础性和新兴议题，包括多模式交通系统建模与优化、共享与自动化运输管理、高速铁路和航空运输建模。
E-mail：fnzhang@hku.hk
灾后应急响应中的卡车一无人机协同调度：鲁棒路径优化方法
论文摘要
针对灾后救援中无人机与卡车协同运输的研究，本论文提出了一套鲁棒优化框架。传统的车辆路径问题多聚焦于单任务或确定性旅时，难以应对灾后 路况不确定 和 多任务服务 等挑战。该研究在灾后多任务救援场景下，考虑卡车与无人机可处理救援物资配送和网络监视两类任务，并允许无人机在不同卡车间灵活协作。论文通过 优先成本 衡量任务延误，构建了具有旅行时间不确定性的最小–最大–最小混合整数规划模型。为了求解该复杂问题，作者将其转化为单层最小化模型并设计了基于 分支定界–鲁棒分解 的算法，该算法结合 Benders 分解 与 列‑约束生成 技术获取上下界并剪枝搜索树。数值实验显示，所提鲁棒路径相比确定性方案可平均提高约 5% 的救援效率。本文贡献在于：首次在车辆‑无人机协同问题中同时考虑旅行时间不确定与多任务救援，并提出高效的精确算法，为应急物流决策提供参考。
一、研究背景与问题
1.1 背景综述
无人机已广泛应用于包裹配送、监测和灾害管理，尤其在道路受阻的灾后环境中能快速完成救援任务。 但无人机受容量和续航限制，单独工作难以满足需求；卡车虽载重大，但道路破坏导致无法抵达所有节点。 多数文献只考虑单任务或确定性路径，缺乏对 旅行时间不确定性 的处理。 灾后救援需要兼顾物资送达和网络监视两类任务，任务紧急程度不同，必须按照优先级调度。
1.2 问题描述
论文研究一个灾后网络 ，其中部分路段毁坏导致卡车无法通行。为此划分出卡车可达网络 和 无人机网络，无人机可飞往所有节点。每个节点可能需要：
配送任务：卡车或无人机携带物资完成，衡量需求重量。 监视任务：无人机悬停拍摄，衡量监视时长。
同时考虑 辆卡车、 架无人机从同一基地出发后协同完成所有任务再返回。假设：
卡车可在任意节点释放无人机后继续行驶；无人机完成多个任务后可返回任意卡车；所有无人机配有摄像头，可在同一飞行中兼顾配送与监视。 优先成本定义为任务延误时间乘以任务优先系数，优先系数根据任务紧急程度预先设定，目标是最小化总体优先成本。
下图展示了灾后卡车‑无人机协同系统：蓝色节点为卡车可达节点，橙色节点为只能无人机服务的节点；实线为卡车路线，虚线为无人机飞行，紫色箭头代表旅行时间的不确定性来源。
二、模型构建与鲁棒优化
2.1 决策变量与目标函数
首先定义若干决策变量，如卡车路线变量 、无人机路线变量 、任务分配变量等。目标函数含两部分：
优先成本：，其中 为任务 在节点 的优先系数， 为任务的开始服务时间。 未服务惩罚：针对因约束无法完成的任务引入大惩罚系数确保模型尽量服务所有任务。
因此整体优化目标为：
2.2 约束条件（概述）
为了完整描述卡车与无人机的协同行动，模型还包括以下主要约束：
流量守恒：保证每辆卡车/无人机从仓库出发后最终回到仓库，每个节点的进出次数一致。 容量约束：卡车每趟行程携带的无人机数量有限，无人机的载重与续航不能超过任务需求。 飞行时间约束：限制无人机单次飞行的累计飞行时间不超过电池容量。 服务顺序与对接约束：无人机必须在卡车或仓库起降，且任务之间的顺序遵循先后逻辑。
2.3 不确定性建模
灾后道路和天气状况使旅行时间难以精确估计。论文采用 基数约束不确定集合 模型描述每条边的旅行时间 、 的偏差范围：
其中 为 名义旅时， 为 最大偏差， 为 不确定预算，可控制整体偏差的数量。
2.4 鲁棒优化模型与松弛
综合上述目标与约束，并考虑旅行时间的不确定性，原问题形成 “外层最小–中层最大–内层最小” 的三层鲁棒模型：
外层决策选择路线与任务分配，内层最小化给定不确定性的成本，最大层选择最坏情形。由于该形式难以直接求解，作者通过对内层问题求 对偶 并引入辅助变量，将其转化为单层的 混合整数线性规划 (MILP)，然后在算法中利用鲁棒分解获取更精确的解决方案。
三、求解方法：分支定界与鲁棒分解
3.1 算法整体框架
论文针对上节 MILP 的规模与复杂度，提出了一种 分支定界（Branch‑and‑Bound, BnB）与鲁棒分解 结合的算法。整体流程如图所示。
整体步骤概述：
初始化节点：设置全局上下界，建立根节点。 分支阶段：根据自定义 分支规则 1 和 分支规则 2，分别决定哪些节点由卡车或无人机服务，确定卡车部分路线；形成子问题并计算下界。 下界计算：利用 鲁棒分配问题 快速计算分支节点的下界；若下界高于当前上界，则剪枝。 鲁棒分解：当满足触发条件时，利用 Benders 分解 与 列‑约束生成 (CCG) 方法求解完整卡车路线，并更新全局上界。 搜索与剪枝：重复以上步骤直至最优性差距小于预设阈值。
3.2 分支规则
分支规则 1：在网络层面对每个节点决定由卡车还是无人机服务。对于卡车不可达节点，必须由无人机服务；对于可达节点则两种方式均可，从而扩大搜索空间。 分支规则 2：在确定卡车服务节点集合后，进一步决定各卡车的访问顺序，形成 部分卡车路径。这一顺序直接影响其他节点的等待时间，因此需要精细化处理。
3.3 下界计算
在每个分支节点上，通过求解一个简化的 鲁棒任务分配问题 来得到下界。该问题在忽略未访问节点顺序的前提下，给剩余卡车和无人机指派任务，考虑不确定旅时，并采用线性松弛获取紧下界。
3.4 鲁棒分解算法（RDA）
当部分路径可构成完整卡车路线时，算法使用 鲁棒分解算法 来求精确上界：
求取完整卡车路线：在已确定的卡车节点上运行 Tabu 搜索 获得初步路线，并用该路线解决内层的鲁棒优化问题获得上界。 列‑约束生成：针对最坏不确定场景添加新的场景列，并使用 Benders 分解 分解主问题和子问题，不断迭代至满足最优条件。 通过这一步得到的上界与下界对比，指导搜索树的剪枝和更新。
四、数值实验与结果分析
作者构建了不同规模的网络实例，设置 3 辆卡车和 6 架无人机，共 20 个节点的随机网络。比较了商业求解器 Gurobi、确定性 BnB 以及所提鲁棒 BnB 的表现。
4.1 算法性能比较
下图给出了在 5 万个随机不确定情景下三种算法的表现。可以看到：
Gurobi 求得的路线对不确定旅时敏感，优先成本波动大，平均效果较差。 BnB_deter 在确定性旅时下得到的路线在大多数随机情况下优于 Gurobi，但仍有明显风险。 BnB_robust 得到的鲁棒路线在所有情景下保持较小的波动和更低的平均优先成本，验证了鲁棒模型的优势。
4.2 协同策略与敏感性分析
作者分析了四种协作策略：单任务卡车+单任务无人机 (ST+DT)、单任务卡车+灵活无人机 (ST+FT)、多任务卡车+单任务无人机 (MT+DT) 和 多任务卡车+灵活无人机 (MT+FT)。下图展示了不同策略下的目标值及相对收益：
可见：
多任务无人机 能显著提升效率，尤其是允许无人机在不同卡车间灵活协作时收益最大。 与 ST+DT 相比，MT+FT 策略在不同实例下平均提升 20% 以上的救援效率，表明提升无人机能力比仅增加数量更有效。
4.3 不确定预算影响
论文还考察了不确定集合参数对救援效率的影响。如图所示，随着卡车旅时不确定预算 增大，优先成本几乎线性上升；在相同 下，提高无人机旅时预算 对优先成本的影响较小，说明卡车的不确定性对救援效率更敏感。
4.4 车队规模与携载能力分析
作者在扩展研究中调整了车队规模与卡车可携带无人机数量。结果表明：增加无人机数量或提高每辆卡车可携带的无人机数量均能降低优先成本；但随着数量增加，边际收益递减。当卡车数量不足时，提高单车携载量比增加无人机数量更为有效。
五、结论与学术贡献
本文围绕灾后多任务救援提出了一个考虑旅行时间不确定性的卡车‑无人机协同路径优化模型。其主要结论和创新点包括：
多任务–灵活协同模型：首次在 VRPD 问题中同时考虑配送与监视两类任务，并允许无人机在不同卡车间灵活协作，提高了救援效率。 优先成本优化目标：通过最小化优先系数加权的延迟成本，将救援时效性与任务紧急程度纳入统一框架。 鲁棒优化建模：使用基数约束不确定集刻画旅时偏差，建立 min‑max‑min 模型并转化为单层 MILP，兼顾求解效率与模型真实性。 分支定界‑鲁棒分解算法：定制化分支规则和下界计算，使 BnB 搜索更高效；结合 Benders 分解和列‑约束生成，精确解决内层问题，算法在实验中显著优于商业求解器。 实践启示：研究显示适度的无人机数量搭配灵活协作可提升救援效率；旅时不确定性管理应重点关注卡车而非无人机；鲁棒方案能在多种极端情景下保持稳定表现。
该研究为灾害应急物流提供了可行的理论模型和算法工具，未来可扩展至更复杂的任务类型、动态灾情及多目标优化等方向。
文章须知
链上镖师团队：常文婕（AEIC）、祁园园、汪朝杰、王一航、张仁义（EIC）、张晓乐
原文链接：https://doi.org/10.1016/j.trb.2025.103378
原文链接见文末，或扫下方交流群二维码。群内实时更新推文及原文 pdf，方便专家学者随时获取（若二维码失效，请翻阅扫描最新文章的二维码）。
