RELAGRAM：递归潜图模型革新车辆路径问题求解

潜递归能否用于神经网络路由？

潜递归（Latent Recursion）是一种让神经网络反复处理内部表示的技术，在解决数独、迷宫等结构化推理任务上已展现出显著效果。但一个关键问题悬而未决：这种递归机制能否支撑神经网络路由（Neural Routing）？

来自最新研究的一项工作给出了肯定答案。研究者提出了 RELAGRAM（Recursive Latent Graph Model，递归潜图模型），首次将潜递归引入图组合优化领域，专门针对带容量约束的车辆路径问题（CVRP）进行求解。

技术核心：边令牌编码与递归变换

RELAGRAM 的设计思路与传统神经组合优化方法有所不同，其核心在于将 CVRP 实例编码为边令牌（Edge Tokens）。

具体而言，模型使用一个小型 Transformer 网络，对这些边令牌的潜表示进行反复更新。每一次递归迭代都复用同一组网络参数，逐步精炼对问题结构的理解。经过多轮递归后，一个输出头（Output Head）将最终的答案状态映射为边热力图（Edge Heatmap），随后通过自回归解码器从中构造出满足容量约束的可行解。

这种"编码—递归—解码"的流程，让模型能够在紧凑的参数空间中完成复杂的组合决策。

边令牌（Edge Tokens） 是图神经网络中一种以「边」为基本处理单元的表示方式。在典型的节点中心（node-centric）图网络中，每个节点对应一个向量，边信息作为消息传递的通道。而边令牌编码将每条边 (i, j) 直接映射为一个独立的特征向量，其中可融合端点坐标、需求、距离以及容量约束等属性。对于 CVRP 而言，解本质上是一组被选中的边构成的回路，因此以边为令牌的表示与决策空间天然对齐：模型只需对每条边输出一个被选中的概率（即边热力图），再据此解码出路径。这种设计与近年来的 Edge Transformer、Anisotropic Graph Neural Network 等架构一脉相承，优点在于避免了从节点表示间接推断边决策所带来的信息损失，也让递归精炼的目标更聚焦于「边是否应出现在解中」这一核心问题。

性能表现：小模型也有竞争力

RELAGRAM 的参数量仅为 0.53M，在深度学习模型中属于极轻量级，但其在 CVRP-100 基准上的表现值得关注。

以 PyVRP 作为参考基准，RELAGRAM 在不同解码策略下的差距如下：

• 贪心解码：差距 13.4%
• 八重对称增强：差距降至 9.8%
• 256 候选搜索：差距进一步缩小至 8.3%

从贪心解码到候选搜索，性能提升超过 5 个百分点，说明潜递归产生的边热力图具备可挖掘的概率信息，能够通过搜索策略进一步释放潜力。

PyVRP 是当前车辆路径问题领域广泛使用的开源求解器，基于 HGS（Hybrid Genetic Search）等元启发式算法，并在多项 CVRP 基准上取得接近最优的求解质量，因此常被用作神经组合优化方法的强基线。所谓「差距 X%」，通常指模型解与 PyVRP 解（或已知最优解）之间的相对间隙，计算公式为 (模型成本 − 基线成本) / 基线成本。需要指出的是，神经方法往往以单次前向推理或有限候选搜索达到该差距，而 PyVRP 通常需要数十秒乃至更长的求解时间，二者的速度-质量权衡并不对等。贪心解码指在每一步直接选择概率最高的边，不进行回溯；八重对称增强利用 CVRP 解在旋转、翻转等八种对称变换下等价的性质，对同一实例做多次前向并合并结果；候选搜索则从边热力图中采样多条候选路径并按成本择优。解码策略越强，越能挖掘热力图中蕴含的概率信息。

零样本泛化：从100到1000的跨规模迁移

组合优化模型的一个常见挑战是泛化能力——在固定规模上训练的模型能否处理更大规模的问题？

RELAGRAM 在这一点上表现突出。模型仅在 CVRP-100 上训练，却能零样本（Zero-shot）泛化到 CVRP-500 和 CVRP-1000：

• CVRP-500：256 候选搜索下差距 15.6%
• CVRP-1000：256 候选搜索下差距 21.7%

随着问题规模从 100 扩大到 1000，性能差距从 8.3% 逐渐增至 21.7%，退化幅度在可接受范围内。这种跨规模泛化能力表明，潜递归学到的不是对特定问题规模的记忆，而是某种可迁移的结构化推理模式。

零样本泛化（Zero-shot Generalization） 在组合优化语境下指模型在某一规模（如节点数 100）上训练后，未经任何微调或再训练，直接推理更大规模实例（如 500、1000 个节点）。这与传统神经组合优化方法形成鲜明对比——许多模型在小规模上训练后，一旦规模改变，性能会急剧下降，因为模型可能隐式地依赖了固定维度的输入或特定规模的统计规律。RELAGRAM 能实现跨规模迁移，关键在于其边令牌编码不绑定节点总数，递归 Transformer 的参数量也与实例规模无关，使得结构化的推理模式（如「优先服务距离近且需求高的节点」）可以在不同规模间复用。需要注意的是，规模增大时候选搜索空间膨胀，单次递归能覆盖的结构信息相对稀释，这正是差距从 8.3% 单调增至 21.7% 的主要原因。

潜递归为何适合路由问题？

路由问题的本质是在离散的图结构上做序贯决策，每一步选择都影响后续可行性。RELAGRAM 的潜递归机制恰好契合这一特性：

反复精炼——每次递归迭代都在更新对当前问题状态的表示，类似于人类求解路径问题时反复审视地图、调整方案的过程。

参数共享——同一个 Transformer 网络被反复调用，使得模型在参数量受限的情况下仍能进行多步推理，避免了堆叠深层网络带来的参数膨胀。

结构感知——以边为令牌的编码方式天然保留了图的拓扑信息，边热力图则直接对应"哪些边应该被选中"的决策信号。

研究者总结认为，这些结果共同证明潜递归是神经网络路由的一条有前景的技术路线。对于需要实时求解或部署在资源受限环境中的车辆路径应用而言，一个 0.53M 参数、支持零样本跨规模泛化的模型，提供了不同于传统启发式算法和大型神经求解器的新选择。

局限与展望

RELAGRAM 当前在 CVRP-1000 上的 21.7% 差距仍然较大，距离实用部署还有距离。候选搜索数量从 8 倍对称增强提升到 256 候选后收益明显，但计算开销也随之增加，如何在推理效率和解质量之间取得平衡，是后续研究需要解答的问题。

此外，该工作目前仅在 CVRP 上验证，潜递归能否同样有效地处理带时间窗的 VRPTW、取送货问题（PDP）等更复杂的路由变体，尚待进一步探索。