EvoHGS: Co-evolving Language Models with Hybrid Genetic Search for Vehicle Routing Problems

Vehicle Routing Problems (VRPs) are a fundamental class of combinatorial optimization problems aimed to find high-quality routes for vehicles under operational constraints. Despite decades of study in operations research, VRPs remain computationally challenging due to their NP-hardness, with additional difficulty introduced by the diverse constraint structures that arise across different variants. Hybrid Genetic Search (HGS) has emerged as a state-of-the-art metaheuristic framework for many VRP variants. However, its performance still depends heavily on manually designed search operators and empirical parameter tuning, limiting its ability to adapt automatically to complex and diverse problem settings. To address the limitation, we propose **EvoHGS**, a large language model (LLM)-guided evolutionary framework that automatically improves HGS across the VRP family. EvoHGS integrates LLM-based heuristic generation with evolutionary search, allowing candidate HGS operators to be generated, evaluated, selected, and refined through an iterative optimization process. To further align generation with downstream search performance, EvoHGS uses feedback collected during evolution to finetune the LLM via reinforcement learning. This enables the model to progressively produce operators that are better adapted to the search dynamics of HGS across VRP variants. Experiments on multiple VRP variants show that EvoHGS consistently outperforms the original HGS baseline at the scale used for evolution, remains competitive when the evolved operators are applied to larger instances, and demonstrates promising zero-shot generalization to unseen VRP variants.