An LLM-Driven Beam Search Framework for Automated Heuristic Design for Capacitated Vehicle Routing Problem

Abstract

Large language model (LLM) based automated heuristic design (AHD) frameworks, such as EoH, FunSearch, and ReEvo, have shown promising performance on a variety of combinatorial optimization problems. However, most existing LLM-based AHD frameworks mainly focus on designing heuristics with the same functional role, although jointly designing functionally complementary heuristics often leads to better solution quality. To address this limitation, this study proposes LLM-BS, an LLM-driven beam search framework for AHD for the capacitated vehicle routing problem (CVRP). LLM-BS simultaneously designs a construction heuristic and a guided local search heuristic, and iteratively refines their combination through expansion and pruning to maintain effective coordination between the two heuristics. Extensive experiments on CVRPLIB benchmark instances show that LLM-BS achieves small gaps relative to the best-known solutions identified by heuristics while outperforming representative LLM-based AHD frameworks in terms of solution quality.