Source-linked AI summary
Reinforcement Learning Enhanced LLM Agents for Complex Vehicle Routing Problems
Yi Chen, Zikang Yu, Jiahai Wang, Jinbiao Chen, Jianpeng Zhou, Zizhen Zhang
TL;DR
Complex VRP variants are difficult to model for expert solvers without substantial domain expertise, limiting access to advanced optimization tools. RLEA combines a reinforcement-learning Planner with LLM agents, retrieval, and evolved memory for automated modeling, achieving higher success and fewer runtime errors than the previous state-of-the-art method.
Problem
Modeling complex VRP variants for solver execution requires substantial domain expertise, limiting accessibility to advanced optimization technologies.
Method
RLEA uses a multi-agent framework with a lightweight Soft Q-learning Planner, retrieval-augmented generation, evolved memory, and iterative refinement to generate solver-ready programs.
Results
16.67% higher success rate and 10.41% lower runtime error rate were achieved by RLEA than by DRoC across 48 distinct VRP variants.
Takeaways & Limitations
RLEA's results support integrating reinforcement learning with LLM-based reasoning for automated optimization modeling of complex VRPs.
Abstract
from arXiv · showhide
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.
1 Introduction
Complex VRP variants are increasingly relevant but harder to solve as constraints grow, while solver-ready modeling remains expertise-intensive. RLEA addresses this accessibility problem by combining LLM agents with reinforcement learning, retrieval, and evolved memory for automated modeling.
- Complex VRP variants better reflect real-world scenarios but become harder to solve as their constraints increase.
- Automatic modeling transforms VRP constraints into programs that directly invoke expert solvers, but traditionally requires substantial domain expertise.
- RLEA is a multi-agent framework that integrates reinforcement learning with LLM agents to generate solver-ready programs for complex VRP variants.
- Its lightweight Soft Q-learning Planner selects agent actions, while retrieval and evolvable memory support efficient exploration and more robust modeling.
- 16.67% higher success rate and 10.41% lower runtime error rate were achieved by RLEA than by the SOTA method DRoC across 48 VRP variants.
2 Related Work
Automatic modeling methods either generate mathematical formulations before code or directly generate executable solver code. RLEA extends the code-only direction with a learned Planner, retrieval-augmented knowledge, and evolved memory to improve efficiency and robustness.
- Existing automatic modeling methods are categorized by whether they generate an explicit mathematical formulation before implementing executable code.
- Formulation-first pipelines improve interpretability but can add error-prone reasoning steps for specialized optimization tasks.
- Code-only methods directly map problem descriptions to executable solver code, with DRoC using solver documentation and constraint-specific knowledge through RAG.
- RLEA addresses code-only limitations by using a lightweight neural Planner to orchestrate LLM-driven actions more efficiently.
- RLEA combines policy learning, retrieval-augmented knowledge, and evolved memory for more efficient and robust automatic modeling of complex VRP variants.
3 Preliminaries
VRPs optimize vehicle routes on a directed graph while satisfying routing and real-world variant constraints. The paper models automated program generation as a memory-augmented MDP and uses Soft Q-learning to encourage exploration.
- VRPs determine routes for vehicles serving customers, represented on a directed graph with depot, customer nodes, travel costs, and binary routing variables.
- The objective minimizes total travel cost subject to constraints ensuring customer coverage and depot flow conservation.
- Nine additional variants include capacity, open routes, distance limits, service times, time windows, multiple depots, resource constraints, prize collecting, and pickup-delivery precedence.
- Automated solver-program generation is formulated as a Markov Decision Process augmented with a memory pool of historical experiences.
- Soft Q-learning adds entropy regularization to encourage stochastic policies and better exploration, while γ balances immediate rewards against long-term performance.
4 Methodology
RLEA combines a neural Planner, an LLM Executor, and an evolving memory module to generate and refine solver-ready programs for complex VRP variants. Its action space supports iterative correction, external solver-knowledge retrieval, and reuse of prior experience, while Soft Q-learning selects actions adaptively.
- Overview: RLEA coordinates a neural Planner, an LLM-based Executor, and a Memory module for automated VRP modeling.The Planner selects actions, the Executor generates or revises code, and memory evolves interaction trajectories into reusable experience.
- Action Space: Its three actions are Refine, Retrieval-Augmented Generation, and Meta-Learning with Evolved Memory.They target iterative error correction, external solver knowledge, and reuse of evolved experience.
- Refine: Refine iteratively checks generated code against required constraints, identifies failures, and revises the program.This action addresses erroneous code and incomplete constraint implementations through debugging-style self-correction.
- Retrieval-Augmented Generation: RAG decomposes the problem into atomic constraints and retrieves documentation using constraint-specific queries before code generation or revision.The Executor filters retrieved candidates, summarizes relevant references, and conditions modeling code on documentation associated with all constraints.
- Meta-Learning with Evolved Memory: MLEM collects execution feedback and distills similar successful and failed cases into demonstrations for adapting to new problem settings.The Collector appends success summaries or failure analyses, while the Memory Distiller retrieves relevant historical experience for the Executor.
- Policy Optimization: Soft Q-learning trains the Planner to select among actions from states encoding the VRP description and current modeling code.The entropy temperature α controls exploration, with larger values encouraging broader exploration when evolved memory is sparse.
5 Experiments
The experiments evaluate RLEA across 48 VRP variants using two optimization solvers and compare it with five representative baselines under matched inference budgets. Performance is assessed primarily through successful feasible execution and runtime errors.
- Experimental Setup: Experiments cover 48 VRP variants composed of different constraint combinations.Evaluations use a Tesla A40 GPU and an Intel i5-7500 CPU.
- Baselines: The comparison includes Direct Generation, Self-Refine, Chain-of-Thought, Chain-of-Experts, and DRoC.These baselines represent standard prompting, reasoning-based methods, formulation-first modeling, and code-only generation.
- Experimental Setup: RLEA is evaluated with Gurobi and OR-Tools under offline and online inference settings.Offline inference uses a pretrained memory pool, whereas online inference dynamically constructs and updates memory during testing.
- Experimental Setup: All baselines receive the same iteration budget, and reported results average three independent runs.Inference uses a maximum of Tmax = 6 interaction steps.
- Performance Metrics: Success Rate measures valid solver execution with a feasible solution, while Runtime Error Rate measures failures from syntax errors, API misuse, or logical flaws.A successful instance requires generated code to execute and yield a feasible solution with a valid objective value.
5.2 Main Results
RLEA achieves the strongest overall performance in the reported comparisons, outperforming prior approaches while reducing runtime errors. Its online setting remains ahead of all baselines, although performance is slightly below offline inference.
- Baseline Comparison: Internal-knowledge-only methods achieve limited performance on complex VRP variants without domain-specific knowledge.The comparison includes Standard Prompting, Chain-of-Thought, and Self-Refine.
- Baseline Comparison: DRoC improves over these methods by incorporating external solver documentation during code generation.This comparison supports the importance of domain-specific knowledge retrieval for complex VRP modeling.
- Main Results: RLEA reaches an SR of 62.50% on OR-Tools, outperforming DRoC by 16.67% while significantly reducing runtime errors.The result is reported as the best overall performance among the compared methods.
- Inference Settings: Online inference performs slightly below offline inference but still surpasses all baselines.Dynamic memory updates introduce additional stochasticity while encouraging broader exploration and reducing runtime errors.
5.3 Ablation Study
The paper conducts ablation studies to assess the contributions of the neural Planner and action modules in RLEA.
- Ablation Study: Ablation studies evaluate the contributions of the neural Planner and action modules using results reported in Tables 2 and 3.
Ablation on the Planner
The Planner ablation compares learned, random, and prompt-based action selection, showing that the learned policy achieves the strongest success performance with faster decisions than prompting.
- Ablation on the Planner: Random action selection is represented by the w/o Planner variant, while prompting DeepSeek-Reasoner supplies the alternative prompt-based strategy.
- Ablation on the Planner: RLEA achieves the highest Success Rate among the Planner variants, indicating that its learned policy captures action-selection patterns across VRP variants.
- Ablation on the Planner: The prompt-based Planner attains a reasonable success rate but incurs higher inference latency than RLEA’s neural Planner.
- Ablation on the Planner: RLEA’s slightly higher Runtime Error Rate reflects a trade-off between aggressive exploration and execution stability.
Ablation on action module
Action-module ablations show that the full framework performs best, with Refine most critical and RAG and MLEM providing complementary benefits.
- Ablation on action module: The full method achieves the highest Success Rate and lowest Runtime Error Rate among variants lacking individual action modules.
- Ablation on action module: Removing Refine causes the largest performance drop, identifying refinement as the framework’s most critical action.
- Ablation on action module: Refine accounts for 50.65% of executed actions on OR-Tools, consistent with its prominent role in correcting modeling and programming errors.
5.5 Sensitivity Analysis of Iterations
OR-Tools performance improves as the interaction budget increases from three to six iterations, after which additional iterations provide only marginal gains.
- 5.5 Sensitivity Analysis of Iterations: The minimum iteration budget is set to 3 because the action space contains three actions.
- 5.5 Sensitivity Analysis of Iterations: From 3 to 6 iterations, Success Rate rises from 34.15% to 62.50% while Runtime Error Rate falls from 43.90% to 16.67%.
- 5.5 Sensitivity Analysis of Iterations: Six iterations deliver the framework’s best performance under the tested OR-Tools interaction budgets.
- 5.5 Sensitivity Analysis of Iterations: Further increasing the iteration budget brings only marginal gains and may incur over-searching or algorithmic stagnation.
6 Conclusion
RLEA automates modeling and solving for complex VRPs by combining reinforcement learning with multi-agent reasoning, retrieval, and evolved memory. Across 48 VRP variants, it achieves a 62.50% success rate and a 16.67% gain over the previous state of the art.
- 6 Conclusion: RLEA is a multi-agent framework for automating the modeling and solving of complex VRPs.
- 6 Conclusion: Its lightweight Soft Q-Learning Planner reduces computational overhead by enabling rapid Executor actions.
- 6 Conclusion: The hybrid memory mechanism combines evolutionary trajectory analysis with external retrieval-augmented knowledge for self-correction of constraint conflicts.
- 6 Conclusion: 62.50% success across 48 VRP variants represents a 16.67% performance gain over the previous state of the art.
- 6 Conclusion: Future work will examine multimodal VRP inputs and dynamic real-time routing with evolving constraints.