VRPAgent: LLM-Driven Discovery of Heuristic Operators for Vehicle Routing Problems

## Abstract

Abstract Designing high-performing heuristics for vehicle routing problems (VRPs) is a complex task that requires both intuition and deep domain knowledge. Large language model (LLM)-based code generation has recently shown promise across many domains, but it still falls short of producing heuristics that rival those crafted by human experts. In this paper, we propose VRPAgent , a framework that integrates LLM-generated components into a metaheuristic and refines them through a novel genetic search. By using the LLM to generate problem-specific operators, embedded within a generic metaheuristic framework, VRPAgent keeps tasks manageable, guarantees correctness, and still enables the discovery of novel and powerful strategies. Across multiple problems, including the capacitated VRP, the VRP with time windows, and the prize-collecting VRP, our method discovers heuristic operators that outperform handcrafted methods and recent learning-based approaches while requiring only a single CPU core. To our knowledge, VRPAgent is the first LLM-based paradigm to advance the state-of-the-art in VRPs, highlighting a promising future for automated heuristics discovery.

## 1 Introduction

Solving combinatorial optimization problems requires sophisticated solution approaches. This is especially true for vehicle routing problems (VRPs), where real-world instances often involve complex constraints and a large number of customers. Over the past decades, operations researchers have developed countless heuristics to address these problems (Konstantakopoulos et al., 2022). Designing a new method that meaningfully improves upon the state of the art across multiple problems is extremely challenging, requiring years of experience and a deep understanding of both general heuristics and the specific problem at hand. Practitioners face similar challenges when applying heuristics. Real-world applications often involve ever-changing requirements that are not supported by existing solution methods. Adapting approaches from the literature to such requirements is a time-consuming and challenging task, and is often considered impractical, even by large companies.

In recent years, neural combinatorial optimization (NCO) has garnered increasing attention due to its potential to automate the discovery of effective heuristics(Bello et al., 2017; Bengio et al., 2021). NCO approaches aim to solve optimization problems by training deep neural networks, typically with reinforcement learning. While NCO methods have demonstrated the ability to learn powerful solution strategies for various combinatorial problems, they also come with notable limitations. First, they require expensive GPUs at test time, which restricts their practical deployment. Second, scalability remains a major challenge as their reliance on attention mechanisms makes it difficult to apply these models to problems that involve processing full distance matrices. Finally, the learned strategies are often difficult for experts to interpret, which raises concerns about their safety and reliability in real-world applications.

The recent advent of performant large language models (LLMs) has enabled new opportunities for automation in general algorithmic design across domains ranging from code synthesis to symbolic planning and mathematical discovery (Madaan et al., 2023). LLMs have proven to be a promising approach for discovering new heuristics in combinatorial optimization problems: they can be used to design new heuristics from scratch or adapt existing ones to real-world requirements, enabling customized solutions at a fraction of the cost of an operations research (OR) expert. Among pioneering works, Romera-Paredes et al. (2024); Liu et al. (2024a); Ye et al. (2025) propose evolutionary frameworks that iteratively evolve general CO problem heuristics. Recent research has focused on increasingly sophisticated approaches for automating heuristic discovery (Dat et al., 2025; Zheng et al., 2025; Yang et al., 2025b; Novikov et al., 2025; Liu et al., 2025). Although these works provide valuable contributions, the discovered heuristics still fall short of those designed by human experts for VRPs. We identify key limitations in most of these works: the design of end-to-end functions, the absence of correctness guardrails and overall solution frameworks, and inefficient exploration of the search space, which leads to a failure in challenging the state-of-the-art.

We introduce VRPAgent, a novel approach that uses LLMs to design heuristic operators for a large neighborhood search (LNS). The high-level LNS is designed to be largely problem-agnostic, allowing our framework to tackle new problems by creating new heuristic operators with minimal human input. To discover strong operators for the LNS, we employ a genetic algorithm (GA) with elitism and biased crossover that iteratively improves operator quality. By focusing on a metaheuristic framework where only problem-specific operators are generated via LLMs, we keep the generation task manageable and effective, while still enabling strong performance on complex problems. We evaluate our method on the capacitated vehicle routing problem (CVRP), the vehicle routing problem with time windows (VRPTW), and the prize-collecting VRP (PCVRP). Our approach discovers heuristic operators for all problems that significantly outperform those designed by human experts.

In summary, we make the following contributions with VRPAgent:

- •
We propose an LNS-based metaheuristic in which the problem-specific heuristic operators are generated by an LLM.
- •
We introduce a simple GA for heuristic discovery featuring elitism with biased crossover for improved exploitation, and a code length penalty to reduce LLM inference costs.
- •
We show that VRPAgent discovers strong heuristics across multiple tasks. To the best of our knowledge, it is the first LLM-based approach to advance the state-of-the-art in VRPs.

## 2 Related Work

##### Traditional Heuristics

VRPs are ubiquitous problems in logistics that have been studied for decades. Large and richly constrained instances remain difficult to solve to optimality within a practical time frame, and thus heuristics are commonly used in real-world settings (Santini et al., 2023). LNS and its adaptive variants are particularly influential, iteratively destroying and repairing parts of a solution (Shaw, 1998; Schrimpf et al., 2000; Christiaens & Vanden Berghe, 2020). Other well-known approaches include LKH3 (Helsgaun, 2017) and hybrid genetic search (HGS) (Vidal, 2022; Wouda et al., 2024). While capable of producing high-quality solutions, these approaches take significant expertise to design and implement, motivating the need for automating their design.

##### Neural Combinatorial Optimization

NCO aims to automate heuristic design by training neural networks from data or via reinforcement learning (Bengio et al., 2021; Berto et al., 2025a; Li et al., 2025b). NCO approaches can be broadly divided into construction and improvement methods. Construction methods such as pointer networks (Vinyals et al., 2015; Bello et al., 2017) and subsequent attention-based models for VRPs (Kool et al., 2019; Kwon et al., 2020; Kim et al., 2022; Berto et al., 2025b; Huang et al., 2025a) generate complete solutions quickly in an autoregressive manner, with recent works including enhancements for diversity (Grinsztajn et al., 2023; Hottung et al., 2025a) and out-of-distribution robustness (Drakulic et al., 2023; Luo et al., 2023). Improvement methods instead refine existing solutions at test time, for example, by learning local edits (Ma et al., 2021), guiding $k$-opt moves (Wu et al., 2022; de O. da Costa et al., 2020; Ma et al., 2023), or integrating with metaheuristic approaches as LNS (Hottung & Tierney, 2020) or ant colony optimization (Ye et al., 2023; Kim et al., 2025). Divide-and-conquer frameworks further extend scalability to large instances (Kim et al., 2021; Li et al., 2021; Ye et al., 2024; Ouyang et al., 2025). Hottung et al. (2025b) adopts a LNS approach with learned heuristics for deconstruction and ordering VRP nodes, showing competitive results against state-of-the-art solvers.
Despite continuous progress, most NCO work still falls short of state-of-the-art handcrafted solvers and requires expensive GPU resources, motivating our use of LLM-generated operators as a lightweight alternative.

##### Automated Heuristic Discovery

The goal of automatically discovering high-performing heuristics is a long-standing challenge in optimization (Muth, 1963). Early works include genetic programming and hyper-heuristics, which construct new solution methods by combining or tuning a set of low-level heuristic components (Burke et al., 2006; 2013) and grammar-based generation (Mascia et al., 2014).
The recent advent of LLMs has enabled a new wave of automation for algorithmic design across domains ranging from code synthesis to symbolic planning and mathematical discovery (Madaan et al., 2023; Shinn et al., 2023; Novikov et al., 2025). Early works in heuristic discovery with LLMs including Romera-Paredes et al. (2024); Liu et al. (2024a) employ evolutionary approaches that generate heuristic code snippets for simple heuristics in combinatorial problems, including vehicle routing, packing, and scheduling. Building on this trend, reflection-augmented evolution demonstrates the ability to discover more sophisticated heuristics during the refinement process (Ye et al., 2025). Orthogonal search strategies further expand the design space: diversity-driven evolution (Dat et al., 2025), Monte Carlo tree search (Zheng et al., 2025), ensembling of different LLMs (Novikov et al., 2025), meta-prompt optimization (Shi et al., 2025),
and portfolio-style discovery of sets of complementary heuristics (Yang et al., 2025b; Liu et al., 2025). More specifically for VRPs, Tran et al. (2025) design heuristics to enhance NCO model decoding. In parallel, finetuning and instruction specialization of LLMs for algorithmic synthesis have been proposed to improve reliability and sample efficiency (Šurina et al., 2025; Huang et al., 2025b; Chen et al., 2025b), and benchmark suites have begun to standardize evaluation protocols for LLM-driven heuristics (Liu et al., 2024b; Sun et al., 2025; Feng et al., 2025; Li et al., 2025a; Chen et al., 2025a).

Despite encouraging progress, LLM-generated heuristics still lag behind traditional solvers and NCO methods alike on VRPs, especially under tight time budgets and realistic constraints. We identify three recurring limitations: (i) weak “agentic playground” formulations that ask LLMs to design small heuristic snippets without an overall solution framework; (ii) weak or absent correctness guards around generated code; and (iii) inefficient exploration that drifts toward verbose, brittle implementations. Our approach follows the principle of keeping AI agents on a leash: we constrain the search to problem-specific operators nested within a robust, correctness-enforcing metaheuristic. VRPAgent’s design keeps the synthesis task tractable, preserves feasibility, and still enables the discovery of novel operators that can advance the state-of-the-art for VRP solving.

## 3 Vehicle Routing Problems

VRPs are a fundamental class of combinatorial optimization problems with the aim to minimize travel costs while respecting some constraints. Travel cost is usually measured by the total distance traveled. Formally, a VRP is defined on a graph $G=(V,E)$, where each node $i\in V$ denotes a customer and each edge $(i,j)\in E$ models traveling from $i$ to $j$ with an associated cost, e.g., the distance between $i$ and $j$. All routes originate from and end at the depot node 0.
In the CVRP, vehicles performing the routes have a limited capacity. The total demand on any route cannot exceed the vehicle’s capacity $C$ at any time, and every customer is served exactly once.
The VRPTW extends this setting, assigning a service time $s_{i}$ and a time window $[t_{i}^{l},t_{i}^{r}]$ to each customer $i$. The service to any customer must start within their time window, i.e., if a vehicle arrives before a customer’s time window starts, it has to wait until $t_{i}^{l}$.
The PCVRP relaxes the requirement of visiting all customers. Servicing a customer $i$ is associated with a prize $p_{i}$. The objective is to maximize the total collected prize while minimizing travel cost.

## 4 VRPAgent

