acceptodds
Under review as a conference paper at ICLR 2027

EvoHGS: Co-evolving Language Models with Hybrid Genetic Search for Vehicle Routing Problems

Abstract

Vehicle Routing Problems (VRPs) are a fundamental class of combinatorial optimization problems aimed to find high-quality routes for vehicles under operational constraints. Despite decades of study in operations research, VRPs remain computationally challenging due to their NP-hardness, with additional difficulty introduced by the diverse constraint structures that arise across different variants. Hybrid Genetic Search (HGS) has emerged as a state-of-the-art metaheuristic framework for many VRP variants. However, its performance still depends heavily on manually designed search operators and empirical parameter tuning, limiting its ability to adapt automatically to complex and diverse problem settings. To address the limitation, we propose **EvoHGS**, a large language model (LLM)-guided evolutionary framework that automatically improves HGS across the VRP family. EvoHGS integrates LLM-based heuristic generation with evolutionary search, allowing candidate HGS operators to be generated, evaluated, selected, and refined through an iterative optimization process. To further align generation with downstream search performance, EvoHGS uses feedback collected during evolution to finetune the LLM via reinforcement learning. This enables the model to progressively produce operators that are better adapted to the search dynamics of HGS across VRP variants. Experiments on multiple VRP variants show that EvoHGS consistently outperforms the original HGS baseline at the scale used for evolution, remains competitive when the evolved operators are applied to larger instances, and demonstrates promising zero-shot generalization to unseen VRP variants.

Primary area:
applications to computer vision, audio, language, and other modalities
Keywords:
Large Language Models, Automated Heuristic Design, Vehicle Routing Problems, Evolutionary Search, Reinforcement Learning

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_8HmPOpenReview ↗
Rating
2
Confidence
4
Informativeness
1
Presentation
3
Soundness
1
Read review
Paper summary

LLM assisted generation of operators in evolutionary framework, assessed, selected and refined in the evolution. Feedback is collected during the evolution to finetune LLM using reinforcement learning. LLM generates ideas for both the code and implementations.

Critical strengths

The proposed EvoHGS showed to improve the performance of HGS to solve six variants of VRP, offering potentially a strong VRP solver to the literature.

Critical weaknesses

There is a lack of justifications for method selection, and research work conducted doesn't reveal deep insights contributing to the research community.

  • It's not clear why the two models, LLM and reinforcement learning, both consuming extensive computation and leading to stochastic behaviour especially from LLM, are chosen in EvoHGS. Would using just LLM or RL directly be sufficient for operator generation (literature showed good results from just one of them)? Why both? The integration seems to be random.
  • EvoHGS seems to be more on a combination of existing methods or techniques (MVMoE, ReEvo into HGS), rather than devised to address key research questions leading to scientific insights.
  • "burden of manual design" is claimed as a research issue. Is operator design always the bottleneck of evolutionary algorithms or HGS? Why is HGS chosen? Why focusing on crossover not mutation, the former causes more problems for constrained problems like VRP? No motivations have been clearly provided to answer meaningful scientific questions in evolutionary computation.
  • research aim is to "enhance the adaptability and automation of HGS search": Would just one of RL or LLM suffice and much cheaper, to address this aim of practical VRP solvers?
  • The main focus is to develop a unified HGS for variants of VRP, while the claimed contributions provide an overview of the performance of EvoHGS framework as VRP solvers, not any scientific insights to the literature.
Questions for authors

See the above questions.

16 comments
AuthorsOpenReview ↗

Response to Reviewer 8HmP (1/5)

We appreciate the reviewer for their comments, which provide us with a valuable opportunity to further emphasize several key aspects of our work. For your convenience, additional tables included in this response are denoted in bold with an "R" prefix (e.g., Table R1), whereas italicized references (e.g., Table 1) refer to results already present in our paper.

W1. It's not clear why the two models, LLM and reinforcement learning, both consuming extensive computation and leading to stochastic behaviour especially from LLM, are chosen in EvoHGS. Would using just LLM or RL directly be sufficient for operator generation (literature showed good results from just one of them)? Why both? The integration seems to be random.

Here we refer to your "LLM" as the "LLM-based evolution" step. Indeed, EvoHGS combines LLM-based evolution and RL. Below we clarify how they relate and why either is needed. First they are not two separate models. There is only one single 8B LLM, which plays the role of mutation and recombination in the evolutionary search: it writes new operators in HGS solver (state-of-the-art VRP solver) from the parents in the pool. RL, in contrast, introduces a relatively lightweight learning mechanism that enables the LLM to learn from the fitness values already computed during the evolutionary search, without requiring additional computation. The methodological novelty of EvoHGS lies in how this LLM is trained within the evolutionary loop, as we state in Section 1 of our paper: "SFT on modifications spanning multiple VRP variants enables the LLM to generate compilable code and confers generalization across the VRP family, while RL within the evolutionary loop co-evolves the LLM with the pool of modifications to further improve performance." Therefore, our RL is used to adaptively enhance LLM for proposing better operators, which in turn become better parents for the subsequent code evolution.

