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 still relies on expert knowledge, and LLM-enhanced evolutionary methods often evolve components separately despite their interactions. LLM-HCJG jointly co-evolves initialization and penalty construction under a shared blueprint, achieving low gaps and best results on 28/29 TSPLIB and 12/12 CVRPLIB benchmarks.

  • Problem

    Existing LLM-enhanced heuristic-design methods give limited treatment to component interactions, while strong heuristic performance often requires extensive domain knowledge and handcrafted rules.

    Source: §1 · p. 2, §2.2 · p. 6

  • Method

    LLM-HCJG jointly evolves solution-initialization and penalty-construction components as complete heuristics under a shared design blueprint.

    Source: §1 · pp. 2–3

  • Results

    Across 41 public benchmarks, LLM-HCJG attained the lowest gaps, with best counts on 28/29 TSPLIB and 12/12 CVRPLIB instances.

    Source: §1 · p. 3

  • Takeaways & Limitations

    The results support cross-instance generalization across evaluated routing settings with only five training instances per fitness evaluation.

    Source: §1 · p. 3, §5 · p. 27

    The authors identify larger, more heterogeneous instances, richer routing environments, and other metaheuristic frameworks as future extensions.

    Source: §5 · p. 27

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

LLM-HCJG jointly evolves interdependent solution-initialization and penalty-construction components within a shared design blueprint, addressing the expertise and adaptability limits of existing heuristic methods. Across evaluated routing testbeds and public benchmarks, it achieves strong results with limited training samples.

Introduction

  • Existing heuristic design requires extensive domain knowledge and handcrafted rules, while many learning-based methods are task-specific and require substantial retraining when settings change.Source: §1 · p. 2
  • GLS search direction depends jointly on initialization, which shapes the subsequent trajectory, and penalty construction, which enables escape from local minima while preserving solution structure.The paper identifies these interdependent bottleneck functions as requiring substantial domain expertise to design effectively.Source: §1 · p. 2
  • LLM-HCJG represents each individual as a complete heuristic with coupled components organized around a shared design blueprint, enabling algorithm-level search.The framework jointly evolves components that determine search direction rather than evolving an isolated rule.Source: §1 · pp. 2–3
  • Initialization and penalty construction are non-separable in search-state transitions, while blueprint consistency aligns design principles and reduces mismatch probability.This analysis justifies evolving the complete component pair as the basic unit.Source: §1 · p. 3
  • The jointly generated components are embedded in an augmented GLS procedure that preserves its interpretable backbone while extending the method from TSP to CVRP.Source: §1 · p. 3
  • LLM-HCJG attains the lowest gaps and best counts of 28/29 on TSPLIB and 12/12 on CVRPLIB, using five training instances per fitness evaluation.The evaluation includes synthetic TSP/CVRP testbeds at 20-, 50-, and 100-node scales and 41 public benchmarks.Source: §1 · p. 3

2 Related Work

Related work distinguishes LLMs that directly generate solutions from LLMs that iteratively design algorithms; this paper belongs to the latter paradigm, LLM-enhanced evolutionary computation (Yu and Liu, 2024).

2.1 LLMs as an Automated Solution Solver

  • LLM solution solvers directly produce candidate solutions, with work progressing from iterative single-solution refinement to population-level search.Examples include Optimization by PROmpting (Yang et al., 2024), executable vehicle-route generation, and population methods (Brahmachary et al., 2025; Liu et al., 2024c). The paradigm remains vulnerable to prompt sensitivity, inconsistent reasoning, and missing feasibility or improvement feedback.Source: §2.1 · pp. 4–5

