2025/02/22 by Lian Li, Fei Liu, Li, Ke +5 · 2 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · #Advanced Graph Theory Research #Artificial Intelligence (cs.AI) #DNA and Biological Computing #FOS: Computer and information sciences #Graph Theory and Algorithms #Machine Learning (cs.LG) #Neural and Evolutionary Computing (cs.NE)
paper · pdf · doi:10.48550/arxiv.2502.16170
openalex publication_date 2025/02/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.