To the best of our knowledge, this is the first two-stage training framework for evolving a solver with an LLM. It enables an 8B model to improve a state-of-the-art solver while keeping it general improvements over different VRP types, which has not been achieved by prior work. Although the operator is evolved only on instances with n=100, it is effective on seen variants, on unseen variants and at larger scales, as shown in Tables 1, 2 and 10 of our paper. In the two-stage training framework, LLM-based evolution and RL are both necessary and effectively interwine:

  • SFT-enhanced LLM-based evolution. A general-purpose LLM cannot reliably rewrite a complete C++ operator inside HGS-PyVRP: only 25.1% of the candidates from the base Qwen3-8B compile and run, and even GPT-5-nano reaches just 46.0% (Figure 2 of our paper). RL started from such a model spends most of its exploration on invalid code. SFT-enhanced LLM-based evolution increases this share to 85.3%. SFT also enhances LLM-based evolution in zero-shot transferability: our SFT-enhanced LLM-based evolution improves statistically significantly on all three unseen variants tested, while canonical LLM-based evolution without SFT on none (Table 11 in our paper; see also Tables R4–R5 in our response to Reviewer vVXj W2).
  • RL inside the evolutionary loop. A fixed LLM can keep what the search has found only in its prompt. GRPO writes it into the weights, so the LLM and the operator pool improve together. On top of SFT-enhanced LLM-based evolution, GRPO, further, brings a statistically significant gain (Table 8 of our paper) over multiple independent runs. The gain is not just a matter of more compilable candidates: the significant improvement remains, even when LLM-based evolution is given exactly the same 1,000 valid operators (Table R2, our response to Reviewer MzmV W2). This indicates the significant effect of RL over the LLM-based evolution with the same computation budget.

Would using just LLM or RL directly be sufficient? Therefore, LLM-based evolution alone or RL alone is not sufficient in our setting. The good results reported in the literature were obtained by writing short heuristics from scratch, and they are measured against other heuristics rather than against a mature solver. In other words, the simple heuristics evolved by these methods are behind the HGS solver. Taking CALM [1] as an example, as shown in Table R11 below, the gap of its CVRP heuristic to HGS-PyVRP under the same runtime can reach up to 25.31%.

Table R11: The CVRP heuristic released by CALM against HGS-PyVRP under the same runtime. Values are mean ± SD over three test instances per size. Gap is relative to HGS-PyVRP.

nCALM OBJ ± SD ↓HGS-PyVRP OBJ ± SD ↓Gap ± SD (%)
509.073 ± 0.4048.073 ± 0.14112.35 ± 3.36
10015.760 ± 0.85412.916 ± 0.76322.04 ± 0.60
20027.845 ± 0.53322.228 ± 0.66125.31 ± 2.74
AuthorsOpenReview ↗

Response to Reviewer 8HmP (2/5)

Since these heuristics are well behind the solver, to examine whether just LLM or RL is sufficient, we adapted the methods in literature to our problem, i.e., evolving an operator inside HGS-PyVRP. None of them improves HGS-PyVRP consistently:

  • Evolution with a fixed LLM. ReEvo is not effective: its gains over HGS-PyVRP are inconsistent across variants and sizes, and not statistically significant (Tables 1 and 7 of our paper). In the zero-shot setting, its operators are worse than HGS-PyVRP in most unseen settings (Tables 2 and 10 in our paper), so it turns a general-purpose solver into a problem-specific one.
  • Evolution with RL but without SFT. EvoTune is worse than HGS-PyVRP in all 18 settings (Table 1 in our paper), and CALM is worse than HGS-PyVRP at all three sizes (Table R3, our response to Reviewer vVXj W1).
  • RL without evolution and without SFT. RFTHGS fine-tunes an LLM with RL for CVRP only and brings no statistically significant gain over HGS-PyVRP on CVRPLIB (Tables 14–15 of our paper).

Therefore, we would like to emphasize that the integration is not random. It is a two-stage training framework designed for evolving a solver, in which each part has its own role, supported by the evidence above: SFT enhances LLM-based evolution to explore and select more valid candidates within a run, and RL turns solver feedback into a better LLM for generating better operators, which then seed the next rounds of evolution. For clarity, we now state these roles explicitly in Section 2 in the revised paper.

W2. EvoHGS seems to be more on a combination of existing methods or techniques (MVMoE, ReEvo into HGS), rather than devised to address key research questions leading to scientific insights.

We thank the reviewer for this comment. We do not refer to any existing techniques from MVMoE and ReEvo. EvoHGS is independent and even different from them in the conceptual level. MVMoE aims to train a single neural solver for a predefined group of VRP variants from scratch. ReEvo aims to evolve standalone heuristics with a fixed LLM. Nevertheless, EvoHGS aims to train an LLM to improve a state-of-the-art solver while keeping it general-purpose. Our motivation is because state-of-the-art VRP solvers such as HGS are general-purpose, i.e., one framework handles many VRP variants, and HGS solver (HGS-PyVRP) still outperforms existing models such as MVMoE and ReEvo. The way to obtain practical gains is therefore to evolve the solver itself while preserving its generality.

Specifically, ReEvo applied to HGS-PyVRP, which is our baseline, does not improve the solver consistently, as shown in Tables 1 and 7 in our paper. MVMoE does not outperform HGS on the variants where HGS is reported (CVRP and VRPTW) in its original paper [2]. In contrast, EvoHGS improves the solver with a novel two-stage training framework, which is, to the best of our knowledge, the first of its kind for evolving a solver with an LLM. It also leads to a scientific insight: for modifying a mature, interface-constrained solver, learning the structure and conventions of its codebase is essential, and cannot be obtained from pretraining alone, as shown in Figure 2 of our paper. We believe this is a useful and transferable message for the community of LLM-based code modification.

W3.1 "burden of manual design" is claimed as a research issue. Is operator design always the bottleneck of evolutionary algorithms or HGS?

The burden of manual design is widely recognized as a research challenge in the evolutionary computation literature; it is not a claim made only by us. A survey describes manual algorithm design as "laborious, error-prone, and requiring intensive specialized knowledge" [3]. Another study notes that the design of metaheuristics is "mostly guided by human expertise, intuition and a great deal of trial-and-error" and "often fails to fully explore the space of possible metaheuristic designs" [4]. We do not claim that operator design is always the bottleneck of evolutionary algorithms. Our point is that designing operators by hand needs expert knowledge and many rounds of experiments, so automating it is worth studying. For HGS, we state this in Section 1 of our paper: "Despite its strong empirical performance, the implementation of search mechanisms in HGS still depends heavily on human expertise and extensive empirical tuning. This limitation becomes more pronounced across the diverse family of VRP variants, where differing constraint structures often hinder the transferability of mechanisms that perform well in one variant to others." In other words, each new VRP variant requires the operators to be designed and tuned by hand again. This repeated effort is the "burden of manual design" we refer to [5].

