RADAR: Learning to Route with Asymmetry-aware DistAnce Representations

本文提出了 RADAR 框架，通过利用奇异值分解（SVD）构建静态嵌入并采用 Sinkhorn 归一化改进注意力机制，有效解决了现有神经求解器在处理车辆路径问题（VRP）中非对称距离矩阵时泛化能力不足的问题，从而在各类 VRP 任务中实现了优于基线的性能。

要点

这篇论文介绍了一种名为 RADAR 的新方法，旨在解决一个非常实际的问题：如何帮物流公司规划出最省钱的送货路线，尤其是在路况复杂、方向不对称的情况下。

为了让你更容易理解，我们可以把这个问题想象成**“在错综复杂的单行道城市里送外卖”**。

1. 核心难题：为什么以前的方法不管用？

想象一下，你以前用的导航软件（以前的神经网络模型）非常聪明，但它有一个致命的弱点：它假设城市里的路都是“双向道”，而且去程和回程的距离是一样的。

• 现实情况是： 城市里有很多单行道。从 A 到 B 可能只要 5 分钟（顺路），但从 B 回 A 可能要绕一大圈，花 20 分钟（逆路）。
• 以前的模型： 就像是一个只看过“对称地图”的司机。当你给它一张全是单行道的真实地图（非对称距离矩阵）时，它要么完全懵了，要么给出的路线非常糟糕，因为它不懂“方向”的重要性。

2. RADAR 的两大绝招

RADAR 就像是一个**“拥有超级直觉的老司机”**，它通过两个核心技巧来适应这种复杂的单行道城市：

绝招一：SVD 初始化 —— “给每个路口贴上双向身份证”

• 以前的做法： 以前的模型在开始规划前，给每个路口（节点）发的“身份证”都是一样的，或者只是随机发的。这导致模型一开始就分不清“我是出发地”还是“我是目的地”。
• RADAR 的做法（SVD 分解）：
  • 想象你有一张巨大的城市交通网，上面密密麻麻写满了从 A 到 B、从 B 到 C 的耗时。
  • RADAR 使用一种叫**“奇异值分解 (SVD)"**的数学魔法，把这张大网“拆解”成两部分：
    1. 左半部分： 告诉模型，这个路口作为**“出发点”**时，它通向哪里最顺畅？
    2. 右半部分： 告诉模型，这个路口作为**“终点”**时，它从哪里来最方便？
  • 比喻： 就像给每个路口发了一张**“双向身份证”**。这张身份证不仅告诉你“我是谁”，还告诉你“我作为起点时有什么特点”以及“我作为终点时有什么特点”。这样，模型一开始就懂了方向感，不再是一头雾水。

绝招二：Sinkhorn 归一化 —— “让注意力更公平，不再只盯着热门路口”

• 以前的做法（Softmax）： 在规划路线时，模型会计算“下一个去哪个路口最好”。以前的算法（Softmax）就像是一个**“势利眼”**。它只关注当前路口周围的情况，容易让所有车都涌向几个“热门路口”（注意力集中在少数几个点上），而忽略了其他路口在整个城市网络中的位置。一旦这些热门路口被访问过，剩下的路就乱成一锅粥了。
• RADAR 的做法（Sinkhorn）：
  • RADAR 换用了一种叫**"Sinkhorn"的算法。这就像是一个“公平的调度员”**。
  • 它不仅看“谁想去这里”（行），还看“这里想去谁”（列）。它强制要求：如果很多车都想去路口 A，那么路口 A 也必须“回馈”给其他路口足够的关注。
  • 比喻： 想象一个派对。以前的算法只让大家都去抢着和“最红的人”说话，导致其他人被冷落。RADAR 的算法则强制大家**“雨露均沾”**，确保每个人都能听到别人的声音，也能让别人听到自己的声音。这样，模型就能看清整个城市的全局关系，而不是只盯着局部。

3. 效果如何？

RADAR 在大量的测试中（包括合成的数据和真实的城市交通数据）都表现惊人：

