RouteRepair: Instance-Level Failure Diagnosis and Targeted Repair in LLM-Based Automated Heuristic Design for Routing Optimization

Large language model (LLM)-based automated heuristic design usually ranks candidate programs according to an aggregate objective, even though a strong routing heuristic may fail repeatedly on a coherent subset of instances. We introduce RouteRepair, a fixed-backbone framework that retains the instance-wise performance profile of each competitive parent, constructs parent-specific failure, strength, and protection sets, and uses this evidence to define a bounded program repair. A Failure Diagnosis Expert produces a structured, risk-aware repair brief; a separate Targeted Repair Expert modifies only the designated scoring rule or edge-prior function. Parent and child programs are evaluated on matched instances, solver seeds, settings, and budgets, and both successful and unsuccessful interventions are recorded in outcome-aware memory. We evaluate five adapters covering constructive TSP, guided local search (GLS) for TSP, constructive CVRP, ant colony optimization (ACO) for TSP, and ACO for CVRP. RouteRepair-GLS reduces the mean TSP gap from 1.7476% to 0.7587%. Under identical 2-opt postprocessing, the constructive TSP rule achieves a 2.8805% mean gap. Constructive CVRP lowers average route cost by 1.91% relative to the Savings heuristic and by 2.06% relative to the strongest LLM-evolved baseline. The ACO priors also improve matched hand-designed priors and retain gains on larger transfer instances. These results support instance-level, evidence-constrained repair as a practical complement to aggregate evolutionary search.