PyVRP+: LLM-Driven Metacognitive Heuristic Evolution for Hybrid Genetic Search in Vehicle Routing Problems
Authors: Manuj Malik, Jianan Zhou, Shashank Reddy Chirra, Zhiguang Cao
Organizations: Singapore Management University Singapore, Singapore · Nanyang Technological University Singapore, Singapore · University of Oxford Oxford, England
Designing high-performing metaheuristics for NP-hard combinatorial optimization problems, such as the Vehicle Routing Problem (VRP), remains a significant challenge, often requiring extensive domain expertise and manual tuning. Recent advances have demonstrated the potential of large language models (LLMs) to automate this process through evolutionary search. However, existing methods are largely reactive, relying on immediate performance feedback to guide what are essentially black-box code mutations. Our work departs from this paradigm by introducing Metacognitive Evolutionary Programming (MEP), a framework that elevates the LLM to a strategic discovery agent. Instead of merely reacting to performance scores, MEP compels the LLM to engage in a structured Reason-Act-Reflect cycle, forcing it to explicitly diagnose failures, formulate design hypotheses, and implement solutions grounded in pre-supplied domain knowledge. By applying MEP to evolve core components of the state-of-the-art Hybrid Genetic Search (HGS) algorithm, we discover novel heuristics that significantly outperform the original baseline. By steering the LLM to reason strategically about the exploration-exploitation trade-off, our approach discovers more effective and efficient heuristics applicable across a wide spectrum of VRP variants. Our results show that MEP discovers heuristics that yield significant performance gains over the original HGS baseline, improving solution quality by up to 2.70% and reducing runtime by over 45% on challenging VRP variants.
Figures & tables
Figure 1. An overview of MEP, which outlines a process for evolving high-performing heuristics. The process continues until convergence criteria or a maximum number of generations is reached, ultimately returning the best-performing heuristic. Diagram showing the process of evolving heuristics in MEP, including steps for convergence and selection of the best heuristic.
Component Evolved
Baseline Cost
Best Evolved Cost
Improvement
select_parents
7942166
7764815
2.23 %
select_survivors
7942166
7886852
0.69 %
update_penalties
7942166
7932973
0.12 %
Table 1. Average cost comparison of the original PyVRP components and the best components evolved by MEP on 100 TSP instances. Lower cost values indicate better performance.
Variant
Baseline Cost
MEP-Evolved Cost
Improvement
Baseline Time (s)
MEP-Evolved Time (s)
CVRP
64450.03
64236.30
0.33 %
9.55
9.11
GVRP
7686993.64
7532007.09
2.01 %
0.87
1.89
MDVRPTW
8955.11
8825.46
1.45 %
12.43
9.74
PCVRPTW
22975.85
22406.42
2.48 %
7.92
4.19
VRPB
83696.21
83146.06
0.66 %
14.07
13.85
VRPTW
33424.48
32521.75
2.70 %
17.03
14.66
Table 2. Performance comparison of the baseline PyVRP solver versus the PyVRP + equipped with the MEP-evolved operators across various VRP variants (average values are presented). Lower cost and shorter times indicate better performance.
Figure 3. Evolution of average cost values over 10 generations for TSP optimization using MEP for parent selection, with averages computed across 100 instances.
Variant
Baseline Cost
Full MEP Impr.
MEP-noInit Impr.
Reactive Evol. Impr.
CVRP
64450.03
0.33 %
0.28 %
−0.20 %
GVRP
7686993.64
1.82 %
0.98 %
1.30 %
MDVRPTW
8955.11
1.49 %
0.90 %
−2.05 %
PCVRPTW
22975.85
2.43 %
2.36 %
1.46 %
VRPB
83696.21
0.57 %
0.53 %
−0.39 %
VRPTW
33424.48
2.25 %
2.24 %
0.10 %
Table 3. Ablation study results for the select_parents operator, showing percentage improvement over the baseline. Average cost values are presented in the table.
Variant
select_parents
select_survivors
update_penalties
PyVRP +
CVRP
0.33 %
0.05 %
0.01 %
0.33 %
GVRP
1.82 %
0.08 %
0.13 %
2.01 %
MDVRPTW
1.49 %
−0.00 %
0.16 %
1.45 %
PCVRPTW
2.43 %
0.15 %
0.06 %
2.48 %
VRPB
0.57 %
0.04 %
0.05 %
0.66 %
VRPTW
2.25 %
0.29 %
0.35 %
2.70 %
Table 4. Generalization performance of individual versus combined MEP-evolved operators. The table shows the percentage improvement over the HGS baseline, with the final column ( PyVRP + ) representing a solver that integrates all individually evolved components.
Appendix figures & tables1 asset
Supplementary material from the paper’s appendix.
Appendix
Method
Average Cost
Gap vs. HGS Baseline
MEP-Evolved (Ours)
64 236.30
− 0.33 % (Improvement)
PyVRP Baseline (HGS)
64 450.03
0.00 %
POMO-MTL (DRL Solver)
71 575.70
+11.06 % (Worse)
Appendix
Table 5. Performance comparison of MEP-Evolved, PyVRP Baseline, and POMO-MTL (DRL Solver) on the CVRP benchmark. Lower cost indicates better performance.
The Capacitated Vehicle Routing Problem (CVRP), a fundamental combinatorial optimization challenge, focuses on optimizing fleet operations under vehicle capacity constraints. While extensively studied in operational research, the NP-hard nature of CVRP continues to pose significant computational challenges, particularly for large-scale instances. This study presents AILS-AHD (Adaptive Iterated Local Search with Automatic Heuristic Design), a novel approach that leverages Large Language Models (LLMs) to revolutionize CVRP solving. Our methodology integrates an evolutionary search framework with LLMs to dynamically generate and optimize ruin heuristics within the AILS method. Additionally, we introduce an LLM-based acceleration mechanism to enhance computational efficiency. Comprehensive experimental evaluations against state-of-the-art solvers, including AILS-II and HGS, demonstrate the superior performance of AILS-AHD across both moderate and large-scale instances. Notably, our approach establishes new best-known solutions for 8 out of 10 instances in the CVRPLib large-scale benchmark, underscoring the potential of LLM-driven heuristic design in advancing the field of vehicle routing optimization.
Zhuoliang Xie, Fei Liu, Zhenkun Wang +1
Southern University of Science and Technology · City University of Hong Kong
Vehicle Routing Problems (VRPs) are fundamental combinatorial optimization problems with widespread applications in various scenarios. The advanced optimization solvers can effectively solve such problems. However, modeling complex VRP variants for solvers often requires substantial domain expertise, which limits the accessibility of advanced optimization technologies. In this paper, we propose Reinforcement Learning Enhanced LLMAgents(RLEA), a multi-agent framework designed to automate the modeling of complex VRPs. RLEA introduces a lightweight neural Planner trained with Soft Q-learning to efficiently orchestrate the actions of LLM-based agents. In addition, we equip the system with an evolutionary memory module and retrieval-augmented generation, enabling the agent to leverage both accumulated experience and external solver knowledge during program generation and refinement for solving VRPs. We evaluated 48 distinct VRP variants across various solvers. The experimental results demonstrate that RLEA outperforms the previous state-of-the-ar method, achieving a 16.67% higher success rate while significantly reducing runtime errors. These results validate that integrating reinforcement learning with LLM-based reasoning is highly effective for automated optimization modeling. The appendix is available at: https://doi.org/10.5281/zenodo.19134435.
Yi Chen, Zikang Yu, Jiahai Wang +3
School of Computer Science and Engineering, Sun Yat-sen University, Guangzhou 510006, China · Department of Industrial Systems Engineering and Management, National University of Singapore, Singapore
The integration of Large Language Models (LLMs) into evolutionary frameworks has established a new paradigm for automated heuristic discovery. Despite their promise, these methods typically search in the discrete space of program syntax, relying on stochastic sampling to navigate a highly non-convex optimization landscape. This work proposes a continuous heuristic discovery framework that shifts optimization to a learned latent manifold. We employ an encoder to map discrete programs into continuous embeddings and train a differentiable surrogate model to predict performance, enabling gradient-based search. To regularize the optimization trajectory, an invertible normalizing flow maps these embeddings to a structured Gaussian prior, where we perform gradient ascent. The resulting optimized latent vectors are projected through a learned mapper into soft prompts, which condition a frozen LLM to synthesize novel executable heuristics. We evaluate the proposed method on the Traveling Salesman Problem (TSP), the Capacitated Vehicle Routing Problem (CVRP), the Knapsack Problem (KSP), and Online Bin Packing (OBP). Empirical results demonstrate that continuous latent-space optimization achieves performance competitive with state-of-the-art discrete evolutionary baselines while offering a complementary methodological alternative for automated algorithm design. The implementation code is available at https://github.com/cheikh025/LHS.