多无人机多车辆场景：时间窗鲁棒调度与分支定价

论文题目：A Branch-and-Price Algorithm for Robust Drone-Vehicle Routing Problem with Time Windows

第一作者：Jaegwan Joo 韩国外国语大学工业与管理工程系，主要研究工业工程领域的优化算法设计与应用。

E-mail：zenare@naver.com

通讯作者：Chungmok Lee 韩国外国语大学工业与管理工程系副教授，核心聚焦运筹学、整数规划、数学规划与鲁棒优化领域，为交通、金融、网络设计、能源等领域的各类优化问题设计精确/启发式算法，运用分支定价、Benders分解等方法处理不确定性问题，研究覆盖无人机-车辆/电动汽车路径规划、机场机位分配、投资组合选择等方向。

E-mail：chungmok@hufs.ac.kr

多无人机多车辆场景：时间窗鲁棒调度与分支定价

论文摘要

随着无人机技术的发展，无人机与传统车辆结合的末端配送模式备受关注。论文提出“鲁棒无人机‑车辆路线问题”（Robust Drone‑Vehicle Routing Problem with Time Windows, RDVRPTW），在传统时间窗车辆路径问题的基础上，允许一辆卡车搭载多架无人机，在指定节点调度无人机执行服务。该问题考虑卡车行驶时间和无人机飞行时间的不确定性，采用预算型鲁棒优化保证在最恶劣情况下仍能满足所有客户的时间窗。针对问题的NP‑难性，作者建立紧凑数学模型并开发分支‑定价算法：通过引入“卡车‑无人机模式”将原问题分解为主问题和定价子问题，并提出两阶段的定价方法：先用标号算法生成鲁棒卡车路线，再用动态规划枚举可行的无人机调度。数值实验表明，该算法显著优于商用MIP求解器。本文旨在从研究背景、模型构建、算法设计及计算实验四个方面，对该论文进行深入解析。

一、研究背景与问题定义

1.1 无人机与车辆协同配送的现状

• 无人机具备速度快、成本低等优势，可绕开道路拥堵，但承载重量小、航程有限。因此在现实中，无人机难以完全替代卡车。
• 协调无人机与卡车能发挥两者长处：卡车作为移动“无人机站”，在合适节点停留并发射无人机执行近距离送货。
• 每个客户设有时间窗，必须在规定时间内由无人机或卡车服务。卡车与无人机行程存在不确定性，若不考虑延误可能导致服务迟到或等待增加。

1.2 RDVRPTW问题描述

• 基本要素：一组客户 ，每个客户有需求 、服务时间  和时间窗 ；一个仓库节点 （复制为起点  和终点 ）；多辆卡车，每辆卡车携带多个相同的无人机。

• 关键假设：

• 卡车装备: 每辆卡车配备多架相同无人机（假设1）。
• 承载约束: 无人机一次只能携带一个客户需求（假设2）；卡车有最大载重 。
• 并行派遣: 多架无人机可同时派遣，返回同一发射点，卡车必须等待所有无人机回归才能继续行驶（假设3–4）。
• 电池更换: 电池可在卡车上快速更换，保证无人机可重复使用（假设5）。
• 节点 where drones are deployed 被称为“等待节点”，无人机从这些节点出发并返回，形成星形航线。

• 卡车与无人机路径：

• 卡车路径由弧集  表示，元素  代表卡车从节点  到 ；每条弧有名义行驶时间  与成本 。
• 无人机可行飞行对由集合  表示， 表示从等待节点  可飞往客户 ；飞行时间 、成本 。
• 无人机飞行对是非对称的，并假定往返所需时间和成本相同。

1.3 不确定性建模

配送过程中，交通和天气引起的延误会影响到时间窗的满足。作者采用 预算式鲁棒优化 描述不确定性：

• 卡车行驶时间不确定集：设定每条弧的行驶时间  在范围内波动，通过参数  限制出现最大延误的弧数量，即

• 无人机飞行时间不确定集：设定每条飞行弧的飞行时间  在范围内波动，并在每个等待节点  处通过预算  限制飞行时间偏差总量，即

• 这两个集合独立控制卡车与无人机延误的严重程度：当  或  较大时，模型更保守；当  或  时回到确定性问题。

二、模型与鲁棒优化框架

2.1 紧凑数学模型（P）

作者在文中给出了一个可由商用求解器直接求解的混合整数规划模型。模型以最小化总运营成本（卡车与无人机成本）为目标。主要决策变量包括：

• ：卡车是否从  行驶至 ；
• ：无人机  是否从等待节点  派遣至客户 ；
• ：考虑不确定预算  时卡车在节点  的到达时间、离开时间和等待时间；
• ：无人机  在等待节点  的第  次派遣是否飞往客户 。

由于模型公式较长，本文不逐一列出。其核心特点在于：

• 引入到达-等待-离开三类时间变量，克服了传统 VRPTW 中卡车只能在时间窗开端到达的约束。
• 利用递归式计算最坏情况下的到达时间，确保在不确定旅行时间下仍能满足所有客户的时间窗。
• 通过二元变量  与条件约束为每个等待节点选择合适的无人机派遣顺序，保证无人机必须先返回卡车才能再次派遣。
• 采用大 M 方法将条件逻辑线性化，然而过多的大 M 约束会降低线性松弛界。

