Reinforcement Learning Enhanced LLM Agents for Complex Vehicle Routing Problems

The VRPs aim to determine the optimal routes for a fleet of vehicles serving a set of customers. Formally, the problem is represented on a directed graph $G=(V,E)$, where $V={0,1,\dots,N}$ denotes the set of nodes (node $0$ is the depot, and $V_{c}=\{1,\dots,N\}$ are the customers), and $E=\{(i,j)\mid i,j\in V,i\neq j\}$ defines the edges. Each edge $(i,j)$ has an associated travel cost $c_{ij}$, representing the distance between nodes $i$ and $j$. The binary decision variable $x_{ij}$ is 1 if a vehicle travels from node $i$ to $j$, and 0 otherwise. The objective is to minimize the total travel cost, expressed as:

This objective is subject to several constraints:

Eq. (2) ensures each customer is visited by exactly one vehicle, and Eq. (3) ensures the depot flow conservation, with the same number of vehicles returning to the depot. We also consider nine additional VRP constraints based on real-world variants encountered in practical applications [12]: 1) Capacity, the vehicle load limit; 2) Open routes, where vehicles don’t have to return to the depot; 3) Distance limit, the total travel distance cannot exceed a specified bound; 4) Service time, each customer requires a specific service time; 5) Time window, each customer must be served within a given time frame; 6) Multiple depots, allowing vehicles to start and return to multiple depots; 7) Resource constraints, additional resource limitations; 8) Prize collecting, maximizing rewards while satisfying routing constraints; 9) Pickup and delivery, where pickup must occur before delivery. More details are in Appendix 1.

The goal of this work is to automatically generate solver-ready programs for complex VRP variants. Formally, We model this process as a Markov Decision Process (MDP) augmented with a memory pool, defined by the tuple $\langle\mathcal{S},\mathcal{A},\mathcal{P},\mathcal{R},\gamma,\mathcal{M}\rangle$.

At each step $t$, an agent follows a policy $\pi(a_{t}\mid s_{t})$ to select an action $a_{t}\in\mathcal{A}$ based on the current state $s_{t}\in\mathcal{S}$. Repeated action selection induces a trajectory $\tau=(s_{0},a_{0},s_{1},a_{1},\dots,s_{T})$, which represents the entire process of code generation and refinement. Each state consists of the embeddings of the problem description and the current modeling code, while the action space defines the operations that the agent can invoke to generate or revise the code. After executing an action, the environment transitions to a new state according to the transition probability $\mathcal{P}(s_{t+1}\mid s_{t},a_{t})$. The reward function $\mathcal{R}$ evaluates the quality and feasibility of the generated code. In addition, a memory pool $\mathcal{M}$ stores historical experiences, allowing the agent to learn from past successes and failures.

To improve exploration and avoid premature convergence to sub-optimal actions, we adopt the Soft Q-Learning framework [9]. This approach augments the standard reinforcement learning objective with an entropy regularization term, encouraging stochastic policies and better exploration. The resulting objective is defined as:

where $\tau$ denotes a trajectory of states, actions, and rewards generated by the policy, $H$ denotes the entropy, and $\alpha$ is a weighting coefficient that regulates the impact of the entropy. The discount factor $\gamma\in[0,1]$ balances immediate rewards with long-term optimization performance.

We propose Reinforcement Learning Enhanced LLM Agents (RLEA), a multi-agent framework for automatic VRP modeling. As illustrated in Figure 1, RLEA consists of three main components: a neural Planner, an LLM-based Executor, and a Memory module. The Planner selects actions based on the current problem state, the Executor carries out the selected action to generate or revise code, and the memory module continuously evolves historical interaction trajectories into reusable experience for future decision-making.

We next describe the action space, followed by the training strategy of the Planner and the inference procedure.

To support automatic VRP modeling in complex settings, we design an action space $\mathcal{A}$ consisting of three actions: Refine, Retrieval-Augmented Generation (RAG), and Meta-Learning with Evolved Memory (MLEM). These actions are designed to address three key requirements in solver-oriented program generation: iterative error correction, the incorporation of external solver knowledge, and the reuse of evolved experience. Detailed prompts are provided in Appendix 2. Below we describe the mechanics of each action.

Static LLM-based decision-making pipelines are often insufficient for complex VRP modeling [14], where the most effective action depends on both the problem context and the current code state. This makes adaptive decision-making essential. In addition, the evolving memory pool is initially sparse, so the MLEM action $a_{m}$ may provide limited benefit in early training, which can further suppress exploration if a fixed action strategy is used. To address these challenges, RLEA employs a lightweight neural Planner trained with Soft Q-learning, enabling adaptive action selection without incurring the high cost of LLM-based decision-making at every interaction step.

The Planner learns a stochastic policy $\pi_{\theta}(a_{t}\mid s_{t})$ over the action space $\mathcal{A}=\{a_{r},a_{g},a_{m}\}$, corresponding to Refine, RAG, and MLEM, respectively. The detailed definitions of these actions are given in Section 4.2. The policy is induced by a soft Q-network through the Boltzmann distribution:

where $\alpha>0$ is the temperature parameter controlling the exploration–exploitation trade-off. A larger $\alpha$ encourages broader exploration over candidate actions, which is particularly beneficial in the early stage when evolved memory is not yet sufficiently informative, whereas a smaller $\alpha$ leads to more greedy action selection.

