CS Paper Radar

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

Juntao Wei, Yangming Zhou, Zhibin Jiang, Shan Jiang

cs.NE ·submitted 2026-09-02 09:25 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

From Search to Signal: Search-Value Credit for Evolutionary Automatic Heuristic Design

cs.LG cs.AIcs.NE ·2026-09-30 ·Yilun Yuan, Tianyu Zhou, Zhenzhou Tang
similarity 0.69
Abstract · 80 pages, including supplementary material. Substantially revised version introducing Search-Value Credit (SVC), with a redesigned reward me…

Large language models generate candidate programs for automatic heuristic design, while evolutionary search evaluates and selects them to guide further generation. Online post-training uses rewards from candidate evaluations to adapt the generator. Retained programs can also guide later generation as parents. This motivates rewards that reflect their reuse opportunities beyond immediate fitness. We propose Search-value credit (SVC), which constructs response-level rewards from actual admission to the retained set and a short-term parent-exposure proxy. Admission determines reward eligibility; the proxy weights eligible responses by reuse opportunities under existing parent-selection rules. Rewards are computed after candidate evaluation, without evaluating descendants. SVC retains the search and learning procedures of the Co-Evolution of Algorithms and Language Model (CALM) framework. Across four combinatorial optimization tasks with the same base model and response budget, SVC achieves the best mean final search performance on three tasks among six conditions. Under identical prompts and parents on traveling salesman and capacitated vehicle routing tasks, SVC-trained generators yield a higher mean proportion of responses whose programs outperform the best prompting parent than those trained with CALM's native reward. These findings support reward construction using search retention and selection information.

0.24

Directing to Diversify: Multi-Directional Search for Automatic Heuristic Design

cs.AI ·2026-10-22 ·Jianghan Zhu, Jianan Zhou, Fei Liu, Ni Zhang, Yaoxin Wu +2 more
similarity 0.68
Abstract · 46 pages, 9 figures, 19 tables. The main paper, including references, is 13 pages; appendices are included

Large language models (LLMs) have demonstrated strong potential to automate heuristic design for NP-hard combinatorial optimization (CO) tasks without human intervention. Recent methods predominantly rely on evolutionary computation (EC) frameworks, where heuristic diversification is mainly induced through EC-like operators or downstream selection, while the direction of heuristic transformation remains largely unharnessed. In this paper, we propose a multi-directional Perturbation-Rewrite Search (PRS) framework for automatic heuristic design that factorizes heuristic transformation through directional search primitives at the generation level. Specifically, PRS operates on heuristic ideas through three complementary directions: expansion toward richer and more expressive designs, compression toward simpler and less specialized designs, and steering for fine-grained refinement, together enabling broader and more sustained exploration of diverse regions in the heuristic design space. PRS further organizes candidate exploration within a breadth-first search-based process with adaptive operator control, which ensures thorough candidate utilization and sustained exploration, and maintains strong search dynamics while preventing premature convergence. Extensive empirical results across diverse CO tasks show that PRS consistently discovers high-quality heuristics, demonstrating the effectiveness and generality of explicitly directional exploration design.

0.24

Multi-Task Evolution for Zero-Shot Cross-Problem Generalization using LLMs

cs.AI ·2026-10-02 ·Zhuoliang Xie, Changliang Zhou, Genghui Li, Zhenkun Wang
similarity 0.68
Abstract

Designing effective heuristics for diverse combinatorial optimization problems requires substantial expertise and repeated search. Large language models (LLMs) automate heuristic generation and refinement, but heuristic search typically depends on evaluation feedback from the problem being optimized. Generalizing to new problem definitions using only source-task feedback therefore remains a central challenge. We introduce MECo, an LLM-driven multi-task evolutionary framework for zero-shot cross-problem generalization. MECo maintains task-conditioned heuristic populations and uses a transfer gap based on cross-task population performance to guide their interactions. These interactions enable the transfer and recombination of heuristics. A complementary selection criterion then constructs a compact heuristic set by rewarding each member's additional coverage of source combinations. The selected set is applied to target problems without further search or adaptation. Experiments on 32 problem variants across vehicle routing (VRP) and flexible job-shop scheduling (FJSP) show that MECo achieves the lowest mean costs compared with eight automated heuristic design (AHD) baselines under the same budgets. On out-of-domain problems, it outperforms the strongest baseline in each family. Moreover, integrating the framework of MECo with different AHD methods improves their ID and OOD performance in both families, supporting its effectiveness across different methods.

0.20

RouteRepair: Instance-Level Failure Diagnosis and Targeted Repair in LLM-Based Automated Heuristic Design for Routing Optimization

cs.AI ·2026-09-10 ·Binghao Ji, Di Huang, Jiahui Fang, Zhiyuan Liu
similarity 0.65
Abstract · 22 pages, 13 figures, 11 tables

Efficient routing optimization is essential to freight transportation, urban logistics, and shared mobility, where high-quality heuristics are often required under limited computational budgets. Recent large language model (LLM)-based automated heuristic design methods can generate effective routing rules, but aggregate evaluation may mask recurrent failures on particular instance structures. To address this limitation, this study develops RouteRepair, which diagnoses parent-specific weaknesses from instance-level performance and applies targeted modifications to the corresponding heuristic components while protecting behavior that already performs well. Routing evidence, solver behavior, and program context are combined to define bounded repair objectives, and each intervention is validated through matched parent-child evaluation of failure recovery and collateral degradation. Experiments on the traveling salesman problem (TSP) and capacitated vehicle routing problem (CVRP) span constructive search, guided local search, and ant colony optimization. RouteRepair-GLS reduces the mean TSP optimality gap from 1.7476% to 0.7587%, while the constructive CVRP heuristic lowers average route cost by 1.91% relative to the savings heuristic; the generated ACO priors also outperform matched hand-designed priors. These results show that failure-aware, evidence-constrained refinement can improve routing heuristics on difficult instances while preserving performance on cases they already solve well.