AuthorsOpenReview ↗

Response to Reviewer 8HmP (3/5)

W3.3 Why focusing on crossover not mutation, the former causes more problems for constrained problems like VRP?

We would like to clarify two points:

  • HGS has no mutation operator. We must clarify that, in the canonical HGS literature and code, there is no random mutation operator in the conventional sense [5,7]. The PyVRP implementation relies exclusively on crossover for recombination, followed strictly by local search, which replaces the perturbation typically provided by mutation. The choice between crossover and mutation therefore does not arise in this framework.
  • SREX is a crossover designed for routing problems with constraints. It was first proposed for such a problem [9]. It exchanges whole routes between the two parents, so no customer appears twice, and the customers that are left out are added back by the search that follows [5]. Solutions that violate constraints are handled by HGS itself, through local search and penalties, and we do not change this part. For these reasons, SREX does not cause extra problems under constraints. As we state in Appendix C.3 in our paper: "We evolve PyVRP's default selective route exchange (SREX) crossover because crossover is a key component of HGS and SREX has received substantial attention from human experts."

W3.4 No motivations have been clearly provided to answer meaningful scientific questions in evolutionary computation.

We would like to emphasize again that the core of EvoHGS is not to study evolutionary computation itself, but to train an LLM so that it improves a state-of-the-art HGS-PyVRP solver while keeping it general-purpose. As we state in Section 1 of our paper: "To address the challenges, we propose EvoHGS, a training-driven LLM framework that co-evolves an LLM policy and a pool of executable HGS operator modifications." In this setting, HGS is the solver being improved, and evolutionary search is the tool used to explore candidate operators. The motivation is also stated in Section 1 in our paper: "However, improving HGS requires a paradigm that differs from general LLM-based automatic heuristic design. Existing LLM-based methods often generate standalone heuristics or programs, whose quality can be assessed independently after execution. In contrast, HGS is an intricate pipeline in which components such as recombination, local improvement, and selection are tightly coupled." In addition, an operator tuned for one VRP variant does not necessarily help on other variants, so the improved solver should remain general-purpose.

Even so, our work also answers a meaningful scientific question in evolutionary computation, namely how an LLM can help in evolving a mature solver whose components are tightly coupled. Our answer is that the LLM must first learn the solver itself. As we state in Section 5.1 of our paper: "modifying a mature solver such as HGS first requires the model to learn the expected code structure, interface conventions, and implementation constraints". Without this step, evolution with a fixed LLM brings no statistically significant improvement over HGS-PyVRP, and evolution with RL is even worse than the original HGS-PyVRP, as shown in Tables 1, 7 and 8 in our paper.

W4. research aim is to "enhance the adaptability and automation of HGS search": Would just one of RL or LLM suffice and much cheaper, to address this aim of practical VRP solvers?

Thank you, this is a thoughtful question. However, our answer is that neither of them alone would suffice for this aim, and neither would be much cheaper.

Reviewer_vVXjOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper presents EvoHGS, a framework for automatically improving internal operators of Hybrid Genetic Search (HGS) using a large language model. The method first fine-tunes Qwen3-8B on operator implementations generated through ReEvo (NeurIPS 2024) across multiple VRP variants. It then alternates evolutionary search over candidate operators with GRPO updates to the language model, jointly improving the candidate pool and the generation policy. The main experiments target the selective route exchange crossover operator in PyVRP and evaluate six seen variants, multiple instance sizes, and ten unseen combinations of constraints. Additional experiments extend the framework to population management. The results show improved code validity and gains in solution quality in several settings.

Critical strengths

S1. Clear integration of model adaptation and solver feedback

The framework combines offline SFT on data spanning multiple VRP variants with online evolutionary search and GRPO updates in a coherent architecture. Candidate operators are integrated into HGS and evaluated through complete solver runs, providing feedback for both operator selection and policy updates. This creates a clear connection between code generation, downstream optimization performance, and model adaptation.

S2. The results provide encouraging evidence of cross-scale and cross-variant generalization

Evolved operators are transferred to unseen constraint combinations without additional search or fine-tuning. At 100 nodes, the reported mean objectives improve over HGS-PyVRP on all ten unseen variants, and gains persist in some 500- and 1,000-node settings. The POP extension also demonstrates cross-variant transfer, including an approximately 0.827% improvement on OVRPBL with 1,000 nodes (Tables 10 and 16).

Critical weaknesses

W1. The methodological contribution relative to the closest prior work remains insufficiently delineated

CALM (ICLR 2026) already incorporates LLM-based AHD and verifiable reward RL. RFTHGS (ICLR 2026) already uses an RL fine-tuned LLM to improve HGS-PyVRP and uses AST-based comparison to penalize copying of operator examples. Section 2 identifies multi-variant SFT, adaptation to the HGS interface, and online updates as distinguishing features. However, it does not sufficiently establish what new methodological mechanism emerges beyond these existing ingredients.

The specific gaps are a detailed comparison of the core mechanisms and a direct comparison with CALM adapted to the same HGS task. The paper does include EvoTune (COLM 2025) and RFTHGS, so relevant baselines are not entirely absent. Nevertheless, those comparisons do not clearly isolate the incremental contribution over existing frameworks.

W2. The sources of the gains from multi-variant SFT and online RL are not fully disentangled

