# Reinforcement Learning Enhanced LLM Agents for Complex Vehicle Routing Problems

arXiv: https://arxiv.org/abs/2609.00859 · HTML: https://mlsanity.com/paper/2609.00859/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in Reinforcement learning for LLM agents, one of 16 directions in LLM agents and tool use.
- Builds on 20 of its 30 references that are in the map.
- First posted on arXiv 1 Sep 2026.

## Placed in

- LLM agents and tool use / [Reinforcement learning for LLM agents](https://mlsanity.com/agents/reinforcement-learning-for-llm-agents/)

## Builds on (most cited first, 20 of 20)

- [Self-Refine: Iterative Refinement with Self-Feedback](https://mlsanity.com/paper/2303.17651/) (2023)
- [Reinforcement Learning with Deep Energy-Based Policies](https://mlsanity.com/paper/1702.08165/) (2017)
- [ReEvo: Large Language Models as Hyper-Heuristics with Reflective Evolution](https://mlsanity.com/paper/2402.01145/) (2024)
- [Evolution of Heuristics: Towards Efficient Automatic Algorithm Design Using Large Language Model](https://mlsanity.com/paper/2401.02051/) (2024)
- [NL4Opt Competition: Formulating Optimization Problems Based on Their Natural Language Descriptions](https://mlsanity.com/paper/2303.08233/) (2023)
- [OptiMUS: Scalable Optimization Modeling with (MI)LP Solvers and Large Language Models](https://mlsanity.com/paper/2402.10172/) (2024)
- [Monte Carlo Tree Search for Comprehensive Exploration in LLM-Based Automatic Heuristic Design](https://mlsanity.com/paper/2501.08603/) (2025)
- [LLMOPT: Learning to Define and Solve General Optimization Problems from Scratch](https://mlsanity.com/paper/2410.13213/) (2024)
- [Learning Generalizable Models for Vehicle Routing Problems via Knowledge Distillation](https://mlsanity.com/paper/2210.07686/) (2022)
- [Large Language Models as End-to-end Combinatorial Optimization Solvers](https://mlsanity.com/paper/2509.16865/) (2025)
- [Neural Combinatorial Optimization Algorithms for Solving Vehicle Routing Problems: A Comprehensive Survey with Perspectives](https://mlsanity.com/paper/2406.00415/) (2024)
- [Solving General Natural-Language-Description Optimization Problems with Large Language Models](https://mlsanity.com/paper/2407.07924/) (2024)
- [BOPO: Neural Combinatorial Optimization via Best-anchored and Objective-guided Preference Optimization](https://mlsanity.com/paper/2503.07580/) (2025)
- [ARS: Automatic Routing Solver with Large Language Models](https://mlsanity.com/paper/2502.15359/) (2025)
- [MoniTor: Exploiting Large Language Models with Instruction for Online Video Anomaly Detection](https://mlsanity.com/paper/2510.21449/) (2025)
- [PhGPO: Pheromone-Guided Policy Optimization for Long-Horizon Tool Planning](https://mlsanity.com/paper/2602.13691/) (2026)
- [Synthesis of Mathematical programs from Natural Language Specifications](https://mlsanity.com/paper/2304.03287/) (2023)
- [Phase-Aware Mixture of Experts for Agentic Reinforcement Learning](https://mlsanity.com/paper/2602.17038/) (2026)
- [An Agentic Framework with LLMs for Solving Complex Vehicle Routing Problems](https://mlsanity.com/paper/2510.16701/) (2025)
- [Learning a Prior for Monte Carlo Search by Replaying Solutions to Combinatorial Problems](https://mlsanity.com/paper/2401.10431/) (2024)

## Built on by (most cited first, 1 of 1)

- [SCA: Spatial Credit Assignment for Reinforcement Learning of GUI Agents](https://mlsanity.com/paper/2609.36939/) (2026)

## Abstract (arXiv)

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.