PyVRP$^+$: LLM-Driven Metacognitive Heuristic Evolution for Hybrid Genetic Search in Vehicle Routing Problems
作者: Manuj Malik, Jianan Zhou, Shashank Reddy Chirra, Zhiguang Cao
分类: cs.NE, cs.AI
发布日期: 2026-04-09
备注: 18 pages, accepted to the 25th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2026)
💡 一句话要点
PyVRP$^+$：基于LLM驱动的元认知启发式进化，用于车辆路径问题中的混合遗传搜索
🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)
关键词: 车辆路径问题 元启发式算法 大型语言模型 进化编程 元认知 混合遗传搜索 组合优化
📋 核心要点
- 设计高性能VRP元启发式算法面临领域知识依赖和手动调优的挑战，现有方法主要依赖即时反馈和黑盒代码突变。
- 论文提出元认知进化编程（MEP），将LLM提升为战略发现代理，通过推理-行动-反思循环，引导LLM进行启发式算法设计。
- 实验结果表明，MEP发现的启发式算法在VRP变体上显著优于原始HGS基线，解决方案质量提升高达2.70%，运行时间减少超过45%。
📝 摘要（中文）
针对车辆路径问题（VRP）等NP-hard组合优化问题，设计高性能的元启发式算法仍然是一个重大挑战，通常需要大量的领域专业知识和手动调整。最近的进展表明，大型语言模型（LLM）有潜力通过进化搜索来自动化这个过程。然而，现有的方法在很大程度上是反应式的，依赖于即时的性能反馈来指导本质上是黑盒的代码突变。我们的工作通过引入元认知进化编程（MEP）来突破这种模式，MEP将LLM提升为战略发现代理。MEP不是仅仅对性能分数做出反应，而是迫使LLM参与一个结构化的推理-行动-反思循环，促使其明确地诊断失败，制定基于预先提供的领域知识的设计假设，并实施解决方案。通过应用MEP来进化最先进的混合遗传搜索（HGS）算法的核心组件，我们发现了新的启发式算法，显著优于原始基线。通过引导LLM战略性地推理探索-利用的权衡，我们的方法发现了更有效和高效的启发式算法，适用于广泛的VRP变体。我们的结果表明，MEP发现的启发式算法在具有挑战性的VRP变体上，相对于原始HGS基线，解决方案质量提高了高达2.70％，运行时间减少了超过45％。
🔬 方法详解
问题定义：论文旨在解决车辆路径问题（VRP）中，设计高性能元启发式算法需要大量领域知识和手动调优的问题。现有方法如基于LLM的进化搜索，主要依赖即时性能反馈和黑盒代码突变，缺乏对问题本身的深入理解和策略性设计。
核心思路：论文的核心思路是引入元认知进化编程（MEP），将LLM从被动的代码突变器转变为主动的战略发现代理。MEP通过结构化的推理-行动-反思循环，引导LLM诊断失败原因，制定设计假设，并基于领域知识实施解决方案，从而更有效地搜索和优化启发式算法。
技术框架：MEP框架包含以下主要阶段：1) 推理（Reason）：LLM分析当前算法的性能，识别瓶颈和改进方向。2) 行动（Act）：LLM基于推理结果，利用预定义的领域知识，生成新的启发式算法或对现有算法进行修改。3) 反思（Reflect）：评估新算法的性能，并将其反馈给LLM，用于下一轮的推理和行动。该循环迭代进行，不断优化启发式算法。
关键创新：最重要的技术创新点在于将元认知能力引入到LLM驱动的启发式算法进化过程中。与传统的基于性能反馈的黑盒优化方法不同，MEP迫使LLM进行显式的推理和反思，从而能够更深入地理解问题，并制定更有效的解决方案。这种方法使得LLM能够更好地利用领域知识，并避免陷入局部最优。
关键设计：MEP框架的关键设计包括：1) 领域知识库：提供给LLM的关于VRP的先验知识，例如不同的路由策略、局部搜索算子等。2) 推理提示：引导LLM进行推理的提示语，例如“当前算法在哪些方面表现不佳？”，“可以尝试哪些改进策略？”。3) 行动空间：定义LLM可以采取的行动，例如修改现有代码、添加新的代码片段等。4) 评估指标：用于评估新算法性能的指标，例如总行驶距离、服务时间等。
🖼️ 关键图片
📊 实验亮点
实验结果表明，MEP在多个VRP变体上显著优于原始HGS基线。具体而言，在解决方案质量方面，MEP平均提升了2.70%；在运行时间方面，MEP平均减少了45%。这些结果表明，MEP能够有效地发现更有效和高效的启发式算法，从而显著提升VRP的求解性能。
🎯 应用场景
该研究成果可广泛应用于物流配送、交通运输、供应链管理等领域，通过自动化设计高性能的车辆路径算法，降低运输成本，提高服务效率。未来，该方法有望扩展到其他组合优化问题，例如旅行商问题、调度问题等，为各行业提供更智能的决策支持。
📄 摘要（原文）
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.