• 更省钱： 它规划出的路线比以前的 AI 模型更短、更省油。
• 更聪明： 即使遇到它没见过的城市规模（比如从 100 个路口突然变成 1000 个路口），它也能迅速适应，不会像以前的模型那样“死机”或乱跑。
• 更实用： 它不再需要完美的“双向地图”，只要有真实的“单行道距离表”就能工作，这让它能真正应用到现实世界的物流、外卖配送中。

总结

简单来说，RADAR 就是给 AI 司机装上了**“方向感雷达”（SVD 身份证）和“全局公平视野”**（Sinkhorn 调度）。它不再假设世界是完美的对称圆，而是学会了在充满单行道和复杂路况的真实世界里，高效、聪明地规划路线。

这就好比以前的导航仪只会走直线，而 RADAR 是一个真正懂城市交通规则的老司机，知道哪里是单行道，哪里该绕路，从而总能找到那条最省时的捷径。

技术摘要

这是一篇发表于 ICLR 2026 的论文 RADAR: LEARNING TO ROUTE WITH ASYMMETRY-AWARE DISTANCE REPRESENTATIONS（基于非对称感知距离表示的神经路由学习）的技术总结。

1. 研究背景与问题 (Problem)

车辆路径问题 (VRP) 是组合优化中的经典 NP-hard 问题。现有的神经求解器（Neural Combinatorial Optimization, NCO）在 VRP 上取得了显著进展，但存在一个关键局限性：

• 对称性假设： 大多数现有模型假设节点间距离是对称的欧几里得距离（即 $d_{ij} = d_{ji}$），通常直接输入节点坐标。
• 现实挑战： 现实世界中的交通网络往往具有非对称性（如单行道、交通拥堵、时间依赖等），导致 $d_{ij} \neq d_{ji}$。此时，仅输入坐标无法表达这种非对称关系，必须依赖成对的非对称距离矩阵作为输入。
• 现有方法的不足：
  • 静态非对称性 (Static Asymmetry)： 现有的初始化方法（如随机初始化、One-hot 编码或简单的邻居距离拼接）难以有效捕捉距离矩阵中的全局方向性结构，导致模型在大规模实例上泛化能力差。
  • 动态非对称性 (Dynamic Asymmetry)： 在编码器的注意力机制中，标准的 Softmax 仅对行（源节点）进行归一化，忽略了目标节点（列）与图中其他节点的交互关系，无法充分建模动态的方向依赖。

2. 方法论 (Methodology)

作者提出了 RADAR 框架，旨在通过两个核心组件增强现有的神经 VRP 求解器，使其能够处理非对称输入：

A. 静态非对称性：基于 SVD 的初始化 (SVD-based Embeddings)

• 核心思想： 利用奇异值分解 (SVD) 对非对称距离矩阵 $D$ 进行分解，以生成能够编码节点“出发”和“到达”角色的紧凑嵌入。
• 具体实现：
  1. 对距离矩阵 $D$ 进行截断 SVD：$D \approx U_k \Sigma_k V_k^\top$。
  2. 其中 $U_k$ 和 $V_k$ 分别对应左奇异向量和右奇异向量，$\Sigma_k$ 为奇异值对角矩阵。
  3. 构建节点特征：将 $U_k \sqrt{\Sigma_k}$（代表出发特征）和 $V_k \sqrt{\Sigma_k}$（代表到达特征）拼接，形成 $2k$ 维的初始嵌入。
  4. 理论依据： 定义了一种“非对称感知嵌入”，证明通过这种构造，模型可以通过线性变换 $W_1, W_2$ 重构出非对称的距离矩阵 $D$，从而在初始化阶段就显式地编码了全局方向性信息。
• 优势： 相比随机初始化或 One-hot 编码，SVD 初始化保留了距离矩阵的全局拓扑结构，显著提升了模型在不同规模实例上的泛化能力。

B. 动态非对称性：Sinkhorn 归一化注意力 (Sinkhorn Normalization)