2.2 LLMs as an Automated Algorithm Designer

  • LLM-enhanced algorithm design evolved from one-shot heuristic generation to iterative program search, but single-trajectory refinement limits diversity and code-level evolution incurs high query costs.FunSearch uses distributed island populations and migration; LLaMEA automates execution, verification, filtering, and repair. Reflective methods add parental, intergenerational, or evolutionary-change feedback, while HSEvo addresses diversity with flash reflection and harmony search.Source: §2.2 · pp. 5–6
  • EoH pairs natural-language design ideas with executable heuristics, while later extensions focus on subproblem-specific operators, more targeted search, and reduced redundant evaluations.Reflective Evolution (Ye et al., 2024), self-evolution reflection (Huang et al., 2024a), HSEvo (Dat et al., 2025), and LLM-driven LNS use feedback to steer subsequent evolution.Source: §2.2 · p. 6
  • Existing heuristic-design methods largely overlook how components interact with a specific optimization framework, leaving tightly coupled design under-specified.EoH’s GLS-TSP search takes nearly two days, while CoEvo-AHD coordinates evolving populations through cross-population evaluation and recombination rather than exploring design-level interdependence within one heuristic.Source: §2.2 · pp. 6–7

3 Joint-Generation Approach for LLM-Enhanced GLS Design

The section presents LLM-HCJG, which jointly generates and evolves solution initialization and penalty construction under a shared blueprint, embedding the pair in an enhanced guided-search mechanism for TSP and CVRP. It explains how shared-blueprint generation addresses component mismatch and describes fixed online GLS mechanisms, including endpoint-targeted perturbation, post-perturbation improvement, and periodic restoration of the best-so-far solution.

3.1 LLM-Driven Heuristic Components Joint Generation Framework

  • The population starts with LLM-generated candidates, applies blueprint-conditioned crossover and mutation, selects parents by fitness-ranked roulette, and truncates the combined pool to the top N.Mutation can optimize performance, retune parameters, or prune redundant structure; offspring inherit or revise their blueprint according to whether the joint principle is preserved.Source: §3.1 · p. 8, §3.1.3 · p. 11, §3.1.4 · p. 12

3.1.1 Individual Representation in Joint coevolution Mechanism

  • Each candidate combines a shared one-sentence design principle with component functions, their rationales and implementations, and a fitness evaluation; evolutionary prompts guide initialization, crossover, and mutation.The framework uses standardized component-specific prompt structures and blueprint-guided coordination.Source: §3.1.1 · pp. 9–10, §3.1.2 · pp. 10–11

3.2 Generalizing the Guided Local Search Backbone from TSP to CVRP

  • For CVRP, GLS extends edge-based penalties to capacity-constrained route sets and uses feasibility-preserving intra-route 2-opt, inter-route relocate, and inter-route swap neighborhoods.The transfer addresses customer assignment, route sequencing, demand, vehicle capacity, and fleet-size constraints.Source: §3.2 · pp. 13–14

3.3 Joint Component Coevolution and Enhanced Guided Search

  • LLM-HCJG jointly evolves initialization and penalty construction under a shared blueprint, then embeds the pair in online edge selection, perturbation, repair, local improvement, and incumbent restoration.The LLM-generated components are separated from the fixed online search mechanism.Source: §3.3 · p. 14, §3.3.1 · p. 14

3.3.1 Joint Generation of Interdependent components

  • Initialization constructs the starting tour or feasible route set, while penalty construction maps that state and edge-use information to a guided distance matrix; CVRP components also use demand, capacity, and fleet size.The functions are ordered as a pair because initialization determines the edge support on which penalty construction operates, and penalty construction governs subsequent perturbation.Source: §3.3.1 · p. 14

3.3.2 Theoretical Characterization of Coupled component Generation

  • Theorem 3.1 establishes that initialization and penalty construction have non-separable state-transition effects, so the complete pair should be generated, evaluated, and selected jointly.Theorem 3.2 characterizes shared-blueprint joint generation as eliminating conditional mismatch; with independent blueprints, mismatch probability is positive when at least two blueprints have positive probability.Source: §3.3.2 · pp. 16–17
  • A shared blueprint guarantees design-principle consistency within jointly generated pairs, while independently generated components can be mismatched with positive probability.Theorem 3.2 characterizes this structural advantage.Source: §3.3.2 · p. 17