Comparing training with and without SFT changes interface familiarity, code priors, and exposure to multiple VRP variants simultaneously. This does not isolate the claim that multi-variant training teaches transferable constraint knowledge. The single-task versus multi-task comparison in Table 11 and Section F.1 concerns the GRPO stage, rather than the composition of the SFT data. A comparison between single-variant and multi-variant SFT with matched dataset sizes is missing.

Section D.2 also explicitly states that the component ablations in Table 8 use the evolution instances. The corresponding complete set of ablations is not reported on held-out instances of the seen tasks. Table 11 does provide evidence of an incremental GRPO benefit on some unseen variants, which should be acknowledged, but it does not fully resolve this attribution issue. Finally, because candidate validity rates differ substantially across configurations, a comparison controlling the number of valid solver evaluations is needed to distinguish gains from reducing invalid generations from gains in the quality of valid candidates (Sections D.2 and E).

W3. The artifacts needed to verify the final operators, and the analysis of their improvements, remain incomplete

The provided manuscript includes prompts, interface descriptions, and procedural details, but does not include the complete final SREX/POP implementations or precise diffs against the original operators. Code and model weights are promised upon acceptance. Since the final operators can run independently of the language model, providing these artifacts would allow readers to verify the reported gains without repeating the entire training and search process.

There is useful operator analysis: Table 9 and Figure 3 trace changes involving route-size matching, vehicle-type compatibility, pairing windows, and offspring selection in a representative run. Section F.2 also discusses possible explanations for runtime differences. However, the paper does not report controlled removal or addition of the key rules in a final operator, or direct measurements that substantiate the proposed mechanisms. Multiple changes occur along a single trajectory, and the recorded performance is measured on evolution instances, so the contribution of each change remains unclear. For POP, which produces larger improvements, the precise changes to fitness, survivor selection, or population maintenance are also not disclosed (Sections D.3 and F.2–F.3).

Questions for authors

Q1. Could the authors provide the complete final evolved operators and the materials needed for direct verification?

Appendix B provides prompt and interface templates, while Table 9 describes modification ideas. I could not locate the final SREX/POP implementations underlying the reported results in the provided manuscript. Please provide their complete source code and diffs against the original PyVRP implementation in anonymous supplementary material or an anonymous repository, identifying the task, run, and table entries associated with each operator. Please also include a minimal evaluation script and the test instances, or generation scripts and seeds sufficient to recover the same instances. If these artifacts are already available in separate supplementary material, please identify their location.

Q2. Which specific modifications in the final operators account for the performance gains?

Table 9 documents the evolution of design choices but does not isolate their effects; the framework-level ablations in Tables 8 and 11 address a different question. Could the authors evaluate controlled removal or addition of key rules, such as route-size matching, pairing-window selection, and offspring selection, on held-out instances? For POP, please specify the final modified rules and support the proposed explanation with relevant measurements, such as actual population size, diversity, or computational overhead.

Q3. Are the gains robust to solver randomness and a broader range of computational budgets?

Section D.1 states that evaluation uses solver seed 0 and that the reported standard deviations reflect three independent evolution runs rather than variation across solver seeds. Section F.2 already evaluates 800, 1,000, and 1,200 iterations and reports runtime differences, but these are not comparisons under equal wall-clock limits. Could the authors provide paired evaluations across multiple HGS seeds, together with equal-time comparisons and substantially longer iteration budgets, to assess whether the gains persist?

15 comments
AuthorsOpenReview ↗

Response to Reviewer vVXj (1/8)

W1. The methodological contribution relative to the closest prior work remains insufficiently delineated CALM (ICLR 2026) already incorporates LLM-based AHD and verifiable reward RL. RFTHGS (ICLR 2026) already uses an RL fine-tuned LLM to improve HGS-PyVRP and uses AST-based comparison to penalize copying of operator examples. Section 2 identifies multi-variant SFT, adaptation to the HGS interface, and online updates as distinguishing features. However, it does not sufficiently establish what new methodological mechanism emerges beyond these existing ingredients.

The specific gaps are a detailed comparison of the core mechanisms and a direct comparison with CALM adapted to the same HGS task. The paper does include EvoTune (COLM 2025) and RFTHGS, so relevant baselines are not entirely absent. Nevertheless, those comparisons do not clearly isolate the incremental contribution over existing frameworks.

We thank the reviewer for this comment. The methodological novelty of EvoHGS is a two-stage training framework in which SFT and RL play different roles. CALM [1] and RFTHGS [2] apply RL directly to a general-purpose LLM, so much of the early exploration is wasted on invalid code: these general-purpose models are only capable of generating valid candidates that compile and run in HGS 25.1% of the time (Figure 2 of our paper). In EvoHGS, multi-variant SFT first teaches the LLM to write valid operators for multiple variants, which avoids this wasted early exploration and gives the LLM generality across variants (Figure 2 and Table 11 of our paper), and RL inside the evolutionary loop then co-evolves the LLM with the pool of operators, which further improves performance (ablation in Table 8 of our paper). As far as we are aware, this is the first two-stage training framework for evolving a solver with an LLM, and it is what enables an 8B model to improve a state-of-the-art solver while keeping it general-purpose (Tables 1 and 2 of our paper). Below we compare EvoHGS with CALM and RFTHGS in turn, starting with CALM.

CALM designs heuristics from scratch, typically as short Python functions. In our work, evolving a solver is definitely a different job. the LLM has to rewrite a complete C++ operator of HGS-PyVRP [3], and an 8B model that has not been fine-tuned on the solver spends much of the early search on code that does not work: in our ablation, only 25.1% of such candidates compile and run in HGS (Figure 2 of our paper). To test this directly, we adapted CALM to the same task, the SREX crossover of HGS-PyVRP on CVRP, with an 8B model and the same 1000 LLM queries per run. For this task CALM turns out to be ineffective, in time as well as in results. From Table R3 below, a CALM search takes about 48 hours, against 6.8 hours for EvoHGS after a one-time 8-hour SFT (Table 5 of our paper), and averaged over three runs the operators CALM returns are worse than the original solver at all three sizes.

