- 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
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].
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.
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.
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:
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.