Reproduce “PyVRP$^+$: LLM-Driven Metacognitive Heuristic Evolution for Hybrid Genetic Search in Vehicle Routing Problems” on OpenResearch

Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.

Universal app for Apple silicon and Intel. Requires macOS 11 or later.

About this paper

Manuj Malik, Jianan Zhou, Shashank Reddy Chirra, Zhiguang Cao

An LLM-driven framework, Metacognitive Evolutionary Programming (MEP), systematically evolves components of a state-of-the-art Hybrid Genetic Search (HGS) solver for Vehicle Routing Problems. This approach enhances solution quality by up to 2.70% and reduces runtime by over 45% across diverse VRP variants, outperforming human-designed baselines.

Key insights

  • Guiding LLMs through a structured metacognitive process (diagnosis, hypothesis, reflection) is crucial for effective heuristic discovery in complex algorithmic contexts, significantly outperforming reactive, feedback-driven approaches.
  • LLMs can generate sophisticated and high-performing heuristics that integrate advanced strategies, such as population stratification and adaptive diversity pressure, directly improving state-of-the-art solvers.
  • The discovered LLM-evolved heuristics demonstrate strong generalization capabilities, consistently providing performance improvements across diverse VRP variants even when not explicitly evaluated during the evolutionary process.

Summary by alphaXiv.

Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.