G-LNS: Generative Large Neighborhood Search for LLM-Based Automatic Heuristic Design
Baoyun Zhao, He Wang, Liang Zeng
2026-02-12
Summary
This paper explores using artificial intelligence, specifically large language models, to automatically create better ways to solve really hard optimization problems, like finding the shortest route for a traveling salesperson or planning delivery routes for trucks.
What's the problem?
Currently, when AI is used to design these problem-solving methods, it's limited to tweaking existing approaches or making small changes to pre-defined rules. This is like trying to find the best path through a maze but only being allowed to adjust the size of the corridors – you might improve things a little, but you can’t fundamentally change the maze’s structure. This limitation makes it hard to find truly optimal solutions because the AI can get stuck in suboptimal paths.
What's the solution?
The researchers developed a new system called G-LNS. Instead of just improving existing methods, G-LNS uses a language model to *create* entirely new ways to disrupt and then rebuild potential solutions. It doesn't just evolve one part of the solution process, but two parts – a 'destroy' operator that breaks down a solution and a 'repair' operator that builds it back up – *together*. The AI learns how these two operators work best when used in combination, leading to more effective and creative problem-solving strategies.
Why it matters?
This work is important because it shows that AI can go beyond simply optimizing existing methods and actually *discover* new and better approaches to solving complex problems. The new methods developed by G-LNS perform better than previous AI-based methods and even rival traditional, manually-designed solutions, while also working well on different variations of the problems. This could lead to significant improvements in logistics, scheduling, and other areas where optimization is crucial.
Abstract
While Large Language Models (LLMs) have recently shown promise in Automated Heuristic Design (AHD), existing approaches typically formulate AHD around constructive priority rules or parameterized local search guidance, thereby restricting the search space to fixed heuristic forms. Such designs offer limited capacity for structural exploration, making it difficult to escape deep local optima in complex Combinatorial Optimization Problems (COPs). In this work, we propose G-LNS, a generative evolutionary framework that extends LLM-based AHD to the automated design of Large Neighborhood Search (LNS) operators. Unlike prior methods that evolve heuristics in isolation, G-LNS leverages LLMs to co-evolve tightly coupled pairs of destroy and repair operators. A cooperative evaluation mechanism explicitly captures their interaction, enabling the discovery of complementary operator logic that jointly performs effective structural disruption and reconstruction. Extensive experiments on challenging COP benchmarks, such as Traveling Salesman Problems (TSP) and Capacitated Vehicle Routing Problems (CVRP), demonstrate that G-LNS significantly outperforms LLM-based AHD methods as well as strong classical solvers. The discovered heuristics not only achieve near-optimal solutions with reduced computational budgets but also exhibit robust generalization across diverse and unseen instance distributions.