Enhancing CVRP Solver through LLM-driven Automatic Heuristic Design

• URL: http://arxiv.org/abs/2602.23092v1
• Date: Thu, 26 Feb 2026 15:12:23 GMT
• Title: Enhancing CVRP Solver through LLM-driven Automatic Heuristic Design
• Authors: Zhuoliang Xie, Fei Liu, Zhenkun Wang, Qingfu Zhang,
• Abstract summary: This study presents AILS-AHD, a novel approach that leverages Large Language Models (LLMs) to revolutionize CVRP solving.<n>Our methodology integrates an evolutionary search framework with LLMs to dynamically generate and optimize ruins within the AILS method.<n>Our approach establishes new best-known solutions for 8 out of 10 instances in the CVRPLib large-scale benchmark.
• Score: 16.7839584177637
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Capacitated Vehicle Routing Problem (CVRP), a fundamental combinatorial optimization challenge, focuses on optimizing fleet operations under vehicle capacity constraints. While extensively studied in operational research, the NP-hard nature of CVRP continues to pose significant computational challenges, particularly for large-scale instances. This study presents AILS-AHD (Adaptive Iterated Local Search with Automatic Heuristic Design), a novel approach that leverages Large Language Models (LLMs) to revolutionize CVRP solving. Our methodology integrates an evolutionary search framework with LLMs to dynamically generate and optimize ruin heuristics within the AILS method. Additionally, we introduce an LLM-based acceleration mechanism to enhance computational efficiency. Comprehensive experimental evaluations against state-of-the-art solvers, including AILS-II and HGS, demonstrate the superior performance of AILS-AHD across both moderate and large-scale instances. Notably, our approach establishes new best-known solutions for 8 out of 10 instances in the CVRPLib large-scale benchmark, underscoring the potential of LLM-driven heuristic design in advancing the field of vehicle routing optimization.

Related papers

• Hierarchical Optimization via LLM-Guided Objective Evolution for Mobility-on-Demand Systems [9.979671028876464]
  We propose a novel framework that integrates large language model (LLM) with mathematical optimization in a dynamic hierarchical system.<n>Within this framework, LLM serves as a meta-optimizer, producing semantics that guide a low-level responsible for constraint enforcement and real-time decision execution.<n>Experiments based on both the New York and Chicago taxi datasets demonstrate the effectiveness of our approach.
  arXiv  Detail & Related papers  (2025-10-12T14:56:19Z)
• Experience-Guided Reflective Co-Evolution of Prompts and Heuristics for Automatic Algorithm Design [124.54166764570972]
  Combinatorial optimization problems are traditionally tackled with handcrafted algorithms.<n>Recent progress has highlighted the potential of automatics design powered by large language models.<n>We propose the Experience-Evolution Reflective Co-Guided of Prompt and Heuristics (EvoPH) for automatic algorithm design.
  arXiv  Detail & Related papers  (2025-09-29T09:24:09Z)
• Hybrid Learning and Optimization methods for solving Capacitated Vehicle Routing Problem [3.652509571098291]
  The Capacitated Vehicle Routing Problem (CVRP) is a fundamental NP-hard problem in logistics.<n>We propose a hybrid optimization approach that integrates deep reinforcement learning (RL) to automate the selection of penalty parameter values within both classical (RL-C-ALM) and quantum-enhanced (RL-Q-ALM) ALM solvers.
  arXiv  Detail & Related papers  (2025-09-18T08:38:29Z)
• Agentic Reinforced Policy Optimization [66.96989268893932]
  Large-scale reinforcement learning with verifiable rewards (RLVR) has demonstrated its effectiveness in harnessing the potential of large language models (LLMs) for single-turn reasoning tasks.<n>Current RL algorithms inadequately balance the models' intrinsic long-horizon reasoning capabilities and their proficiency in multi-turn tool interactions.<n>We propose Agentic Reinforced Policy Optimization (ARPO), a novel agentic RL algorithm tailored for training multi-turn LLM-based agents.
  arXiv  Detail & Related papers  (2025-07-26T07:53:11Z)