Table R3: CALM adapted to the HGS crossover task on CVRP. Values are mean ± SD over three independent runs, each with a budget of 1000 LLM queries, and every operator is evaluated with 1000 HGS iterations. Mean Gap is relative to the original HGS-PyVRP. Bold marks the best value in each column.

MethodMean OBJ ± SD ↓ (n = 100)Mean Gap ± SD (%) ↓Mean OBJ ± SD ↓ (n = 500)Mean Gap ± SD (%) ↓Mean OBJ ± SD ↓ (n = 1000)Mean Gap ± SD (%) ↓
CALM15.793 ± 0.0020.054 ± 0.01537.839 ± 0.1000.255 ± 0.26651.420 ± 0.1530.208 ± 0.299
EvoHGS15.760 ± 0.002−0.156 ± 0.01337.763 ± 0.0640.051 ± 0.16951.346 ± 0.0310.064 ± 0.059

RFTHGS is closer to our setting because it does modify HGS, but it fine-tunes a 14B LLM with RL for a single problem only (CVRP). This turns a general-purpose solver into a problem-specific one, and it is computationally heavy (8 GPUs in its official release). Moreover, RFTHGS wastes much of its exploration on invalid code: in our reproduction of RFTHGS, only 3/10 operators compile (Appendix F.2 of our paper). In contrast, EvoHGS outperforms RFTHGS with an 8B model (Table 15 of our paper). Therefore, EvoHGS novelly proposes two methodological innovations:

  • (1) We first apply SFT, so that the LLM generates valid code and generalizes across variants: SFT raises the compilable share to 85.3% (Figure 2 in our paper), and evolution from the SFT checkpoint improves significantly over HGS on all three unseen variants tested, whereas evolution without SFT does so on none (Table 11 in our paper).
  • (2) We then apply RL inside the evolutionary loop, so that the LLM and the pool of operators co-evolve and RL can focus on improving performance, which further lowers the gap (Table 8 in our paper).
AuthorsOpenReview ↗

Response to Reviewer vVXj (2/8)

We respectfully emphasize that EvoHGS is not just an incremental improvement over existing frameworks. Instead, it solves a fundamental problem that prior methods cannot: improving a state-of-the-art solver while preserving its general-purpose capability. To the best of our knowledge, few frameworks currently consider the general-purpose capability and they somehow overfit LLM power to a specific problem. Even so, baselines such as CALM, EvoTune [4] and ReEvo [5] were built to design short heuristics, which are themselves weaker than a state-of-the-art solver. For evolving a solver, they do not hold up:

  • ReEvo loses generality (Tables 2 and 10 of our paper),
  • CALM ends worse than the original solver after about 48 hours of search (Table R3),
  • and EvoTune is worse than the original solver in all 18 settings (Table 1 of our paper).
  • RFTHGS brings no significant gain (Table 15 of our paper) while turning the general-purpose solver into a problem-specific one. EvoHGS achieves both (Tables 2, 7 and 10 of our paper).

Given our novel training and co-evolving framework, our method has shown much better performance than these baselines (Tables 1, 2, 10, 14, and 15 in our paper).

W2. The sources of the gains from multi-variant SFT and online RL are not fully disentangled Comparing training with and without SFT changes interface familiarity, code priors, and exposure to multiple VRP variants simultaneously. This does not isolate the claim that multi-variant training teaches transferable constraint knowledge. The single-task versus multi-task comparison in Table 11 and Section F.1 concerns the GRPO stage, rather than the composition of the SFT data. A comparison between single-variant and multi-variant SFT with matched dataset sizes is missing.

Section D.2 also explicitly states that the component ablations in Table 8 use the evolution instances. The corresponding complete set of ablations is not reported on held-out instances of the seen tasks. Table 11 does provide evidence of an incremental GRPO benefit on some unseen variants, which should be acknowledged, but it does not fully resolve this attribution issue. Finally, because candidate validity rates differ substantially across configurations, a comparison controlling the number of valid solver evaluations is needed to distinguish gains from reducing invalid generations from gains in the quality of valid candidates (Sections D.2 and E).

W2P1: We thank the reviewer for raising this distinction. The experiment below supplements the zero-shot ablation in Table 11 of the paper, which attributes zero-shot transfer primarily to SFT. That SFT uses data from six VRP variants. To test what the multi-variant data contributes, we trained a separate SFT checkpoint on CVRP data only and ran the co-evolution from it. We call the result EvoHGS (CVRP-only SFT); EvoHGS (six-variant SFT) below is the EvoHGS (single-task) configuration of the manuscript. We evaluated the CVRP-only version on CVRP and then, without any further adaptation, on OVRPB, OVRPBL, and OVRPBLTW, none of which it saw during fine-tuning. All instances have 100 nodes. Table R4 below gives the CVRP results and Tables R5a–R5c the zero-shot results.

Table R4: CVRP results. Values are reported as mean ± SD. Mean Gap is relative to the original HGS-PyVRP (Org).

MetricReEvoEvoHGS (CVRP-only SFT)EvoHGS (six-variant SFT)
Mean OBJ ± SD ↓15.781 ± 0.02215.755 ± 0.00115.760 ± 0.002
Mean Gap ± SD (%) ↓−0.025 ± 0.141−0.188 ± 0.003−0.156 ± 0.013
AuthorsOpenReview ↗

Response to Reviewer vVXj (3/8)

Table R5a: Zero-shot results on OVRPB. Mean Gap is relative to the original HGS-PyVRP. Significance tests are against Org or ReEvo, as indicated in the column headings; (*) p < 0.05, (**) p < 0.01.

