论文题目：New integer optimization models and decomposition-based algorithms for the multi-agent pathfinding problem with time-spacing constraints

第一作者：Seyoung Oh 韩国首尔大学工业工程系博士后，聚焦多智能体路径规划、批量决策与调度问题，探索不确定性场景下的鲁棒优化及产能与库存管理策略，在EJOR、Omega等期刊发表多篇文章。

E-mail：sayzeros@snu.ac.kr

通讯作者：Kyungsik Lee 教授，博士生导师，专注于离散优化理论与应用领域的研究，核心方向涵盖整数规划与组合优化、不确定性下的优化，并将这些理论方法落地应用于物流系统、能源系统、医疗系统等多个场景。

E-mail：optima@snu.ac.kr


多智能体路径规划可行域收缩：去冗余行为的整数建模方法

论文摘要

本文关注 多智能体路径规划（Multi‑Agent Pathfinding，MAPF）在存在 时间间隔约束（time‑spacing constraints，TS）下的扩展问题——MAPF‑TS。该问题要求在给定图上为多个自主移动体规划无碰撞路径，且额外限制任一节点在连续  时间窗口内只能由一个代理占据。MAPF‑TS 能同时应对机器人实际执行过程中出现的延迟与提前现象。由于约束更严格，MAPF‑TS 属于 NP 难 问题。

论文指出某些重访行为（revisit behaviors）在最优解中是不必要的：代理离开顶点后若在  步内又回到该顶点，会导致现有模型中的约束被违反，但这类重访并不会改变问题的可行性。在此基础上作者提出两类新的 整数优化模型： 用于完整的 MAPF‑TS， 用于禁止重访的缩减可行域，并进一步提出四类 有效不等式（TVC1–TVC4）以强化模型。此外，论文设计了两种分解型精确算法：Lagrangian 松弛分支定界算法（LAG） 和 分支定价剪枝算法（BPC），分别通过 Lagrangian 松弛和路径定价‑割平面的方式解决大规模 MAPF‑TS。大量基准实验表明，新模型的 LP 下界明显紧于旧模型，LAG 能快速找到高质量可行解，而 BPC 在求得紧下界方面表现更优。

一、研究背景与问题定义

1.1 多智能体路径规划与时间间隔约束

  • MAPF 问题：给定无向图 、代理集合  以及离散时间窗口 ，要求为每个代理  规划从起点  到终点  的路径 ，每个时间步只能留在当前顶点或前往相邻顶点。目标是在避开顶点冲突和交换冲突的同时最小化所有代理的总行程。

  • 时间间隔冲突：若存在两条路径 、某个顶点 ，以及  与 ，使得  或 ，则称为时间间隔冲突。时间间隔约束等价于禁止所有此类冲突，从而使解在有界时间偏差下对执行延迟或提前具有鲁棒性。

  • 复杂性：作者证明了 MAPF‑TS 是 NP 难的，其难度至少与经典 MAPF 相当。

1.2 基本整数优化建模

现有 ARC-flow 模型  使用时空图对代理运动进行编码。以二元决策变量  表示代理  在时间  经过弧 ，模型的目标是在避免冲突的同时最小化总成本：

模型受到以下主要约束：

  • 流守恒约束对于任一顶点  和时间 ，进入顶点的流量与离开的流量相等：

  • 起点与终点约束每个代理在起点时间只能离开起点一次，在终点时间只能到达终点一次，这些约束在文中公式 (3)、(4) 中给出。

  • 时间间隔冲突约束通过约束形式禁止顶点和交换冲突，控制两个代理在  内不能占用同一顶点。

然而，该模型的一个关键问题是决策变量和约束数量随着时间地平线  的增大呈指数增长；例如一个  的小型仓库场景就可能产生超过百万个变量和约束。

二、现有模型的局限与挑战

  • 时间地平线未知：在求解前无法确定最优解需要多长的时间地平线；取  过大导致模型膨胀，取  过小则可能漏掉最优解。

  • 变量规模巨大：即使知道最小时间地平线，一些实例（如 10 个代理的小仓库）也会产生超过一百万个变量，使通用整数优化求解器难以直接求解。

  • LP 下界松弛：现有模型的线性放松下界较弱，导致分支定界算法难以快速剪枝，影响求解效率。

为此需要寻找更紧凑的模型和针对性算法。

三、新模型与理论贡献

3.1 剔除重访行为并缩减可行域

作者发现代理在  步内离开某顶点后又返回同一顶点的“重访行为”不影响最优解，因此可被剔除。对于禁止重访的可行域，作者定义了集合

并证明对于任意实例至少存在一个最优解属于 。

图1 重访行为示例（取自 Fig.1）
图1 重访行为示例（取自 Fig.1）

3.2 新的整数优化模型

基于上述观察，作者提出两种新模型：

  1. 模型  ：适用于所有 MAPF-TS 可行解。在原 ARC-flow 模型基础上，利用新的冲突约束 时间间隔不等式 (T) 描述时间间隔冲突的兼容集合，并将部分不必要变量移除。该模型的冲突约束数量只与顶点数和时间地平线相关，大大减少了约束规模。

  2. 模型  ：适用于禁止重访的缩减可行域。相比 ，该模型在可行域内强制 时间区间出弧不等式 (R) ，并引入四类有效不等式（TVC1–TVC4）以紧化线性放松。作者证明这些不等式支配了早期文献提出的等待边、双代理等待边等四类不等式。

新模型体现为一个 集合划分问题：在时间-顶点-代理三维空间中，任何不相容的动作不能同时发生，其最大团不等式可写为：

其中  为不兼容动作构成的最大团集合。

3.3 新模型的优势

