Destroy and Repair Using Hyper-Graphs for Routing

Ke Li, Fei Liu, Zhenkun Wang, Qingfu ZhangAAAI 2025 · DOI

Presented at AAAI-25, DRHG (Destroy and Repair using Hyper-Graphs) is a novel iterative framework designed to solve large-scale routing problems like the Traveling Salesman Problem (TSP). By representing partially destroyed solutions as condensed hyper-graphs, DRHG enables neural networks to search significantly larger "neighborhoods" than previous methods. This approach achieves state-of-the-art performance on problems with up to 10,000 nodes.

Scaling Neural Combinatorial Optimization

Routing problems, including the Traveling Salesman Problem (TSP) and Capacitated Vehicle Routing Problem (CVRP), are NP-hard yet fundamental to logistics and manufacturing. Traditional Neural Combinatorial Optimization (NCO) methods typically fall into two categories:

  1. Non-iterative (One-shot): These build solutions from scratch. While fast, they struggle with large-scale instances because early errors can propagate through the entire tour.
  2. Iterative (Local Search): These improve existing solutions. However, most neural iterative solvers are limited to small "neighborhoods" (e.g., simple node swaps).

The central challenge addressed by DRHG is how to allow a neural network to efficiently search a large neighborhood—re-routing many nodes simultaneously—without being overwhelmed by the complexity of the full graph.

Methodology: The Destroy-and-Repair Framework

DRHG utilizes a Destroy-and-Repair framework powered by a unique Hyper-Graph Representation.

The DRHG framework illustrates the iterative process of graph reduction, model-based solving, and restoration for both training and testing phases.

The process consists of four main steps:

  1. Destroy: A portion of an existing solution is "destroyed" by removing edges, resulting in several intact segments and a set of isolated nodes.
  2. Hyper-Graph Reduction: This is the core innovation. Instead of processing every node, the model treats each intact segment as a single "hyper-edge," considering only the two endpoints. This drastically reduces the input size for the neural network.
  3. Neural Repair: A Transformer-based model, featuring a light encoder and a heavy decoder with Linear Attention, learns to connect isolated nodes and hyper-edges into a new, complete tour.
  4. Training: The model is trained via Supervised Learning (SL) using high-quality solutions from classical solvers (e.g., Concorde for TSP and HGS for CVRP) as ground truth.

Scale Invariance and Efficiency

By reducing segments to hyper-edges, the input size depends on the amount of destruction rather than the total problem size. This allows a model trained on 100 nodes to effectively repair a 10,000-node tour. Furthermore, the hyper-graph formulation focuses the model's "attention budget" solely on the parts of the problem that require fixing.

Experimental Results

The researchers evaluated DRHG on synthetic and real-world benchmarks (TSPLib and CVRPLib) with instances ranging from 100 to 10,000 nodes.

Performance comparison on large-scale TSP instances (1K, 5K, and 10K nodes) shows DRHG achieving significantly lower optimality gaps than other neural methods.

Key findings include:

  • State-of-the-Art Performance: On TSP100, DRHG achieved a 0.000% optimality gap. For massive TSP10,000 instances, it maintained a 1.33% gap, significantly outperforming recent neural methods like SIL (2.23%) and LEHD (12.50%).
  • Computational Efficiency: DRHG is substantially faster than exact solvers. For TSP1000, it finds near-optimal solutions in approximately 1.7 minutes.
  • Robust Generalization: The model demonstrated strong performance on real-world libraries, indicating it learns fundamental routing principles rather than just memorizing synthetic data.
  • High Precision: On TSP100, DRHG produced non-optimal solutions in only 1.29% of cases, compared to 18.22% for the next best competitor, BQ.

Conclusion and Future Work

DRHG demonstrates that hyper-graph reduction is a powerful tool for scaling NCO to massive problems. While highly effective for TSP, its performance on CVRP is slightly less dominant due to additional constraints like vehicle capacity. Future research may explore "learned" destruction strategies to identify weak parts of a tour more effectively or apply hyper-graph reduction to other combinatorial domains like scheduling and circuit design.

Summary updated

BibTeX
@inproceedings{li2025destroy,
  author = {Ke Li and Fei Liu and Zhenkun Wang and Qingfu Zhang},
  title = {{Destroy and Repair Using Hyper-Graphs for Routing}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i17.34018},
}
Figure