MethodMean Gap ± SD (%) ↓z vs. Orgp vs. Orgz vs. ReEvop vs. ReEvo
ReEvo0.010 ± 0.002−1.5090.934——
EvoHGS (CVRP-only SFT)−0.013 ± 0.0160.1380.4451.6690.048 (*)
EvoHGS (six-variant SFT)−0.019 ± 0.0051.3350.0913.207<0.001 (**)

Table R5b: Zero-shot results on OVRPBL. Metrics and comparisons are the same as in Table R5a.

MethodMean Gap ± SD (%) ↓z vs. Orgp vs. Orgz vs. ReEvop vs. ReEvo
ReEvo−0.022 ± 0.0041.1680.121——
EvoHGS (CVRP-only SFT)−0.059 ± 0.0381.2760.1010.1520.439
EvoHGS (six-variant SFT)−0.065 ± 0.0113.990<0.001 (**)2.3250.010 (*)

Table R5c: Zero-shot results on OVRPBLTW. Metrics and comparisons are the same as in Table R5a.

MethodMean Gap ± SD (%) ↓z vs. Orgp vs. Orgz vs. ReEvop vs. ReEvo
ReEvo−0.0012 ± 0.00160.2350.407——
EvoHGS (CVRP-only SFT)0.0079 ± 0.04000.5440.2931.0890.138
EvoHGS (six-variant SFT)−0.0073 ± 0.00182.8210.002 (**)1.8950.029 (*)

As Table R4 above shows, EvoHGS (CVRP-only SFT) reaches a lower mean objective than ReEvo on CVRP. We attribute this to SFT as such. A model that already knows the solver interface and the code structure it requires wastes far fewer generations on invalid code, which leaves more compute for effective exploration.

On the unseen variants, EvoHGS (CVRP-only SFT) shows no statistically significant improvement over the original HGS-PyVRP (Org), yielding a positive mean gap on OVRPBLTW and only statistically significantly outperforming ReEvo on OVRPB. In contrast, EvoHGS (six-variant SFT) statistically significantly beats ReEvo across all three variants and outperforms Org on OVRPBL and OVRPBLTW with a much smaller standard deviation (Tables R5a–R5c).

As a conclusion, while any SFT teaches the model to generate valid solver code, robust zero-shot generalization requires multi-variant SFT; training solely on CVRP simply degrades a general-purpose solver into a CVRP-specific one.

W2P2: To first clarify the terminology for the datasets used in our evaluation:

  • 100_val in Table 9& Figure 3 of our paper: The 100-node validation set used during the search (i.e., evolution instances).
  • 100 in all other tables of our paper: The unseen 100-node test set evaluated post-evolution (i.e., held-out instances, disjoint from 100_val).

We first clarify that Section D.2 mistakenly reported using 100_val; the evaluation was actually conducted on 100. The text in the appendix has been updated accordingly to reflect this correction.

Section D.3 illustrates the evolutionary trajectory by tracking successive best operators. Because the search actively uses 100_val to identify these new versions, this progression is naturally recorded on 100_val. To verify that these improvements do not overfit the validation data, Table R6 below reports the gaps on both datasets, showing that the performance gains achieved on 100_val consistently translate to the unseen 100 test set.

Table R6: Successive best versions in comparison order. Gaps (%) are relative to the original HGS-PyVRP evaluated on the corresponding dataset (100_val or 100). Query denotes the index, among the 1000 LLM queries of the run, at which the representative operator was obtained.

Query3106136149373884996
100_val-0.001%-0.014%-0.032%-0.061%-0.089%-0.132%-0.153%
100-0.001%-0.019%-0.030%-0.061%-0.094%-0.135%-0.157%

As a conclusion, we have provided evidence demonstrating the effectiveness of our method on both seen tasks and unseen task variants.

Finally, because candidate validity rates differ substantially across configurations, a comparison controlling the number of valid solver evaluations is needed to distinguish gains from reducing invalid generations from gains in the quality of valid candidates (Sections D.2 and E).

Please refer to our response in Table R2 (Fixed Generation vs. Fixed Valid), where we evaluate both methods after exactly 1,000 valid operators have been collected. Under this strict budget, EvoHGS maintains a significant advantage over SFT + Evo, driven by the inherent quality of the generated operators rather than a higher validity rate.

Reviewer_MzmVOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper aims to find better solutions for Vehicle Routing Problems (VRPs) by improving the Hybrid Genetic Search (HGS). This is achieved by using Large Language Models (LLMs) to generate modifications to the crossover operator, allowing the HGS to produce better routing solutions. The LLMs are then fine-tuned based on the feedback (rewards) of the actual routing execution to generate better modifications to the crossover operator. Repeating this process leads to the evolution of both the crossover operator and the LLM itself. This proposed approach is named EvoHGS in the paper. The authors claim that EvoHGS provides better solutions than original HGS on problems of the same scale, exhibits competitive performance on larger-scale problems, and shows generalisation to unseen VRP variants.

Critical strengths

As HGS is already a strong routing solver, improving its performance using LLM-based automated code generation is an interesting research direction. The experimental results support that the Supervised Fine-Tuning (SFT) improves the LLM’s capability to generate valid modifications to the crossover operator, as demonstrated by the higher percentage of generated modification (code) that can be compiled. The conducted experiments cover different VRP variants and problem sizes, including the unseen combinations of constraints. The paper also conducted meaningful ablation experiments to investigate the contributions of SFT and Group Relative Policy Optimisation (GRPO) to the proposed approach.

Critical weaknesses

The paper claims that GRPO contributes to the performance improvement. Although this claim is statistically supported by the experiments (p=0.049), the reported p-value is very close to the conventional significance threshold of 0.05. It would be better to further verify whether this improvement is consistent across more independent training runs or using different solver random seeds. Furthermore, GRPO increases the code compilability rate, which means that further ablation experiments would help clarify whether the GRPO generates better crossover operators or whether the improvement comes from more compilable candidates. My main concern is the methodological novelty, as previous papers, such as Algorithm Discovery With LLMs: Evolutionary Search Meets Reinforcement Learning and Mathematical discoveries from program search with large language models, have already proposed similar approaches.

