海上物流协同：母船无人机组合的路径规划研究

论文题目：The Mothership and Drone Routing Problem

第一作者：Stefan Poikonen, Professor (Assistant) at University of Colorad. 研究核心聚焦组合优化与路径规划，重点围绕旅行商问题（TSP）、车辆路径问题（VRP）及无人机相关路径规划展开。

E-mail：stefan.poikonen@ucdenver.edu

大牛作者：Bruce L. Golden, Editor-in-Chief of the INFORMS Journal on Computing. 聚焦组合优化、网络模型与应用运筹学，深耕车辆路径、旅行商等问题的算法研究，跨医疗、物流等场景落地应用，且推动技术转化为实用软件并为多家企业提供咨询。

E-mail：bgolden@rhsmith.umd.edu

海上物流协同：母船无人机组合的路径规划研究

论文摘要

本文研究的 母船‑无人机路径规划问题（MDRP）关注一个大型运输工具与一架小型无人机协同执行任务。与经典的卡车‑无人机配送不同，本问题在连续欧几里得空间中，母船可以在任意位置起降无人机。在给定的目标集合  下，每个目标必须由无人机从母船出发访问并返回；无人机续航时间受限为 ，速度为 。文章通过构建 二阶锥规划 子模型解决固定访问序列下的起降点优化，结合 分支定界 策略搜索最佳访问顺序。此外，提出多种启发式算法，如贪心序列、局部搜索以及部分求解‑贪心插入，旨在在大规模实例中快速获得高质量解。研究还扩展到允许无人机连续访问多个目标的 无限容量模型（MDRP‑IC），通过划分无人机子巡回并优化母船起降位置解决。计算实验表明，所提方法在不同规模和分布实例上显著缩短了总任务时间，相比传统旅行商路线节省 20%～35% 的时间，并能灵活适应续航半径和速度比的变化。

一、问题背景与意义

1.1 研究背景

• 无人机与传统运输工具组合被广泛应用于物流、军事和灾害救援。
• 先前的研究集中在卡车‑无人机协同，如 飞行助手旅行商问题 (FSTSP) 和 卡车‑无人机旅行商问题 (TSP‑D) 。
• MDRP 的特点在于母船在连续空间航行，能在任意点起降无人机，不再局限于图上的离散节点。
• 应用包括岛屿或海上配送、海上搜救和军事侦察等。

1.2 问题定义

• 车辆构成：一艘母船和一架无人机起点与终点相同，母船速度为 1，无人机速度为 。
• 任务要求：无人机必须从母船出发访问每个目标  并返回，且每次飞行时间  不超过续航上限 。
• 连续决策：起降位置  与  可以在平面上自由选择，起飞、降落时间以及飞行长度均为连续变量。
• 目标：使母船和无人机从起点返回终点的总完成时间最短。
• 理论界：作者证明 MDRP 的最优时间介于旅行商问题 (TSP) 的时间与其  倍之间：

  这说明利用无人机协同可显著缩短任务时间。

下图展示了一个包含 4 个目标的 MDRP 示例解，其中黑线表示母船航迹，红色虚线表示无人机飞行路径，叉号标识起降点：

二、模型与方法

2.1 固定序列下的二阶锥规划

若访问顺序  已知，需确定各目标的最佳起飞点  和降落点 。作者将该子问题称为 LENSEQ(S) ，使用二阶锥规划求解。

• 决策变量：

• ：母船与无人机合体航行时间；
• ：无人机飞行及等待时间；
• ：第  个目标的起飞与降落位置；
• ：无人机往返飞行距离。

• 目标函数：

  即最小化任务总时长。

• 主要约束：

• 母船合体航行时间必须不短于从上一降落点到下一起飞点的距离：
• 无人机飞行时间必须覆盖往返飞行距离：
• 起飞与降落点分别与目标的距离不超过  和 。

该模型可以通过二阶锥规划求解器高效求得，使得在给定顺序下起降点最优。

2.2 分支定界法搜索最优序列

由于  个目标的访问顺序组合为 ，逐一枚举不可行。作者利用 分支定界 (BAB) ，通过下界剪枝缩小搜索空间。其核心思想是：

• 对于每个节点关联一个部分序列 ，求解 LENSEQ 获得下界 。若其下界过大，则该序列的扩展不会更优。
• 逐步选择与当前序列中目标距离最远的未访问点作为新扩展，并将其插入不同位置产生子序列；对每个子序列计算下界，并根据是否已包含全部目标设定上界。
• 当根节点上下界相等时找到最优序列，再调用 LENSEQ 获得对应起降点，保证全局最优。

下图是针对三个目标的分支定界树示例，圆节点标注了不同的访问序列。

