# The Transformer Network for the Traveling Salesman Problem

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

## Key facts

- Cited by 59 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 43 references that are in the map.
- First posted on arXiv 4 Mar 2021.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Neural Machine Translation by Jointly Learning to Align and Translate](https://mlsanity.com/paper/1409.0473/) (2014)
- [Playing Atari with Deep Reinforcement Learning](https://mlsanity.com/paper/1312.5602/) (2013)
- [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)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [Reinforcement Learning for Solving the Vehicle Routing Problem](https://mlsanity.com/paper/1802.04240/) (2018)
- [Exact Combinatorial Optimization with Graph Convolutional Neural Networks](https://mlsanity.com/paper/1906.01629/) (2019)
- [Diverse Beam Search: Decoding Diverse Solutions from Neural Sequence Models](https://mlsanity.com/paper/1610.02424/) (2016)
- [An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem](https://mlsanity.com/paper/1906.01227/) (2019)
- [Solving Mixed Integer Programs Using Neural Networks](https://mlsanity.com/paper/2012.13349/) (2020)
- [Learning Improvement Heuristics for Solving Routing Problems](https://mlsanity.com/paper/1912.05784/) (2019)
- [Best-First Beam Search](https://mlsanity.com/paper/2007.03909/) (2020)
- [Revised Note on Learning Algorithms for Quadratic Assignment with Graph Neural Networks](https://mlsanity.com/paper/1706.07450/) (2017)
- [Learning the Multiple Traveling Salesmen Problem with Permutation Invariant Pooling Networks](https://mlsanity.com/paper/1803.09621/) (2018)

## Built on by (most cited first, 30 of 59)

- [Diffusion models as plug-and-play priors](https://mlsanity.com/paper/2206.09012/) (2022)
- [DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization](https://mlsanity.com/paper/2302.08224/) (2023)
- [GLOP: Learning Global Partition and Local Construction for Solving Large-scale Routing Problems in Real-time](https://mlsanity.com/paper/2312.08224/) (2023)
- [BQ-NCO: Bisimulation Quotienting for Efficient Neural Combinatorial Optimization](https://mlsanity.com/paper/2301.03313/) (2023)
- [DeepACO: Neural-enhanced Ant Systems for Combinatorial Optimization](https://mlsanity.com/paper/2309.14032/) (2023)
- [Fast T2T: Optimization Consistency Speeds Up Diffusion-Based Training-to-Testing Solving for Combinatorial Optimization](https://mlsanity.com/paper/2502.02941/) (2025)
- [Generalization of Neural Combinatorial Solvers Through the Lens of Adversarial Robustness](https://mlsanity.com/paper/2110.10942/) (2021)
- [Towards Better Out-of-Distribution Generalization of Neural Algorithmic Reasoning Tasks](https://mlsanity.com/paper/2211.00692/) (2022)
- [Learning to Solve Travelling Salesman Problem with Hardness-adaptive Curriculum](https://mlsanity.com/paper/2204.03236/) (2022)
- [Neural Combinatorial Optimization Algorithms for Solving Vehicle Routing Problems: A Comprehensive Survey with Perspectives](https://mlsanity.com/paper/2406.00415/) (2024)
- [Distilling Autoregressive Models to Obtain High-Performance Non-Autoregressive Solvers for Vehicle Routing Problems with Faster Inference Speed](https://mlsanity.com/paper/2312.12469/) (2023)
- [Reducing Collision Checking for Sampling-Based Motion Planning Using Graph Neural Networks](https://mlsanity.com/paper/2210.08864/) (2022)
- [Distance-aware Attention Reshaping: Enhance Generalization of Neural Solver for Large-scale Vehicle Routing Problems](https://mlsanity.com/paper/2401.06979/) (2024)
- [Learning to Solve Combinatorial Graph Partitioning Problems via Efficient Exploration](https://mlsanity.com/paper/2205.14105/) (2022)
- [DISCO: Efficient Diffusion Solver for Large-Scale Combinatorial Optimization Problems](https://mlsanity.com/paper/2406.19705/) (2024)
- [GAReT: Cross-view Video Geolocalization with Adapters and Auto-Regressive Transformers](https://mlsanity.com/paper/2408.02840/) (2024)
- [An Efficient Diffusion-based Non-Autoregressive Solver for Traveling Salesman Problem](https://mlsanity.com/paper/2501.13767/) (2025)
- [Combining Reinforcement Learning and Optimal Transport for the Traveling Salesman Problem](https://mlsanity.com/paper/2203.00903/) (2022)
- [Learning for routing: A guided review of recent developments and future directions](https://mlsanity.com/paper/2507.00218/) (2025)
- [G-LNS: Generative Large Neighborhood Search for LLM-Based Automatic Heuristic Design](https://mlsanity.com/paper/2602.08253/) (2026)
- [Supplementing Recurrent Neural Networks with Annealing to Solve Combinatorial Optimization Problems](https://mlsanity.com/paper/2207.08189/) (2022)
- [UAV Trajectory Planning for AoI-Minimal Data Collection in UAV-Aided IoT Networks by Transformer](https://mlsanity.com/paper/2401.02425/) (2023)
- [SymmetricDiffusers: Learning Discrete Diffusion on Finite Symmetric Groups](https://mlsanity.com/paper/2410.02942/) (2024)
- [Reinforcement Learning-based Non-Autoregressive Solver for Traveling Salesman Problems](https://mlsanity.com/paper/2308.00560/) (2023)
- [Hybrid Pointer Networks for Traveling Salesman Problems Optimization](https://mlsanity.com/paper/2110.03104/) (2021)
- [Learning from Drivers to Tackle the Amazon Last Mile Routing Research Challenge](https://mlsanity.com/paper/2205.04001/) (2022)
- [A Lightweight CNN-Transformer Model for Learning Traveling Salesman Problems](https://mlsanity.com/paper/2305.01883/) (2023)
- [Learning to Untangle Genome Assembly with Graph Convolutional Networks](https://mlsanity.com/paper/2206.00668/) (2022)
- [Lattice Protein Folding with Variational Annealing](https://mlsanity.com/paper/2502.20632/) (2025)
- [Neural Simulated Annealing](https://mlsanity.com/paper/2203.02201/) (2022)

## Abstract (arXiv)

The Traveling Salesman Problem (TSP) is the most popular and most studied combinatorial problem, starting with von Neumann in 1951. It has driven the discovery of several optimization techniques such as cutting planes, branch-and-bound, local search, Lagrangian relaxation, and simulated annealing. The last five years have seen the emergence of promising techniques where (graph) neural networks have been capable to learn new combinatorial algorithms. The main question is whether deep learning can learn better heuristics from data, i.e. replacing human-engineered heuristics? This is appealing because developing algorithms to tackle efficiently NP-hard problems may require years of research, and many industry problems are combinatorial by nature. In this work, we propose to adapt the recent successful Transformer architecture originally developed for natural language processing to the combinatorial TSP. Training is done by reinforcement learning, hence without TSP training solutions, and decoding uses beam search. We report improved performances over recent learned heuristics with an optimal gap of 0.004% for TSP50 and 0.39% for TSP100.