理论上，作者证明新模型的 LP 下界比旧模型更紧；具体而言， 的 LP 可行集包含于 ，而  又包含于旧模型  的 LP 可行集，从而有

实验也验证了这一点，特别是在包含大量潜在冲突的图上， 的 LP 下界提高超过 70%。

四、分解算法设计

为应对模型规模大与求解困难，论文提出两种基于分解的精确算法。

4.1 Lagrangian 松弛分支定界算法（LAG）

LAG 通过 Lagrangian 松弛 将时间间隔冲突约束以乘子  形式转移至目标函数，分解为各代理的最短路子问题。主要步骤如下：

  • 松弛建模：将冲突约束  松弛，得到松弛问题 ，并通过求解最短路获得子问题解 。

  • 求解拉格朗日对偶：通过 子梯度法 更新乘子 ，并采用基于 A* 的最短路算法作为子问题求解器。

  • 分支定界：在搜索树中，每个节点由一组禁止某代理在特定时间访问某顶点的分支约束表示。算法利用 FindConflict 过程寻找当前解中最早发生的时间间隔冲突并生成子节点。

  • 启发式求解：当下界得到显著改进时应用启发式方法，逐个固定代理的路径以快速构造可行解，提高上界质量。

相较标准分支定界算法，LAG 在分支过程中可能直接找到最优解，并利用父节点乘子初始化子节点，提升收敛速度。

4.2 分支定价剪枝算法（BPC）

BPC 基于 Dantzig–Wolfe 重构 将 ARC‑flow 模型转化为路径‑基模型，使用路径变量  表示代理  是否选择路径 。其核心思想如下：

  • 列生成：在根节点只包含少量路径变量，求解主问题（RMP）。随后通过 价格子问题（求解修改成本的最短路径）找到具有负 reduced cost 的新路径，并加入 RMP。

  • 割平面：对 LP 解进行剪枝，检查哪些有效不等式被违反，并动态加入这些约束。这些不等式分为四类（TVC1–TVC4），其检查可以通过简单的时空冲突检测完成。

  • 分支规则：采用 divergence node branching，选择存在流分叉的节点进行二分，将不兼容的路径分配到不同子节点，以保持价格子问题的结构。

  • 上界启发式：利用 LP 对偶信息构造可行解，依次选择修改后成本最小的路径并固定，同时禁用与已定路径发生时间间隔冲突的弧。

BPC 针对路径数量巨大问题，只生成必要路径和约束；但其列和割分离的迭代导致计算时间较长。

五、实验设计与结果分析

作者在标准 MAPF 基准中选择了五种 2D 网格图（empty‑8‑8、random‑64‑64‑20、warehouse‑10‑20‑10‑2‑1、warehouse‑20‑40‑10‑2‑2、brc202d），并测试多个时间间隔参数  和代理数量组合。对比模型包括旧模型 、新模型 、缩减模型  以及附加 TVC1–TVC4 不等式的 。

5.1 LP 放松比较

  • 模型紧致性：实验表明四种模型的 LP 下界大小为 。尤其在存在大量潜在冲突的图（如 empty‑8‑8、random‑64‑64‑20）上， 的平均 LP gap 达到 70% 以上，而  下界最松但求解时间最短。

  • 求解时间：加入有效不等式后，模型更紧但单个 LP 求解时间增加约两倍。

5.2 LAG 与 BPC 的性能

  1. LAG 对比：采用缩减模型  的 LAG 在所有测试实例中均能找到可行解，而  在 small 图 empty-8-8 的 4 个实例上未能找到可行解。在 78% 的情况下，新模型将 LAG 的剪枝差距  平均减少 78%，求解时间  平均减少 64%。

  2. BPC 对比：BPC 对四种模型求解部分实例时仍无法找到可行解，但  与  在大多数情况下提供最好的下界  约 0.51，尤其在 empty-8-8 图上  的  达 0.98。不过，BPC 总体求解时间比 LAG 长，适用于关注下界质量的应用。

5.3 算法间比较

综合考虑可行解比例 、最优证明比例 、剪枝差距  和求解时间 ，作者的结论如下：

  • LAG+新模型：在大多数实例中能在较短时间内找到高质量可行解， 和  均优于 BPC 与 CBS。

  • BPC+新模型：能够提供更紧的下界和最优性证明，但时间成本更高。

  • CBS：作为基准，CBS 适合稀疏场景，但在密集场景或  较大的情况下表现不如 LAG 和 BPC。

六、结论与未来展望

本文通过系统的理论与实验分析，对 MAPF‑TS 这一现代智能物流、机器人和交通系统中的关键问题进行了深入探讨。主要贡献包括：

  • 证明重访行为不必要，从而缩减可行域并推出更紧凑的整数模型。
  • 提出两种新模型  与  及四类有效不等式，理论上提升 LP 下界，在实验中显著改进求解效率。
  • 设计 Lagrangian 松弛分支定界算法与分支定价剪枝算法，分别侧重于快速找到高质量可行解和提供紧下界，能处理大规模实例。
  • 综合实验验证：在标准 benchmark 上，新模型与算法整体优于现有方法，尤其在复杂和拥挤的网格上。

未来工作方向包括：

  1. 深入研究两顶点团不等式和其他组合不等式 的分离与添加策略，以进一步加强模型；
  2. 分析 MAPF‑TS 可行性问题的复杂性，目前仅针对 LP 和特定条件有分析；
  3. 发展更高效的剪枝启发式，在 LAG 和 BPC 中动态调整分支顺序和路径选择；
  4. 扩展到连续时间或非网格图环境，以应对真实机器人系统中的复杂运动学约束。


文章须知 

推文编辑：单子叶 

责任编辑：张仁义

原文链接：https://doi.org/10.1016/j.ejor.2025.07.068

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