# Enhancing Transformer-based Routing by Encoding Distance via Relative Positional Encoding

arXiv: https://arxiv.org/abs/2607.18909 · HTML: https://mlsanity.com/paper/2607.18909/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 18 references that are in the map.
- First posted on arXiv 21 Jul 2026.

## Builds on (most cited first, 12 of 12)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Transformer-XL: Attentive Language Models Beyond a Fixed-Length Context](https://mlsanity.com/paper/1901.02860/) (2019)
- [Rethinking Attention with Performers](https://mlsanity.com/paper/2009.14794/) (2020)
- [Generating Long Sequences with Sparse Transformers](https://mlsanity.com/paper/1904.10509/) (2019)
- [Self-Attention with Relative Position Representations](https://mlsanity.com/paper/1803.02155/) (2018)
- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [A Simple and Effective Positional Encoding for Transformers](https://mlsanity.com/paper/2104.08698/) (2021)
- [A Reinforcement Learning Approach to the Orienteering Problem with Time Windows](https://mlsanity.com/paper/2011.03647/) (2020)
- [A Benchmark for Multi-UAV Task Assignment of an Extended Team Orienteering Problem](https://mlsanity.com/paper/2009.00363/) (2020)
- [Sequential Recommendation with Relation-Aware Kernelized Self-Attention](https://mlsanity.com/paper/1911.06478/) (2019)
- [TOP-Former: A Multi-Agent Transformer Approach for the Team Orienteering Problem](https://mlsanity.com/paper/2311.18662/) (2023)

## Abstract (arXiv)

This paper explores Relative Positional Encoding (RPE) as an additive bias in Transformer architectures to solve the Team Orienteering Problem. By embedding in the attention mechanism pairwise spatial relationships among nodes of the graph that represents the routing problem, the transformer encoder can compute a richer spatial-aware graph embedding that allows the decoder to estimate better routes. Experimental results involving instances up to 100 nodes demonstrate consistent improvements in collected rewards and optimality gaps over vanilla Transformer architectures used by other state-of-the-art works. These findings highlight that explicit relational modeling significantly enhances scalability and generalization for complex combinatorial optimization.