# Learning to Solve Travelling Salesman Problem with Hardness-adaptive Curriculum

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

## Key facts

- Cited by 27 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 37 references that are in the map.
- First posted on arXiv 7 Apr 2022.

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

- [Generative Modeling by Estimating Gradients of the Data Distribution](https://mlsanity.com/paper/1907.05600/) (2019)
- [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)
- [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)
- [On The Power of Curriculum Learning in Training Deep Networks](https://mlsanity.com/paper/1904.03626/) (2019)
- [How to Train Your Energy-Based Models](https://mlsanity.com/paper/2101.03288/) (2021)
- [An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem](https://mlsanity.com/paper/1906.01227/) (2019)
- [Competence-based Curriculum Learning for Neural Machine Translation](https://mlsanity.com/paper/1903.09848/) (2019)
- [Reverse Curriculum Generation for Reinforcement Learning](https://mlsanity.com/paper/1707.05300/) (2017)
- [Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instances](https://mlsanity.com/paper/2012.10658/) (2020)
- [Automatic Curriculum Learning For Deep RL: A Short Survey](https://mlsanity.com/paper/2003.04664/) (2020)
- [CurriculumNet: Weakly Supervised Learning from Large-Scale Web Images](https://mlsanity.com/paper/1808.01097/) (2018)
- [STC: A Simple to Complex Framework for Weakly-supervised Semantic Segmentation](https://mlsanity.com/paper/1509.03150/) (2015)
- [Combinatorial Optimization by Graph Pointer Networks and Hierarchical Reinforcement Learning](https://mlsanity.com/paper/1911.04936/) (2019)
- [The Transformer Network for the Traveling Salesman Problem](https://mlsanity.com/paper/2103.03012/) (2021)
- [How hard can it be? Estimating the difficulty of visual search in an image](https://mlsanity.com/paper/1705.08280/) (2017)
- [On Learning Paradigms for the Travelling Salesman Problem](https://mlsanity.com/paper/1910.07210/) (2019)
- [Image Difficulty Curriculum for Generative Adversarial Networks (CuGAN)](https://mlsanity.com/paper/1910.08967/) (2019)
- [Evaluating Curriculum Learning Strategies in Neural Combinatorial Optimization](https://mlsanity.com/paper/2011.06188/) (2020)

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

- [GLOP: Learning Global Partition and Local Construction for Solving Large-scale Routing Problems in Real-time](https://mlsanity.com/paper/2312.08224/) (2023)
- [MVMoE: Multi-Task Vehicle Routing Solver with Mixture-of-Experts](https://mlsanity.com/paper/2405.01029/) (2024)
- [Towards Omni-generalizable Neural Methods for Vehicle Routing Problems](https://mlsanity.com/paper/2305.19587/) (2023)
- [Learning Generalizable Models for Vehicle Routing Problems via Knowledge Distillation](https://mlsanity.com/paper/2210.07686/) (2022)
- [LLM4DyG: Can Large Language Models Solve Spatial-Temporal Problems on Dynamic Graphs?](https://mlsanity.com/paper/2310.17110/) (2023)
- [Learning to Handle Complex Constraints for Vehicle Routing Problems](https://mlsanity.com/paper/2410.21066/) (2024)
- [ASP: Learn a Universal Neural Solver!](https://mlsanity.com/paper/2303.00466/) (2023)
- [Dynamic Mixture of Curriculum LoRA Experts for Continual Multimodal Instruction Tuning](https://mlsanity.com/paper/2506.11672/) (2025)
- [Neural Combinatorial Optimization Algorithms for Solving Vehicle Routing Problems: A Comprehensive Survey with Perspectives](https://mlsanity.com/paper/2406.00415/) (2024)
- [Data-centric Graph Learning: A Survey](https://mlsanity.com/paper/2310.04987/) (2023)
- [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)
- [Spectral Invariant Learning for Dynamic Graphs under Distribution Shifts](https://mlsanity.com/paper/2403.05026/) (2024)
- [Curriculum Graph Machine Learning: A Survey](https://mlsanity.com/paper/2302.02926/) (2023)
- [Promoting Generalization for Exact Solvers via Adversarial Instance Augmentation](https://mlsanity.com/paper/2310.14161/) (2023)
- [Collaboration! Towards Robust Neural Methods for Routing Problems](https://mlsanity.com/paper/2410.04968/) (2024)
- [Out-of-Distribution Generalized Dynamic Graph Neural Network for Human Albumin Prediction](https://mlsanity.com/paper/2311.15545/) (2023)
- [Unsupervised Graph Neural Architecture Search with Disentangled Self-supervision](https://mlsanity.com/paper/2403.05064/) (2024)
- [Towards Efficient Constraint Handling in Neural Solvers for Routing Problems](https://mlsanity.com/paper/2602.16012/) (2026)
- [Lifelong Learner: Discovering Versatile Neural Solvers for Vehicle Routing Problems](https://mlsanity.com/paper/2508.11679/) (2025)
- [Game-Theoretic Co-Evolution for LLM-Based Heuristic Discovery](https://mlsanity.com/paper/2601.22896/) (2026)
- [Empowering Targeted Neighborhood Search via Hyper Tour for Large-Scale TSP](https://mlsanity.com/paper/2510.20169/) (2025)
- [A Curriculum-Based Deep Reinforcement Learning Framework for the Electric Vehicle Routing Problem](https://mlsanity.com/paper/2601.15038/) (2026)
- [LRM-1B: Towards Large Routing Model](https://mlsanity.com/paper/2507.03300/) (2025)
- [On Distributional Dependent Performance of Classical and Neural Routing Solvers](https://mlsanity.com/paper/2508.02510/) (2025)
- [Generative Modeling for Robust Deep Reinforcement Learning on the Traveling Salesman Problem](https://mlsanity.com/paper/2508.08718/) (2025)
- [Towards a General Framework for Predicting and Explaining the Hardness of Graph-based Combinatorial Optimization Problems using Machine Learning and Association Rule Mining](https://mlsanity.com/paper/2512.20915/) (2025)
- [Adversarial Instance Generation and Robust Training for Neural Combinatorial Optimization with Multiple Objectives](https://mlsanity.com/paper/2601.01665/) (2026)

## Abstract (arXiv)

Various neural network models have been proposed to tackle combinatorial optimization problems such as the travelling salesman problem (TSP). Existing learning-based TSP methods adopt a simple setting that the training and testing data are independent and identically distributed. However, the existing literature fails to solve TSP instances when training and testing data have different distributions. Concretely, we find that different training and testing distribution will result in more difficult TSP instances, i.e., the solution obtained by the model has a large gap from the optimal solution. To tackle this problem, in this work, we study learning-based TSP methods when training and testing data have different distributions using adaptive-hardness, i.e., how difficult a TSP instance can be for a solver. This problem is challenging because it is non-trivial to (1) define hardness measurement quantitatively; (2) efficiently and continuously generate sufficiently hard TSP instances upon model training; (3) fully utilize instances with different levels of hardness to learn a more powerful TSP solver. To solve these challenges, we first propose a principled hardness measurement to quantify the hardness of TSP instances. Then, we propose a hardness-adaptive generator to generate instances with different hardness. We further propose a curriculum learner fully utilizing these instances to train the TSP solver. Experiments show that our hardness-adaptive generator can generate instances ten times harder than the existing methods, and our proposed method achieves significant improvement over state-of-the-art models in terms of the optimality gap.