VRPAgent is a framework for solving VRPs that automatically discovers strong heuristic operators using LLMs. It is built on two main components. The first ([Section˜4.1](https://arxiv.org/html/2510.07073v1#S4.SS1)) is an LNS (Shaw, 1998) variant for VRPs, which relies on heuristic operators to improve solutions iteratively. At test time, this LNS produces solutions for VRP instances on a single CPU core. The second component ([Section˜4.2](https://arxiv.org/html/2510.07073v1#S4.SS2)) is a GA used in a discovery phase to generate these heuristic operators. In the discovery phase, operator implementations are iteratively created, modified, and refined with the help of an LLM. Classic genetic operations such as crossover and mutation are applied to operator implementations, with the LLM carrying out these transformations. Each generated operator is evaluated by inserting it into the LNS and testing the resulting search performance on a set of training instances. The performance on these instances defines the fitness value of the individual. Over successive generations, the GA produces increasingly effective heuristic operators. [Fig.˜1](https://arxiv.org/html/2510.07073v1#S4.F1) shows a high-level overview of VRPAgent.

Figure: Figure 1: VRPAgent overview.
Refer to caption: x1.png

### 4.1 Large Neighborhood Search with LLM-generated Operators

VRPAgent employs an LNS with LLM-generated operators to find solutions for VRPs. The high-level LNS guides the search process and ensures feasibility by acting as a safeguard around the LLM-generated code. In short, the LNS works by repeatedly removing a set of customers from their tours, ordering the removed customers, and reinserting them one by one at their locally optimal positions. The removal and ordering strategies are defined by LLM-written heuristic operators.

[Algorithm˜1](https://arxiv.org/html/2510.07073v1#alg1) presents the pseudocode of our LNS. The algorithm begins by generating an initial solution $s$ for a given instance $l$. For all routing problems, this initial solution is constructed with one tour per customer. The solution is then iteratively improved until a termination criterion is met. In each iteration, $s$ is first destroyed by removing customers from their tours using the LLM-generated removal operator $f_{\textsc{Remove}}$. This yields an incomplete solution $s^{\prime}$ in which the removed customers are unassigned. Next, the removed customers are ordered by the LLM-generated operator $f_{\textsc{Order}}$. They are then reinserted one by one in that order, always placed at the locally optimal position. That is, the insertion that increases the objective value as little as possible. Finally, an acceptance decision is made: $s^{\prime}$ replaces $s$ if it is better, or it may alternatively be accepted according to a simulated annealing rule. After all iterations, the algorithm returns the final solution $s$.

Figure: Algorithm 1 VRPAgent-LNS

### 4.2 Heuristic Discovery

VRPAgent discovers heuristic operators using a simple GA that is heavily focused on exploitation. Given the very large search space and limited search budget, this bias toward exploitation proves highly beneficial, leading to significant improvements in our experiment. Each individual in our GA represents an implementation of the operator pair $(f_{\textsc{Remove}},f_{\textsc{Order}})$ as C++ code. During the discovery phase, new individuals are created through the means of mutation and crossover. To evaluate an individual, we run VRPAgent-LNS using its operator pair on a set of training instances.

[Algorithm˜2](https://arxiv.org/html/2510.07073v1#alg2) outlines the core logic of our GA. It takes as input the initial population size $N_{\text{init}}$, the number of elites $N_{\text{E}}$, and the number of offspring $N_{\text{C}}$ generated in each iteration.
The algorithm begins by creating an initial population of heuristic operators and then enters the main evolutionary loop, which runs until a termination criterion is reached.
At the start of each iteration, all individuals are evaluated, and the top $N_{\text{E}}$ are selected as elites. Next, $N_{\text{C}}$ offspring are created by pairing one elite with one non-elite individual and combining them using biased crossover. This crossover favors the elite parent while still injecting diversity from the non-elite.

Figure: Algorithm 2 VRPAgent-GA

Each elite is refined through mutation. Unlike standard GAs, where mutation is typically applied to offspring to promote exploration, we apply it directly to elites. These mutations are small, making the procedure more exploitation-focused. If a mutated elite achieves better fitness, it replaces the original; otherwise, the original is kept. This replacement rule ensures that mutated elites do not accumulate in the population, thereby preventing premature convergence.
Finally, the next generation is formed by combining the elites with the newly generated offspring. The process repeats until termination, after which the best heuristic operator discovered is returned. We describe the initialization, crossover, mutation, and fitness evaluation steps in the following paragraphs.

##### Initial Population Generation

The initial population is created by prompting the LLM to generate implementations of the two operators. For this, the LLM is provided with a global system context that explains the overall problem and the LNS, a trivial example implementation of both operators, and technical details of the LNS implementation in the form of C++ header files that allow operators to access shared variables and methods efficiently (see LABEL:lst:system_prompt, LABEL:lst:seed_code_prompt and LABEL:lst:cvrp_headers_prompt in [Appendix˜A](https://arxiv.org/html/2510.07073v1#A1)).

##### Biased Crossover

The offspring are produced by combining two parents through crossover. We use biased crossover, which pairs an elite individual with a non-elite one. The LLM is given both their implementations and is prompted to take most ideas and concepts from the implementation of the elite individuals and only a predefined $\%$ from the implementation of the non-elite individual. This adaptation of standard crossover significantly increases exploitation. The complete crossover instruction provided to the LLM corresponds to LABEL:lst:system_prompt and LABEL:lst:crossover_prompt in [Appendix˜A](https://arxiv.org/html/2510.07073v1#A1).

##### Mutation

VRPAgent uses mutation to slightly modify elite implementations. Following Liu et al. (2024a), we implement multiple mutation prompts that focus on different areas of improvement for better exploration. More precisely, the LLM is given the implementation that should be modified together with one randomly selected mutation prompt (LABEL:lst:mutation_adjust_prompt, LABEL:lst:mutation_extend_prompt, LABEL:lst:mutation_ablation_prompt and LABEL:lst:mutation_refactor_prompt in [Appendix˜A](https://arxiv.org/html/2510.07073v1#A1)) and the global system context LABEL:lst:system_prompt. The four supported mutations include Ablation (i.e., removing a random mechanic), Extend (i.e., adding a new mechanic), Adjust-Parameters (i.e., changing the hyperparameter settings), and Refactor (i.e, modify the code so that the runtime is improved).

##### Fitness Function with Code Length Penalty

We evaluate an individual $i$ by running VRPAgent-LNS with the operator pair defined by $i$ on a set of training instances $I^{\text{train}}$. The resulting solutions are then used to compute the fitness value. Specifically, the fitness of $i$ is defined as the average objective value across all training instances, plus a penalty proportional to the length (i.e., number of lines) of the corresponding implementation $\mathcal{C}_{i}$:

$$ $\text{Fit}(i)\;=\;\frac{1}{|I^{\text{train}}|}\sum_{j\in I^{\text{train}}}\text{Obj}(s_{i,j})\;+\;\lambda\cdot\text{Len}(\mathcal{C}_{i}),$ (1) $$

where $s_{i,j}$ is the solution obtained by applying VRPAgent-LNS with the operators of individual $i$ to training instance $j$, and $\lambda$ controls the strength of the code length penalty.

The penalty helps prevent uncontrolled growth in implementation size, which we observed when no regularization was applied. More compact implementations are also easier for humans to interpret and maintain, making the generated heuristics more useful in practice. Finally, a shorter code reduces the number of tokens processed by the LLM during generation, which in our experiments lowers token usage by more than 50%, and thus significantly reduces generation costs and latency.

## 5 Experiments

We evaluate VRPAgent on three vehicle routing problems: the CVRP, the VRPTW, and the PCVRP. The best discovered heuristics are made publicly available in our online repository at [https://github.com/ai4co/vrpagent](https://github.com/ai4co/vrpagent).

##### VRPAgent Hyperparameters

During the discovery phase we use the following parameters unless stated otherwise: elite size $N_{E}=10$, offspring size $N_{C}=30$, an initial population size of $N_{\text{init}}=100$. The code length penalty factor is set to $\lambda=2\cdot 10^{-4}$ and the discovery phase is terminated after 40 iterations. Individuals are evaluated with VRPAgent-LNS on a training set of $64$ instances, each with $500$ customers, using a runtime limit of $20$s per instance. We employ Gemini 2.5 Flash (Comanici et al., 2025) as the LLM.

### 5.1 Comparison to State-of-the-Art

##### Benchmark Setup

We evaluate all methods on the three problems using instance sets of 500, 1000, and 2000 customers. To ensure consistency, we adopt the same test instances and baseline configurations as described in Hottung et al. (2025b) using a single core of an AMD Milan 7763 processor and an additional single NVIDIA A100 for approaches that require a GPU. For a fair comparison, we limit the search by runtime when possible. The operators used by VRPAgent are obtained from 10 discovery runs per problem (conducted on instances of size 500 only), with the best operator selected based on performance on a separate validation set.

##### Baselines

We compare VRPAgent to several established operations research solvers: HGS (Vidal, 2022), SISRs (Christiaens & Vanden Berghe, 2020), and LKH3 (Helsgaun, 2017). We also include PyVRP (Wouda et al., 2024) (version 0.9.0), an open-source extension of HGS that supports additional VRP variants, and the recent GPU-based NVIDIA cuOpt (NVIDIA Corporation, 2025). For the CVRP, we further consider learning-based approaches that require GPUs at test time: BQ (Drakulic et al., 2023), LEHD (Luo et al., 2023), UDC (Zheng et al., 2024), and NDS (Hottung et al., 2025b). In addition, we compare against LLM-based methods that learn a construction heuristic, including EoH (Liu et al., 2024a), MCTS-AHD (Zheng et al., 2025), and ReEvo (Ye et al., 2025). These approaches only generate a single solution with runtime values <1 second and do not benefit from additional search budget. We further compare to two stronger LLM-based baselines that do leverage search, ReEvo-ACO, which combines LLM-generated heuristics with the Ant Colony Optimization (ACO) metaheuristic, and NCO-LLM (Tran et al., 2025), which enhances LEHD by automating the design of output logit reshaping for test-time search.

**Table 1: Performance on test data. The gap is calculated relative to SISRs. Runtime is reported on a per-instance basis in seconds. The best results (i.e., those with the lowest objective function value) are shown in bold, and the second-best are underlined. * Indicates that feasible solution were not found for all instances.**
| Method | N=500 | N=1000 | N=2000 |  |  |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Obj.$\downarrow$ | Gap$\downarrow$ | Time | Obj.$\downarrow$ | Gap$\downarrow$ | Time | Obj.$\downarrow$ | Gap$\downarrow$ | Time |  |  |  |
| CVRP | SISRs | CPU | 36.65 | - | 60 | 41.14 | - | 120 | 56.04 | - | 240 |
| HGS | CPU | 36.66 | 0.00% | 60 | 41.51 | 0.84% | 121 | 57.38 | 2.33% | 241 |  |
| LKH$3$ | CPU | 37.25 | 1.66% | 174 | 42.16 | 2.46% | 408 | 58.12 | 3.70% | 1448 |  |
| NVIDIA cuOpt | CPU+GPU | 37.38 | 1.98% | 60 | 42.71 | 3.78% | 121 | 59.22 | 5.66% | 241 |  |
| BQ (BS64) | CPU+GPU | 37.51 | 2.34% | 23 | 43.32 | 5.30% | 164 | - | - | - |  |
| LEHD (RRC) | CPU+GPU | 37.04 | 1.06% | 60 | 42.47 | 3.25% | 121 | 60.11 | 7.25% | 246 |  |
| UDC | CPU+GPU | 37.63 | 2.69% | 60 | 42.65 | 3.68% | 121 | - | - | - |  |
| NDS | CPU+GPU | 36.57 | -0.20% | 60 | 41.11 | -0.07% | 120 | 56.00 | -0.07% | 240 |  |
| EoH | CPU | 45.89 | 25.21% | <1 | 52.42 | 27.42% | <1 | 71.21 | 27.07% | <1 |  |
| MCTS-AHD | CPU | 45.51 | 24.17% | <1 | 52.49 | 27.59% | <1 | 71.15 | 26.96% | <1 |  |
| ReEvo | CPU | 44.21 | 20.63% | <1 | 52.23 | 26.96% | <1 | 70.01 | 24.93% | <1 |  |
| ReEvo-ACO | CPU | 40.25 | 9.83% | 60 | 46.22 | 12.34% | 120 | 63.76 | 13.77% | 240 |  |
| NCO-LLM | CPU+GPU | 36.93 | 0.76% | 60 | 41.96 | 1.99% | 121 | 59.43 | 6.05% | 246 |  |
|  | VRPAgent | CPU | 36.60 | -0.12% | 60 | 41.06 | -0.19% | 120 | 55.98 | -0.11% | 240 |
| VRPTW | SISRs | CPU | 48.09 | - | 60 | 87.68 | - | 120 | 167.49 | - | 240 |
| PyVRP-HGS | CPU | 49.01 | 1.91% | 60 | 90.35 | 3.08% | 120 | 173.46 | 3.62% | 240 |  |
| NVIDIA cuOpt | CPU+GPU | 49.30 | 2.60% | 61 | 90.31 | 3.11% | 121 | 173.52 | 3.85%* | 243 |  |
| NDS | CPU+GPU | 47.94 | -0.30% | 60 | 87.54 | -0.16% | 120 | 167.48 | -0.00% | 240 |  |
| EoH | CPU | 60.40 | 25.60% | <1 | 118.80 | 35.49% | <1 | 245.70 | 46.70% | <1 |  |
| MCTS-AHD | CPU | 58.31 | 21.25% | <1 | 113.72 | 29.70% | <1 | 231.11 | 37.98% | <1 |  |
| ReEvo | CPU | 58.01 | 20.63% | <1 | 110.55 | 26.08% | <1 | 218.90 | 30.69% | <1 |  |
| ReEvo-ACO | CPU | 52.91 | 10.03% | 60 | 97.39 | 11.07% | 120 | 193.13 | 15.31% | 240 |  |
| VRPAgent | CPU | 47.97 | -0.24% | 60 | 87.40 | -0.33% | 120 | 166.96 | -0.33% | 240 |  |
| PCVRP | SISRs | CPU | 43.22 | - | 60 | 81.12 | - | 120 | 158.17 | - | 240 |
| PyVRP-HGS | CPU | 44.97 | 4.10% | 60 | 84.91 | 4.81% | 120 | 165.56 | 4.78% | 240 |  |
| NVIDIA cuOpt | CPU+GPU | 43.34 | 0.19% | 60 | 81.89 | 0.84% | 121 | 160.33 | 1.22% | 241 |  |
| NDS | CPU+GPU | 43.12 | -0.23% | 60 | 80.99 | -0.17% | 121 | 158.09 | -0.06% | 241 |  |
| VRPAgent | CPU | 43.18 | -0.09% | 60 | 80.95 | -0.21% | 120 | 157.69 | -0.32% | 240 |  |

[Table˜1](https://arxiv.org/html/2510.07073v1#S5.T1) presents the results of our experiments. On instances with $1000$ and $2000$ customers, VRPAgent outperforms all other methods across all problem types, achieving gaps of around $-0.30\%$ relative to the state-of-the-art SISRs. This represents a substantial improvement that can translate into significant savings in large-scale, real-world scenarios.
On smaller instances, VRPAgent approaches the performance of NDS, which relies on an expensive GPU at test time and is trained specifically for each instance size. Compared to other LLM-based methods, VRPAgent consistently demonstrates significantly better performance across all test cases.

### 5.2 Analyses

##### Ablation Studies

Figure: Figure 2: Ablation results.
Refer to caption: x2.png

We analyze the contribution of key components in our GA by disabling or replacing them.
Specifically, we test three variants: (i) replacing our biased crossover with a standard crossover, where the LLM is instructed to take roughly half the elements from each parent, (ii) removing mutation while increasing offspring size to maintain a comparable population, and (iii) replacing our entire GA with the GA of ReEvo (Ye et al., 2025), which uses a reflection mechanism. Each variant is tested on the CVRP 10 times, and results are averaged. [Fig.˜2](https://arxiv.org/html/2510.07073v1#S5.F2) reports performance on the training set during the discovery phase. Across all cases, modifications lead to reduced performance. Biased crossover is particularly important: by favoring elite solutions while still incorporating elements from weaker parents, it balances exploitation and exploration and drives faster convergence. Removing mutation lowers final solution quality, and replacing our GA with ReEvo’s yields the weakest results, confirming that our combination of elitism, biased crossover, and mutation is essential for discovering high-quality heuristics.

##### Performance Across Different LLMs

We study the performance of VRPAgent when paired with different LLMs. We conduct discovery runs of 20 iterations each for the CVRP using six models. We access Gemini 2.0 Flash and Gemini 2.5 Flash (Comanici et al., 2025) via API, while Qwen3 (Yang et al., 2025a), Llama 3.3 (Grattafiori et al., 2024), Gemma 3 (Team et al., 2025), and gpt-oss (Agarwal et al., 2025) are served locally via vLLM (Kwon et al., 2023). [Fig.˜3](https://arxiv.org/html/2510.07073v1#S5.F3) reports the average objective value on the training set during discovery (left) and the total computational cost per run (right). All tested models substantially improve the heuristic operators throughout the discovery process. Gemini 2.5 Flash and gpt-oss both discover heuristics that outperform the state-of-the-art baseline. Gemini 2.5 Flash achieves the best overall results, but at a cost of nearly $20 per run. In contrast, the open-source gpt-oss model, run on two NVIDIA A100 (40GB) GPUs, achieves nearly the same performance under $2 per run.

Figure: Figure 3: Performance on the CVRP for different LLMs. Detailed cost calculations are provided in [Section˜B.1](https://arxiv.org/html/2510.07073v1#A2.SS1).
Refer to caption: x3.png

##### Performance Over the Discovery Process

We analyze the convergence rate of the discovery process with Gemini 2.5 Flash on all three problems across 40 iterations. As a baseline, we report the performance of VRPAgent-LNS when used in combination with handcrafted operators. Specifically, we reimplement the operators from SISRs (Christiaens & Vanden Berghe, 2020), which represent the state of the art in LNS-based routing methods. As shown in [Fig.˜4](https://arxiv.org/html/2510.07073v1#S5.F4), VRPAgent produces heuristics that outperform the state-of-the-art (SOTA) handcrafted operators.

Figure: Figure 4: Performance over the course of the discovery process.
Refer to caption: x4.png

##### Crossover Bias and Elite Size

We evaluate the effect of the crossover bias and elite size $N_{E}$ on the performance of our GA. As shown in [Fig.˜5(a)](https://arxiv.org/html/2510.07073v1#S5.F5.sf1), the best results are achieved with an elite size of $10$ and a crossover bias of $80\%$, indicating that a strong preference for elite mechanics provides a good balance between exploitation and exploration.

##### Code Length Penalty

We investigate the impact of the code length penalty factor $\lambda$ on both the quality and length of the discovered heuristics. Several discovery runs with varying $\lambda$ values reveal that the penalty strongly controls implementation size without substantially degrading performance. For instance, increasing $\lambda$ to $4\cdot 10^{-4}$ reduces the average length of generated heuristics by roughly 50%, while only causing a marginal drop in objective value ([Fig.˜5(b)](https://arxiv.org/html/2510.07073v1#S5.F5.sf2)). These results highlight the importance of the penalty: it prevents unnecessarily long, hard-to-interpret implementations, and reduces LLM generation costs, all while preserving high-quality heuristics.

Figure: ((a))
Refer to caption: x5.png

## 6 Analysis of Discovered Heuristic Operators

We gave the task of analyzing the best discovered heuristic operators for each problem to three coauthors of this paper who have years of experience writing OR heuristics in routing and related fields. The goal of our analysis is to assess the
(1) readability,
(2) coherence and soundness,
(3) maintainability,
(4) interpretability,
(5) and novelty
of the generated heuristic operators. We note that our assessment of the heuristics is not meant to be a thorough scientific analysis that generalizes to other LLMs or optimization problems. We offer a detailed analysis in [Appendix˜C](https://arxiv.org/html/2510.07073v1#A3).

The removal and sorting mechanisms of all three analyzed heuristics can be described as ensemble approaches that use random numbers to choose different (combinations of) heuristics in each iteration. Given the popularity and success of such ensembles in well-known metaheuristics (e.g., adaptive LNS (Pisinger & Ropke, 2019)), it is perhaps not a surprise that we encounter ensembles in the discovered heuristics. We assess the generated heuristics as relatively easy to read and very coherent – all three experts read and understood the heuristics without any comments provided by the LLM. The heuristics are maintainable, however the interpretability is difficult given the way the ensembles are coded, especially due to a sometimes convoluted use of random numbers.

All of the heuristics generated can be said to be novel. We are not aware of any heuristics in the literature exactly matching these algorithms, however we note that the heuristics mainly consist of recombinations of ideas existing in the literature, e.g., SISRs or simple greedy criteria related to distance/demand/time/prizes. Given the complexity of the ensembles, with some having up to nine different component heuristics, a detailed ablation study would be necessary to try to find out which components or combinations of components lead to good performance.

## 7 Conclusion

In this work, we introduced VRPAgent, a metaheuristic framework in which LLMs generate problem-specific operators for a LNS. By focusing on operator generation rather than end-to-end heuristics, VRPAgent makes the discovery task more manageable while achieving strong performance. Using a GA with elitism and biased crossover for algorithm discovery, VRPAgent consistently finds heuristic operators that outperform human-designed approaches on a range of vehicle routing problems. Our results highlight a promising future for automated heuristic discovery, suggesting that LLMs could play a key role in designing efficient and adaptable optimization methods for complex, real-world problems. For future work, we will investigate how to further simplify the generated heuristics to help increase the ease of using VRPAgent generated code in practice.

### Reproducibility Statement

We have made every effort to ensure the reproducibility of our results. Detailed descriptions of configurations, prompts, the discovery pipeline, and overall experimental setups are provided in both the main paper and the appendix to enable independent reproducibility. All code to reproduce the experiments will be made open-source upon acceptance.

### Acknowledgements

André Hottung and Nayeli Gast Zepeda received support from the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under Grant No. 521243122.
This work was also supported by the Institute of Information & Communications Technology Planning & Evaluation (IITP) grant, funded by the Korean government (MSIT) [Grant No. 2022-0-01032, Development of Collective Collaboration Intelligence Framework for Internet of Autonomous Things].
We thank OMELET for providing additional computing resources and API key access to Gemini. Furthermore, we gratefully acknowledge the Paderborn Center for Parallel Computing (PC²) for providing valuable computing time for this project.

## References

- Agarwal et al. (2025)
Sandhini Agarwal, Lama Ahmad, Jason Ai, Sam Altman, Andy Applebaum, Edwin Arbus, Rahul K Arora, Yu Bai, Bowen Baker, Haiming Bao, et al.
gpt-oss-120b & gpt-oss-20b model card.
*arXiv preprint arXiv:2508.10925*, 2025.
URL [https://arxiv.org/abs/2508.10925](https://arxiv.org/abs/2508.10925).
- Bello et al. (2017)
Irwan Bello, Hieu Pham, Quoc V. Le, Mohammad Norouzi, and Samy Bengio.
Neural Combinatorial Optimization with Reinforcement Learning.
In *5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Workshop Track Proceedings*. OpenReview.net, 2017.
URL [https://openreview.net/forum?id=Bk9mxlSFx](https://openreview.net/forum?id=Bk9mxlSFx).
- Bengio et al. (2021)
Yoshua Bengio, Andrea Lodi, and Antoine Prouvost.
Machine learning for combinatorial optimization: A methodological tour d’horizon.
*European Journal of Operational Research*, 290(2):405–421, 2021.
ISSN 0377-2217.
doi: https://doi.org/10.1016/j.ejor.2020.07.063.
URL [https://www.sciencedirect.com/science/article/pii/S0377221720306895](https://www.sciencedirect.com/science/article/pii/S0377221720306895).
- Berto et al. (2025a)
Federico Berto, Chuanbo Hua, Junyoung Park, Laurin Luttmann, Yining Ma, Fanchen Bu, Jiarui Wang, Haoran Ye, Minsu Kim, Sanghyeok Choi, Nayeli Gast Zepeda, André Hottung, Jianan Zhou, Jieyi Bi, Yu Hu, Fei Liu, Hyeonah Kim, Jiwoo Son, Haeyeon Kim, Davide Angioni, Wouter Kool, Zhiguang Cao, Jie Zhang, Kijung Shin, Cathy Wu, Sungsoo Ahn, Guojie Song, Changhyun Kwon, Lin Xie, and Jinkyoo Park.
RL4CO: an Extensive Reinforcement Learning for Combinatorial Optimization Benchmark.
In *Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining*, 2025a.
URL [https://github.com/ai4co/rl4co](https://github.com/ai4co/rl4co).
- Berto et al. (2025b)
Federico Berto, Chuanbo Hua, Nayeli Gast Zepeda, André Hottung, Niels Wouda, Leon Lan, Junyoung Park, Kevin Tierney, and Jinkyoo Park.
RouteFinder: Towards Foundation Models for Vehicle Routing Problems.
*Transactions on Machine Learning Research*, 2025b.
ISSN 2835-8856.
URL [https://openreview.net/forum?id=QzGLoaOPiY](https://openreview.net/forum?id=QzGLoaOPiY).
- Burke et al. (2006)
Edmund K Burke, Matthew R Hyde, and Graham Kendall.
Evolving bin packing heuristics with genetic programming.
In *International Conference on Parallel Problem Solving from Nature*, pp. 860–869. Springer, 2006.
URL [https://link.springer.com/chapter/10.1007/11844297_87](https://link.springer.com/chapter/10.1007/11844297_87).
- Burke et al. (2013)
Edmund K Burke, Michel Gendreau, Matthew Hyde, Graham Kendall, Gabriela Ochoa, Ender Özcan, and Rong Qu.
Hyper-heuristics: A survey of the state of the art.
*Journal of the Operational Research Society*, 64(12):1695–1724, 2013.
URL [https://doi.org/10.1057/jors.2013.71](https://doi.org/10.1057/jors.2013.71).
- Chen et al. (2025a)
Hongzheng Chen, Yingheng Wang, Yaohui Cai, Hins Hu, Jiajie Li, Shirley Huang, Chenhui Deng, Rongjian Liang, Shufeng Kong, Haoxing Ren, Samitha Samaranayake, Carla P. Gomes, and Zhiru Zhang.
Heurigym: An agentic benchmark for LLM-crafted heuristics in combinatorial optimization.
*arXiv preprint arXiv:2506.07972*, 2025a.
URL [https://arxiv.org/abs/2506.07972](https://arxiv.org/abs/2506.07972).
- Chen et al. (2025b)
Yitian Chen, Jingfan Xia, Siyu Shao, Dongdong Ge, and Yinyu Ye.
Solver-informed RL: Grounding large language models for authentic optimization modeling.
In *Advances in Neural Information Processing Systems*, 2025b.
URL [https://arxiv.org/abs/2505.11792v2](https://arxiv.org/abs/2505.11792v2).
- Christiaens & Vanden Berghe (2020)
Jan Christiaens and Greet Vanden Berghe.
Slack induction by string removals for vehicle routing problems.
*Transportation Science*, 54(2):417–433, 2020.
URL [https://pubsonline.informs.org/doi/10.1287/trsc.2019.0914](https://pubsonline.informs.org/doi/10.1287/trsc.2019.0914).
- Comanici et al. (2025)
Gheorghe Comanici, Eric Bieber, Mike Schaekermann, Ice Pasupat, Noveen Sachdeva, Inderjit Dhillon, Marcel Blistein, Ori Ram, Dan Zhang, Evan Rosen, et al.
Gemini 2.5: Pushing the frontier with advanced reasoning, multimodality, long context, and next generation agentic capabilities.
*arXiv preprint arXiv:2507.06261v4*, 2025.
URL [https://arxiv.org/abs/2507.06261v4](https://arxiv.org/abs/2507.06261v4).
- Dat et al. (2025)
Pham Vu Tuan Dat, Long Doan, and Huynh Thi Thanh Binh.
Hsevo: Elevating automatic heuristic design with diversity-driven harmony search and genetic algorithm using llms.
In *Proceedings of the AAAI Conference on Artificial Intelligence*, volume 39, pp. 26931–26938, 2025.
[https://github.com/datphamvn/HSEvo](https://github.com/datphamvn/HSEvo).
- de O. da Costa et al. (2020)
Paulo R. de O. da Costa, Jason Rhuggenaath, Yingqian Zhang, and Alp Akçay.
Learning 2-opt Heuristics for the Traveling Salesman Problem via Deep Reinforcement Learning.
In *Proceedings of The 12th Asian Conference on Machine Learning*, Proceedings of Machine Learning Research, pp. 465–480. PMLR, 2020.
URL [http://proceedings.mlr.press/v129/costa20a/costa20a.pdf](http://proceedings.mlr.press/v129/costa20a/costa20a.pdf).
- Drakulic et al. (2023)
Darko Drakulic, Sofia Michel, Florian Mai, Arnaud Sors, and Jean-Marc Andreoli.
BQ-NCO: Bisimulation Quotienting for Efficient Neural Combinatorial Optimization.
In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (eds.), *Advances in Neural Information Processing Systems*, volume 36, pp. 77416–77429. Curran Associates, Inc., 2023.
URL [https://proceedings.neurips.cc/paper_files/paper/2023/file/f445ba15f0f05c26e1d24f908ea78d60-Paper-Conference.pdf](https://proceedings.neurips.cc/paper_files/paper/2023/file/f445ba15f0f05c26e1d24f908ea78d60-Paper-Conference.pdf).
- Feng et al. (2025)
Shengyu Feng, Weiwei Sun, Shanda Li, Ameet Talwalkar, and Yiming Yang.
A comprehensive evaluation of contemporary ML-based solvers for combinatorial optimization.
*ArXiv*, abs/2505.16952, 2025.
URL [https://arxiv.org/abs/2505.16952](https://arxiv.org/abs/2505.16952).
- Grattafiori et al. (2024)
Aaron Grattafiori, Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Alex Vaughan, et al.
The llama 3 herd of models.
*arXiv preprint arXiv:2407.21783v3*, 2024.
URL [https://arxiv.org/abs/2407.21783v3](https://arxiv.org/abs/2407.21783v3).
- Grinsztajn et al. (2023)
Nathan Grinsztajn, Daniel Furelos-Blanco, Shikha Surana, Clément Bonnet, and Tom Barrett.
Winner Takes It All: Training Performant RL Populations for Combinatorial Optimization.
In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (eds.), *Advances in Neural Information Processing Systems*, volume 36, pp. 48485–48509. Curran Associates, Inc., 2023.
URL [https://proceedings.neurips.cc/paper_files/paper/2023/file/97b983c974551153d20ddfabb62a5203-Paper-Conference.pdf](https://proceedings.neurips.cc/paper_files/paper/2023/file/97b983c974551153d20ddfabb62a5203-Paper-Conference.pdf).
- Helsgaun (2017)
Keld Helsgaun.
An Extension of the Lin-Kernighan-Helsgaun TSP Solver for Constrained Traveling Salesman and Vehicle Routing Problems: Technical report.
dec 2017.
URL [http://www.akira.ruc.dk/˜keld/research/LKH-3/LKH-3_REPORT.pdf](http://www.akira.ruc.dk/~keld/research/LKH-3/LKH-3_REPORT.pdf).
- Hottung & Tierney (2020)
André Hottung and Kevin Tierney.
Neural large neighborhood search for the capacitated vehicle routing problem.
In Giuseppe De Giacomo, Alejandro Catalá, Bistra Dilkina, Michela Milano, Senén Barro, Alberto Bugarín, and Jérôme Lang (eds.), *ECAI 2020 - 24th European Conference on Artificial Intelligence*, volume 325 of *Frontiers in Artificial Intelligence and Applications*, pp. 443–450. IOS Press, 2020.
URL [https://doi.org/10.3233/FAIA200124](https://doi.org/10.3233/FAIA200124).
- Hottung et al. (2025a)
André Hottung, Mridul Mahajan, and Kevin Tierney.
PolyNet: Learning Diverse Solution Strategies for Neural Combinatorial Optimization.
In Y. Yue, A. Garg, N. Peng, F. Sha, and R. Yu (eds.), *International Conference on Learning Representations*, pp. 80417–80435, 2025a.
URL [https://proceedings.iclr.cc/paper_files/paper/2025/file/c7b9810b2e27bccdc8d605a3a54c8cd6-Paper-Conference.pdf](https://proceedings.iclr.cc/paper_files/paper/2025/file/c7b9810b2e27bccdc8d605a3a54c8cd6-Paper-Conference.pdf).
- Hottung et al. (2025b)
André Hottung, Paula Wong-Chung, and Kevin Tierney.
Neural deconstruction search for vehicle routing problems.
*Transactions on Machine Learning Research*, 2025b.
ISSN 2835-8856.
URL [https://openreview.net/forum?id=bCmEP1Ltwq](https://openreview.net/forum?id=bCmEP1Ltwq).
- Huang et al. (2025a)
Ziwei Huang, Jianan Zhou, Zhiguang Cao, and Yixin Xu.
Rethinking light decoder-based solvers for vehicle routing problems.
In *The Thirteenth International Conference on Learning Representations*, 2025a.
URL [https://openreview.net/forum?id=4pRwkYpa2u](https://openreview.net/forum?id=4pRwkYpa2u).
- Huang et al. (2025b)
Ziyao Huang, Weiwei Wu, Kui Wu, Jianping Wang, and Wei-Bin Lee.
CALM: Co-evolution of Algorithms and Language Model for Automatic Heuristic Design, 2025b.
URL [https://arxiv.org/abs/2505.12285](https://arxiv.org/abs/2505.12285).
- Kim et al. (2021)
Minsu Kim, Jinkyoo Park, and Joungho Kim.
Learning Collaborative Policies to Solve NP-hard Routing Problems.
In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), *Advances in Neural Information Processing Systems*, volume 34, pp. 10418–10430. Curran Associates, Inc., 2021.
URL [https://proceedings.neurips.cc/paper_files/paper/2021/file/564127c03caab942e503ee6f810f54fd-Paper.pdf](https://proceedings.neurips.cc/paper_files/paper/2021/file/564127c03caab942e503ee6f810f54fd-Paper.pdf).
- Kim et al. (2022)
Minsu Kim, Junyoung Park, and Jinkyoo Park.
Sym-NCO: Leveraging Symmetricity for Neural Combinatorial Optimization.
In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh (eds.), *Advances in Neural Information Processing Systems*, volume 35, pp. 1936–1949. Curran Associates, Inc., 2022.
URL [https://proceedings.neurips.cc/paper_files/paper/2022/file/0cddb777d3441326544e21b67f41bdc8-Paper-Conference.pdf](https://proceedings.neurips.cc/paper_files/paper/2022/file/0cddb777d3441326544e21b67f41bdc8-Paper-Conference.pdf).
- Kim et al. (2025)
Minsu Kim, Sanghyeok Choi, Hyeonah Kim, Jiwoo Son, Jinkyoo Park, and Yoshua Bengio.
Ant Colony Sampling with GFlowNets for Combinatorial Optimization.
In Yingzhen Li, Stephan Mandt, Shipra Agrawal, and Emtiyaz Khan (eds.), *Proceedings of The 28th International Conference on Artificial Intelligence and Statistics*, volume 258 of *Proceedings of Machine Learning Research*, pp. 469–477. PMLR, 2025.
URL [https://proceedings.mlr.press/v258/kim25a.html](https://proceedings.mlr.press/v258/kim25a.html).
- Konstantakopoulos et al. (2022)
Grigorios D Konstantakopoulos, Sotiris P Gayialis, and Evripidis P Kechagias.
Vehicle routing problem and related algorithms for logistics distribution: A literature review and classification.
*Operational research*, 22(3):2033–2062, 2022.
URL [https://doi.org/10.1007/s12351-020-00600-7](https://doi.org/10.1007/s12351-020-00600-7).
- Kool et al. (2019)
Wouter Kool, Herke van Hoof, and Max Welling.
Attention, Learn to Solve Routing Problems!
In *International Conference on Learning Representations*, 2019.
URL [https://openreview.net/forum?id=ByxBFsRqYm](https://openreview.net/forum?id=ByxBFsRqYm).
- Kwon et al. (2023)
Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph Gonzalez, Hao Zhang, and Ion Stoica.
Efficient Memory Management for Large Language Model Serving with PagedAttention.
In *Proceedings of the 29th Symposium on Operating Systems Principles*, SOSP ’23, pp. 611–626. Association for Computing Machinery, 2023.
URL [https://doi.org/10.1145/3600006.3613165](https://doi.org/10.1145/3600006.3613165).
- Kwon et al. (2020)
Yeong-Dae Kwon, Jinho Choo, Byoungjip Kim, Iljoo Yoon, Youngjune Gwon, and Seungjai Min.
POMO: Policy Optimization with Multiple Optima for Reinforcement Learning.
In *Advances in Neural Information Processing Systems*, volume 33, pp. 21188–21198, 2020.
URL [https://proceedings.neurips.cc/paper_files/paper/2020/file/f231f2107df69eab0a3862d50018a9b2-Paper.pdf](https://proceedings.neurips.cc/paper_files/paper/2020/file/f231f2107df69eab0a3862d50018a9b2-Paper.pdf).
- Li et al. (2021)
Sirui Li, Zhongxia Yan, and Cathy Wu.
Learning to delegate for large-scale vehicle routing.
*Advances in Neural Information Processing Systems*, 34:26198–26211, 2021.
URL [https://proceedings.neurips.cc/paper/2021/file/dc9fa5f217a1e57b8a6adeb065560b38-Paper.pdf](https://proceedings.neurips.cc/paper/2021/file/dc9fa5f217a1e57b8a6adeb065560b38-Paper.pdf).
- Li et al. (2025a)
Xiaozhe Li, Jixuan Chen, Xinyu Fang, Shengyuan Ding, Haodong Duan, Qingwen Liu, and Kai Chen.
Opt-bench: Evaluating llm agent on large-scale search spaces optimization problems, 2025a.
URL [https://arxiv.org/abs/2506.10764](https://arxiv.org/abs/2506.10764).
- Li et al. (2025b)
Yang Li, Jiale Ma, Wenzheng Pan, Runzhong Wang, Haoyu Geng, Nianzu Yang, and Junchi Yan.
Unify ML4TSP: Drawing Methodological Principles for TSP and Beyond from Streamlined Design Space of Learning and Search.
In Y. Yue, A. Garg, N. Peng, F. Sha, and R. Yu (eds.), *International Conference on Representation Learning*, pp. 65269–65305, 2025b.
URL [https://proceedings.iclr.cc/paper_files/paper/2025/file/a3dc6e903082902d8e916bb9fccbfcbc-Paper-Conference.pdf](https://proceedings.iclr.cc/paper_files/paper/2025/file/a3dc6e903082902d8e916bb9fccbfcbc-Paper-Conference.pdf).
- Liu et al. (2024a)
Fei Liu, Tong Xialiang, Mingxuan Yuan, Xi Lin, Fu Luo, Zhenkun Wang, Zhichao Lu, and Qingfu Zhang.
Evolution of heuristics: Towards efficient automatic algorithm design using large language model.
In Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp (eds.), *Proceedings of the 41st International Conference on Machine Learning*, volume 235 of *Proceedings of Machine Learning Research*, pp. 32201–32223. PMLR, 21–27 Jul 2024a.
URL [https://proceedings.mlr.press/v235/liu24bs.html](https://proceedings.mlr.press/v235/liu24bs.html).
- Liu et al. (2024b)
Fei Liu, Rui Zhang, Zhuoliang Xie, Rui Sun, Kai Li, Xi Lin, Zhenkun Wang, Zhichao Lu, and Qingfu Zhang.
LLM4AD: A platform for algorithm design with large language model.
2024b.
URL [https://arxiv.org/abs/2412.17287](https://arxiv.org/abs/2412.17287).
- Liu et al. (2025)
Fei Liu, Yilu Liu, Qingfu Zhang, Xialiang Tong, and Mingxuan Yuan.
EoH-S: Evolution of Heuristic Set using LLMs for Automated Heuristic Design.
*arXiv preprint arXiv:2508.03082*, 2025.
URL [https://doi.org/10.48550/arXiv.2508.03082](https://doi.org/10.48550/arXiv.2508.03082).
- Luo et al. (2023)
Fu Luo, Xi Lin, Fei Liu, Qingfu Zhang, and Zhenkun Wang.
Neural combinatorial optimization with heavy decoder: Toward large scale generalization.
In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (eds.), *Advances in Neural Information Processing Systems*, volume 36, pp. 8845–8864. Curran Associates, Inc., 2023.
URL [https://proceedings.neurips.cc/paper_files/paper/2023/file/1c10d0c087c14689628124bbc8fa69f6-Paper-Conference.pdf](https://proceedings.neurips.cc/paper_files/paper/2023/file/1c10d0c087c14689628124bbc8fa69f6-Paper-Conference.pdf).
- Ma et al. (2021)
Yining Ma, Jingwen Li, Zhiguang Cao, Wen Song, Le Zhang, Zhenghua Chen, and Jing Tang.
Learning to Iteratively Solve Routing Problems with Dual-Aspect Collaborative Transformer.
In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), *Advances in Neural Information Processing Systems*, volume 34, pp. 11096–11107. Curran Associates, Inc., 2021.
URL [https://proceedings.neurips.cc/paper_files/paper/2021/file/5c53292c032b6cb8510041c54274e65f-Paper.pdf](https://proceedings.neurips.cc/paper_files/paper/2021/file/5c53292c032b6cb8510041c54274e65f-Paper.pdf).
- Ma et al. (2023)
Yining Ma, Zhiguang Cao, and Yeow Meng Chee.
Learning to Search Feasible and Infeasible Regions of Routing Problems with Flexible Neural k-Opt.
In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (eds.), *Advances in Neural Information Processing Systems*, volume 36, pp. 49555–49578. Curran Associates, Inc., 2023.
URL [https://proceedings.neurips.cc/paper_files/paper/2023/file/9bae70d354793a95fa18751888cea07d-Paper-Conference.pdf](https://proceedings.neurips.cc/paper_files/paper/2023/file/9bae70d354793a95fa18751888cea07d-Paper-Conference.pdf).
- Madaan et al. (2023)
Aman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan, Luyu Gao, Sarah Wiegreffe, Uri Alon, Nouha Dziri, Shrimai Prabhumoye, Yiming Yang, Shashank Gupta, Bodhisattwa Prasad Majumder, Katherine Hermann, Sean Welleck, Amir Yazdanbakhsh, and Peter Clark.
Self-refine: Iterative refinement with self-feedback.
In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (eds.), *Advances in Neural Information Processing Systems*, volume 36, pp. 46534–46594. Curran Associates, Inc., 2023.
URL [https://proceedings.neurips.cc/paper_files/paper/2023/file/91edff07232fb1b55a505a9e9f6c0ff3-Paper-Conference.pdf](https://proceedings.neurips.cc/paper_files/paper/2023/file/91edff07232fb1b55a505a9e9f6c0ff3-Paper-Conference.pdf).
- Mascia et al. (2014)
Franco Mascia, Manuel López-Ibáñez, Jérémie Dubois-Lacoste, and Thomas Stützle.
Grammar-based generation of stochastic local search heuristics through automatic algorithm configuration tools.
*Computers & Operations Research*, 51:190–199, 2014.
URL [https://doi.org/10.1016/j.cor.2014.05.020](https://doi.org/10.1016/j.cor.2014.05.020).
- Muth (1963)
J Muth.
Probabilistic learning combinations of local job-shop scheduling rules.
*Industrial scheduling*, 1963.
- Novikov et al. (2025)
Alexander Novikov, Ngân Vũ, Marvin Eisenberger, Emilien Dupont, Po-Sen Huang, Adam Zsolt Wagner, Sergey Shirobokov, Borislav Kozlovskii, Francisco JR Ruiz, Abbas Mehrabian, et al.
AlphaEvolve: A coding agent for scientific and algorithmic discovery.
*arXiv preprint arXiv:2506.13131*, 2025.
URL [https://arxiv.org/abs/2506.13131](https://arxiv.org/abs/2506.13131).
- NVIDIA Corporation (2025)
NVIDIA Corporation.
NVIDIA cuOpt: Gpu-accelerated decision optimization.
[https://github.com/NVIDIA/cuopt](https://github.com/NVIDIA/cuopt), 2025.
Accessed: 2025-09-25.
- Ouyang et al. (2025)
Wenbin Ouyang, Sirui Li, Yining Ma, and Cathy Wu.
Learning to segment for vehicle routing problems.
*arXiv preprint arXiv:2507.01037*, 2025.
URL [https://doi.org/10.48550/arXiv.2507.01037](https://doi.org/10.48550/arXiv.2507.01037).
- Pisinger & Ropke (2019)
David Pisinger and Stefan Ropke.
Large neighborhood search.
In Michel Gendreau and Jean-Yves Potvin (eds.), *Handbook of Metaheuristics*, pp. 99–127. Springer International Publishing, Cham, 2019.
URL [https://doi.org/10.1007/978-3-319-91086-4_4](https://doi.org/10.1007/978-3-319-91086-4_4).
- Romera-Paredes et al. (2024)
Bernardino Romera-Paredes, Mohammadamin Barekatain, Alexander Novikov, Matej Balog, M Pawan Kumar, Emilien Dupont, Francisco JR Ruiz, Jordan S Ellenberg, Pengming Wang, Omar Fawzi, et al.
Mathematical discoveries from program search with large language models.
*Nature*, 625(7995):468–475, 2024.
URL [https://doi.org/10.1038/s41586-023-06924-6](https://doi.org/10.1038/s41586-023-06924-6).
- Santini et al. (2023)
Alberto Santini, Michael Schneider, Thibaut Vidal, and Daniele Vigo.
Decomposition strategies for vehicle routing heuristics.
*INFORMS Journal on Computing*, 35(3):543–559, 2023.
URL [https://doi.org/10.1287/ijoc.2023.1288](https://doi.org/10.1287/ijoc.2023.1288).
- Schrimpf et al. (2000)
Gerhard Schrimpf, Johannes Schneider, Hermann Stamm-Wilbrandt, and Gunter Dueck.
Record Breaking Optimization Results Using the Ruin and Recreate Principle.
*Journal of Computational Physics*, 159(2):139–171, 2000.
URL [https://doi.org/10.1006/jcph.1999.6413](https://doi.org/10.1006/jcph.1999.6413).
- Shaw (1998)
Paul Shaw.
Using Constraint Programming and Local Search Methods to Solve Vehicle Routing Problems.
In Michael Maher and Jean-Francois Puget (eds.), *International conference on principles and practice of constraint programming (CP98)*, pp. 417–431, Berlin, Heidelberg, 1998. Springer, Springer Berlin Heidelberg.
URL [https://doi.org/10.1007/3-540-49481-2_30](https://doi.org/10.1007/3-540-49481-2_30).
- Shi et al. (2025)
Yiding Shi, Jianan Zhou, Wen Song, Jieyi Bi, Yaoxin Wu, and Jie Zhang.
Generalizable Heuristic Generation Through Large Language Models with Meta-Optimization.
*arXiv preprint arXiv:2505.20881*, 2025.
URL [https://arxiv.org/abs/2505.20881](https://arxiv.org/abs/2505.20881).
- Shinn et al. (2023)
Noah Shinn, Federico Cassano, Ashwin Gopinath, Karthik Narasimhan, and Shunyu Yao.
Reflexion: Language Agents with Verbal Reinforcement Learning.
In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (eds.), *Advances in Neural Information Processing Systems*, volume 36, pp. 8634–8652. Curran Associates, Inc., 2023.
URL [https://proceedings.neurips.cc/paper_files/paper/2023/file/1b44b878bb782e6954cd888628510e90-Paper-Conference.pdf](https://proceedings.neurips.cc/paper_files/paper/2023/file/1b44b878bb782e6954cd888628510e90-Paper-Conference.pdf).
- Sun et al. (2025)
Weiwei Sun, Shengyu Feng, Shanda Li, and Yiming Yang.
Co-bench: Benchmarking language model agents in algorithm search for combinatorial optimization.
*ArXiv*, abs/2504.04310, 2025.
URL [https://arxiv.org/abs/2504.04310](https://arxiv.org/abs/2504.04310).
- Šurina et al. (2025)
Anja Šurina, Amin Mansouri, Amal Seddas, Maryna Viazovska, Emmanuel Abbe, and Caglar Gulcehre.
Algorithm discovery with LLMs: Evolutionary search meets reinforcement learning.
In *Scaling Self-Improving Foundation Models without Human Supervision*, 2025.
URL [https://openreview.net/forum?id=1kAwyBpoO1](https://openreview.net/forum?id=1kAwyBpoO1).
- Team et al. (2025)
Gemma Team, Aishwarya Kamath, Johan Ferret, Shreya Pathak, Nino Vieillard, Ramona Merhej, Sarah Perrin, Tatiana Matejovicova, Alexandre Ramé, Morgane Rivière, et al.
Gemma 3 technical report.
*arXiv preprint arXiv:2503.19786*, 2025.
URL [https://doi.org/10.48550/arXiv.2503.19786](https://doi.org/10.48550/arXiv.2503.19786).
- Tran et al. (2025)
Cong Dao Tran, Quan Nguyen-Tri, Huynh Thi Thanh Binh, and Hoang Thanh-Tung.
Large language models powered neural solvers for generalized vehicle routing problems.
In *ICLR 2025 Workshop on Towards Agentic AI for Science: Hypothesis Generation, Comprehension, Quantification, and Validation*, 2025.
URL [https://openreview.net/forum?id=EVqlVjvlt8](https://openreview.net/forum?id=EVqlVjvlt8).
- Vidal (2022)
Thibaut Vidal.
Hybrid genetic search for the CVRP: Open-source implementation and SWAP* Neighborhood.
*Computers & Operations Research*, 140:105643, 2022.
URL [https://doi.org/10.1016/j.cor.2021.105643](https://doi.org/10.1016/j.cor.2021.105643).
- Vinyals et al. (2015)
Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly.
Pointer Networks.
In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett (eds.), *Advances in Neural Information Processing Systems*, volume 28, pp. 2692–2700. Curran Associates, Inc., 2015.
URL [https://proceedings.neurips.cc/paper_files/paper/2015/file/29921001f2f04bd3baee84a12e98098f-Paper.pdf](https://proceedings.neurips.cc/paper_files/paper/2015/file/29921001f2f04bd3baee84a12e98098f-Paper.pdf).
- Wouda et al. (2024)
Niels A. Wouda, Leon Lan, and Wouter Kool.
PyVRP: a high-performance VRP solver package.
*INFORMS Journal on Computing*, 36(4):943–955, 2024.
doi: 10.1287/ijoc.2023.0055.
URL [https://doi.org/10.1287/ijoc.2023.0055](https://doi.org/10.1287/ijoc.2023.0055).
- Wu et al. (2022)
Yaoxin Wu, Wen Song, Zhiguang Cao, Jie Zhang, and Andrew Lim.
Learning Improvement Heuristics for Solving Routing Problems.
*IEEE Transactions on Neural Networks and Learning Systems*, 33(9):5057–5069, 2022.
URL [https://doi.org/10.1109/TNNLS.2021.3068828](https://doi.org/10.1109/TNNLS.2021.3068828).
- Yang et al. (2025a)
An Yang, Anfeng Li, Baosong Yang, Beichen Zhang, Binyuan Hui, Bo Zheng, Bowen Yu, Chang Gao, Chengen Huang, Chenxu Lv, et al.
Qwen3 Technical Report.
*CoRR*, abs/2505.09388, 2025a.
URL [https://doi.org/10.48550/arXiv.2505.09388](https://doi.org/10.48550/arXiv.2505.09388).
- Yang et al. (2025b)
Xianliang Yang, Ling Zhang, Haolong Qian, Lei Song, and Jiang Bian.
HeurAgenix: Leveraging LLMs for Solving Complex Combinatorial Optimization Challenges.
*arXiv preprint arXiv:2506.15196*, 2025b.
URL [https://arxiv.org/abs/2506.15196](https://arxiv.org/abs/2506.15196).
- Ye et al. (2023)
Haoran Ye, Jiarui Wang, Zhiguang Cao, Helan Liang, and Yong Li.
DeepACO: Neural-enhanced Ant Systems for Combinatorial Optimization.
In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (eds.), *Advances in Neural Information Processing Systems*, volume 36, pp. 43706–43728. Curran Associates, Inc., 2023.
URL [https://proceedings.neurips.cc/paper_files/paper/2023/file/883105b282fe15275991b411e6b200c5-Paper-Conference.pdf](https://proceedings.neurips.cc/paper_files/paper/2023/file/883105b282fe15275991b411e6b200c5-Paper-Conference.pdf).
- Ye et al. (2024)
Haoran Ye, Jiarui Wang, Helan Liang, Zhiguang Cao, Yong Li, and Fanzhang Li.
GLOP: Learning Global Partition and Local Construction for Solving Large-Scale Routing Problems in Real-Time.
In *Proceedings of the AAAI Conference on Artificial Intelligence*, volume 38, pp. 20284–20292, 2024.
doi: 10.1609/aaai.v38i18.30009.
URL [https://ojs.aaai.org/index.php/AAAI/article/view/30009](https://ojs.aaai.org/index.php/AAAI/article/view/30009).
- Ye et al. (2025)
Haoran Ye, Jiarui Wang, Zhiguang Cao, Federico Berto, Chuanbo Hua, Haeyeon Kim, Jinkyoo Park, and Guojie Song.
ReEvo: large language models as hyper-heuristics with reflective evolution.
In *Proceedings of the 38th International Conference on Neural Information Processing Systems*, NIPS ’24, Red Hook, NY, USA, 2025. Curran Associates Inc.
URL [https://dl.acm.org/doi/10.5555/3737916.3739297](https://dl.acm.org/doi/10.5555/3737916.3739297).
- Zheng et al. (2024)
Zhi Zheng, Changliang Zhou, Xialiang Tong, Mingxuan Yuan, and Zhenkun Wang.
UDC: A Unified Neural Divide-and-Conquer Framework for Large-Scale Combinatorial Optimization Problems.
In A. Globerson, L. Mackey, D. Belgrave, A. Fan, U. Paquet, J. Tomczak, and C. Zhang (eds.), *Advances in Neural Information Processing Systems*, volume 37, pp. 6081–6125. Curran Associates, Inc., 2024.
URL [https://proceedings.neurips.cc/paper_files/paper/2024/file/0b8e4c8468273ee3bafb288229c0acbc-Paper-Conference.pdf](https://proceedings.neurips.cc/paper_files/paper/2024/file/0b8e4c8468273ee3bafb288229c0acbc-Paper-Conference.pdf).
- Zheng et al. (2025)
Zhi Zheng, Zhuoliang Xie, Zhenkun Wang, and Bryan Hooi.
Monte carlo tree search for comprehensive exploration in LLM-based automatic heuristic design.
In *42nd International Conference on Machine Learning*, 2025.
URL [https://openreview.net/forum?id=Do1OdZzYHr](https://openreview.net/forum?id=Do1OdZzYHr).

## Appendix A Prompts

The exact prompts used by VRPAgent-GA are presented below. We distinguish between general prompts, which remain the same across all problems, and problem-specific prompts, which must be tailored to each task. The two are combined by substituting variables in the general prompts (e.g., replacing {problem_desc} with the corresponding problem-specific description). For crossover and ablation prompts, the provided template is further extended by inserting the implementations of the associated individuals at the designated positions.

For brevity, we report only the problem-specific prompts for the CVRP, while the rest will be provided in the final code release.

### A.1 General prompts

Figure: Prompt 1: Global system context.

Figure: Prompt 2: Initial operator generation.

Figure: Prompt 3: Crossover prompt with 80% bias.

Figure: Prompt 4: Ablation (Mutation).

Figure: Prompt 5: Extend (Mutation).

Figure: Prompt 6: Adjust-Parameters (Mutation).

Figure: Prompt 7: Refactor (Mutation).

### A.2 Problem-Specific Prompts

#### A.2.1 CVRP

Figure: Prompt 8: Problem description CVRP).

Figure: Prompt 9: Metaheuristic context ({LNS_headers}).

Figure: Prompt 10: Seed heuristic ({seed_code}).

## Appendix B Additional Details

### B.1 Costs per Run

**Table 2: Comparison token usage and cost estimates across models per run (as of Sep. 2025) with inference providers sources.**
| Model | Open Source | Token Usage | Costs ($) | Total Costs ($) | Source |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- |
| Input | Output | Input | Output |  |  |  |  |
| Gemini 2.0 Flash | ✗ | 2.5M | 1.2M | 0.10 | 0.40 | 0.73 | [Vertex AI](https://cloud.google.com/vertex-ai) |
| Gemini 2.5 Flash | ✗ | 4.1M | 7.1M | 0.30 | 2.50 | 18.98 | [Vertex AI](https://cloud.google.com/vertex-ai) |
| gpt-oss (120B) | ✓ | 4.0M | 2.5M | 0.09 | 0.36 | 1.26 | [Clarifai](https://www.clarifai.com/) |
| gemma 3 (27B) | ✓ | 2.5M | 1.2M | 0.09 | 0.16 | 0.42 | [DeepInfra](https://deepinfra.com/) |
| Qwen3 (30B) | ✓ | 1.5M | 4.4M | 0.08 | 0.29 | 1.40 | [Clarifai](https://www.clarifai.com/) |
| Llama 3.3 (70B) | ✓ | 2.3M | 1.0M | 0.08 | 0.29 | 0.47 | [Clarifai](https://www.clarifai.com/) |

### B.2 Use of Large Language Models

LLMs played an active role in this work. Beyond serving as general-purpose writing assistants for improving clarity, style, and grammar and as coding assistants, LLMs were employed as heuristic discovery tools during the optimization phase of our study. Importantly, the core research contributions, including the design of the framework, theoretical development, and validation of results, were conceived, implemented, and verified exclusively by the authors. All outputs from LLMs were critically assessed, refined, and integrated to ensure correctness and adherence to academic standards.

## Appendix C Discussion of discovered heuristics

LLM generated code raises many questions about its quality and maintainability. A further question is how the code works and how it is able to achieve state-of-the-art performance. While we are unable to fully answer these questions, we try to provide some initial insights into the quality of the best heuristic generated for each problem. To do this, we have three co-authors of the paper with many years of experience writing heuristics by hand analyze the code according to several criteria. We acknowledge that this is not a scientific study and is not intended to draw generalizations about the ability of LLMs to code heuristics for optimization problems. Rather, our goal is to give some indications as to how the code generated compares to code written by humans and what kind of ideas are present. We note that the code is generated without comments to avoid the LLM influencing the analysis, however we note that variable names are present that do give some contextual information about what the code does.

The three heuristics experts have XX (expert 1), YY (expert 2) and ZZ (expert 3) years of experience writing OR heuristics(^1^11To avoid potentially violating the double blind submission policy, we do not indicate the years of experience of the experts, as they are all coauthors of the work. These will be provided in the accepted version of this work, and this message will be removed.). All experts have experience with routing problems in addition to other types of OR problems. Each expert provides an evaluation of the generated code of the best performing heuristic for each of the three problems examined in this work. The experts describe a consensus description of how the heuristic works then write independent discussions of each heuristic. The individual rating criteria are as follows:

- 1.
Readability (noting that the assessments are not general statements about LLM code)
- 2.
Coherence and soundness
- 3.
Maintainability
- 4.
Interpretability, i.e., do we know why this code works well?
- 5.
Are there any new ideas in the heuristic?

### C.1 CVRP

The removal and sorting mechanisms are best described as ensembles of heuristics in which the heuristic applied at any given iteration is chosen at random according to a probability distribution determined through the static parameters of the approach. For the selection of customers for removal, the heuristics of the ensemble show a similarity to the SISRs heuristic. In the first, adjacent customers are selected for removal and in the second, random segments of tours are chosen. Since these segments can overlap, we also have a SISRs-like idea. The third heuristic, as best as we can determine, tries to expand a tour segment. For sorting, the heuristic first decides whether to sort descending or ascending according to one of seven different heuristics. We omit a detailed description of all the heuristics, but note that these include generally known ideas for sorting customers in a CVRP, e.g. using criteria such as the distance to the depot, the demand of the customers, weighted combinations of distance and demand, and greedy nearest-neighbor sequencing.

#### C.1.1 Expert 1

The code is generally easy to read and understand, although there are many sanity checks that might be unnecessary. The heuristics are rather coherent and are rather reasonable, however note that the removal mechanism likely could be simplified as the heuristics somewhat overlap in what they do. An ablation analysis of the sorting would likely also show that not all of the heuristics are necessary. The code looks relatively easy to maintain as it does not use any special constructs or libraries, and furthermore its memory management is very simple. A detailed ablation analysis would be necessary to find out why the code works well. Finally, the heuristic does not present anything radically new, but there are not any sorting heuristics like this in the literature. The removal heuristic, as mentioned, is a SISRs variation so its novelty is low.

#### C.1.2 Expert 2

The code is relatively easy to understand and mostly makes sense. In many places, however, it is unnecessarily complex and redundant. A human coder would certainly come up with a better-to-understand and more concise implementation of (almost) the same heuristic. As an example, the probabilistic strategy choices involve deeply nested if-else statements and could be managed in a simpler way. Regarding redundancy, the initialization phase and the main strategy loop of the selection heuristic randomly opt for a segment-based selection; I don’t think removing it from the initialization would make any difference. The code involves several parameters (including strategy selection parameters) which are mostly interpretable; I cannot assess if the parameters are well-chosen without further experiments. Overall, all the elements of the ensemble are variations of known strategies, but to the best of my knowledge, the chosen combination is new.

#### C.1.3 Expert 3

The code is overall well-structured and, thanks to informative variable names, fairly easy to follow. However, the extensive nesting of loops and conditionals can make it difficult to trace the logic, particularly for less experienced users. If rewritten by an expert, the implementation would likely be shorter and more concise. The large number of parameters and probability values further complicates interpretability, as it is not immediately clear which of them actually matter in practice. Conceptually, the code combines several known ideas from the literature in a structured ensemble; while none of the components are new by themselves, the way they are combined is somewhat novel.

### C.2 VRPTW

The selection and sorting heuristics form portfolio approaches, that is, ensembles of different heuristics that are probabilistically selected and combined. The selection heuristic removes a randomly chosen number of customers (10-15). It starts with a randomly picked customer and then uses a main loop in which one additional customer is added per iteration, using spatial proximity and tour neighborhood to a selected reference customer as well as pure randomness to guide the choice. The sorting code involves ten different strategies, of which one is randomly chosen per call of the heuristic. Five strategies rely on simple smetrics such as demand or time window start time, four are based on combined metrics and one is a purely random shuffling of the customers. One of the combined metrics is highly complex and heavily parameterized.

#### C.2.1 Expert 1

This heuristic is again fairly easy to read, however a human would likely select the random number differently for determining which heuristic of the ensemble to use for the removal operator. Both the removal and sorting operators are coherent with a clear structure. The removal operator could likely be simplified without losing the core ideas. The methods are, as in the CVRP, not very interpretable and require significant ablation to figure out what actually works. The sorting criteria are mostly standard and there are no big surprises, even though some of the combinations of criteria might be unusual.

#### C.2.2 Expert 2

The code is not hard to read and the variable names are mostly interpretable. There are no substantial errors, and the heuristics are mostly coherent, but the logic is at times unnecessarily hard to understand and may lead to misinterpretations. As an example, there are parameters referring to probabilities of strategies in the selection step which may be easily misinterpreted as they are applied in a nested fashion. In addition, parts of the code regarding random selection are unnecessarily complicated and highly redundant. The sorting code is sometimes hard to read because certain parts belonging to the same strategy are spread across the function body, and declaring certain variables on a global scope does not contribute to maintainability. The sorting criteria are well-known, but two combined criteria are very complex, including weights and stochastic perturbations that make it very hard to assess, maintain and tune.

#### C.2.3 Expert 3

The code is overall readable and, as in the other case, reflects a consistent style the LLM uses. The nested conditionals make the logic harder to follow, and if rewritten manually the implementation would likely be shorter and clearer. The removal procedure is coherent and grounded in known ideas, though the many probabilistic parameters and fallback rules make its behavior less transparent. The sorting part includes many variants, but the large number of options risks obscuring which criteria truly matter. Overall, the components are standard for the VRPTW.

### C.3 PCVRP

The removal and sorting heuristics form an ensemble of heuristics, with the specific method chosen at random according to static parameters defined at the beginning. The removal operator first determines how many customers to remove. It starts the selection from either an unvisited customer, a customer based on a random tour, or a purely random choice. Customers are then added iteratively based on adjacency and tour neighbors, with random selection used as a fallback. The sorting operator either shuffles customers randomly or scores them using a combination of properties such as prize, distance to the depot, and demand, with probabilities applied to vary the weights of these properties.

#### C.3.1 Expert 1

The ensembles for removal and sorting are relatively clear, but there are some “magic numbers” strewn about the code. The code is generally coherent, but the removal heuristic gets rather complicated with its choice of random customers. The sorting uses many random numbers and if a student wrote this for me, I would demand a re-write. These heuristics are again mostly combining multiple elements that are already known into a random selection ensemble. It is exceptionally hard to say where the good performance of this heuristic is coming from.

#### C.3.2 Expert 2

The code is generally easy to read and to interpret, but in some cases prone to a misinterpretation of parameters representing probabilities. The code mostly appears coherent and makes reasonable choices, but the implementation is often unnecessarily complex and feels over-parameterized. The elements contributing to the ensemble are mostly straightforward and known in the literature. In the sorting heuristic, tunable parameters are not located in a single location at the beginning of the code, but spread across the code; in some cases, important parameters are not even variables. Interestingly, all three main sorting strategies use the same criteria (all criteria are relatively standard), although with different weight combinations. I cannot really make sense of the weight generation, and it would certainly be hard to tune given the way it is implemented.

#### C.3.3 Expert 3

The code is well-structured and generally readable, though some parts, such as the selection of the first customer, appear overcomplicated and could likely be simplified without losing functionality. The overall structure is consistent, but it relies on many nested components, which can make the logic harder to follow and maintain. Sorting uses numerous hard-coded values, which make the impact of the introduced probabilities not clear. While the components themselves are familiar and standard for this problem domain, some of their combinations are unusual.

## Peer Reviews

confidence: 4
contribution: 3
initial_rating: 6
presentation: 3
questions: 1. Have you considered incorporating interpretability metrics into the fitness function to encourage more transparent heuristics without sacrificing performance?
2. Can you provide more insight into why strong exploitation (biased crossover, elite-only mutation) works so well? Is there something specific about the LLM-generated operator search space that makes this effective?
3. How sensitive is the approach to the choice of metaheuristic framework? Would similar results be achievable with other frameworks beyond LNS?
4. The expert analysis mentions ensemble approaches in all discovered heuristics. Is this a fundamental property of effective operators, or an artifact of the LLM's training or the prompt design?
5. Have you investigated whether operators discovered for one problem (e.g., CVRP) can be adapted or fine-tuned for related problems (e.g., VRPTW) more efficiently than starting from scratch?
soundness: 3
strengths: 1. Novel and Practical Framework: The approach of generating only problem-specific operators within a fixed metaheuristic is well-motivated. This "keeping AI agents on a leash" philosophy addresses key limitations of prior LLM-based approaches by ensuring correctness and manageability while still enabling discovery of novel strategies.
2. Strong Empirical Results: VRPAgent achieves impressive performance improvements over both traditional OR solvers and recent learning-based methods, with negative gaps (around -0.30%) relative to state-of-the-art SISRs on larger instances. The consistency across multiple problem variants and instance sizes is particularly compelling.
3. Computational Efficiency: The single CPU core requirement at test time is a significant practical advantage over GPU-dependent NCO methods, making deployment more accessible.
4. Thorough Experimental Analysis: The paper includes comprehensive ablation studies demonstrating the importance of biased crossover and mutation, analysis across different LLMs (showing that open-source gpt-oss achieves near-SOTA performance at low cost), and sensitivity analyses on GA hyperparameters.
5. Expert Analysis: The inclusion of expert evaluation of generated heuristics (Appendix C) provides valuable qualitative insights into readability, coherence, and novelty, adding credibility beyond pure performance metrics.
summary: This paper presents VRPAGENT, a framework that uses Large Language Models (LLMs) to automatically discover heuristic operators for Vehicle Routing Problems (VRPs). The approach embeds LLM-generated problem-specific operators within a Large Neighborhood Search (LNS) metaheuristic and refines them through a genetic algorithm with elitism and biased crossover. The authors evaluate their method on three VRP variants (CVRP, VRPTW, PCVRP) and demonstrate state-of-the-art performance using only a single CPU core at test time.
weaknesses: **Major issues**

1. Interpretability Concerns: The expert analysis consistently notes that discovered heuristics are difficult to interpret due to complex logic, nested conditionals, and convoluted use of random numbers. This limits practical adoption where transparency is important. The paper acknowledges this but doesn't propose concrete solutions.
2. Limited Generalization Analysis:
- Training is conducted only on 500-customer instances, yet the approach generalizes well to 1000 and 2000 customers. More analysis on why this generalization occurs would strengthen the paper.
- The operators are discovered separately for each problem variant. Can operators transfer across problems or be adapted more efficiently?
3. LLM Dependency:
- Best results require Gemini 2.5 Flash at ~$19 per run, which may limit accessibility
- While gpt-oss performs well, the reliance on specific LLM characteristics raises questions about reproducibility and long-term viability
4. GA Design Choices:
- The strong bias toward exploitation (80% elite in crossover, mutation only on elites) is unusual. While ablations show it works, more analysis on why exploitation is so beneficial in this search space would be valuable.
- Limited exploration of other GA hyperparameters (e.g., initial population diversity, selection mechanisms)
5. Comparison Limitations:
- Some baselines use different time budgets or hardware configurations, making direct comparison slightly less clear
- The paper compares against construction-based LLM methods (EoH, ReEvo) that don't benefit from search budgets, but limited comparison with other LLM-based improvement heuristics
6. Novelty of Discovered Heuristics: While the expert analysis confirms novelty, it also notes that heuristics are primarily "recombinations of existing ideas." The paper could better discuss what fundamentally new concepts (if any) were discovered.

**Minor Issues**
1. The abstract mentions "VRPAGENT is the first LLM-based paradigm to advance the state-of-the-art in VRPs," which is a strong claim. While the results support this, it might be beneficial to briefly acknowledge the ongoing rapid advancements in LLM-based optimization to provide full context, perhaps by rephrasing slightly to "among the first" or "a pioneering LLM-based paradigm."
2. Notation Consistency: In Algorithm 2, line 4 uses NE (non-elite) which could be confused with the elite size parameter also denoted $N_E$. Consider using different notation. In Algorithm 2, line 7 uses $RANDOM(Е)$ and line 8 uses $RANDOM(NE)$. It would be clearer to explicitly state what $E$ and $NE$ represent in this context (e.g., a list of elite individuals, a list of non-elite individuals) to avoid ambiguity for readers unfamiliar with the specific GA implementation.
3. Missing Details: The paper mentions that full prompts will be provided in the "final code release" but only shows CVRP-specific prompts in the appendix. For reproducibility, all prompts should be included.
4. Statistical Significance: Results lack error bars or significance tests, though the consistent improvements across problems suggest robustness.
5. Figure Quality: Figure 1 is informative but quite busy. Consider simplifying or providing a higher-level conceptual diagram first.

---

confidence: 3
contribution: 3
initial_rating: 4
presentation: 2
questions: 1. In Fig. 2, why does the curve without mutation decrease faster in the early iterations, yet later perform worse than the one with mutation? It seems that 20 iterations are insufficient for convergence. It is recommended to extend the number of iterations to show a more complete convergence process.

2. The analysis of Fig. 5 (a) and (b) is inadequate. The discussion merely restates the numerical results without providing insight into the underlying reasons or the conclusions that can be drawn from them.

3. The paper claims that the proposed framework has strong transferability. Therefore, the results and implementation should be made open-source to enable further verification and application by other researchers across different problems and domains.

4. All test cases in the paper are limited to VRP-related problems, yet the method itself does not incorporate any VRP-specific structural design or analysis. Moreover, the generated heuristics are not analyzed, leaving the algorithm’s interpretability and physical rationale unclear.

5. As mentioned in Comment 4, since the algorithm is not specifically tailored to VRP, it is suggested to include additional results on other mixed-integer programming benchmarks (e.g., general MILP instances) in the appendix to demonstrate the generality and effectiveness of the proposed approach.

6. Although the paper compares with many deep learning–based methods, it does not include comparisons with classical solvers such as Gurobi or CPLEX, which are widely used in practice. Without such baselines, the practical applicability of the proposed method to real-world VRP problems remains unclear. It is recommended to supplement results comparing with Gurobi and/or CPLEX.
soundness: 3
strengths: The work presented in this paper is solid and substantial, with comprehensive comparisons against many methods published in top-tier conferences, demonstrating strong overall performance.

The manuscript is well-written, logically organized, and carefully proofread.

The proposed method also shows promising potential for extension and application to other problem domains.
summary: Designing effective heuristics for VRP problems based on the Large Neighborhood Search (LNS) algorithm typically requires extensive human expertise and trial-and-error. To address this issue, the paper proposes using large language models (LLMs) to automatically design heuristic operators. Building on the concept of genetic algorithms, the LLM generates diverse heuristic candidates, retains the best-performing ones according to the solution results, and performs heuristic modifications and explorations to further improve performance. The proposed method is validated on multiple types of VRP problems, demonstrating a significant overall performance advantage compared with other AI-enhanced LNS approaches.
weaknesses: The proposed framework exhibits general applicability; however, the experimental cases are limited to the VRP domain.

The effectiveness of the proposed method still requires further investigation, as it has not been compared with widely used commercial solvers. Moreover, the results do not show a significant improvement in either computational speed or solution quality compared with existing approaches.

---

confidence: 4
contribution: 2
initial_rating: 4
presentation: 2
questions: 1. How sensitive is the genetic search to the initialization of random heuristics and the specific code-length penalty functions? Can you provide detailed ablation studies quantifying how different parameter choices impact final solution quality and code interpretability, particularly for non-benchmark VRP variants or logistics settings outside the training corpus?​​

2. Given that several domain experts found the final heuristic code verbose, redundant, or over-complicated, what mechanisms (besides code-length penalty) do you propose to systematically regularize the structure, improve succinctness, and enhance human interpretability for large LLM-generated operator populations?​​

3. What validation and error-checking processes are in place to guarantee that newly synthesized operators do not introduce infeasibility, silent bugs, or performance degradation, especially as code complexity increases over generations and as operators interact in ensembles? Is there any theoretical or empirical guarantee that VRPAgent will not produce brittle or unsafe solutions on realistic, highly constrained, or adversarial VRP instances?
soundness: 2
strengths: 1. The proposed VRPAgent leverages LLMs to generate and evolve problem-specific destroy/insert heuristics for VRPs, significantly reducing the need for expert-written code and enabling discovery of novel strategies.​

2. The framework combines LLM-generated operators with a genetic algorithm using elitism, biased crossover, and code-length penalties, leading to efficient search and interpretable code that is competitive with and sometimes superior to handcrafted heuristics.​

3. VRPAgent consistently outperforms or matches best-in-class expert and neural approaches on benchmark VRPs (CVRP, VRPTW, PCVRP), working efficiently on CPU and scaling to large instances.​

4. The approach maintains strong performance across multiple VRP classes without requiring expensive hardware. By modularizing heuristic generation and search refinement, it allows for adaptation to different problem types and operator ensembles.​

5. By focusing LLM synthesis on manageable code components within a robust metaheuristic shell, VRPAgent strikes a balance between automated innovation and guarantees of feasibility and quality
summary: This paper proposes a framework for automated heuristic discovery in VRPs using LLMs called VRPAgent. VRPAgent integrates LLM-generated problem-specific operators within a Large Neighborhood Search (LNS) metaheuristic and refines them through a genetic algorithm that employs elitism, biased crossover, and code-length penalty mechanisms.​

Key features include generating problem-specific destroy and insert heuristics via LLMs, and evolving these operators over multiple generations to maximize solution quality while controlling code complexity. The method is evaluated across standard VRPs (capacitated, time windows, prize-collecting), consistently discovering heuristics that outperform handcrafted and previous LLM/learning-based methods on large benchmark instances using only CPU resources.​

The approach offers interpretability, practical efficiency, and a reproducible pipeline for discovering and improving heuristics for combinatorial optimization, highlighting a new path for LLM-driven algorithmic design in operations research.​

The contributions include:
1. A hybrid metaheuristic framework (LLM-in-the-loop LNS) for VRPs where LLMs generate, mutate, and combine code for local operators.
2. A genetic algorithm with code-length penalties to evolve and select the best LLM-generated operators.
3. Demonstrating state-of-the-art or superior performance compared to both expert-designed heuristic solvers and recent neural/LLM solutions on several large VRP benchmarks, with superior interpretability and scalability
weaknesses: 1. Many LLM-generated heuristics discovered by VRPAgent are ensembles or recombinations of standard strategies from the literature (e.g., SISRs-like removal, weighted greedy criteria for sorting). The framework excels at combining known components but provides little evidence of discovering fundamentally new algorithms that would advance state-of-the-art theory for VRPs.​

2. While the code is readable to experts, it is often overly redundant, deeply nested, and filled with hard-to-tune random parameters and magic numbers. Several domain experts in the study noted that a human would write more succinct, interpretable, and maintainable code. The logic behind some probabilistic choices is especially convoluted, making ablation studies and performance analysis difficult.​

3. The performance improvements are attributed to complex ensembles and parameterized strategies, but the paper lacks detailed ablation studies pinpointing which components are truly responsible for gains. This makes it hard to generalize findings beyond the benchmarked VRP instances.​

4. Many key parameters affecting the algorithms' behavior are scattered, sometimes hard-coded and sometimes embedded within random logic, increasing risk of inadvertent misconfiguration. This could hinder code modification, adaptation, or debugging in practice.​

5. The experiments focus on classic VRPs and well-known benchmark formats. There is no evaluation of the heuristics' robustness under noisy, dynamic, or highly custom problem constraints, which are common in operational logistics scenarios.​

6. Although some level of interpretability is claimed, true transparency into how and why the LLM-generated code behaves well is lacking. For many users and practitioners, relying on black-box or stochastic mixtures of heuristics without clear guidance or analysis may be risky.​

7. The framework does not address risks inherent in LLM-generated code, such as silent propagation of bugs, accidental feasibility violations, or malicious prompt engineering in operational settings. This could be critical for industrial deployment.​

8. Claims of extensibility to other combinatorial domains (packing, scheduling) are made, but without any experimental or theoretical evidence.

---

confidence: 4
contribution: 2
initial_rating: 4
presentation: 2
questions: see weaknesses
soundness: 2
strengths: 1. The approach is clear, and the LLM-guided evolutionary framework has discovered operators that go beyond expert-designed ones.
2. The authors have conducted a certain level of analysis on the generated heuristic operators.
summary: This paper introduces VRPAGENT, a framework for discovering heuristic operators for Vehicle Routing Problems (VRPs) using large language models (LLMs). The method combines LLM-generated “destroy” and “order” operators with a Large Neighborhood Search (LNS) metaheuristic, leveraging genetic algorithms (GAs) to iteratively evolve improved operators. Although the research motivation and validation results seem feasible, the approach is almost identical to existing LLM-guided heuristic frameworks, which weakens the overall contribution of the paper.
weaknesses: 1.	**Incrementa novelty** — The evolutionary framework of VRPAgent is similar to existing heuristic evolutionary frameworks (such as Heuristics evolution based on LLM, e.g., EoH [1]), and the proposed "code length penalty" is also negligible.
2.	**Empirical overclaiming** — The experimental results of VRPAGENT show only minor improvements compared to existing methods. There is a lack of comparison with LLM-empowered LNS approaches, such as LLM-LNS [2]. It is also unclear how it performs compared to adaptive LNS methods like PPO-ALNS [3].
3.	**Fairness of experiments** — It is not clearly stated whether the comparison methods based on LLM heuristic generation have a similar number of API calls.
4.	**Incomplete experimental analysis** — The study lacks an analysis of aspects such as the convergence of the genetic algorithm or the probability of code correctness.

[1] Evolution of heuristics: Towards efficient automatic algorithm design using large language model. ICML 2024.

[2] Large Language Model-driven Large Neighborhood Search for Large-Scale MILP Problems. ICML 2025.

[3] Reinforcement learning-guided adaptive large neighborhood search for vehicle routing problem with time windows. Journal of Combinatorial Optimization, 2025.