# Rethinking Positional Encoding for Neural Vehicle Routing

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

## Key facts

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

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [RoFormer: Enhanced Transformer with Rotary Position Embedding](https://mlsanity.com/paper/2104.09864/) (2021)
- [Self-Attention with Relative Position Representations](https://mlsanity.com/paper/1803.02155/) (2018)
- [Train Short, Test Long: Attention with Linear Biases Enables Input Length Extrapolation](https://mlsanity.com/paper/2108.12409/) (2021)
- [A Generalization of Transformer Networks to Graphs](https://mlsanity.com/paper/2012.09699/) (2020)
- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [Convolutional Sequence to Sequence Learning](https://mlsanity.com/paper/1705.03122/) (2017)
- [POMO: Policy Optimization with Multiple Optima for Reinforcement Learning](https://mlsanity.com/paper/2010.16011/) (2020)
- [Graph Neural Networks with Learnable Structural and Positional Representations](https://mlsanity.com/paper/2110.07875/) (2021)
- [Neural Combinatorial Optimization with Heavy Decoder: Toward Large Scale Generalization](https://mlsanity.com/paper/2310.07985/) (2023)
- [Hybrid Genetic Search for the CVRP: Open-Source Implementation and SWAP* Neighborhood](https://mlsanity.com/paper/2012.10384/) (2020)
- [Learning to Iteratively Solve Routing Problems with Dual-Aspect Collaborative Transformer](https://mlsanity.com/paper/2110.02544/) (2021)
- [BQ-NCO: Bisimulation Quotienting for Efficient Neural Combinatorial Optimization](https://mlsanity.com/paper/2301.03313/) (2023)
- [Winner Takes It All: Training Performant RL Populations for Combinatorial Optimization](https://mlsanity.com/paper/2210.03475/) (2022)
- [PyVRP: a high-performance VRP solver package](https://mlsanity.com/paper/2403.13795/) (2023)
- [PolyNet: Learning Diverse Solution Strategies for Neural Combinatorial Optimization](https://mlsanity.com/paper/2402.14048/) (2024)
- [Efficient Neural Neighborhood Search for Pickup and Delivery Problems](https://mlsanity.com/paper/2204.11399/) (2022)
- [Neural Deconstruction Search for Vehicle Routing Problems](https://mlsanity.com/paper/2501.03715/) (2025)

## Abstract (arXiv)

Transformer-based models have become the dominant paradigm for neural combinatorial optimization (NCO) of vehicle routing problems (VRPs), yet the role of positional encoding (PE) in these architectures remains largely unexplored. Unlike natural language, where tokens are uniformly spaced on a line, routing solutions exhibit several properties that render standard NLP positional encodings inadequate. In this work, we formalize three such structural properties that a routing-aware PE should respect, namely anisometric node distances, cyclic and direction-aware topology, and hierarchical depot-anchored global multi-route structure, combining them with a unifying design principle of geometric grounding. Guided by these criteria, we analyze and compare PE methods spanning NLP, graph-transformer, and routing-specific families, and propose a hierarchical anisometric PE that combines a distance-indexed, circularly consistent in-route encoding with a depot-anchored angular cross-route encoding. Extensive experiments across diverse VRP variants demonstrate that geometry-grounded PE consistently outperforms index-based alternatives, with gains that transfer across problem variants, model architectures, and distribution shifts.