Publication Type

Conference Proceeding Article

Version

publishedVersion

Publication Date

5-2026

Abstract

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.

Keywords

Metaheuristic, Vehicle Routing Problem, Combinatorial Optimiza-tion, Large Language Model, Evolutionary Algorithm

Discipline

Artificial Intelligence and Robotics | Operations Research, Systems Engineering and Industrial Engineering

Research Areas

Intelligent Systems and Optimization

Areas of Excellence

Sustainability

Publication

AAMAS 2026: Proc. of the 25th International Conference on Autonomous Agents and Multiagent Systems, Paphos, Cyprus, May 25-29

First Page

2800

Last Page

2808

ISBN

9798400723179

Identifier

10.65109/ISFV2587

Publisher

ACM

City or Country

New York

Additional URL

https://doi.org/10.65109/ISFV2587

Download

Share

COinS