# PyVRP^+: LLM-Driven Metacognitive Heuristic Evolution for Hybrid Genetic Search in Vehicle Routing Problems

arXiv: https://arxiv.org/abs/2604.07872 · HTML: https://mlsanity.com/paper/2604.07872/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 34 references that are in the map.
- First posted on arXiv 9 Apr 2026.

## Builds on (most cited first, 13 of 13)

- [Self-Refine: Iterative Refinement with Self-Feedback](https://mlsanity.com/paper/2303.17651/) (2023)
- [The AI Scientist: Towards Fully Automated Open-Ended Scientific Discovery](https://mlsanity.com/paper/2408.06292/) (2024)
- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [ReEvo: Large Language Models as Hyper-Heuristics with Reflective Evolution](https://mlsanity.com/paper/2402.01145/) (2024)
- [MLGym: A New Framework and Benchmark for Advancing AI Research Agents](https://mlsanity.com/paper/2502.14499/) (2025)
- [Monte Carlo Tree Search for Comprehensive Exploration in LLM-Based Automatic Heuristic Design](https://mlsanity.com/paper/2501.08603/) (2025)
- [HSEvo: Elevating Automatic Heuristic Design with Diversity-Driven Harmony Search and Genetic Algorithm Using LLMs](https://mlsanity.com/paper/2412.14995/) (2024)
- [PyVRP: a high-performance VRP solver package](https://mlsanity.com/paper/2403.13795/) (2023)
- [Algorithm Discovery With LLMs: Evolutionary Search Meets Reinforcement Learning](https://mlsanity.com/paper/2504.05108/) (2025)
- [Large Language Models as End-to-end Combinatorial Optimization Solvers](https://mlsanity.com/paper/2509.16865/) (2025)
- [Large Language Models for Combinatorial Optimization: A Systematic Review](https://mlsanity.com/paper/2507.03637/) (2025)
- [How Should We Meta-Learn Reinforcement Learning Algorithms?](https://mlsanity.com/paper/2507.17668/) (2025)
- [Refining Hybrid Genetic Search for CVRP via Reinforcement Learning-Finetuned LLM](https://mlsanity.com/paper/2510.11121/) (2025)

## Built on by (most cited first, 1 of 1)

- [MeEvo: Metacognitive Evolution Combined with Natural Evolution for Automatic Heuristic Design](https://mlsanity.com/paper/2606.14202/) (2026)

## Abstract (arXiv)

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.