# Destroy and Repair Using Hyper Graphs for Routing

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 22 references that are in the map.
- First posted on arXiv 22 Feb 2025.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Pointer Networks](https://mlsanity.com/paper/1506.03134/) (2015)
- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [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)
- [An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem](https://mlsanity.com/paper/1906.01227/) (2019)
- [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)
- [Hybrid Genetic Search for the CVRP: Open-Source Implementation and SWAP* Neighborhood](https://mlsanity.com/paper/2012.10384/) (2020)
- [Learning to Iteratively Solve Routing Problems with Dual-Aspect Collaborative Transformer](https://mlsanity.com/paper/2110.02544/) (2021)
- [Learning Collaborative Policies to Solve NP-hard Routing Problems](https://mlsanity.com/paper/2110.13987/) (2021)
- [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)
- [Self-Improved Learning for Scalable Neural Combinatorial Optimization](https://mlsanity.com/paper/2403.19561/) (2024)

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

- [URS: A Unified Neural Routing Solver for Cross-Problem Zero-Shot Generalization](https://mlsanity.com/paper/2509.23413/) (2025)
- [MOTIF: Multi-strategy Optimization via Turn-based Interactive Framework](https://mlsanity.com/paper/2508.03929/) (2025)
- [Survey on Neural Routing Solvers](https://mlsanity.com/paper/2602.21761/) (2026)
- [Efficient Neural Combinatorial Optimization Solver for the Min-max Heterogeneous Capacitated Vehicle Routing Problem](https://mlsanity.com/paper/2507.21386/) (2025)
- [CADO: From Imitation to Cost Minimization for Heatmap-based Solvers in Combinatorial Optimization](https://mlsanity.com/paper/2602.08210/) (2026)
- [Empowering Targeted Neighborhood Search via Hyper Tour for Large-Scale TSP](https://mlsanity.com/paper/2510.20169/) (2025)
- [Rethinking Constraint Awareness for Efficient State Embedding of Neural Routing Solver](https://mlsanity.com/paper/2605.10122/) (2026)
- [RsGCN: Subgraph-Based Rescaling Enhances Generalization of GCNs for Solving Traveling Salesman Problems](https://mlsanity.com/paper/2506.00533/) (2025)
- [Learning Memory-Enhanced Improvement Heuristics for Flexible Job Shop Scheduling](https://mlsanity.com/paper/2603.02846/) (2026)
- [A Unified Knowledge Embedded Reinforcement Learning-based Framework for Generalized Capacitated Vehicle Routing Problems](https://mlsanity.com/paper/2605.14416/) (2026)
- [GeoPAR: Large-Scale Multi-Agent Combinatorial Optimization with Geometry-Guided Parallel Autoregressive Learning](https://mlsanity.com/paper/2609.00577/) (2026)
- [When Evidence Changes the Subject: Subject-Typed Claim Licensing for Learned Routing](https://mlsanity.com/paper/2609.33505/) (2026)
- [Compute Time Scaling with Recursive Models for Combinatorial Optimization](https://mlsanity.com/paper/2609.34585/) (2026)
- [Depot-Closed Multi-Component Construction for Neural Vehicle Routing](https://mlsanity.com/paper/2609.35066/) (2026)

## Abstract (arXiv)

Recent advancements in Neural Combinatorial Optimization (NCO) have shown promise in solving routing problems like the Traveling Salesman Problem (TSP) and Capacitated Vehicle Routing Problem (CVRP) without handcrafted designs. Research in this domain has explored two primary categories of methods: iterative and non-iterative. While non-iterative methods struggle to generate near-optimal solutions directly, iterative methods simplify the task by learning local search steps. However, existing iterative methods are often limited by restricted neighborhood searches, leading to suboptimal results. To address this limitation, we propose a novel approach that extends the search to larger neighborhoods by learning a destroy-and-repair strategy. Specifically, we introduce a Destroy-and-Repair framework based on Hyper-Graphs (DRHG). This framework reduces consecutive intact edges to hyper-edges, allowing the model to pay more attention to the destroyed part and decrease the complexity of encoding all nodes. Experiments demonstrate that DRHG achieves stateof-the-art performance on TSP with up to 10,000 nodes and shows strong generalization to real-world TSPLib and CVRPLib problems.