PaperlayerView exact revision on arXiv

Source-linked AI summary

LLM-Driven Joint Evolution of Coupled Heuristics Components for Routing Optimization

Juntao Wei, Yangming Zhou, Zhibin Jiang, Shan Jiang

arXiv:2609.02353v1cs.NE

TL;DR

Heuristic design requires extensive domain knowledge and handcrafted rules, while existing approaches give limited treatment to LLM-designed components. LLM-HCJG addresses this with joint generation and reports strong solution quality, efficient training, and robust generalization, while identifying prompt sensitivity and scalability as boundaries.

  • Problem

    Heuristic design typically requires extensive domain knowledge and carefully handcrafted rules, while treatments of LLM-designed components remain limited.

  • Method

    LLM-HCJG is a joint-generation framework that advances algorithm-level search by explicitly modeling interdependent components under a shared design blueprint.

  • Results

    LLM-HCJG demonstrates strong solution quality, efficient training, and robust generalization, consistently surpassing single-component LLM-enhanced baselines.

  • Takeaways & Limitations

    Ablation analyses confirm the non-separability and effectiveness of the jointly generated components.

  • Takeaways & Limitations

    The approach faces high prompt sensitivity and performance degradation due to weak reasoning consistency, with future work targeting scalable deployment on larger settings.

Abstract

from arXiv · show

Heuristic design for combinatorial optimization remains heavily reliant on expert knowledge, while existing large language model (LLM)-enhanced evolutionary methods typically evolve isolated algorithmic components, even when one determines the search state on which another operates. This paper proposes LLM-driven Heuristic Components Joint Generation (LLM-HCJG), a population-based framework that jointly generates and co-evolves interdependent heuristic components under a shared design blueprint. Applied to guided local search (GLS), LLM-HCJG couples solution initialization with penalty construction and embeds the generated pair into an enhanced online search mechanism. The resulting form is further transferred from the traveling salesman problem (TSP) to the capacitated vehicle routing problem (CVRP). Theoretical analysis establishes the non-separable state-transition effects between the two components and the advantage in generation consistency. Across synthetic instances and 41 public TSPLIB/CVRPLIB benchmarks, LLM-HCJG attains consistently low optimality gaps, including best or tied-best results on 28 of 29 TSPLIB instances and all 12 CVRPLIB instances. Ablation and structural analyses further indicate that these gains are associated with cross-component compatibility and alignment rather than isolated-component recombination. These results support effective cross-instance transfer within the evaluated routing settings under limited-sample, modest-cost training.

1 Introduction

The paper introduces LLM-HCJG to jointly evolve coupled heuristic components within GLS, addressing the expertise and coordination demands of adaptive routing optimization. Across synthetic and public benchmarks, the framework shows strong performance with limited training samples.

  • Motivation: Heuristic methods often require extensive domain knowledge and handcrafted rules, while changing problem settings can demand substantial retraining.These constraints widen the gap between real-world complexity and practical deployment of adaptive, scalable solution methods.
  • LLM-HCJG framework: LLM-HCJG jointly generates and co-evolves solution-initialization and penalty-construction functions within a shared design blueprint.Each individual represents a complete heuristic composed of coupled components rather than an isolated rule or solution.
  • LLM-HCJG framework: Solution initialization and penalty construction are non-separable in GLS search-state transitions, making the complete component pair the basic evolution unit.The two functions respectively shape the starting route and subsequent perturbations that guide escape from local minima.
  • Theoretical basis: Blueprint consistency enforces design-principle alignment and reduces mismatch probability between generated components.This provides a theoretical basis for coordinating interdependent functions during joint generation.
  • Routing application: LLM-HCJG embeds jointly generated components into an enhanced GLS procedure and transfers the design from TSP to CVRP.The framework preserves GLS’s interpretable backbone while extending its search direction across routing problem types.
  • Empirical findings: 28/29 TSPLIB instances and 12/12 CVRPLIB instances achieve the lowest gaps and best counts using only five training instances per fitness evaluation.The evaluation covers synthetic 20-, 50-, and 100-node testbeds plus 41 public TSPLIB/CVRPLIB benchmarks.

2 Related Work

