Reinforcement Learning Enhanced LLM Agents for Complex Vehicle Routing Problems

• URL: http://arxiv.org/abs/2609.00859v1
• Date: Tue, 01 Sep 2026 07:56:15 GMT
• Title: Reinforcement Learning Enhanced LLM Agents for Complex Vehicle Routing Problems
• Abstract summary: Vehicle Routing Problems (VRPs) are fundamental optimization problems with widespread applications in various scenarios.<n>We propose Reinforcement Learning Enhanced LLMAgents(RLEA), a multi-agent framework designed to automate the modeling of complex VRPs.
• Score: 22.538946344456857
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Vehicle Routing Problems (VRPs) are fundamental combinatorial optimization problems with widespread applications in various scenarios. The advanced optimization solvers can effectively solve such problems. However, modeling complex VRP variants for solvers often requires substantial domain expertise, which limits the accessibility of advanced optimization technologies. In this paper, we propose Reinforcement Learning Enhanced LLMAgents(RLEA), a multi-agent framework designed to automate the modeling of complex VRPs. RLEA introduces a lightweight neural Planner trained with Soft Q-learning to efficiently orchestrate the actions of LLM-based agents. In addition, we equip the system with an evolutionary memory module and retrieval-augmented generation, enabling the agent to leverage both accumulated experience and external solver knowledge during program generation and refinement for solving VRPs. We evaluated 48 distinct VRP variants across various solvers. The experimental results demonstrate that RLEA outperforms the previous state-of-the-ar method, achieving a 16.67% higher success rate while significantly reducing runtime errors. These results validate that integrating reinforcement learning with LLM-based reasoning is highly effective for automated optimization modeling. The appendix is available at: https://doi.org/10.5281/zenodo.19134435.

Related papers

• PyVRP$^+$: LLM-Driven Metacognitive Heuristic Evolution for Hybrid Genetic Search in Vehicle Routing Problems [30.443372626623887]
  We introduce Metacognitive Programming (MEP), a framework that elevates a large language model to a strategic discovery agent.<n>Our results show that MEP discoverss that yield significant performance gains over the original HGS baseline, improving solution quality by up to 2.70% and reducing runtime by over 45% on challenging VRP variants.
  arXiv  Detail & Related papers  (2026-04-09T06:36:15Z)
• Enhancing CVRP Solver through LLM-driven Automatic Heuristic Design [16.7839584177637]
  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.
  arXiv  Detail & Related papers  (2026-02-26T15:12:23Z)
• An Agentic Framework with LLMs for Solving Complex Vehicle Routing Problems [66.60904891478687]
  We propose an Agentic Framework with LLMs (AFL) for solving complex vehicle routing problems.<n>AFL directly extracts knowledge from raw inputs and enables self-contained code generation.<n>We show that AFL substantially outperforms existing LLM-based baselines in both code reliability and solution feasibility.
  arXiv  Detail & Related papers  (2025-10-19T03:59:25Z)
• 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)
• Improving Retrospective Language Agents via Joint Policy Gradient Optimization [57.35348425288859]
  RetroAct is a framework that jointly optimize both task-planning and self-reflective evolution capabilities in language agents.<n>We develop a two-stage joint optimization process that integrates imitation learning and reinforcement learning.<n>We conduct extensive experiments across various testing environments, demonstrating RetroAct has substantial improvements in task performance and decision-making processes.
  arXiv  Detail & Related papers  (2025-03-03T12:54:54Z)
• Scaling Autonomous Agents via Automatic Reward Modeling And Planning [52.39395405893965]
  Large language models (LLMs) have demonstrated remarkable capabilities across a range of tasks.<n>However, they still struggle with problems requiring multi-step decision-making and environmental feedback.<n>We propose a framework that can automatically learn a reward model from the environment without human annotations.
  arXiv  Detail & Related papers  (2025-02-17T18:49:25Z)
• A Multi-AI Agent System for Autonomous Optimization of Agentic AI Solutions via Iterative Refinement and LLM-Driven Feedback Loops [3.729242965449096]
  This paper introduces a framework for autonomously optimizing Agentic AI solutions across industries.<n>The framework achieves optimal performance without human input by autonomously generating and testing hypotheses.<n>Case studies show significant improvements in output quality, relevance, and actionability.
  arXiv  Detail & Related papers  (2024-12-22T20:08:04Z)
• From Novice to Expert: LLM Agent Policy Optimization via Step-wise Reinforcement Learning [62.54484062185869]
  We introduce StepAgent, which utilizes step-wise reward to optimize the agent's reinforcement learning process.<n>We propose implicit-reward and inverse reinforcement learning techniques to facilitate agent reflection and policy adjustment.
  arXiv  Detail & Related papers  (2024-11-06T10:35:11Z)
• Machine Learning Insides OptVerse AI Solver: Design Principles and Applications [74.67495900436728]
  We present a comprehensive study on the integration of machine learning (ML) techniques into Huawei Cloud's OptVerse AI solver. We showcase our methods for generating complex SAT and MILP instances utilizing generative models that mirror multifaceted structures of real-world problem. We detail the incorporation of state-of-the-art parameter tuning algorithms which markedly elevate solver performance.
  arXiv  Detail & Related papers  (2024-01-11T15:02:15Z)
• 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.