• 核心思想： 替换传统的 Softmax 注意力归一化，采用 Sinkhorn 归一化，强制注意力矩阵同时满足行和列的归一化约束。
• 具体实现：
  • 在计算注意力分数 $A_{i,j}$ 时，不再仅对行 $i$ 进行 Softmax 归一化，而是通过迭代算法（Sinkhorn 算法）对矩阵的行和列进行联合归一化，使其成为双随机矩阵（Doubly Stochastic Matrix）。
• 作用：
  • 传统的 Softmax 仅关注源节点 $i$ 的局部上下文。
  • Sinkhorn 归一化使得 $A_{i,j}$ 不仅反映 $i$ 对 $j$ 的偏好，还隐含了 $j$ 在整个图中的交互结构（即 $j$ 作为目标节点时的全局接收情况）。
  • 这种机制更好地建模了非对称场景下的双向流量平衡和全局方向依赖。

3. 主要贡献 (Key Contributions)

1. 现实场景适配： 首次系统性地研究了在非对称距离矩阵输入下的神经 VRP 求解器，填补了 NCO 方法在现实非对称路由场景中的应用空白。
2. 创新初始化策略： 提出了基于 SVD 的初始化方案，能够从输入矩阵中提取全局方向关系，解决了非对称矩阵缺乏几何坐标先验的难题，显著提升了跨规模泛化性。
3. 注意力机制改进： 证明了 Sinkhorn 归一化在捕捉非对称交互中的重要性，通过联合归一化行列，增强了模型对全局距离信息的感知能力。
4. 广泛的实验验证： 在 17 种合成 VRP 变体（包括 ATSP, ACVRP 等）和 3 个真实世界数据集上进行了评估，结果一致优于现有最先进（SOTA）基线。

4. 实验结果 (Results)

• 合成数据 (ATSP & ACVRP)：
  • 在 ATSP（非对称旅行商问题）和 ACVRP（非对称带容量 VRP）上，RADAR 在训练集（N=100）和零样本泛化到更大规模（N=200, 500, 1000）时，均取得了最低的 Gap（与最优解的差距）。
  • 在 ACVRP-200 上，RADAR 甚至超越了传统启发式算法 LKH-1000。
  • 消融实验表明，SVD 初始化和 Sinkhorn 归一化各自独立且联合使用时，均能带来显著的性能提升。
• 多任务学习： 在包含 16 种不同约束的 VRP 变体的多任务设置中，RADAR 的平均 Gap 最低，证明了其强大的通用性。
• 真实世界数据： 在 RRNCO 提供的真实城市交通数据集（ATSP, ACVRP, ACVRPTW）上，RADAR 在分布内和分布外（不同城市/聚类）的测试中均表现出鲁棒性，Gap 显著低于 GCN、MatNet 和 RRNCO 等基线。
• 非对称程度分析： 随着非对称程度（噪声系数）的增加，RADAR 的性能下降幅度远小于其他基于随机或简单初始化的方法，证明了其对非对称结构的鲁棒性。
• 坐标 vs. 距离矩阵： 实验发现，在非对称任务中，RADAR 即使不使用坐标信息（仅依赖距离矩阵），其表现也优于使用坐标增强的基线模型，说明 SVD 嵌入有效捕捉了结构信息。

5. 意义与影响 (Significance)

• 理论突破： 该工作揭示了在缺乏几何坐标先验的情况下，如何通过矩阵分解（SVD）和注意力机制改进（Sinkhorn）来有效编码非对称关系，为图神经网络处理非对称图数据提供了新的范式。
• 实际应用价值： 解决了神经求解器难以直接应用于真实物流、交通规划等存在单行道和复杂路况场景的痛点，推动了 NCO 技术从实验室走向实际工业应用。
• 未来方向： 作者提出该方法可推广至其他以关系矩阵（如加工时间、兼容性矩阵）为核心的组合优化问题（如柔性作业车间调度 FFSP），并计划将其与改进启发式算法结合，进一步提升求解质量。

总结： RADAR 通过引入SVD 初始化和Sinkhorn 注意力，成功解决了神经 VRP 求解器在处理非对称距离矩阵时的泛化瓶颈，在保持高效推理的同时，实现了在大规模和真实世界非对称场景下的最优性能。