# GeoRouteNet: A Geometry-Aware Non-Autoregressive Neural Solver for the Euclidean Traveling Salesman Problem

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

## Key facts

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

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Layer Normalization](https://mlsanity.com/paper/1607.06450/) (2016)
- [GLU Variants Improve Transformer](https://mlsanity.com/paper/2002.05202/) (2020)
- [Pointer Networks](https://mlsanity.com/paper/1506.03134/) (2015)
- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [Neural Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1611.09940/) (2016)
- [POMO: Policy Optimization with Multiple Optima for Reinforcement Learning](https://mlsanity.com/paper/2010.16011/) (2020)
- [Reinforcement Learning for Solving the Vehicle Routing Problem](https://mlsanity.com/paper/1802.04240/) (2018)
- [An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem](https://mlsanity.com/paper/1906.01227/) (2019)
- [DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization](https://mlsanity.com/paper/2302.08224/) (2023)
- [DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problems](https://mlsanity.com/paper/2210.04123/) (2022)
- [Sym-NCO: Leveraging Symmetricity for Neural Combinatorial Optimization](https://mlsanity.com/paper/2205.13209/) (2022)
- [Neural Large Neighborhood Search for the Capacitated Vehicle Routing Problem](https://mlsanity.com/paper/1911.09539/) (2019)
- [Learning to Iteratively Solve Routing Problems with Dual-Aspect Collaborative Transformer](https://mlsanity.com/paper/2110.02544/) (2021)
- [Learning the Travelling Salesperson Problem Requires Rethinking Generalization](https://mlsanity.com/paper/2006.07054/) (2020)
- [An Efficient Diffusion-based Non-Autoregressive Solver for Traveling Salesman Problem](https://mlsanity.com/paper/2501.13767/) (2025)
- [LocalEscaper: A Weakly-supervised Framework with Regional Reconstruction for Scalable Neural TSP Solvers](https://mlsanity.com/paper/2502.12484/) (2025)

## Abstract (arXiv)

Non-autoregressive neural solvers amortize computation across traveling salesman problem (TSP) instances, but models trained on random Euclidean instances can degrade when the number or spatial distribution of nodes changes. We study whether explicit geometric features and a richer within-instance training signal improve transfer across graph sizes and spatial distributions. We introduce GeoRouteNet, which augments a non-autoregressive TSP solver with centered node offsets and radii, learnable radial distance bases, distance-aware graph attention, explicit edge messages, and cross-layer representation mixing. We also introduce multi-candidate self-comparison reinforcement learning (MCS-RL), which trains on several sampled tours per instance using a leave-one-out adaptive baseline, winner-candidate guidance, and annealed entropy regularization. In a single-seed study, all neural variants are trained only on random TSP-50 instances and evaluated with the same greedy and beam-search decoders. Under Beam-1000 decoding, GeoRouteNet-MCS-RL obtains gaps of 0.32% on the TSP-50 validation set used for checkpoint selection, 1.26% on a correlated TSP-100 size diagnostic, and 3.60% across 27 TSPLIB EUC_2D instances. The NAR4TSP-PG gaps on the same evaluations are 0.42%, 2.73%, and 17.12%. A 2x2 comparison crosses encoder and training choices. Under PG, the geometry-aware encoder has lower gaps than the reproduced encoder on the TSP-100 diagnostic and TSPLIB. With the geometry-aware encoder, MCS-RL is associated with a further reduction; with the reproduced encoder, it has a higher TSPLIB gap.