论文题目：Exact methods and a two-stage iterative heuristic for the carrier-vehicle traveling salesman problem

第一作者：李延通 大连海事大学航运经济与管理学院副教授，博士生导师，中国运筹学会排序分会理事、随机服务与运作管理分会青年理事，研究聚焦：物流与供应链管路、运筹优化与智能决策、低空经济运营与管理、港航运输。

E-mail：yantong.li@dlmu.edu.cn。

通讯作者：Jean-Franc¸ois Coˆte  Professor (Operations and decision systems)Université Laval，研究聚焦于运筹学的数学与算法研究，涵盖组合优化、随机 / 鲁棒优化等领域，应用于车辆路径、物流调度、仓储包装等场景。

E-mail：Jean-Francois.Cote@fsa.ulaval.ca。


载体-子载具协同系统：新型旅行商问题的建模与求解

论文摘要

随着无人机等无人系统在巡检与救援中的广泛应用，其续航与载荷受限问题日益突出。本文研究“载体-载具”协同巡检中的载体-载具旅行商问题（CVTSP），通过联合优化载体行程与无人机起降点，最小化载体返回起点的最大完成时间。作者提出强化的 MISOCP 模型，并设计基于逻辑式 Benders 分解的精确算法，将目标访问顺序与起降点选址有效解耦；同时提出两阶段迭代启发式以应对大规模实例。529 个基准算例表明：所提方法在小中规模下可高效求得最优解，在大规模场景中显著优于现有算法，体现了模型强化、改进解析割与两阶段框架的综合优势。

一、问题背景与挑战

1.1 载体‑载具协同系统的应用

  • 无人系统协同：无人机、无人艇等因安全、精确与低成本被广泛用于环境监测、灾害救援和海上巡检，但单机续航有限。
  • 载体协作：通过载体输送无人机至目标附近，无人机完成巡检后返回载体，可兼顾高效率与远程能力。
  • CVTSP 定义：包含一个大型载体（速度 ）和一个小型无人机（速度 、续航 ），需要访问  个目标，决定访问顺序以及无人机起飞/降落点，目标是最小化载体返回起点的时间。

1.2 挑战分析

  • 组合与连续决策交织：既要确定目标顺序（离散决策），又要连续优化无人机起飞/降落位置，问题复杂度高，属于 NP‑Hard 的旅行商问题推广。
  • 速度与续航约束：无人机的出发时间  和返回时间  必须满足 、 以及  等约束。
  • 载体‑无人机同步：根据性质 1，最优解中载体与无人机在每个目标点上严格同步。
  • 计算规模大：现有模型最多只能处理 15–20 个目标，需要开发更强模型与高效算法。

二、问题建模与模型加强

2.1 基础 MISOCP 模型

  • 决策变量：

    • ：若目标  在  之前访问，则 ，否则为 0。
    • 、：无人机在访问目标  的起飞与降落坐标。
    • 、：无人机从起飞点到目标、从目标返回降落点的时间。
    • ：载体从  的降落点到  的起飞点的行驶时间。

  • 目标函数与约束：该模型最小化最大完成时间：

    并通过以下关键约束保证各部分配合：

    • 无人机飞行距离约束  与 。
    • 载体运载无人机时行驶距离 。
    • 载体单独运行时 ，大  用于禁止不连续弧。
    • 续航约束 。
    • 流量平衡与子巡回消除约束（改进的 Miller‑Tucker‑Zemlin 约束）。

2.2 新增变量与有效不等式

作者引入独立的  和  替代传统模型中单一的 ，借此推导出多条有效不等式以增强模型：

  • 最小距离约束：两个连续访问目标  的总行程不得短于它们的欧氏距离 ：
  • 车辆飞行时间上界：利用三角不等式推导无人机出发与返回时间的上界：
  • 载体行驶时间界定：对于弧 ，
    并对出发和返回时的特殊弧做类似处理。
  • makespan 下界  ：结合距离和续航给出每条弧的最小可能行程，用于约束 。
  • 远距离目标的满续航约束：若前后目标与  的距离超过 ，则无人机必须耗尽续航。

通过引入上述约束，模型得到显著强化，计算实验表明较原模型大幅降低求解时间与 gap。

三、逻辑式 Benders 分解方法

3.1 分解思想与流程

逻辑式 Benders 分解利用原问题的自然结构：主问题负责确定目标访问顺序（TSP），子问题负责在给定顺序下决定起飞/降落点（CVP）。其流程如下：

  • 主问题 (MP) ：基于强化的整数约束及有效不等式，求解旅行商模型，得到目标访问顺序；同时约束 ，其中  由两阶段启发式提供。

  • 子问题 (SP) ：固定访问顺序后，求解二阶锥规划确定起落点并计算上界 。

  • Benders 割：利用子问题信息反向补充主问题，通过下述四类割加速收敛：

    • 排除割（No‑Good Cut）：排除已经评估过且代价不优的顺序。
    • 最优割：当主问题候选顺序与子问题解一致时强制 。
    • 解析割：对每条在当前顺序中的弧  设定最大可能的行程减少 ，产生
      其中  由距离和续航决定。
    • 改进解析割：在解析割基础上加入弧不在  时的最小行程 ，即
      更准确反映弧的替换效应。

3.2 收敛性与优势

与文献中的排序型算法不同，LBBD 通过割逐步删除次优的访问顺序，而非枚举所有 Hamilton 路径。改进的解析割显著减少求解空间，在基准实例上可以比传统精确算法更快找到最优解。

四、两阶段迭代启发式

4.1 第一阶段：基于近似行程矩阵的 TSP 求解

