# Empowering Targeted Neighborhood Search via Hyper Tour for Large-Scale TSP

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 57 references that are in the map.
- First posted on arXiv 23 Oct 2025.

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

- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Pointer Networks](https://mlsanity.com/paper/1506.03134/) (2015)
- [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)
- [DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization](https://mlsanity.com/paper/2302.08224/) (2023)
- [Learning to Perform Local Rewriting for Combinatorial Optimization](https://mlsanity.com/paper/1810.00337/) (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)
- [Neural Combinatorial Optimization with Heavy Decoder: Toward Large Scale Generalization](https://mlsanity.com/paper/2310.07985/) (2023)
- [GLOP: Learning Global Partition and Local Construction for Solving Large-scale Routing Problems in Real-time](https://mlsanity.com/paper/2312.08224/) (2023)
- [Simulation-guided Beam Search for Neural Combinatorial Optimization](https://mlsanity.com/paper/2207.06190/) (2022)
- [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)
- [Winner Takes It All: Training Performant RL Populations for Combinatorial Optimization](https://mlsanity.com/paper/2210.03475/) (2022)
- [Fast T2T: Optimization Consistency Speeds Up Diffusion-Based Training-to-Testing Solving for Combinatorial Optimization](https://mlsanity.com/paper/2502.02941/) (2025)
- [INViT: A Generalizable Routing Problem Solver with Invariant Nested View Transformer](https://mlsanity.com/paper/2402.02317/) (2024)
- [Combinatorial Optimization with Policy Adaptation using Latent Space Search](https://mlsanity.com/paper/2311.13569/) (2023)
- [Learning to Solve Travelling Salesman Problem with Hardness-adaptive Curriculum](https://mlsanity.com/paper/2204.03236/) (2022)
- [ASP: Learn a Universal Neural Solver!](https://mlsanity.com/paper/2303.00466/) (2023)
- [Meta-SAGE: Scale Meta-Learning Scheduled Adaptation with Guided Exploration for Mitigating Scale Shift on Combinatorial Optimization](https://mlsanity.com/paper/2306.02688/) (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)
- [Destroy and Repair Using Hyper Graphs for Routing](https://mlsanity.com/paper/2502.16170/) (2025)
- [Approximation algorithms for TSP with neighborhoods in the plane](https://mlsanity.com/paper/1703.01640/) (2017)
- [Age Optimal Information Gathering and Dissemination on Graphs](https://mlsanity.com/paper/1901.02178/) (2019)

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

- [Compute Time Scaling with Recursive Models for Combinatorial Optimization](https://mlsanity.com/paper/2609.34585/) (2026)

## Abstract (arXiv)

Traveling Salesman Problem (TSP) is a classic NP-hard problem that has garnered significant attention from both academia and industry. While neural-based methods have shown promise for solving TSPs, they still face challenges in scaling to larger instances, particularly in memory constraints associated with global heatmaps, edge weights, or access matrices, as well as in generating high-quality initial solutions and insufficient global guidance for efficiently navigating vast search spaces. To address these challenges, we propose a Hyper Tour Guided Neighborhood Search (HyperNS) method for large-scale TSP instances. Inspired by the ``clustering first, route second" strategy, our approach initially divides the TSP instance into clusters using a sparse heatmap graph and abstracts them as supernodes, followed by the generation of a hyper tour to guide both the initialization and optimization processes. This method reduces the search space by focusing on edges relevant to the hyper tour, leading to more efficient and effective optimization. Experimental results on both synthetic and real-world datasets demonstrate that our approach outperforms existing neural-based methods, particularly in handling larger-scale instances, offering a significant reduction in the gap to the optimal solution.