Related work spans LLMs used as direct solution solvers and as automated algorithm designers. The paper emphasizes limitations involving prompt sensitivity, computational cost, and insufficient treatment of interactions among coupled heuristic components.

  • LLM roles: LLMs are studied both as automated solution solvers that generate candidates and as algorithm designers that evolve search strategies.The latter paradigm, LLM-enhanced evolutionary computation, is the focus of heuristic innovation in this paper.
  • LLMs as solution solvers: Direct LLM solution generation has expanded from iterative single-solution refinement to population-level prompting and multimodal route construction.Examples use solution history, self-reflection, exploration–exploitation pools, or visual-spatial information to improve candidate routes.
  • LLMs as solution solvers: Direct solver approaches remain limited by high prompt sensitivity, weak reasoning consistency, and absent feasibility or improvement feedback.The paper therefore characterizes relying solely on LLMs as end-to-end solvers as insufficient.
  • LLMs as algorithm designers: LLM-enhanced evolutionary methods evolve heuristic code or designs through population search, executable evaluation, reflection, and prompt-based variation.Representative systems include FunSearch, LLaMEA, EoH, Hercules, and reflective evolutionary mechanisms.
  • Limitations of prior work: Existing algorithm-design methods can incur high LLM-query costs, with EoH’s GLS-TSP search reported to take nearly two days.Single-trajectory refinement also restricts algorithmic diversity, while code-level evolution remains computationally expensive.
  • Research gap: Prior methods largely under-specify how LLM-designed components interact with a particular algorithmic framework when search directions depend on tightly coupled functions.Cross-population evaluation and recombination leave within-heuristic design-level interdependence largely unexplored.

3 Joint-Generation Approach for LLM-Enhanced GLS Design

LLM-HCJG represents complete heuristic algorithms as blueprint-coordinated coupled components and evolves them through LLM-guided population operations. Applied to GLS, it jointly designs initialization and penalty construction while retaining an interpretable search framework and establishing their non-separable interaction.

  • Framework overview: LLM-HCJG redesigns search direction within an interpretable GLS backbone for TSP and CVRP, while confining LLM modifications to two locally critical components.Solution initialization determines the starting search state, whereas penalty construction guides subsequent perturbations.
  • Individual representation: Each algorithm individual stores a shared design blueprint and coupled component functions rather than a candidate solution.The blueprint specifies the joint principle governing complementary component roles and their intended interaction.
  • Evolutionary process: A population of N LLM-created individuals is evaluated on training instances and evolved through selection, crossover, mutation, and population management over Ng generations.Crossover first creates a child blueprint and then generates both components conditionally on it; mutation can optimize performance, retune parameters, or prune redundant structure.
  • Three-layer composition: The framework uses three layers: component-specific function structure, individual composition, and evolutionary prompt construction.These layers define component tasks, assemble coordinated candidates, and control initialization, crossover, and mutation.
  • Theoretical characterization: Theorem 3.1 establishes that initialization and penalty-construction effects cannot be decomposed into fixed, independently attributable contributions.When the interaction term is nonzero, the complete component pair should be generated, evaluated, and selected jointly.
  • Joint generation: Shared-blueprint generation guarantees design-principle consistency within a component pair, whereas independent generation can produce mismatched pairs with positive probability.The LLM first generates the blueprint and then conditionally generates initialization and penalty-construction components.

4 Experiments

Experiments evaluate LLM-HCJG’s training behavior, evolved heuristic structure, component alignment, and performance against GLS and LLM-enhanced baselines on synthetic and public routing benchmarks.

  • Training process: 410 candidate-generation attempts produced 361 valid TSP candidates and 390 valid CVRP candidates, yielding effective generation rates of 88.0% and 95.12%.Under GPT-4o-mini, average training required 34 minutes for TSP and 183 minutes for CVRP.
  • Evolutionary outcome: The best TSP and CVRP individuals emerged at generations 4 and 7, indicating convergence within the adopted training budget.Figure 4 tracks the best-validated elite heuristic gap over generations.
  • Evolutionary outcome: The best TSP and CVRP individuals reached final performance gaps of 2.046% and 0.000%, respectively, and remained preserved in later generations.They were identified as individuals No. 151 and No. 251 and generated through the e1 and m1 operators.
  • Synthetic-instance comparison: On synthetic instances, LLM-HCJG achieved gaps of 0.070% on TSP100 and 3.526% on CVRP100, outperforming the evaluated baselines.FA-GLS first reduced GLS gaps from 1.212% to 0.140% on TSP100 and from 8.362% to 4.523% on CVRP100.
  • Public-benchmark comparison: LLM-HCJG obtained the best or tied-best result on 28 of 29 TSPLIB instances and all 12 CVRPLIB instances, with average gaps of 0.017% and 1.686%.The TSPLIB average improved over EoH–HCJG, HCJG–EoH, and EoH–EoH, while hybrid degradation supported cross-component compatibility rather than simple recombination.

