🤖 machine learning

Neural Cluster First, Route Second: One-Shot Capacitated Vehicle Routing via Differentiable Optimal Transport

本文介绍了Neural CFRS，这是一种新颖的非自回归框架，它利用可微最优传输进行聚类和路径规划，从而在单次求解中解决带容量约束的车辆路径问题，并相较于现有的自回归神经方法实现了更优越的分布外泛化能力和参数效率。

原作者： Samuel J. K. Chin, Maximilian Schiffer

发布于 2026-05-12

📖 1 分钟阅读☕ 轻松阅读

原作者： Samuel J. K. Chin, Maximilian Schiffer

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你是一家拥有多辆配送卡车的车队经理。每天早上，你会收到一份需要配送包裹的客户清单，而你拥有的卡车数量有限，且每辆卡车都有特定的载重上限。你的目标是确定每辆卡车服务哪些客户以及按什么顺序服务，以便在不过载任何卡车的前提下，尽可能减少燃油消耗（行驶距离）。

这就是带容量约束的车辆路径问题（CVRP）。这是一个经典的数学谜题，随着客户数量的增加，其难度会变得极高。

旧方法与新方法

旧方法（自回归模型）：
可以将当前最佳的 AI 方法想象成一位非常迅速但略显困惑的导游。它们试图一次一个站点地构建配送路线。“好的，我在配送中心，下一个是谁？哦，是这户人家。现在，谁在那户人家旁边？”

问题所在： 随着城市规模扩大，这种“逐个”的方法变得缓慢且混乱。AI 会迷失在细节中，难以处理对称性（如果旋转地图，它会感到困惑），并且当城市布局与其训练数据略有不同时，往往就会失败。

新方法（神经 CFRS）：
这篇论文的作者 Samuel Chin 和 Maximilian Schiffer 决定不再逐个构建路线。相反，他们回归到一个老派的想法，即“先聚类，后路径”（Cluster-First, Route-Second）。

想象一下你在组织一场大型聚会。与其逐个告诉人们具体坐在哪里，不如先根据他们认识谁以及每张桌子能坐多少人，将房间划分为不同的组。一旦分组完成，你只需告诉每个组：“去找出你们在桌边就座的最佳方式。”

神经 CFRS 正是这样做的：

先聚类： 它瞬间将客户分组到符合卡车载重容量的“桶”（簇）中。
后路径： 它将这些“桶”交给标准的、完美的数学求解器，以计算出每个组的具体行驶路径。

工作原理：魔法成分

这篇论文引入了一些巧妙的技巧，使这种“分组”能够瞬间且完美地完成：

1. “城市地图”记忆（空间词汇）
大多数 AI 将每个城市视为全新的、随机的点云。但在现实生活中，配送路线每天都在同一个城市发生。

类比： 想象 AI 预先记住了城市“街区”的地图。它不需要每天早上重新学习“主街在河边附近”。它只需在记忆中查找该街区。
结果： 这使得 AI 可以非常小巧且快速（像一个轻量级应用），同时仍能深刻理解地理环境。它能在几秒钟内处理 1,000 个客户，而这项任务通常需要几分钟甚至几小时。

2. “软分配”（可微最优传输）
通常，决定哪个客户由哪辆卡车服务是一个“硬性”的是/否选择。如果选错了卡车，数学计算就会崩溃。

类比： 与其立即做出硬性决定，AI 使用一种“模糊”逻辑层（称为最优传输）。这就像将水倒入桶中。水（客户）会自然地流向最合适的桶（卡车），同时尊重桶的容量限制。
结果： 这使得 AI 能够平滑地学习和调整其决策，而不是过早地陷入错误的选择中。

3. “对称性”护盾
如果你将地图旋转 90 度，配送问题完全相同。但许多 AI 对此感到困惑，认为这是一个全新的问题。

类比： 新系统就像一个知道正方形桌子无论从正面还是侧面看都是一样的的人。它忽略“方向”，只关注点与点之间的关系。
结果： AI 不需要在成千上万张旋转过的地图上进行训练就能理解它们。它天生就“懂”这一点。

结果：快速、轻量且精准

这篇论文声称，这种新方法之所以能改变游戏规则，原因如下：

单次推理速度： 它在一次前向传播（单次 glance）中解决整个问题，而不是分步进行。
零样本扩展： 即使它仅在 100 个客户的问题上训练过，它也能解决拥有1,000 个客户（规模巨大）的问题。它不需要重新训练；它只是进行了泛化。
小巧而强大： 即使是他们 AI 的一个非常简单的版本（仅有一层“神经元”），其表现也几乎与复杂的深度模型相当，与完美解的差距仅为 5% 左右。
面向现实世界： 在标准测试（CVRP100）中，它与最佳可能解的差距为2.73%，击败了其他许多顶级 AI 方法，并非常接近最佳传统数学求解器（后者需要运行数小时）的表现。

核心结论

作者们认为，与其试图教 AI 一步步“驾驶”路线（这既困难又缓慢），不如教它先将站点“组织”成组。通过将这种老派逻辑与现代快速数学（最优传输）以及预先记忆的城市地图相结合，他们创造了一个快速、高效且令人惊讶地擅长解决大规模配送难题的系统，而且无需超级计算机。

技术摘要：先聚类后路由

问题定义

本文 addressed 的**带容量约束的车辆路径问题（CVRP）**是最后一公里物流中的根本性挑战：在统一容量为 $Q$ 的车队从中央配送中心服务一组具有特定需求的客户，同时最小化总行驶距离。