2.3 启发式算法

分支定界在目标数较大时计算量巨大。为提高效率，文中提出以下启发式方法：

• 贪心序列 (GS)：先求解欧氏旅行商序列，然后直接利用 LENSEQ 计算起降点，得到近似解。
• 贪心序列‑局部搜索 (GSLS)：在 GS 基础上通过局部交换、插入或反转操作生成邻域序列，逐步改善目标序列。
• 部分求解‑贪心插入 (PSGI)：先选取一半目标构建分支定界树求得部分最优序列，再将剩余目标逐一插入，使每次插入后的 LENSEQ 结果最小。

三、无限容量扩展模型 MDRP‑IC

3.1 模型拓展与定义

在实际任务中，无人机或小艇可能连续访问多个目标后再回母船。作者提出 MDRP‑IC，允许无人机连续执行多个目标巡回。关键概念如下：

• 无人机子巡回 ST：一组按顺序访问的目标 ，期间无人机不回母船。
• 组合 (composition) ：给定全序列 ，将其中的目标划分为若干子巡回且保持顺序不变，如 。
• 无限续航极限：当续航时间  时，无人机会连续访问所有目标，问题等价于速度为  的欧氏旅行商问题。

3.2 固定组合下的起降优化

对于给定组合 ，作者构建 LENCOMP(C) 模型确定每个子巡回的起飞点  和降落点 ，并计算母船和无人机的总时间。与 LENSEQ 类似，LENCOMP 通过二阶锥规划最小化总时长，约束无人机在飞行与母船分离时不超过续航限制。

3.3 组合与序列的选择方法

为选择高质量的组合 ，文中提出几种策略：

• BAB‑C：分支定界法的扩展。在每个节点上不仅优化序列还要搜索最佳组合下界，直到上下界收敛。由于组合数 ，需配合高效的下界计算方法。
• 贪心序列‑精确组合 (GSEC)：先利用旅行商路径作为访问序列，然后对该序列寻找使 LENCOMP 最小的组合，获得近似最优结果。
• 贪心序列‑贪心组合 (GSGC)：在旅行商序列上依次将尽可能多的目标装入同一子巡回，直到满足  且首尾距离不超过 ，然后进行下一子巡回。
• 贪心序列‑贪心组合(带余量) (GSGC+S)：在 GSGC 基础上预留一定续航余量，避免每个子巡回填满，方便母船起降位置自由调整。

下图展示了 GSGC 与 GSGC+S 策略在同一实例上的对比，右图预留了余量使母船行驶距离更短：

而 MDRP‑IC 典型解的示例如图所示，三条红线分别表示三个子巡回，黑线为母船航迹：

四、实验设计与结果分析

为评估各算法性能，作者在两类实例上进行实验：一类为目标点在  区域内均匀分布，另一类为目标集中在两个圆形集群。参数设置为无人机续航 ，速度比 。

• MDRP 结果：在 25 组随机实例上，分支定界法能够得到最优解，但当目标数超过 20 时计算时间迅速增长，在  时往往超时；贪心序列及局部搜索能在几秒钟内获得接近最优的结果，节省率约 25%～34%，相对 TSP 解平均节省 30% 的时间。部分求解‑贪心插入在大实例上表现最好，兼顾时间和解的质量。
• MDRP‑IC 结果：在  时，扩展分支定界 BAB‑C 可以求得最优组合，但同样面临时间瓶颈；GSEC 与 GSGC+S 启发式的差距很小，后者预留续航余量在某些实例中取得更短总时长。与 MDRP 相比，允许连续巡回显著缩短母船行程，但无人机连续飞行需要合理的子巡回分组。

总体而言，启发式方法能够在极短时间内获得高质量解，特别适用于目标数量较大的实际场景；分支定界法虽能提供最优解，但受限于计算资源。

五、结论与贡献

本文首次在连续空间提出 母船‑无人机路径规划问题 (MDRP) 并给出精确与启发式求解方法。主要贡献包括：

• 建立了二阶锥规划模型 LENSEQ 与 LENCOMP，实现连续空间下起降位置与时间的联合优化。
• 设计了基于下界剪枝的分支定界算法，在保证全局最优的同时避免对所有序列穷举搜索。
• 提出三种启发式算法（GS、GSLS、PSGI）以及对应的 MDRP‑IC 启发式（GSEC、GSGC、GSGC+S），为大规模实例提供高效求解方案。
• 通过理论界限证明 MDRP 的最优值介于旅行商总距离与其  倍之间，为实际应用提供估计区间。
• 扩展至 MDRP‑IC 模型，提出无人机子巡回与组合的概念，为连续访问多个目标的场景提供了可行框架。

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