• Preference Optimization for Combinatorial Optimization Problems [54.87466279363487]
  Reinforcement Learning (RL) has emerged as a powerful tool for neural optimization, enabling models learns that solve complex problems without requiring expert knowledge.<n>Despite significant progress, existing RL approaches face challenges such as diminishing reward signals and inefficient exploration in vast action spaces.<n>We propose Preference Optimization, a novel method that transforms quantitative reward signals into qualitative preference signals via statistical comparison modeling.
  arXiv  Detail & Related papers  (2025-05-13T16:47:00Z)
• A Large Language Model-Enhanced Q-learning for Capacitated Vehicle Routing Problem with Time Windows [3.0518581575184225]
  This paper proposes a novel Q-learning framework to address the Capacitated Vehicle Routing Problem with Time Windows (CVRPTW)<n>Our framework achieves a 7.3% average reduction in cost compared to traditional Q-learning, with fewer training steps required for convergence.
  arXiv  Detail & Related papers  (2025-05-09T16:45:43Z)
• TeLL-Drive: Enhancing Autonomous Driving with Teacher LLM-Guided Deep Reinforcement Learning [61.33599727106222]
  TeLL-Drive is a hybrid framework that integrates a Teacher LLM to guide an attention-based Student DRL policy.<n>A self-attention mechanism then fuses these strategies with the DRL agent's exploration, accelerating policy convergence and boosting robustness.
  arXiv  Detail & Related papers  (2025-02-03T14:22:03Z)
• Learn to Solve Vehicle Routing Problems ASAP: A Neural Optimization Approach for Time-Constrained Vehicle Routing Problems with Finite Vehicle Fleet [0.0]
  We propose an NCO approach to solve a time-constrained capacitated VRP with a finite vehicle fleet size. The method is able to find adequate and cost-efficient solutions, showing both flexibility and robust generalizations.
  arXiv  Detail & Related papers  (2024-11-07T15:16:36Z)
• Multiobjective Vehicle Routing Optimization with Time Windows: A Hybrid Approach Using Deep Reinforcement Learning and NSGA-II [52.083337333478674]
  This paper proposes a weight-aware deep reinforcement learning (WADRL) approach designed to address the multiobjective vehicle routing problem with time windows (MOVRPTW) The Non-dominated sorting genetic algorithm-II (NSGA-II) method is then employed to optimize the outcomes produced by the WADRL.
  arXiv  Detail & Related papers  (2024-07-18T02:46:06Z)
• DNN Partitioning, Task Offloading, and Resource Allocation in Dynamic Vehicular Networks: A Lyapunov-Guided Diffusion-Based Reinforcement Learning Approach [49.56404236394601]
  We formulate the problem of joint DNN partitioning, task offloading, and resource allocation in Vehicular Edge Computing. Our objective is to minimize the DNN-based task completion time while guaranteeing the system stability over time. We propose a Multi-Agent Diffusion-based Deep Reinforcement Learning (MAD2RL) algorithm, incorporating the innovative use of diffusion models.
  arXiv  Detail & Related papers  (2024-06-11T06:31:03Z)
• Reinforcement Learning for Solving Stochastic Vehicle Routing Problem [0.09831489366502298]
  This study addresses a gap in the utilization of Reinforcement Learning (RL) and Machine Learning (ML) techniques in solving the Vehicle Routing Problem (SVRP) We propose a novel end-to-end framework that comprehensively addresses the key sources of SVRP and utilizes an RL agent with a simple yet effective architecture and a tailored training method. Our proposed model demonstrates superior performance compared to a widely adopted state-of-the-art meeuristic, achieving a significant 3.43% reduction in travel costs.
  arXiv  Detail & Related papers  (2023-11-13T19:46:22Z)

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.