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

arXiv: https://arxiv.org/abs/2609.11452 · HTML: https://mlsanity.com/paper/2609.11452/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 22 of its 38 references that are in the map.
- First posted on arXiv 10 Sep 2026.

## Builds on (most cited first, 22 of 22)

- [Reflexion: Language Agents with Verbal Reinforcement Learning](https://mlsanity.com/paper/2303.11366/) (2023)
- [Self-Refine: Iterative Refinement with Self-Feedback](https://mlsanity.com/paper/2303.17651/) (2023)
- [AlphaEvolve: A coding agent for scientific and algorithmic discovery](https://mlsanity.com/paper/2506.13131/) (2025)
- [ReEvo: Large Language Models as Hyper-Heuristics with Reflective Evolution](https://mlsanity.com/paper/2402.01145/) (2024)
- [Evolution of Heuristics: Towards Efficient Automatic Algorithm Design Using Large Language Model](https://mlsanity.com/paper/2401.02051/) (2024)
- [Is Self-Repair a Silver Bullet for Code Generation?](https://mlsanity.com/paper/2306.09896/) (2023)
- [Evolution through Large Models](https://mlsanity.com/paper/2206.08896/) (2022)
- [EvoPrompting: Language Models for Code-Level Neural Architecture Search](https://mlsanity.com/paper/2302.14838/) (2023)
- [Language Model Crossover: Variation through Few-Shot Prompting](https://mlsanity.com/paper/2302.12170/) (2023)
- [Monte Carlo Tree Search for Comprehensive Exploration in LLM-Based Automatic Heuristic Design](https://mlsanity.com/paper/2501.08603/) (2025)
- [Graph Neural Network Guided Local Search for the Traveling Salesperson Problem](https://mlsanity.com/paper/2110.05291/) (2021)
- [EoH-S: Evolution of Heuristic Set using LLMs for Automated Heuristic Design](https://mlsanity.com/paper/2508.03082/) (2025)
- [Understanding the Importance of Evolutionary Search in Automated Heuristic Design with Large Language Models](https://mlsanity.com/paper/2407.10873/) (2024)
- [HeurAgenix: Leveraging LLMs for Solving Complex Combinatorial Optimization Challenges](https://mlsanity.com/paper/2506.15196/) (2025)
- [Efficient Heuristics Generation for Solving Combinatorial Optimization Problems Using Large Language Models](https://mlsanity.com/paper/2505.12627/) (2025)
- [A Deep Reinforcement Learning Approach for Solving the Traveling Salesman Problem with Drone](https://mlsanity.com/paper/2112.12545/) (2021)
- [Planning of Heuristics: Strategic Planning on Large Language Models with Monte Carlo Tree Search for Automating Heuristic Optimization](https://mlsanity.com/paper/2502.11422/) (2025)
- [Beyond the Hype: Benchmarking LLM-Evolved Heuristics for Bin Packing](https://mlsanity.com/paper/2501.11411/) (2025)
- [Generalizable Heuristic Generation Through LLMs with Meta-Optimization](https://mlsanity.com/paper/2505.20881/) (2025)
- [EB-GLS: An Improved Guided Local Search Based on the Big Valley Structure](https://mlsanity.com/paper/1709.07576/) (2017)
- [RedAHD: Reduction-Based End-to-End Automatic Heuristic Design with Large Language Models](https://mlsanity.com/paper/2505.20242/) (2025)
- [Vehicle Dispatching and Routing of On-Demand Intercity Ride-Pooling Services: A Multi-Agent Hierarchical Reinforcement Learning Approach](https://mlsanity.com/paper/2307.06742/) (2023)

## Abstract (arXiv)

Efficient routing optimization is essential to freight transportation, urban logistics, and shared mobility, where high-quality heuristics are often required under limited computational budgets. Recent large language model (LLM)-based automated heuristic design methods can generate effective routing rules, but aggregate evaluation may mask recurrent failures on particular instance structures. To address this limitation, this study develops RouteRepair, which diagnoses parent-specific weaknesses from instance-level performance and applies targeted modifications to the corresponding heuristic components while protecting behavior that already performs well. Routing evidence, solver behavior, and program context are combined to define bounded repair objectives, and each intervention is validated through matched parent-child evaluation of failure recovery and collateral degradation. Experiments on the traveling salesman problem (TSP) and capacitated vehicle routing problem (CVRP) span constructive search, guided local search, and ant colony optimization. RouteRepair-GLS reduces the mean TSP optimality gap from 1.7476% to 0.7587%, while the constructive CVRP heuristic lowers average route cost by 1.91% relative to the savings heuristic; the generated ACO priors also outperform matched hand-designed priors. These results show that failure-aware, evidence-constrained refinement can improve routing heuristics on difficult instances while preserving performance on cases they already solve well.