During training, the planner interacts with the environment to generate a trajectory $\tau$. To guide policy optimization, we design a dense reward based on the optimality gap. Let $y_{t}^{\mathrm{obj}}$ denote the objective value of the solution obtained at step $t$. The relative optimality gap $\delta_{t}$ is defined as

where $y^{*}$ denotes the reference optimal objective value obtained from expert benchmarks. To encourage high-quality solutions while explicitly penalizing execution failures, the reward $r_{t}$ is defined as

This reward is bounded in $(0,1]$ for valid solutions and approaches 1 as the solution converges to the optimum.

The Planner is parameterized by a soft Q-network $Q_{\theta}(s,a)$. Its input state is the embedding of the current problem context, including the VRP variant description and the current modeling code, extracted by a frozen open-source small language model. The Planner is trained by minimizing the soft Bellman residual. Specifically, the soft temporal-difference target is defined as

where $d_{t}\in\{0,1\}$ is the termination flag, $\gamma\in[0,1]$ is the discount factor, and $Q_{\bar{\theta}}$ denotes the target network. The training objective is

where $\mathcal{B}$ is the experience replay buffer. Meanwhile, memory evolution proceeds in parallel with policy optimization. The replay buffer $\mathcal{B}$ is used exclusively for reinforcement learning updates, whereas the memory pool $\mathcal{M}$ is maintained separately to accumulate and evolve historical interaction records for the MLEM action.

During inference, the Planner parameters $\theta$ are frozen. Given a target VRP variant, the executor first attempts to generate solver-ready code from the problem description directly. If this initial attempt fails to produce a valid code, the problem description together with the generated code is encoded as the initial state for the Planner.

Starting from this state, the Planner performs a forward pass and selects actions from the action space $\mathcal{A}$ according to the learned policy. Conditioned on the selected actions, the Executor iteratively generates or refines the modeling code for the target problem. In this way, the Planner serves as a lightweight decision-making module that orchestrates the interaction process without requiring costly LLM-based deliberation at every step.

We impose a maximum number of steps $T_{max}$. The procedure terminates early once the generated code successfully invokes the solver and produces a solution whose relative optimality gap is below 5%. This mechanism prevents infinite refinement loops while still allowing sufficient opportunities for the agent to correct modeling or syntax errors.

Table 1 reports the performance of RLEA and five representative baselines in terms of Success Rate (SR) and Runtime Error Rate (RER) on both OR-Tools and Gurobi solvers.

Methods that rely solely on the internal knowledge of LLMs, including Standard Prompting, CoT, and Self-Refine, achieve limited performance, indicating that complex VRP variants are difficult to model accurately without domain-specific knowledge. CoE produces the lowest rates on SR due to its focus on Mixed-Integer Programming rather than complex VRPs, it maintains a remarkably low RER suggesting the potential of the multi-agent framework. By incorporating external solver documentation, DRoC improves performance over these methods, demonstrating the importance of domain-specific knowledge retrieval.

Our method achieves the best overall performance. On OR-Tools, RLEA reaches an SR of 62.50%, outperforming the previous state-of-the-art DRoC by 16.67%, while also significantly reducing runtime errors. Although the generated solutions are not always optimal, they already provide valid solver implementations, allowing human developers to focus on solution improvement rather than constructing models from scratch. This improvement stems from the synergy of the learned Planner policy, external knowledge retrieval, evolved memory, and the refine mechanism, which together enable effective error correction and solution refinement.

In the online inference setting, the performance is slightly lower than in the offline setting but still surpasses all baselines. This difference is mainly due to the dynamic updating of the memory pool during inference, which introduces additional stochasticity in the learning process. However, this dynamic memory mechanism encourages broader exploration and ultimately contributes to a further reduction in runtime errors.

We conduct ablation studies to evaluate the contribution of key components in RLEA, including the neural Planner and the action modules. The results are presented in Table 2 and Table 3.

The experimental results in Table 4 reveal a clear performance advantage in heterogeneous multi-agent collaboration, specifically validating the optimal division of Action (reasoning-intensive models) and Memory (general-purpose models). The DeepSeek-r1 (Action) and GPT-4o (Memory) configuration achieves a peak Success Rate (SR) of 62.50%, demonstrating that DeepSeek-r1 demonstrates its ability to leverage reasoning capabilities for the effective modeling of complex VRPs, while GPT-4o provides a robust contextual foundation for retrieval.

Conversely, when assigning GPT-4o to execute action and DeepSeek-r1 to manage the memory modules, the SR to drop to 45.83%. This suggests that DeepSeek-r1’s intensive reasoning may be counterproductive for memory distillation, where its tendency toward over-deliberation introduces noise that hinders concise information flow. Furthermore, all single-model setups exhibit significant performance bottlenecks, such as the standalone GPT-4o’s low 37.50% SR. These findings underscore that decoupling roles within a multi-agent framework prevents the cognitive overload inherent in single-agent architectures, allowing specialized LLMs to leverage their distinct strengths for superior collective performance.

We analyze the effect of the maximum number of interaction iterations on performance using OR-Tools. Since the action space contains three actions, the minimum number of iterations is set to 3. As shown in Figure 3, performance improves steadily as the number of iterations increases from 3 to 6: the SR rises from 34.15% to 62.50%, while the RER decreases from 43.90% to 16.67%.

When the iteration number reaches 6, the framework achieves its best performance. Further increasing the iteration budget brings only marginal gains. This suggests that excessive iterations may lead to over-searching or algorithmic stagnation, where the added computational cost no longer yields better performance.