# On Learning Paradigms for the Travelling Salesman Problem

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

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Oct 2019.

## Built on by (most cited first, 24 of 24)

- [DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problems](https://mlsanity.com/paper/2210.04123/) (2022)
- [Deep Policy Dynamic Programming for Vehicle Routing Problems](https://mlsanity.com/paper/2102.11756/) (2021)
- [Unsupervised Learning for Solving the Travelling Salesman Problem](https://mlsanity.com/paper/2303.10538/) (2023)
- [Learning to Solve Travelling Salesman Problem with Hardness-adaptive Curriculum](https://mlsanity.com/paper/2204.03236/) (2022)
- [On the Generalization of Neural Combinatorial Optimization Heuristics](https://mlsanity.com/paper/2206.00787/) (2022)
- [Neural Combinatorial Optimization Algorithms for Solving Vehicle Routing Problems: A Comprehensive Survey with Perspectives](https://mlsanity.com/paper/2406.00415/) (2024)
- [Analytics and Machine Learning in Vehicle Routing Research](https://mlsanity.com/paper/2102.10012/) (2021)
- [An Overview and Experimental Study of Learning-based Optimization Algorithms for Vehicle Routing Problem](https://mlsanity.com/paper/2107.07076/) (2021)
- [Learning to Solve Vehicle Routing Problems: A Survey](https://mlsanity.com/paper/2205.02453/) (2022)
- [Deep Reinforcement Learning for Combinatorial Optimization: Covering Salesman Problems](https://mlsanity.com/paper/2102.05875/) (2021)
- [Curriculum Design for Teaching via Demonstrations: Theory and Applications](https://mlsanity.com/paper/2106.04696/) (2021)
- [Generalization in Deep RL for TSP Problems via Equivariance and Local Search](https://mlsanity.com/paper/2110.03595/) (2021)
- [Unsupervised Training for Neural TSP Solver](https://mlsanity.com/paper/2207.13667/) (2022)
- [Maximizing Influence with Graph Neural Networks](https://mlsanity.com/paper/2108.04623/) (2021)
- [Improving Generalization of Deep Reinforcement Learning-based TSP Solvers](https://mlsanity.com/paper/2110.02843/) (2021)
- [Learning to Untangle Genome Assembly with Graph Convolutional Networks](https://mlsanity.com/paper/2206.00668/) (2022)
- [End-to-End Pareto Set Prediction with Graph Neural Networks for Multi-objective Facility Location](https://mlsanity.com/paper/2210.15220/) (2022)
- [Predicting Drivers' Route Trajectories in Last-Mile Delivery Using A Pair-wise Attention-based Pointer Neural Network](https://mlsanity.com/paper/2301.03802/) (2023)
- [Mechanistic Interpretability for Neural TSP Solvers](https://mlsanity.com/paper/2510.21693/) (2025)
- [Neural Simulated Annealing](https://mlsanity.com/paper/2203.02201/) (2022)
- [Multi-Start Team Orienteering Problem for UAS Mission Re-Planning with Data-Efficient Deep Reinforcement Learning](https://mlsanity.com/paper/2303.01963/) (2023)
- [Pivoting Retail Supply Chain with Deep Generative Techniques: Taxonomy, Survey and Insights](https://mlsanity.com/paper/2403.00861/) (2024)
- [SEAFormer: A Spatial Proximity and Edge-Aware Transformer for Real-World Vehicle Routing Problems](https://mlsanity.com/paper/2601.19395/) (2026)
- [Offline Decision Transformers for Neural Combinatorial Optimization: Surpassing Heuristics on the Traveling Salesman Problem](https://mlsanity.com/paper/2603.25241/) (2026)

## Abstract (arXiv)

We explore the impact of learning paradigms on training deep neural networks for the Travelling Salesman Problem. We design controlled experiments to train supervised learning (SL) and reinforcement learning (RL) models on fixed graph sizes up to 100 nodes, and evaluate them on variable sized graphs up to 500 nodes. Beyond not needing labelled data, our results reveal favorable properties of RL over SL: RL training leads to better emergent generalization to variable graph sizes and is a key component for learning scale-invariant solvers for novel combinatorial problems.