通过相对位置编码对距离进行编码以增强基于Transformer的路由

# 通过相对位置编码编码距离来增强基于Transformer的路径规划

来源：https://arxiv.org/html/2607.18909
[![[无标题图像]](https://arxiv.org/html/2607.18909v1/x1.png)Leyre Encío](https://orcid.org/0000-0002-5534-3487)[![[无标题图像]](https://arxiv.org/html/2607.18909v1/x2.png)Daniel Fuertes](https://orcid.org/0000-0002-5746-2199)[![[无标题图像]](https://arxiv.org/html/2607.18909v1/x3.png)Carlos R. del-Blanco](https://orcid.org/0000-0003-0618-3488)[![[无标题图像]](https://arxiv.org/html/2607.18909v1/x4.png)Fernando Jaureguizar](https://orcid.org/0000-0001-6449-5151) 图像处理小组，信息处理与电信中心，ETSITelecomunicación，马德里理工大学，28040，马德里，西班牙 \{leyre.encio, d.fcoiras, carlosrob.delblanco, fernando.jaureguizar\}@upm.es

###### 摘要

本文探讨了将相对位置编码（RPE）作为Transformer架构中的加性偏置来解决团队定向问题。通过将表示路径规划问题的图中节点间的成对空间关系嵌入到注意力机制中，Transformer编码器可以计算出更丰富的空间感知图嵌入，从而使解码器能够估算出更好的路径。涉及多达100个节点的实例的实验结果表明，与其它最先进工作中使用的普通Transformer架构相比，在收集奖励和最优性差距方面均有持续改进。这些发现表明，显式的关系建模显著增强了复杂组合优化的可扩展性和泛化能力。

*关键词*车辆路径问题⋅\cdot深度强化学习⋅\cdot相对位置编码⋅\cdot图Transformer网络

## 1 引言

车辆路径问题（VRPs）是神经组合优化（NCO）中的一个重要研究领域，其中一组代理需要在操作约束下访问一个节点序列，同时优化给定目标。这些问题本质上被结构化为节点图，并且通常是NP难的，这使得在大规模下精确求解具有挑战性。因此，人们对能够利用问题结构并跨实例泛化的基于学习的方法越来越感兴趣。

由Vaswani等人（2017）提出的Transformer架构，因其依赖自注意力机制而非循环（Gama and L. Fernandes，2021）或卷积（Qi等人，2024）而成为序列建模的主要范式。原始的Transformer将注意力计算为缩放点积（Vaswani等人，2017），后来扩展到诸如稀疏（Child等人，2019）、关系感知（Ji等人，2020）和线性（Choromanski等人，2021）注意力机制等变体。其中，关系感知自注意力（Shaw等人，2018）引入了成对位置项，提高了性能并实现了超越序列的泛化。

参照图注图1：作为归纳偏置的RPE示例自注意力能够通过并行计算建模长程依赖关系，但本质上是置换不变的，因此需要显式的位置信息来编码结构。早期的Transformer采用绝对位置编码，通常是正弦或学习到的嵌入，这些被添加到输入表示中。虽然在自然语言处理中有效，但这些编码强加了刚性的位置概念，可能无法很好地泛化到诸如VRP之类的基于图的问题。为了解决这一限制，引入了相对位置编码（RPE），其中注意力分数依赖于元素之间的成对关系而非绝对索引（Shaw等人，2018）。位置编码方法可以分为：绝对编码（Devlin等人，2019），它注入顺序但不注入关系；相对编码（Dai等人，2019），它对应用于输入嵌入的成对距离进行建模；以及加性注意力偏置公式（Chen等人，2021；Yang等人，2025），其中位置信息直接添加到多头注意力logits中，允许模型基于相对距离调整注意力权重，这提高了效率和可扩展性。

Transformer已通过深度强化学习（DRL）成功应用于VRPs（Kool等人，2019；Fuertes等人，2025；Tang等人，2026），使用对节点嵌入的注意力。然而，许多方法依赖隐式距离编码（绝对位置信息），而不是显式地建模成对关系（Guan等人，2025），后者仍未得到充分探索。

在这项工作中，我们探索使用RPE作为Transformer架构中的加性偏置来解决团队定向问题（TOP）（I-Ming等人，1996）。通过将关系结构显式嵌入到注意力机制中，我们旨在提高与标准隐式距离编码相比的泛化能力和解决方案质量（见图1）。

## 2 系统描述

在这项工作中，我们考虑了TOP，它定义了一个完全图G = (V, E)，其中每个节点关联一个奖励和成对距离。其目标是在预算约束下构建一组路径，最大化总收集奖励。为了解决这个问题，我们采用了一种基于注意力的编码器-解码器架构，其中节点特征首先嵌入到潜在空间中，然后由一堆Transformer层处理以捕获全局依赖关系。然后，解码器通过关注编码后的节点表示来顺序地构建可行解，遵循标准的自回归路径规划范式。

所提出RPE的核心组件是一个修改后的多头自注意力机制，它显式地整合了关系信息。在标准公式中，注意力权重计算如下：

Attention(Q, K, V) = SoftMax(QK^T / √d_k) V  (1)

这并没有显式地考虑成对空间结构。为了解决这一限制，我们引入了一个RPE项作为注意力logits中的加性偏置：

Attention(Q, K, V) = SoftMax(QK^T / √d_k + B) V  (2)

我们使用距离信息构建了B ∈ R^(n×n)，其中n是节点数量，以捕获问题的互补几何特性。具体来说，我们考虑了节点坐标之间的欧氏距离、曼哈顿距离、切比雪夫距离和余弦相似度，以产生一个统一的偏置项，使模型能够在注意力机制内自适应地利用不同邻近度和方向性概念。由此产生的架构在保留置换不变性的同时，引入了与VRP图结构一致的强归纳偏置。此外，由于偏置直接添加到注意力logits中，所提出的RPE保持了标准Transformer的计算效率和可扩展性。

在解码过程中，模型基于从注意力机制导出的概率分布顺序地选择下一个节点来构建解。在每个步骤中，不可行动作（如重新访问节点或违反预算约束）会被屏蔽以确保有效解。用所提出的偏置项B增强的注意力分数通过优先考虑在潜在空间中相关且在空间关系方面有利的节点来指导选择过程。这种整合允许模型共同推理奖励、可行性和基于距离的结构，从而更有效地探索解空间。

## 3 结果

表1：TOP方法在平均收集奖励和差距百分比方面的比较（最佳以粗体显示）。表1报告了所提出的RPE在TOP上的性能，包括平均收集奖励和最优性差距。比较包括优化求解器Gurobi（Gurobi Optimization, LLC，2024）和元启发式求解器蚁群优化（ACO）（Xiao等人，2022）。需要注意的是，由于Gurobi生成解所需时间过长，已为每个实例设置了60秒的超时时间。所有基于学习的模型每epoch在1280000个实例上进行训练，总计100个epoch。所有实验的超参数保持一致，以确保公平比较。

结果显示，将相对位置信息作为加性注意力偏置整合，在所有问题规模上持续改善了普通Transformer基线、Gurobi和ACO的指标。这证实了显式建模成对关系能导致更有效的解构建。对于较小实例（n=20），问题复杂度较低，基线方法已能获得接近最优的解，改进相对较小。然而，随着问题规模增大（n=50和n=100），所提出方法的好处变得更加明显。在这些设置下，整合了RPE的模型获得了更高的奖励和更低的最优性差距，表明其能更好地捕获问题的底层结构并做出更明智的决策。

总体而言，结果表明关键因素不是所使用的具体距离度量，而是将相对位置信息显式整合到注意力机制中。通过提供对成对关系的直接访问，模型受益于更强的归纳偏置，从而在更大且更具挑战性的场景中带来改进的泛化能力和可扩展性。

## 4 结论

总之，将相对位置信息作为加性注意力偏置整合显著增强了基于Transformer的TOP求解器。结果表明，RPE方法提供了优越的归纳偏置，随着问题复杂性的增长提高了性能和可扩展性。通过在注意力logits中显式建模成对距离，架构获得了对问题空间表示的更深层次理解，使模型能够预测更有效和优化的路径。这项工作强调，改进基于学习的路径规划模型的关键在于显式地整合关系结构。最终，所提出的RPE为解决基于图的NCO问题提供了一个稳健、可扩展的框架。

## 5 致谢

这项工作部分得到了马德里自治区在项目TEC-2024/COM-322 (IDEALCVCM) 下的支持，部分得到了西班牙政府MCIU/AEI/10.13039/501100011033在项目PID2023148922OA-I00 (EEVOCATIONS) 下的支持，以及部分得到了“ETSIT-UPM教学研究人员研究资助 (2026)”在项目“SATURNO”下的支持。作者还要感谢Airbus Defence and Space的支持。

## 参考文献

- [1] (2021) A simple and effective positional encoding for transformers. In Proceedings of the 2021 conference on empirical methods in natural language processing, pp. 2974–2988. Cited by: §1.
- [2] R. Child, S. Gray, A. Radford, and I. Sutskever (2019) Generating long sequences with sparse transformers. arXiv preprint arXiv:1904.10509. Cited by: §1.
- [3] K. M. Choromanski, V. Likhosherstov, D. Dohan, X. Song, A. Gane, T. Sarlos, P. Hawkins, J. Q. Davis, A. Mohiuddin, L. Kaiser, D. B. Belanger, L. J. Colwell, and A. Weller (2021) Rethinking attention with performers. In International Conference on Learning Representations, Cited by: §1.
- [4] Z. Dai, Z. Yang, Y. Yang, J. G. Carbonell, Q. Le, and R. Salakhutdinov (2019) Transformer-xl: attentive language models beyond a fixed-length context. In Proceedings of the 57th annual meeting of the association for computational linguistics, pp. 2978–2988. Cited by: §1.
- [5] J. Devlin, M. Chang, K. Lee, and K. Toutanova (2019) Bert: pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 conference of the North American chapter of the association for computational linguistics: human language technologies, volume 1 (long and short papers), pp. 4171–4186. Cited by: §1.
- [6] D. Fuertes, C. R. del-Blanco, F. Jaureguizar, and N. García (2025) TOP-former: a multi-agent transformer approach for the team orienteering problem. IEEE Transactions on Intelligent Transportation Systems 26 (9), pp. 13799–13810. External Links: Document Cited by: §1.
- [7] R. Gama and H. L. Fernandes (2021) A reinforcement learning approach to the orienteering problem with time windows. Computers & Operations Research 133, pp. 105357. External Links: ISSN 0305-0548, Document Cited by: §1.
- [8] Q. Guan, H. Cao, L. Jia, D. Yan, and B. Chen (2025) Synergetic attention-driven transformer: a deep reinforcement learning approach for vehicle routing problems. Expert Systems with Applications 274, pp. 126961. Cited by: §1.
- [9] Gurobi Optimization, LLC (2024) Gurobi Optimizer Reference Manual. Note: https://www.gurobi.com/ Cited by: §3.
- [10] C. I-Ming, B. Golden, and E. Wasil (1996) The team orienteering problem. European Journal of Operational Research 88 (3), pp. 464–474. Cited by: §1.
- [11] M. Ji, W. Joo, K. Song, Y. Kim, and I. Moon (2020) Sequential recommendation with relation-aware kernelized self-attention. In Proceedings of the AAAI conference on artificial intelligence, Vol. 34, pp. 4304–4311. Cited by: §1.
- [12] W. Kool, H. van Hoof, and M. Welling (2019) Attention, learn to solve routing problems!. In International Conference on Learning Representations, Cited by: §1.
- [13] D. Qi, Y. Zhao, Z. Wang, W. Wang, L. Pi, and L. Li (2024) Joint approach for vehicle routing problems based on genetic algorithm and graph convolutional network. Mathematics 12 (19). External Links: ISSN 2227-7390, Document Cited by: §1.