3.3.3 Framework-Level Search Enhancement

  • The online GLS framework adds four fixed mechanisms, including endpoint-targeted perturbation, post-perturbation local improvement, and best-so-far restoration every 50 outer iterations.Local improvement follows guidance from D′ while evaluating quality under D; the fixed mechanisms are framework components rather than LLM-generated components.Source: §3.3.3 · pp. 17–18

4 Experiments

LLM-HCJG achieves low gaps on synthetic and public routing benchmarks, with gains associated with cross-component compatibility and alignment. Its experiments evaluate the method’s training outcomes, structural behavior, benchmark performance, and joint-evolution ablations.

4.1 Experiments Settings and Evolutionary Outcome

  • The best TSP and CVRP elites emerged at generations 4 and 7, with final gaps of 2.046% and 0.000%, respectively.Training averaged 34 minutes for TSP and 183 minutes for CVRP; valid-candidate rates were 88.0% and 95.12%, respectively.Source: §4.1 · pp. 19–20

4.1.1 Structural Alignment of the Best-Evolved component Pairs

  • For the best TSP and CVRP individuals, (Focus, Diversity) were (0.980, 0.318) and (0.978, 0.438), indicating jointly evolved component pairs realize state-aligned, selective perturbation patterns.Focus measures alignment of gap signals with the current search state; Diversity measures differentiation across edges rather than uniform distribution.Source: §4.1.1 · p. 20

4.2 Baseline Methods

  • TSP comparisons include all baseline categories, whereas CVRP comparisons are restricted to GLS, EoH, and ReEvo because comparable neural results and canonical KGLS/EBGLS variants are unavailable.EoH and ReEvo optimize the edge-distance update while using the default nearest-feasible-customer rule for node selection; neural results are taken from their original publications.Source: §4.2 · p. 22

4.3 Performance Comparison on Synthetic Instances

  • On synthetic TSP100 and CVRP100, LLM-HCJG achieves the best overall gaps: 0.070% and 3.526%, respectively.FA-GLS reduces original GLS gaps from 1.212% to 0.140% on TSP100 and from 8.362% to 4.523% on CVRP100; LLM-HCJG also improves on EoH and ReEvo at both scales.Source: Table 2 · p. 23, Table 3 · p. 23, §4.3 · pp. 23–24

4.4 Performance Comparison on TSPLIB and CVRPLIB

  • LLM-HCJG averages 0.017% gap and is best or tied-best on 28 of 29 TSPLIB instances; on CVRPLIB, it averages 1.686% and is best or tied-best on all 12.On TSPLIB, it improves on EoH (3.407%) and ReEvo (0.030%); on CVRPLIB, it beats GLS (6.240%), FA-GLS (6.152%), EoH (3.601%), and ReEvo (9.451%).Source: §4.4 · p. 24

4.5 Ablation Studies on Joint Combinatorial Dependency coevolution

  • HCJG–HCJG is best or tied-best at every synthetic scale and has the lowest TSPLIB mean gap, 0.017%, supporting cross-component compatibility over recombination.On TSP100, the other pairings yield 0.082%, 0.152%, and 0.159%; on TSPLIB, EoH–HCJG yields 0.030%, HCJG–EoH 0.611%, and EoH–EoH 2.788%. Bootstrap 95% confidence intervals lie above zero and paired Wilcoxon tests satisfy p < 0.05.Source: §4.5 · pp. 26–27

5 Conclusion … D Performance Comparison on Public Benchmark Instances

This section documents LLM-HCJG’s joint evolution of solution initialization and penalty construction and their integration into TSP/CVRP GLS, including component prompts, evolution operators, procedures, examples, and CVRP penalty-update and search-structure indicators. The supplied passages focus on methods and structural descriptions and do not report benchmark results.

5 Conclusion

  • LLM-HCJG jointly evolves solution initialization and penalty construction under a shared blueprint, reshaping GLS search direction while preserving its interpretable backbone across TSP and CVRP.Theoretical and ablation analyses support the components’ non-separability and pairwise compatibility; experiments report strong solution quality, efficient training, robust generalization, and consistent gains over single-component LLM-enhanced baselines.Source: §5 · p. 27
  • Future work targets larger and more heterogeneous instances, model fine-tuning for higher-quality generation, and extension to richer routing settings and other metaheuristics.Source: §5 · p. 27