Questions for authors

Can the authors explain whether GRPO generates better crossover operators when evaluated using the same set of compilable caididates? That would provide more straightforward evidence to support their approach. If the results are positive, I would consider increasing my score.

6 comments
AuthorsOpenReview ↗

Response to Reviewer MzmV (1/3)

We sincerely thank the reviewer for their careful evaluation and valuable feedback. Below, we provide detailed clarifications to address your concerns point by point. For your convenience, additional tables included in this response are denoted in bold with an "R" prefix (e.g., Table R1), whereas italicized references (e.g., Table 1) refer to results already present in our paper.

W1. The paper claims that GRPO contributes to the performance improvement. Although this claim is statistically supported by the experiments (p=0.049), the reported p-value is very close to the conventional significance threshold of 0.05. It would be better to further verify whether this improvement is consistent across more independent training runs or using different solver random seeds.

Table 8 of our paper is already the results of three independent training runs. The overall significance (p=0.049) is calculated by averaging the objective values across the three runs for each instance, and then applying the significance test to the averaged values. A closer look at the three individual runs in Table R1 below reveals a significant consistency: EvoHGS manages to improve upon the SFT+Evo setup in every single run, with most p values smaller than 0.045 and some even smaller than 0.03.

Table R1: Cross-validation of EvoHGS against SFT + Evo across all combinations of independent runs. The row and column headers indicate the specific run and its corresponding performance gap relative to the original PyVRP [1] baseline (Gap vs. Ori). Each cell reports the Win/Tie/Loss instances of EvoHGS compared to SFT + Evo, followed by the Wilcoxon test statistics (z / p).

EvoHGS ↓ \ SFT + Evo →r1r2r3
r135/0/15 (1.762 / 0.039*)37/0/13 (1.887 / 0.030*)34/0/16 (1.713 / 0.043*)
r235/0/15 (1.675 / 0.047*)30/0/20 (1.665 / 0.048*)28/0/22 (1.694 / 0.045*)
r332/0/18 (2.071 / 0.019*)34/0/16 (1.656 / 0.049*)32/0/18 (2.244 / 0.012*)

Much Smaller p in the Main Comparisons. Additionally, we would like to clarify that p=0.049 is just an ablation result comparing our full model EvoHGS (SFT + evolution + GRPO) with its variant without GRPO (SFT + evolution), isolating the marginal gain of GRPO. As our main aim of automatically improving HGS solver, we have obtained significant results in the main comparisons:

  • As detailed in Table 8 of our paper, our advantage translates into a decidedly significant improvement (p=0.003) when compared to the original PyVRP baseline.
  • Paired tests show that EvoHGS statistically significantly outperforms both the original solver (HGS-PyVRP) and the strongest baseline (ReEvo [2]), including seen tasks (Table 7 in our paper) and unseen variants (Table 11 in our paper), with significantly small p values reaching p<0.001.

W2. Furthermore, GRPO increases the code compilability rate, which means that further ablation experiments would help clarify whether the GRPO generates better crossover operators or whether the improvement comes from more compilable candidates.

We thank the reviewer for the constructive feedback. In our experimental settings and definition, each run has a fixed budget of 1,000 LLM generations, which generates 1,000 HGS operators in total, including situations of no extractable code, compilation failures and compilable candidates. This ensures a fair comparison with the same budget of LLM calls.

A generated operator goes through the same pipeline: code extraction, compilation within PyVRP, and then a complete HGS run on the instances. A generation is considered "valid" strictly if it successfully passes all three stages. We have clarified this definition in Figure 2 our paper to prevent any misunderstanding. Consequently, the rate shown is the number of valid generations divided by our total budget of 1,000 LLM generations.

As for the reviewer’s suggestion to compare on “the same set of compilable candidates”, we clarify that EvoHGS does not select operators from a fixed pool; they are generated dynamically. After the first RL update, the two candidate sets can no longer be identical. To isolate the effect of GRPO with the same set of compilable candidates, we therefore designed two additional controlled experiments. In the two settings, the initial pool is filled with exactly the same seed operators up to the target size (Lp=8), and the co-evolving step begins only after this pool is full. Starting from this common point, we tested two conditions.

  • In Fixed Generation, the search stops after 1,000 total generations, similar to our original runs but now with an identical initial pool.
  • In Fixed Valid, the search stops only after exactly 1,000 valid operators have been collected.

The latter condition addresses the concern about runs having different numbers of compilable candidates. The results are gathered in Table R2 below.

AuthorsOpenReview ↗

Response to Reviewer MzmV (2/3)

Table R2: Performance comparison under Fixed Generation (1000 total generations) and Fixed Valid (1000 compilable candidates) budgets.

ConditionMethodGap vs. Ori (%) ↓Comp. Rate (Valid/Gen.) ↑W/T/L (z / p) vs. OriW/T/L (z / p) vs. Previous
Fixed Generationw/ SFT, w/ Evo-0.11782.2 (822 / 1000)34/1/15 (2.084 / 0.019*)-
EvoHGS-0.16288.3 (883 / 1000)34/1/15 (2.969 / 0.001**)27/5/18 (1.727 / 0.042*)
Fixed Validw/ SFT, w/ Evo-0.10986.4 (1000 / 1158)30/1/19 (1.733 / 0.042*)-
EvoHGS-0.15590.9 (1000 / 1100)33/1/16 (2.362 / 0.009**)29/1/20 (1.778 / 0.038*)