由于 MISOCP 中二阶锥约束导致计算复杂，作者在启发式中使用一个近似行程矩阵将 CVTSP 简化为 TSP。针对任意两目标 ，近似行程 需满足 。作者根据目标间距离和续航 给出初始化公式：

并用 Lin‑Kernighan 启发式求解 TSP 获得访问顺序。

4.2 第二阶段：CVP 求解与矩阵更新

在固定顺序下求解 CVP（SOCP），得到最优起飞点、降落点以及无人机出发和返回时间。随后按照

更新与当前顺序相关的 。未被访问的弧保持原值。这一更新过程反映图 1 所示的三步：初始矩阵、计算元素、更新矩阵。

4.3 更新矩阵示意图

为了帮助理解矩阵更新过程，论文给出三幅示意图 (a)-(c)，下图展示更新策略：左图是初始化的行程矩阵，中图通过当前起降点计算新的行程值 ，右图用红色标记新值更新矩阵。该图直观说明如何利用 SOCP 解更新近似行程，从而改进下一次 TSP 求解。

图1 更新矩阵方法示意（取自 Fig.1）
图1 更新矩阵方法示意（取自 Fig.1）

图1 中：

  • (a) 显示初始估计行程矩阵 。
  • (b) 在某次迭代中，利用求解得到的起飞/降落点计算具体行程，例如 、 等。
  • (c) 将新的行程值写入矩阵形成  供下一轮 TSP 使用。

4.4 多样化机制

仅更新当前连接弧可能陷入局部最优。作者提出多样化机制：当连续  次迭代无改进时，基于三参数 、期望值 、上界，按均匀分布随机重新生成 ：

这一随机化既保持探索潜力，又倾向于在期望值附近取样，从而促进全局搜索。

五、数值实验与结果分析

5.1 基准实例与设置

实验采用三个基准库，共 529 个实例，包括：

  • Gam72：72 个 10–15 目标的实例，分为 SD、MD、LD、VLD 四类；车辆速度 、无人机速度 、续航 。
  • Erd132：132 个 16–50 目标实例，参数与 Gam72 相同，规模更大。
  • Poi325：325 个 10–100 目标实例，续航 ，、，目标点布置更复杂。

所有模型使用 CPLEX 20.10 求解，单次运行时间限制 3,600 或 7,200 秒。启发式的多样化参数设置为 、迭代次数 。

5.2 精确方法对比

作者将强化模型（Model+）和 LBBD 与文献中的 MISOCP 模型（G2018、E2021）及排序式算法（RBA、BAB）比较。主要发现：

  • 在 Gam72 小规模实例中，所有方法均能在时间限制内达到相同最优值，但 Model+ 和 LBBD 平均求解时间更短，LBBD 在 MD、LD、VLD 组中最快。
  • 对于 Erd132 中 16–20 个目标实例，Model+ 与 LBBD 明显快于现有模型，并能在更短时间内找到最优解。对于 25–50 目标实例，Model+ 和 LBBD 提供有效上界与下界，其他方法无法提供。
  • 在 Poi325 大规模实例中，Model+ 与 LBBD 能处理最多 100 个目标，并给出有效界；LBBD 在大实例中提供最优的上界，而其他方法难以求解。

5.3 启发式对比

两阶段迭代启发式 (TSIH) 与现有启发式（如迭代局部搜索 ILS、贪婪序列 GS 等）进行比较，结果显示：

  • 在 Gam72 和 Erd132 上，TSIH 平均上界与最优解偏差极小，多数实例可以达到或接近最优。
  • 在大规模 Poi325 上，TSIH 发现了多数实例的新最佳解，比贪婪策略与局部搜索方法精度高且运行速度快。
  • 多样化机制有效避免了启发式陷入局部最优，保证算法的稳定性。

六、结论与创新点

6.1 研究结论

本文针对载体‑载具旅行商问题提出了完整的求解框架。通过引入独立的出发时间和返回时间变量，构建出强化的 MISOCP 模型，并推导出多条有效不等式。基于逻辑式 Benders 分解，利用改进解析割显著提升了精确求解性能。为应对大规模实例，作者设计了简洁高效的两阶段迭代启发式，结合矩阵更新与多样化策略，实现了快速收敛。在 529 个基准实例上的实验表明，该模型与算法在求解质量和效率上均领先于现有工作。

6.2 主要创新亮点

  • 模型增强：提出新的 、 变量与对应约束，推导出针对距离、续航的有效不等式和下界 ，显著加强了 MISOCP 模型的紧致性。
  • 改进解析割：在 Benders 分解中提出新的解析割与改进解析割，可同时考虑删除弧带来的减小和新增弧带来的增大，明显改善收敛速度。
  • 两阶段迭代框架：首次将 CVTSP 划分为基于近似行程矩阵的 TSP 与二阶锥规划的 CVP，利用更新矩阵迭代改进访问顺序，并辅以多样化机制保证全局搜索。
  • 计算表现优异：精确算法能在可接受时间内解决 20–50 目标实例，启发式在 100 目标规模上依旧表现出色，找到大量新最佳解。

6.3 展望

未来研究可考虑：

  • 扩展模型处理多辆载体、多次飞行或多个无人机的协同；
  • 引入动态因素，如目标优先级、时间窗和随机天气，构建更贴近实际的模型；
  • 结合机器学习预测估计行程矩阵，为启发式提供更准确的初始估计，加速收敛。

本研究为海空协同巡检等任务提供了强有力的理论与算法支持，对无人系统的协同调度与优化具有重要意义。

文章须知 

链上镖师团队：常文婕（AEIC）、祁园园、汪朝杰、王一航、张仁义（EIC）、张晓乐

原文链接：https://doi.org/10.1287/ijoc.2025.1140

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