A.1–A.2 Basic Attribute Descriptions

  • The TSP/CVRP prompts pair route-construction tasks with signed edge-guidance tasks, where positive gaps penalize edges and negative gaps encourage them.The CVRP construction prompt selects among feasible customers, and its guidance prompt also takes customer demands and vehicle capacity as inputs.Source: §A.1 · pp. 31–32, §A.2 · pp. 33–34

A.4–A.5 LLM-HCJG Crossover Prompt Specifications

  • Crossover prompts request a shared blueprint articulating complementary component roles, with e1 seeking different algorithm forms and e2 allowing inspiration from parents.Both prompts frame the two algorithms as jointly instantiating a common search-direction principle rather than operating independently.Source: §A.4 · p. 36, §A.5 · p. 37

A.6–A.8 LLM-HCJG Mutation Prompt Specifications

  • Mutation prompts generate paired algorithms as modified versions, parameter-setting variants, or simplified versions of an elite individual’s components.The prompts also request a shared blueprint describing how the two components jointly instantiate a common search-direction principle.Source: §A.6 · p. 38, §A.7 · p. 39, §A.8 · p. 39

B.2 LLM-Driven GLS Procedure for TSP

  • The LLM-driven GLS procedure uses generated components to initialize the route and update edge distances through penalty construction.The procedure identifies these as LLM solution initialization and LLM penalty construction, respectively.Source: §B.2 · p. 41
  • The TSP and transferred CVRP GLS procedures use edge penalties and retain lower-cost best solutions.The CVRP procedure specifies distance matrix, demands, vehicle capacity, vehicle count, and route set as inputs.Source: §B.2 · p. 41, §B.3 · p. 42

B.4 LLM-Driven GLS Procedure for CVRP

  • The LLM-driven CVRP GLS procedure initializes a feasible solution with an LLM and uses an LLM-generated penalty construction within the search.The algorithm calls LLM_select_next_node for feasible-solution initialization and LLM_update_edge_distance for penalty construction.Source: §B.4 · p. 43

C.1 Best LLM-Generated Elite Heuristic for TSP

  • The TSP elite heuristic selects nodes using immediate distance plus randomized nearest-continuation distance, and penalizes local-optimal-tour edges by distance, usage, and randomness.Its shared blueprint describes distance-driven stochastic guidance for initialization and usage-adaptive randomized penalties for search diversification.Source: §C.1 · pp. 44–45

C.2 Best LLM-Generated Elite Heuristic for CVRP

  • The CVRP elite heuristic constructs feasible routes using immediate distance, spatial coherence, and a long-move penalty, then adjusts route-edge distances using demand and historical usage.The penalty adjustment also uses edge distance and preserves stability through clipping and symmetry.Source: §C.2 · pp. 46–48

C.3.1 EoH on TSP from Publication (Liu et al., 2024a)

  • The TSP EoH penalty-construction example [Liu et al., 2024a] updates edge distances using edge counts, distance, usage, and a decay factor to encourage exploration.The description also includes a pheromone-like effect.Source: §C.3.1 · p. 49

C.3.2 EoH on CVRP

  • The CVRP EoH example revises traversed-edge costs according to customer demand, distance, and historical usage to balance capacity awareness and search diversification..Source: §C.3.2 · pp. 49–50

C.3.3 ReEvo on TSP

  • The TSP ReEvo example reshapes edge distances with usage-aware nonlinear penalties, decay and underused-edge adjustments, and exploration noise.Its description also specifies preserving symmetry, non-negativity, and the original overall scale.Source: §C.3.3 · pp. 50–51

