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

• URL: http://arxiv.org/abs/2609.02353v1
• Date: Wed, 02 Sep 2026 09:25:55 GMT
• Title: LLM-Driven Joint Evolution of Coupled Heuristics Components for Routing Optimization
• Abstract summary: This paper proposes a population-based framework that jointly generates and co-evolves interdependent components under a shared design blueprint.<n>Across synthetic instances and 41 public benchmarks, LLM-HCJG attains consistently low optimality gaps.
• Score: 6.642260387629958
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Beyond Isolation: Unlocking Reinforcement Learning Component Synergy for Sample-Efficient Continuous Control [59.15149762610843]
  Reinforcement learning systems are significantly more complex than other machine learning paradigms.<n>Despite advances in individual algorithmic components, their functional interdependencies remain underexplored.<n>We propose ROSER, an RL framework that coordinates three critical dimensions: Model-based Representation, Optimization Stability, and Experience Replay.
  arXiv  Detail & Related papers  (2026-08-07T10:38:31Z)
• MuEvo: LLM-Driven Evolution of Multi-Heuristic Ensemble [16.72462798926915]
  We propose MuEvo, an LLM-driven framework for evolving ensembles under ensemble-level feedback.<n>We evaluate MuEvo on selection-heuristics and componentized ant colony optimization across four optimization domains.
  arXiv  Detail & Related papers  (2026-08-04T13:19:51Z)
• LLM-Driven Co-Evolutionary Automated Heuristic Design for Bi-Component Coupled Combinatorial Optimization [9.1230734846341]
  Large Language Models (LLMs) have recently shown promise in Automated Heuristic Design (AHD)<n>We propose CoEvo-AHD, an LLM-driven dual-population co-evolutionary framework for automated design in coupled optimization.
  arXiv  Detail & Related papers  (2026-05-30T13:04:51Z)
• ReVEL: Multi-Turn Reflective LLM-Guided Heuristic Evolution via Structured Performance Feedback [0.0]
  We propose ReVEL: Multi-Turn Reflective LLM-Heuristic Evolution via Structured Performance Feedback.<n>The core of ReVEL lies in two mechanisms: (i) performance-profile grouping and (ii) multi-turn feedback-driven reflection.<n>Our results highlight multi-turn reasoning with structured grouping as a principled paradigm for automated design.
  arXiv  Detail & Related papers  (2026-03-05T04:52:11Z)
• Search-R2: Enhancing Search-Integrated Reasoning via Actor-Refiner Collaboration [49.9937230730202]
  We propose Search-R2, a novel Actor-Refiner collaboration framework that enhances reasoning through targeted intervention.<n>Our approach decomposes the generation process into an Actor, which produces initial reasoning trajectories.<n>We show that Search-R2 consistently outperforms strong RAG and RL-based baselines across model scales.
  arXiv  Detail & Related papers  (2026-02-03T15:32:09Z)
• ECCO: Evidence-Driven Causal Reasoning for Compiler Optimization [9.85275171877854]
  We introduce ECCO, a framework that bridges interpretable reasoning with search.<n>We first propose a reverse engineering methodology to construct a Chain-of-Thought dataset.<n>We then design a collaborative inference mechanism where the Large Language Model functions as a strategist.
  arXiv  Detail & Related papers  (2026-01-23T01:23:20Z)
• Stratified GRPO: Handling Structural Heterogeneity in Reinforcement Learning of LLM Search Agents [90.45197506653341]
  Large language model (LLM) agents increasingly rely on external tools such as search engines to solve complex, multi-step problems.<n>The trajectories of search agents are structurally heterogeneous, where variations in the number, placement, and outcomes of search calls lead to fundamentally different answer directions and reward distributions.<n>Standard policy gradient methods, which use a single global baseline, suffer from what we identify and formalize as cross-stratum bias.<n>We propose Stratified GRPO, whose central component, Stratified Advantage Normalization (SAN), partitions trajectories into homogeneous strata based on their structural properties and computes advantages locally within each
  arXiv  Detail & Related papers  (2025-10-07T17:59:13Z)
• Joint Cooperative and Non-Cooperative Localization in WSNs with Distributed Scaled Proximal ADMM Algorithms [11.088311601906284]
  Cooperative and non-cooperative localization arise together in wireless sensor networks.<n>We develop the Scaled Proximal Direction Method of Multipliers for Joint Cooperative and Non-Cooperative localization.
  arXiv  Detail & Related papers  (2025-09-21T14:32:53Z)
• LLM4CMO: Large Language Model-aided Algorithm Design for Constrained Multiobjective Optimization [54.35609820607923]
  Large language models (LLMs) offer new opportunities for assisting with algorithm design.<n>We propose LLM4CMO, a novel CMOEA based on a dual-population, two-stage framework.<n>LLMs can serve as efficient co-designers in the development of complex evolutionary optimization algorithms.
  arXiv  Detail & Related papers  (2025-08-16T02:00:57Z)
• NDCG-Consistent Softmax Approximation with Accelerated Convergence [67.10365329542365]
  We propose novel loss formulations that align directly with ranking metrics.<n>We integrate the proposed RG losses with the highly efficient Alternating Least Squares (ALS) optimization method.<n> Empirical evaluations on real-world datasets demonstrate that our approach achieves comparable or superior ranking performance.
  arXiv  Detail & Related papers  (2025-06-11T06:59:17Z)
• Federated Distributionally Robust Optimization for Phase Configuration of RISs [106.4688072667105]
  We study the problem of robust reconfigurable intelligent surface (RIS)-aided downlink communication over heterogeneous RIS types in a supervised learning setting. By modeling downlink communication over heterogeneous RIS designs as different workers that learn how to optimize phase configurations in a distributed manner, we solve this distributed learning problem. Our proposed algorithm requires fewer communication rounds to achieve the same worst-case distribution test accuracy compared to competitive baselines.
  arXiv  Detail & Related papers  (2021-08-20T07:07:45Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.