2.2 模型创新点与难点

• 与现有鲁棒无人机‑卡车问题比较，RDVRPTW允许多卡车多无人机并行，需同时决策卡车路线、无人机派遣节点与派遣序列。
• 模型不仅考虑卡车行驶时间不确定性，还考虑无人机飞行时间的不确定性。
• 由于每个等待节点的无人机调度是一个平行机调度问题，嵌入模型后大幅增加变量与约束，导致MIP求解效率低。

三、分支‑定价算法设计

为克服紧凑模型的计算困难，论文提出了分支‑定价算法框架，其核心在于将原问题拆分为易于处理的子结构：

3.1 主问题：卡车‑无人机模式建模

• 引入“卡车‑无人机模式”，每个模式由一条卡车路径  和一组无人机派遣弧  组成，例如模式  与派遣 。
• 构建主问题MP，决策是否选用模式 （变量 ）以及是否实际使用派遣弧 （变量 ），并要求每个客户要么由卡车途经，要么被某一派遣覆盖。
• 该模式化建模区别于传统的集合划分模型 (MP‑SP)：通过引入  实现对同一路径的派遣组合，使一条模式生成后可以隐含覆盖多个子模式，从而减少列生成次数。

3.2 两阶段定价子问题

定价子问题旨在生成具有负化减成本的新模式来改进主问题的线性松弛。作者提出“两阶段”策略：

3.2.1 阶段一：卡车路径生成

• 将卡车路径视为带资源约束的最短路问题 (SPPRC)。资源包括需求容量和满足时间窗及鲁棒约束的到达时间。
• 采用标号算法扩展部分路径，每个标号记录累计成本和资源消耗，并通过支配准则剔除劣于已生成标号的路径。
• 为降低无人机调度对卡车路径标号维度的影响，阶段一暂不考虑无人机，利用对无人机收益的上界下界对卡车路径的化减成本进行估计，从而在不引入具体派遣序列的情况下筛选潜在有益的卡车路径。

3.2.2 阶段二：无人机派遣构建

• 对阶段一得到的卡车路径 ，在满足时间窗和鲁棒约束的前提下，枚举可行的无人机派遣组合 ；这相当于在一个等待节点上解决多个并行机调度问题。
• 采用动态规划计算派遣组合的最大化收益 ，并与卡车部分组合得出该模式的总化减成本；若化减成本为负，则将该模式加入主问题。
• 两阶段策略显著减少定价问题的计算量，使算法能够处理多架无人机并行的复杂场景。

3.3 分支策略与流程

整个分支‑定价算法流程如图3所示：先解主问题的线性松弛（RMP），若存在负化减成本的模式则通过定价子问题生成新模式并加入RMP；若线性解非整数，则对变量实施分支生成分支节点，继续循环直至所有节点处理完毕。

四、计算实验与结果分析

4.1 实例设置

• 作者测试了两类实例：Solomon标准VRPTW（共25个客户）和基于美国UPS实际数据生成的UPS问题（最多90个客户）。为公平比较，卡车数和无人机数统一为2台。
• 鲁棒参数设定为 ，即允许最多两条弧出现最坏延误。
• 实验在同一台计算机上执行，使用Python+Cplex实现；分支‑定价算法与MIP模型均限制运行时间为1小时。

4.2 性能比较

• 对Solomon实例，分支‑定价算法在几秒到几分钟内即能得到最优解，且根节点松弛差距几乎为零，而MIP求解器常常超时或需要更多分支节点。
• 对UPS实例，算法在大多数问题上能在几分钟至数十分钟内找到最优或近优解；某些大规模实例虽未在时间限制内完全证明最优性，但相对误差较小。相比之下，MIP模型在许多实例上因为时间或内存限制无法返回结果。
• 作者还在附录中通过蒙特卡洛模拟验证所得路线的鲁棒性，说明考虑不确定性的计划能显著减少实际运行中的迟到风险。

五、结论与展望

• 论文首次提出鲁棒无人机‑车辆路线问题，同时考虑多卡车、多无人机和时间窗不确定性，建立了紧凑数学模型并证明问题NP‑困难。
• 通过引入“卡车‑无人机模式”和两阶段定价方法，构建了高效的分支‑定价算法，有效减少了需要生成的列数，显著提升求解效率。
• 数值实验显示，算法能在中等规模问题上获得优于商用MIP求解器的性能，对实际物流企业具有较高应用价值。
• 创新亮点在于：将预算式鲁棒优化与无人机调度相结合；设计可并行处理多无人机的标号算法与动态规划；提出比传统集合划分更紧的主问题。
• 未来工作可从以下方向展开：考虑动态订单到达、车辆不同类型或多仓库等复杂场景；研究不同不确定集（如分布鲁棒）的影响；开发面向更大规模实例的近似算法或机器学习辅助调度策略。

通过上述分析，读者可以理解论文的核心问题、模型思想与算法机制，以及其在无人机‑车辆协同配送领域的贡献和潜在发展方向。

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