As detailed in Table R2 above, even when restricted to evaluating an identical number of valid operators, EvoHGS (SFT+Evo+RLFT) yields a tighter final gap. Beyond the final solution quality, it converges noticeably faster. Take the Fixed Generation setting, for instance: EvoHGS discovers its best heuristic by the 604th query, whereas SFT+Evo does not reach this milestone until query 915. This acceleration holds under the Fixed Valid protocol as well, with the best solutions emerging at the 649th and 883rd queries, respectively. Ultimately, EvoHGS proves more sample-efficient, requiring just 1,100 total queries to clear the 1,000 valid operator threshold compared to 1,158 for the baseline. Notably, giving SFT + Evo even 178 more valid evaluations (822 to 1000) does not improve its result and it remains behind EvoHGS under both budgets. The advantage of GRPO therefore does not come from producing more compilable candidates but from steering the model to generate inherently better operators.

W3. My main concern is the methodological novelty, as previous papers, such as Algorithm Discovery With LLMs: Evolutionary Search Meets Reinforcement Learning and Mathematical discoveries from program search with large language models, have already proposed similar approaches.

Regarding methodological novelty, we agree that combinining LLMs with evolutionary search is a commonly used paradigm in similar fields. FunSearch [3] evolves programs with a fixed LLM for the cap set and online bin packing problems, while EvoTune [4] alternates evolutionary search with DPO for bin packing, the traveling salesman problem, and FlatPack. We have already included them in the related work of our paper. However, our methodology has significantly more distinctions from them beyond the common evelutionary search concept.

Specifically, our novelty does not lie in the established LLM+evolutionary search. We propose a training framework designed to modify the internal mechanics of a SOTA VRP solver across a diverse family of problem variants. This task introduces strict practical constraints. A candidate must compile within the solver's codebase, and adhere to its native interface. Consequently, general coding ability falls short. Without fine-tuning, even capable LLMs struggle, producing valid candidates only 46.0% (GPT-5-nano [5]) and 25.1% (Qwen3-8B [6]) of the time (Figure 2 of our paper). Success demands strict structural conformity to the target codebase. This reality raises two distinct challenges that our framework resolves, offering novel and effective takeaways for LLM-driven code evolution:

(1) Interface alignment and transfer across variants via SFT. Existing systems like FunSearch and EvoTune build independent heuristic functions from scratch. However, such standalone functions rarely outperform existing strong solvers. EvoHGS takes a different route by enhancing the state-of-the-art solver internally. Since candidate operators must compile within PyVRP and strictly follow native HGS interfaces, raw coding skills fall short. Taking the base Qwen3 8B model as an example, without SFT, it generates valid code only 25.1% of the time, wasting the evolutionary budget on structural flaws. Our SFT phase dramatically lifts this compilation success rate to 85.3%.

More importantly, it unlocks zero-shot transfer to novel problem families. If we only apply evolution directly from the base model on three unseen variants, the process quickly stagnates. Starting from our SFT checkpoint, however, allows the evolution to successfully beat the HGS PyVRP baseline across all three cases, as shown in Table 11 of our paper.

AuthorsOpenReview ↗

Response to Reviewer MzmV (3/3)

(2) Solver with online policy update. Building upon the SFT model, GRPO updates the policy online using complete HGS evaluations. This differs fundamentally from Funsearch and EvoTune in how feedback is utilized. Specifically, GRPO operates on policy. It utilizes the magnitude of performance rewards, applying graded penalties for formatting, compilation, and runtime errors. Crucially, it can learn directly from invalid outputs. Such capability is vital in our context, where failures occur frequently and carry high costs. The empirical results strongly support this design. GRPO delivers the only statistically significant improvement in our component ablation study, detailed in Table 8 of our paper. This advantage remains robust even when we match the number of valid evaluations, as discussed in our response to W2. Additionally, it provides further zero-shot gains on the more challenging unseen variants OVRPBL and OVRPBLTW, shown in Table 11 of our paper.. By contrast, EvoTune with a mere off-policy DPO fails to show improvement over the HGS PyVRP baseline on CVRP instances of any size (Table 1 of our paper).

Fundamentally, SFT and RLFT (i.e.GRPO) serve complementary roles. SFT establishes a valid and transferable search space to ensure generalizability. Building on this foundation, RLFT then refines the operators through direct solver feedback. To provide greater clarity, we have explicitly highlighted these mechanics in the revised Section 2 and Appendix D.3. On a broader level, we believe this training-based approach offers a practical takeaway for the community. When an LLM is tasked with modifying an existing solver, raw programming capability simply falls short. The model must instead develop a deep understanding of the target codebase, encompassing its interfaces, data structures, and constraints. This level of intuition emerges only through dedicated training. This is a key methodological novelty of our training framework, which, to the best of our knowledge, has not been explored in the VRP literature.

Q1. Can the authors explain whether GRPO generates better crossover operators when evaluated using the same set of compilable caididates?

We appreciate the reviewer raising this point. We have detailedly answered this question in our response to your W2.

Citations:

[1] Wouda, Niels A., Leon Lan, and Wouter Kool. "PyVRP: A high-performance VRP solver package." INFORMS Journal on Computing 36.4 (2024): 943-955.

[2] Ye, Haoran, et al. "Reevo: Large language models as hyper-heuristics with reflective evolution." Advances in neural information processing systems 37 (2024): 43571-43608.

[3] Romera-Paredes, Bernardino, et al. "Mathematical discoveries from program search with large language models." Nature 625.7995 (2024): 468-475.

[4] Šurina, Anja, et al. "Algorithm Discovery With LLMs: Evolutionary Search Meets Reinforcement Learning." Second Conference on Language Modeling.

[5] Singh, Aaditya, et al. "Openai gpt-5 system card." arXiv preprint arXiv:2601.03267 (2025).

[6] Yang, An, et al. "Qwen3 technical report." arXiv preprint arXiv:2505.09388 (2025).

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.