作者指出了当前**神经组合优化（NCO）**方法的关键局限性：

自回归（AR）瓶颈：主流的 NCO 方法逐 token 构建解，导致顺序解码成本高、对空间对称性敏感，以及分布外（OOD）泛化能力脆弱。
方法论脱节：虽然旅行商问题（TSP）纯粹是路由任务，但 CVRP 本质上涉及划分问题（将客户装箱到满足容量约束的簇中）与路由的耦合。现有 NCO 方法常将 CVRP 视为路径生成任务，将容量约束留给昂贵的后验搜索来强制执行。
基准不匹配：标准基准随机独立同分布（i.i.d.）重采样节点坐标，忽略了现实物流中固定的地理支撑（例如城市街道网络），在这些场景中，同一区域每日以变化的需求进行路由。

方法：神经 CFRS

作者提出了神经 CFRS，这是首个基于经典**先聚类后路由（CFRS）范式的纯非自回归（NAR）**一次性神经框架。该模型不顺序生成路径，而是对客户到车辆簇进行全局可微分配，随后并行求解独立的 TSP。

该架构分为三个阶段运行：

1. 预训练与空间支撑先验（ $\Psi$ ）

为解决现实物流中固定地理的问题，作者在固定的一组潜在客户位置（ $X$ ）上预训练了一个空间掩码自编码器（SMAE）。

SMAE 通过重建成对欧氏距离和局部 $k$ -NN 连通性（而不消耗绝对坐标），学习 $E(2)$ 不变（平移、旋转、反射不变）的嵌入。
这些冻结的嵌入（ $\Psi$ ）充当“空间词汇表”，使下游模型能够在同一地图上泛化到新的需求实例，而无需重新学习几何结构。

2. 阶段一：种子生成

**种子 Transformer（ST）**识别一组节点作为初始簇中心（“种子”）。

它预测节点作为种子的边际概率，并学习对比表示以分组相似节点。
容量感知贪婪解码策略选择 $K$ 个种子（其中 $K$ 为估计的车队规模），并根据对比相似性贪婪地将附近节点打包到这些种子中，确保空间分散性和容量可行性。

3. 阶段二：通过可微最优传输进行全局分配

**聚类 Transformer（CT）**计算客户与选定种子之间的潜在距离（ $\Delta_{ij}$ ）。

可微松弛：为了端到端地强制执行全局容量约束，离散的容量分配问题（CAP）被松弛为连续**最优传输（OT）**问题。
Sinkhorn-Knopp（SK）算法：模型最小化熵正则化 OT 目标，生成满足容量约束的连续传输计划（ $\hat{Y}$ ）。该计划作为离散分配矩阵的可微代理。

4. 阶段三：OR 解码

连续传输计划 $\hat{Y}$ 引导精确混合整数规划（MIP）求解器恢复最终的离散簇。

稀疏化：模型利用置信度阈值来固定高置信度分配（硬分配）或剪枝低概率边（Sinkhorn 引导的稀疏化）。
这极大地减少了精确求解器的搜索空间，随后该求解器使用现成求解器（如 LKH-3）将剩余的子问题作为独立 TSP 求解。

主要贡献

非自回归框架：引入了首个纯 NAR 神经 CVRP 求解器，通过将问题框架化为全局划分任务，绕过了顺序解码瓶颈。
可微容量约束：开发了一种新颖的端到端可微层，利用熵正则化最优传输来强制执行车队容量约束，弥合了神经分配与精确整数规划之间的差距。
对称性抽象：提供了形式化理论保证，证明该架构在构建上内在抽象了 $E(2)$ 空间对称性、路径间排列和路径内遍历对称性，从而消除了对昂贵数据增强的需求。
空间支撑先验：证明了在固定地理上利用预训练空间词汇表可实现极致的参数效率，并实现向大规模问题规模的零样本扩展。

实验结果

该框架在恒定容量操作设置（固定地理）和标准基准（i.i.d. 坐标）上进行了评估。

零样本泛化：神经 CFRS 稳健地扩展到分布外实例，最多达 $N=1000$ 个客户。
- 在恒定容量设置（ $Q=50$ ）下，它在 30 秒内实现了 $N=1000$ 实例上 < 4% 的优化间隙。
- 值得注意的是，一个超轻量级单层架构（68.2 万参数）在此规模下仍保持约 5% 的间隙，挑战了大规模路由需要深度架构的观念。
标准基准：在标准 CVRP100 基准上，精确解码变体实现了 2.73% 的优化间隙，优于贪婪自回归基线（如 POMO、BQ、LEHD），并与经典启发式算法竞争。
效率：该方法完全消除了对后验局部搜索进行初始聚类的依赖，转而依靠神经模型引导精确求解器的能力。

意义与主张

本文认为，神经 CFRS代表了路由问题 NCO 的结构性转变：

与深度学习优势的契合：它利用深度学习学习全局上下文中的相似性和分配的能力，而不是强迫其构建长顺序路径。
现实可行性：通过尊重固定空间支撑和恒定容量，该框架与真实世界物流中摊销的、对延迟敏感的模式相一致，为静态服务区域的日常路由提供了可行路径。
范式转变：结果表明，任务特定的定制（例如在空间支撑上预训练）可以在无需大量微调的情况下产生最先进结果，并且当与正确的归纳偏置（CFRS 分解和空间先验）配对时，简单、浅层的架构可以非常有效。

作者总结道，虽然该框架表现具有竞争力，但未来的工作应专注于改进向更大实例的零样本扩展，并完善模型在边缘情况下平衡容量利用率与空间效率的能力。