5 Conclusion

LLM-HCJG jointly evolves coupled heuristic components under a shared design blueprint, reshaping GLS search direction while preserving an interpretable backbone across TSP and CVRP. Analyses and experiments associate its solution quality and generalization with component non-separability and compatibility, while future work targets broader scale, model integration, and routing settings.

  • Broader implication: LLM-HCJG advances LLM-enhanced evolutionary computation from isolated heuristic construction toward coordinated component coevolution.The framework is presented as a distinct algorithmic dimension that redesigns search direction and can shape structural search bias.
  • Framework and contribution: LLM-HCJG jointly evolves solution-initialization and penalty-construction components under a shared design blueprint.The paired components reshape GLS search direction while preserving its interpretable backbone across TSP and CVRP.
  • Framework and contribution: Theoretical and ablation analyses confirm that the coupled components are non-separable and effective through pairwise compatibility.These analyses concern the interaction between component functions rather than isolated-component recombination.
  • Empirical findings: Experiments on TSP/CVRP synthetic instances and public benchmarks demonstrate strong solution quality, efficient training, and robust generalization.The reported experiments consistently surpass single-component LLM-enhanced baselines.
  • Future work: Future research targets scalable deployment on larger, more heterogeneous instances, tighter integration with model fine-tuning, and richer routing or metaheuristic settings.These directions define the current scope boundary of the reported framework.

D.1 Results on TSPLIB Instances

The paper reports performance comparisons on TSPLIB and CVRPLIB instances, with optimality gaps used to identify the smallest or tied-smallest result for each instance.

  • Table 4 compares performance on TSPLIB instances.
  • Optimality gaps are reported as percentages, with boldface marking the smallest or tied-smallest gap on each instance.
  • Table 5 compares performance on CVRPLIB instances.

E.1 Cross-Component Combination Results on Synthetic TSP Instances

Cross-component combination results are reported for synthetic TSP instances, with performance comparisons organized in Table 6.

  • Table 6 reports cross-component combination ablation results on synthetic TSP instances.

E.2 Cross-Component Combination Results on TSPLIB Instances

The paper evaluates cross-component combinations on TSPLIB instances and provides a visual comparison of their optimality gaps.

  • Table 7 reports cross-component combination ablation results on TSPLIB instances.
  • Figure 8 visually compares optimality gaps on TSPLIB using non-identical results.

F Statistical Significance and Uncertainty Analysis

The statistical analysis compares per-instance optimality gaps against LLM-HCJG using bootstrap confidence intervals and Wilcoxon signed-rank tests.

  • Paired differences are defined as the compared-method gap minus the HCJG gap in percentage points.
  • 95% confidence intervals for mean paired differences use 20,000 percentile-bootstrap instance-level resamples with a fixed random seed.
  • Two-sided Wilcoxon signed-rank tests assess statistical significance at α = 0.05.
  • Table 8 presents paired uncertainty and significance analysis on public benchmarks.
  • An interval entirely above zero favors LLM-HCJG.

F.2 Cross-Component Co-Evolution Ablation

The paired uncertainty and significance analysis for the TSPLIB ablation reports an interval entirely above zero, favoring HCJG+HCJG.

  • An interval entirely above zero favors HCJG+HCJG in the TSPLIB ablation.The analysis is presented as paired uncertainty and significance analysis.

G.1 Proof of Theorem 3.1

The proof establishes that initialization and penalty construction cannot be separated at the search-state-transition level. It does so by deriving a contradiction from the assumption that their interaction vanishes for every component combination.

  • Assuming the interaction vanishes for every component combination leads to a contradiction.The proof proceeds by supposing that Gs and Gu satisfy the separability condition universally, then showing this conflicts with I ≠ 0.
  • The initialization and penalty-construction components are non-separable at the search-state-transition level.

G.2 Proof of Theorem 3.2

The proof compares joint and independent generation through their consistency probabilities. It concludes that independent generation has a strictly positive mismatch probability under the stated condition.

  • Joint generation makes the relevant component conditions hold simultaneously with probability one conditional on any blueprint.
  • The law of total probability is used to derive the joint-generation consistency probability.
  • Independent generation factorizes through the independence of Zs and Zu, yielding the mismatch result.Taking the complement establishes the mismatch probability in (25).
  • The mismatch probability in (25) is strictly positive when z∈Z πθ(z | x)2 < 1.
Loading 2609.02353v1…