G-LNS: Generative Large Neighborhood Search for LLM-Based Automatic Heuristic Design
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.
698bf9256052d3bed9630ad3
Baoyun Zhao
claimed_verified
2026-02-11T11:14:17.040Z
698ae59d70be6790cd1e6a53
/avatars/66125d952e7880baa4fe1635aafbc160.svg
Baoyun Zhao
ZBoyn
user
ZBoyn
698bf9256052d3bed9630ad4
He Wang
claimed_verified
2026-02-12T13:57:46.758Z
617a39153490eedabaa5391f
/avatars/29ce0101b99bc96f81032ac6228ce878.svg
He Wang
iphysresearch
user
iphysresearch
698bf9256052d3bed9630ad5
Liang Zeng
G-LNS: Generative Large Neighborhood Search for LLM-Based Automatic Heuristic Design
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.
A generative evolutionary framework extends large language models for automated design of large neighborhood search operators in combinatorial optimization problems.
Large Language Models Automated Heuristic Design Combinatorial Optimization Problems Large Neighborhood Search generative evolutionary framework constructive priority rules parameterized local search deep local optima Traveling Salesman Problems Capacitated Vehicle Routing Problems