RouteRepair: Instance-Level Failure Diagnosis and Targeted Repair in LLM-Based Automated Heuristic Design for Routing Optimization
Binghao Ji, Di Huang, Jiahui Fang, Zhiyuan Liu
cs.AI
Quick verdict
RouteRepair adds instance-level failure diagnosis and targeted repair to LLM-evolved routing heuristics, with promising GLS/CVRP/ACO gains and honest, but single-seed, evidence.
Summary
RouteRepair targets a blind spot of LLM-based automated heuristic design: a competitive routing heuristic can still fail repeatedly on structurally related instance subsets that an average fitness score conceals. From a parent heuristic's instance-wise performance profile, the method builds failure, strength, and protection sets, processed by two expert modules: a Failure Diagnosis Expert that converts routing evidence, solver behavior, and program context into a bounded repair objective, and a Targeted Repair Expert that makes local code edits to only the designated scoring rule or edge-prior function. Every repair is validated through matched parent-child runs under identical instances, seeds, and budgets, requiring recovery on failures while limiting collateral degradation. Five adapters cover constructive heuristics, guided local search, and ant colony optimization for TSP and CVRP. Key results: RouteRepair-GLS cuts mean TSP optimality gap from 1.7476% to 0.7587%; constructive CVRP lowers average route cost by 1.91% versus the savings heuristic; generated ACO priors beat matched hand-designed priors. A budget-aware comparison with the complete ReEvo system shows a quality-cost trade-off: RouteRepair attains 0.7587% average gap with 216 LLM calls versus ReEvo's 0.6861% with 302. The authors' own stated limitations include single-seed ablation; no code or data release is mentioned, and no variance or significance testing is reported for headline results.
Review complete
Assessment at a glance
4
risk flags identified
● high 2
● medium 2
● low 0
4 strengths · 4 weaknesses · 5 author questions
AI text signal = Binoculars zero-shot detector score over 20 sampled passages (Fast-DetectGPT co-reported) — absence does not prove human authorship, and a flag does not imply misconduct.
Levels reflect verification complexity — not a quality score. Evolve never rates your paper.
Key claims under review
- Instance-level failure diagnosis with a two-expert, evidence-constrained repair loop improves competitive routing heuristics where average-fitness replacement cannot, while preserving behavior on already-solved cases.
- RouteRepair-GLS reduces mean TSP optimality gap from 1.7476% (Standard GLS) to 0.7587%, a 56.6% relative reduction under a common solver scaffold (Table 3).
- Constructive CVRP lowers held-out average route cost by 1.91% versus the savings heuristic and 2.06% versus a ReEvo-adapted guide, with the lowest gap to OR-Tools Routing GLS among matched-interface methods (Table 8).
- Generated ACO edge priors beat matched hand-designed priors on both TSP (equal-scale average 5.145% vs ReEvo 5.341%) and CVRP (3.32% cost reduction across 16 held-out instances, 14/16 wins, plus 3.59% on CVRP1000 transfer).
- Ablations show instance-level failure attribution, targeted repair, and outcome-aware memory are each necessary; removing any collapses the TSP-GLS gap to roughly standard-GLS level (~1.70-1.75%).
Strengths
Verification-first repair protocol
Eq. 11-14 formalize matched parent-child validation: recovery rate R_F must clear τ_F while one-sided collateral degradation C_A over the full protection set A(h_p)=D\F (Eq. 10) must stay under τ_A; success is explicitly decoupled from population entry, and failed interventions are stored in outcome-aware memory (§3.6), addressing the self-repair illusion the authors cite via Olausson et al. 2024.
Honest budget-aware comparison
§4.2.2/Table 4 states plainly that ReEvo attains the lower average TSP20-200 gap (0.6861% vs 0.7587%) while RouteRepair uses 86 fewer LLM calls (216 vs 302) and wins only on TSP200/TSP500; §4.3.2 likewise declines a ReEvo CVRP-ACO claim 'because a matched run under the same evaluation protocol was unavailable'. Conclusions repeat that dominance is not claimed.
Breadth of evaluation across three solver families
Ablations attribute gains to the full loop
Weaknesses
No variance or significance anywhere
Acceptance thresholds and fractions never specified
GLS baselines are 'lite' component transfers
Eq. 14 gate vs Table 11 degradation rates unresolved
Full Review Report
$1.99 · one-timeUnlock the complete preliminary analysis Evolve produced for this paper.
Report preview
Scope & Claims
RouteRepair (arXiv 2609.11452) proposes a refinement stage for LLM-based automated heuristic design (AHD) on routing problems: instead of replacing candidates by average fitness, it diagnoses why an already-competitive parent heuristic fails on structurally coherent instance subsets and repairs it with bounded, verified code edits. Three claimed contributions: (i) instance-level repair as a new refinement perspective; (ii) an evidence-constrained two-expert diagnosis-repair methodology; (iii) a transferable, verifiable repair mechanism across five adapters. Headline claims are concrete: RouteRepair-GLS cuts mean TSP optimality gap from 1.7476% to 0.7587% under a common solver scaffold (Table 3); constructive CVRP cuts average route cost 1.91% versus savings (Table 8); ACO priors beat matched hand-designed priors (Tables 7, 9).
The remaining sections cover Methodology Assessment, Statistical Evidence, Results & Reproducibility, Limitations & Risks, and Verdict & Recommendations.
- All 4 strengths & 4 weaknesses, analyzed in detail
- 4 risk flags with severity, section & reviewer questions
- Methods & statistical evidence assessment
- 5 questions a peer reviewer would ask
- Full six-dimension evaluation report & recommendations
One-time purchase · this paper only
One-time purchase, this paper only. AI-generated preliminary analysis — not peer review.
Frequently asked questions
What is RouteRepair in one sentence?
RouteRepair is a framework that finds the specific routing instances where an LLM-generated heuristic (for TSP/CVRP) repeatedly fails, diagnoses the likely weakness in the heuristic's code, applies a bounded targeted fix, and accepts the fix only if matched before/after tests show recovery without degrading cases the heuristic already solved.
How much does RouteRepair improve results?
In the paper's experiments it cuts the mean TSP optimality gap of guided local search from 1.7476% to 0.7587%, lowers constructive CVRP route cost by 1.91% versus the classic savings heuristic, and beats hand-designed ACO priors by 3.32% mean route cost on CVRP; gains vary by instance and method.
Is RouteRepair better than ReEvo?
Not uniformly. With a comparable budget RouteRepair used fewer LLM calls (216 vs 302) and did better on the largest TSP instances, but ReEvo achieved the lower average gap (0.6861% vs 0.7587%); the paper presents this as a quality-cost trade-off, not dominance.
Can I reproduce the results?
Conceptually yes — TSP/CVRP solvers are standard and seeds/instance counts are given — but the paper specifies no code or data release, prompt details appear only as figures, and the repair-acceptance thresholds are never given numeric values, so exact replication currently requires the authors' input.
About this review
This is an AI-generated preliminary review by Evolve.Pub, produced from the openly available text of the paper. It is not peer review and does not represent the authors' views. The canonical record of the paper is at the publisher link above.
- Equation typography (Eq. 1-2, 5-7, 11-12) is symbol-garbled by PDF extraction; surrounding prose defines the notation, and all numbers cited here come from intact tables and text.
- Figure contents (Fig. 1-13, including prompt templates in Fig. 3-5) are present but not extractable, so prompt-level review relies on the surrounding prose; no quoted or cited element in this review was missing from the text.
Go deeper on this paper
Wrote a paper? Stress-test it before reviewers do.
Upload your manuscript for the same structured scrutiny — reasoning, statistics, evidence, figures, and reproducibility.