Large Language Models for Designing Heuristic Components in Vehicle Routing Problems

Destroy-and-repair (D&R) is a powerful framework for vehicle routing problems (VRPs), whose performance depends critically on the synergy between destroy and repair operators. While prior learning-based methods have primarily focused on repair, destroy operator design remains underexplored. We propose an LLM-based framework to automatically discover destroy heuristics for D&R. Instead of learning a neural destroy policy, our method leverages the code generation and algorithm synthesis abilities of large language models to produce explicit, executable, and plug-and-play destroy operators that can be directly integrated into existing solvers and paired with strong repair modules. Experiments on TSP and CVRP show that the discovered destroy heuristics consistently improve a fixed neural repair backend over the corresponding baseline. The learned heuristics also generalize competitively across multiple instance distributions. These findings highlight the potential of LLMs as a practical tool for modular heuristic discovery in VRPs, especially for components that are difficult to optimize through conventional learning approaches. © 2026 IEEE.