0.24

Evolutionary Giant Tour for CVRP using NSE and ML Heuristic]{Evolutionary Giant Tour approach for CVRP using Node Shift Encoding and Machine Learning repair heuristic

cs.NE ·2026-10-01 ·Souad Abdoune, Menouar Boulif
benchmark similarity 0.65
Abstract · 21 pages, 16 figures

The Capacitated Vehicle Routing Problem (CVRP) remains a central concern in logistics research, as route optimisation under rigid capacity and fleet restrictions directly affects operational performance. Genetic Algorithms are widely used for this problem, yet their effectiveness depends heavily on the choice of solution encoding and on the mechanisms used to preserve feasibility during the search. This paper proposes a sequential framework that separates the evolutionary process from route construction. We adapt Node Shift Encoding (NSE) to the CVRP giant-tour setting and benchmark it against Path Representation and Double Chromosome. We further propose an unsupervised machine-learning repair heuristic that restores fleet feasibility after an unconstrained linear split, and compare this pipeline against fleet-constrained split taken from the literature. Computational tests on standard benchmark instances show that NSE consistently outperforms the other encodings in solution quality and feasibility. The repair heuristic restores feasibility in approximately 72\% of cases, and the Linear-Split-ML-Heuristic pipeline proves more robust than the constrained split, delivering lower costs and higher feasibility rates.

0.28

Just Initialize: A Training-Free Initialization Component for Large-Scale Routing Optimization

cs.AI ·2026-09-28 ·Jiale Zhao, Sirui Mao, Zimu Chen, Wentao Yang, Zihan Wang +3 more
similarity 0.64
Abstract · 31 pages, 5 figures

Large-scale routing problems are difficult to solve efficiently as their search spaces grow rapidly with problem size. Existing approaches primarily improve the optimization procedure itself, often at increasing computational cost. We instead shift the focus to a useful initialization that can be refined into a high-quality solution with limited downstream refinement. We propose Just Initialize, a training-free and solver-agnostic initialization component for large-scale routing optimization. Just Initialize compresses a large routing instance into a compact surrogate space, optimizes its global routing structure, and recovers the resulting solution as an optimization-friendly starting point in the original space. Extensive experiments on Traveling Salesman Problems (TSPs), Capacitated Vehicle Routing Problems (CVRPs), Vehicle Routing Problems with Time Windows (VRPTWs), and Prize-Collecting Traveling Salesman Problems (PCTSPs) demonstrate that Just Initialize achieves high-quality solutions comparable to or better than state-of-the-art methods while substantially reducing computational cost across instances ranging from 1K to 100K nodes, including an average speedup of approximately 70$\times$, sub-second runtimes on 10K-node instances, and runtimes within tens of seconds on 100K-node instances.

0.19

Tailoring Optimization Approaches with Domain Knowledge in Industry Process for Meta-heuristic Development

cs.NE cs.AI ·2026-11-10 ·Jakub Cebula, Konrad Gmyrek, Paweł B. Myszkowski, Marko Đurasević, Łukasz P. Olech +1 more
similarity 0.63
Abstract

The paper presents an Industry Process for Meta-heuristic Development (IPMD) schema, a systematic methodology for applying meta- and hyper-heuristic applications to optimization problems. In this context, we present a case study of Balancing Non-dominated Tournament Genetic Programming (BNTGP) applied to solve two NP-hard multi-objective optimization problems: routing (Capacitated Vehicle Routing Problem with Time Windows) and scheduling (Multi-Skill Resource Constrained Project Scheduling Problem). The BNTGP method is based on a metaheuristic design. Its genetic programming-based representation makes BNTGP a hyper-heuristic, as it enables the exploration of a search space of heuristics for solving problems in general. The resulting heuristic can then be applied across a set of problem instances.

0.21

Smart routes: a system for development and comparison of algorithms for solving vehicle routing problems with realistic constraints

cs.LG ·2026-08-14 ·Andrew Soroka, German Mikhelson, Alexander Mescheryakov, Sergey Gerasimov
published similarity 0.59
Abstract

The problem of route optimization with realistic constraints is becoming extremely relevant in the face of global urban population growth. While we are aware of approaches that theoretically provide an exact optimal solution, their application becomes challenging as the problem size increases because of exponential complexity. We investigate the Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) and compare solutions obtaining by exact solver SCIP with heuristic algorithms such as LKH, 2-OPT, 3-OPT, the ORTools framework, and the deep learning model JAMPR. We demonstrate that for problem of size 50 deep learning and classical heuristic solutions became close to SCIP exact solution but requires less time. Additionally for problems with size 100, SCIP exact methods around 13 times slower that neural and classical heuristics with the same route cost and on around 50% worse for the first feasible solution on the same time. To conduct experiments, we developed the Smart Routes platform for solving route optimization problems, which includes exact, heuristic, and deep learning models, and facilitates convenient integration of custom algorithms and datasets.

0.22