C.3.4 ReEvo on CVRP

  • The CVRP ReEvo example increases unique route-edge costs nonlinearly based on repeated usage, endpoint demand, and total route load.This is described as a route-diversification strategy.Source: §C.3.4 · p. 52
  • The CVRP update combines edge usage, combined demand, and route ratio in a penalty term, then adds a scaled penalty symmetrically to edge distances.The updated distance matrix is symmetrized, clipped to nonnegative values, and given a zero diagonal.Source: §C.3.4 · pp. 52–53

C.4 Structural Focus and Diversity Indicators

  • The structural analysis defines normalized penalty-focus and penalty-focus-diversity indicators from positive edge gaps in the current search state.Diversity is based on the standard deviation relative to the mean of those gaps.Source: §C.4 · p. 54

D.1 Results on TSPLIB Instances · D.2 Results on CVRPLIB Instances

The section presents performance comparisons on TSPLIB and CVRPLIB instances, reported separately in Tables 4 and 5.

D.1 Results on TSPLIB Instances

  • Table 4 presents a performance comparison on TSPLIB instances.Source: Table 4 · p. 55

D.2 Results on CVRPLIB Instances

  • Table 5 presents a performance comparison on CVRPLIB instances.Source: Table 5 · p. 55

E Joint Component Co-Evolution Ablation · E.1 Cross-Component Combination Results on Synthetic TSP Instances

The section presents a cross-component combination ablation on synthetic TSP instances.

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

  • Table 6 reports cross-component combination ablation results on synthetic TSP instances.The supplied caption does not provide the table’s values or comparative findings.Source: Table 6 · p. 56

E.2 Cross-Component Combination Results on TSPLIB Instances

This section presents cross-component combination ablation results on TSPLIB instances and a visual comparison of optimality gaps for non-identical results.

E.2 Cross-Component Combination Results on TSPLIB Instances

  • Table 7 reports cross-component combination ablation results on TSPLIB, and Figure 8 visually compares optimality gaps for non-identical results.Source: Table 7 · p. 56, Figure 8 · p. 57

F Statistical Significance and Uncertainty Analysis · F.1 Public TSPLIB and CVRPLIB Benchmarks

The section specifies paired uncertainty and significance procedures for public benchmark optimality gaps. It defines paired differences relative to HCJG and assesses their uncertainty and significance using bootstrap intervals and Wilcoxon tests.

F Statistical Significance and Uncertainty Analysis

F.1 Public TSPLIB and CVRPLIB Benchmarks

F.2 Cross-Component Co-Evolution Ablation · G Proofs of Theoretical Results

The supplied evidence covers the TSPLIB cross-component co-evolution ablation: its paired uncertainty and significance analysis states that an interval entirely above zero favors HCJG+HCJG.

F.2 Cross-Component Co-Evolution Ablation

  • An interval entirely above zero favors HCJG+HCJG in the paired uncertainty and significance analysis for the TSPLIB ablation.Source: Table 9 · p. 58, §F.2 · p. 58

G.1 Proof of Theorem 3.1

The proof shows that initialization and penalty construction are non-separable at the search-state-transition level by deriving a contradiction from the assumption that they are separable for every component combination.

G.1 Proof of Theorem 3.1

  • Assuming separability for every component combination contradicts I ≠ 0, proving the components are non-separable at the search-state-transition level.The proof derives I ≠ 0 before ruling out the separability condition.Source: §G.1 · p. 59

G.2 Proof of Theorem 3.2

The proof derives the joint-generation property by conditioning on the blueprint, then uses independence to show that the mismatch probability in (25) is strictly positive under the stated condition.

G.2 Proof of Theorem 3.2

  • For joint generation, (5) implies that the stated properties hold simultaneously with probability one conditional on any blueprint Z = z.The proof then applies the law of total probability.Source: §G.2 · p. 59
  • For independent generation, (22) and (5) imply an expression; its last equality follows from independence of Zs and Zu, and taking its complement proves (25).Source: §G.2 · p. 60
  • Under z∈Z πθ(z | x)2 < 1, the mismatch probability in (25) is strictly positive.The proof obtains this conclusion by taking the complement of the independent-generation expression.Source: §G.2 · p. 60

Related papers

Loading 2609.02353v1…