# Generalization in Deep RL for TSP Problems via Equivariance and Local Search

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 43 references that are in the map.
- First posted on arXiv 7 Oct 2021.

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

- [Relational inductive biases, deep learning, and graph networks](https://mlsanity.com/paper/1806.01261/) (2018)
- [Group Equivariant Convolutional Networks](https://mlsanity.com/paper/1602.07576/) (2016)
- [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)
- [An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem](https://mlsanity.com/paper/1906.01227/) (2019)
- [Curriculum Learning: A Survey](https://mlsanity.com/paper/2101.10382/) (2021)
- [An Introduction to Deep Reinforcement Learning](https://mlsanity.com/paper/1811.12560/) (2018)
- [Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search](https://mlsanity.com/paper/1810.10659/) (2018)
- [Learning Improvement Heuristics for Solving Routing Problems](https://mlsanity.com/paper/1912.05784/) (2019)
- [Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instances](https://mlsanity.com/paper/2012.10658/) (2020)
- [Curriculum Learning by Transfer Learning: Theory and Experiments with Deep Networks](https://mlsanity.com/paper/1802.03796/) (2018)
- [Learning 2-opt Heuristics for the Traveling Salesman Problem via Deep Reinforcement Learning](https://mlsanity.com/paper/2004.01608/) (2020)
- [Combinatorial Optimization by Graph Pointer Networks and Hierarchical Reinforcement Learning](https://mlsanity.com/paper/1911.04936/) (2019)
- [Learning to Solve NP-Complete Problems - A Graph Neural Network for Decision TSP](https://mlsanity.com/paper/1809.02721/) (2018)
- [Combining Reinforcement Learning with Lin-Kernighan-Helsgaun Algorithm for the Traveling Salesman Problem](https://mlsanity.com/paper/2012.04461/) (2020)
- [On Learning Paradigms for the Travelling Salesman Problem](https://mlsanity.com/paper/1910.07210/) (2019)
- [Analytics and Machine Learning in Vehicle Routing Research](https://mlsanity.com/paper/2102.10012/) (2021)
- [Evaluating Curriculum Learning Strategies in Neural Combinatorial Optimization](https://mlsanity.com/paper/2011.06188/) (2020)
- [Reinforcement Learning Driven Heuristic Optimization](https://mlsanity.com/paper/1906.06639/) (2019)
- [Improving Generalization of Deep Reinforcement Learning-based TSP Solvers](https://mlsanity.com/paper/2110.02843/) (2021)

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

- [Sym-NCO: Leveraging Symmetricity for Neural Combinatorial Optimization](https://mlsanity.com/paper/2205.13209/) (2022)
- [RL4CO: an Extensive Reinforcement Learning for Combinatorial Optimization Benchmark](https://mlsanity.com/paper/2306.17100/) (2023)
- [INViT: A Generalizable Routing Problem Solver with Invariant Nested View Transformer](https://mlsanity.com/paper/2402.02317/) (2024)
- [Preference Optimization for Combinatorial Optimization Problems](https://mlsanity.com/paper/2505.08735/) (2025)
- [Learning for routing: A guided review of recent developments and future directions](https://mlsanity.com/paper/2507.00218/) (2025)
- [RLOR: A Flexible Framework of Deep Reinforcement Learning for Operation Research](https://mlsanity.com/paper/2303.13117/) (2023)
- [ASAP: Exploiting the Satisficing Generalization Edge in Neural Combinatorial Optimization](https://mlsanity.com/paper/2501.17377/) (2025)
- [Generative Modeling for Robust Deep Reinforcement Learning on the Traveling Salesman Problem](https://mlsanity.com/paper/2508.08718/) (2025)
- [EDISCO: Equivariant DIScrete Diffusion for Euclidean Combinatorial Optimization](https://mlsanity.com/paper/2610.04953/) (2026)

## Abstract (arXiv)

Deep reinforcement learning (RL) has proved to be a competitive heuristic for solving small-sized instances of traveling salesman problems (TSP), but its performance on larger-sized instances is insufficient. Since training on large instances is impractical, we design a novel deep RL approach with a focus on generalizability. Our proposition consisting of a simple deep learning architecture that learns with novel RL training techniques, exploits two main ideas. First, we exploit equivariance to facilitate training. Second, we interleave efficient local search heuristics with the usual RL training to smooth the value landscape. In order to validate the whole approach, we empirically evaluate our proposition on random and realistic TSP problems against relevant state-of-the-art deep RL methods. Moreover, we present an ablation study to understand the contribution of each of its component