PaperlayerView exact revision on arXiv

Source-linked AI summary

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

arXiv:2609.11452v1cs.AI

TL;DR

Aggregate-fitness evaluation can miss recurring failures on particular routing-instance structures, limiting how LLM-generated heuristics are refined. RouteRepair diagnoses parent-specific weaknesses from instance-level evidence, applies bounded component repairs, and validates them against the parent under matched conditions. Across TSP and CVRP tasks spanning constructive search, guided local search, and ACO, the method improves routing quality while targeting difficult cases and protecting already strong behavior.

  • Problem

    Aggregate evaluation of LLM-based automated heuristic design can mask recurrent poor performance on structurally related routing instances.

  • Method

    RouteRepair preserves parent-specific instance profiles, uses evidence-constrained diagnosis and targeted component repair, and validates parent-child changes under matched conditions.

  • Results

    Across TSP and CVRP, RouteRepair improves constructive search, guided local search, and ACO, including reducing the mean TSP gap from 1.7476% to 0.7587%.

  • Takeaways & Limitations

    Failure-aware, evidence-constrained refinement improves routing heuristics on difficult instances while preserving performance on cases their parents already solve well.

  • Takeaways & Limitations

    The method does not dominate every method or instance; some comparisons are modest or scale-dependent, and the ablation uses a single controlled seed.

Abstract

from arXiv · show

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.

1. Introduction

Routing heuristics are difficult to design because rules must adapt to heterogeneous instance structures, while aggregate evaluation can conceal recurring local failures. RouteRepair addresses this gap with evidence-constrained, instance-level diagnosis and targeted repair of competitive LLM-generated heuristics.

  • 1. Introduction: Routing heuristics must balance competing criteria and remain effective across changes in customer geometry, demand dispersion, vehicle capacity, and instance size.The relevant components include next-node selection, GLS feature penalization, and variation or selection rules.
  • 1. Introduction: LLM-based automated heuristic design expands program variation beyond manually specified hyper-heuristic primitives through generation, execution, evaluation, selection, and feedback.
  • 1. Introduction: RouteRepair preserves each parent’s instance-wise performance profile, identifies failure, strength, and protection cases, and uses separate diagnosis and repair experts to modify designated heuristic components.The diagnosis combines objective records, instance descriptors, route behavior, and program context.
  • 1. Introduction: Matched parent-child evaluation uses identical instances, seeds, solver settings, and computational budgets to assess failure recovery alongside collateral degradation.
  • 1. Introduction: RouteRepair transfers across five TSP and CVRP adapters spanning constructive search, guided local search, and ACO while improving solution quality and limiting degradation on previously well-solved instances.

2. Related Work

Prior work embeds learned or LLM-generated components within specified routing procedures and increasingly addresses heterogeneity through portfolios, selectors, and broader program search. RouteRepair instead targets revision of one competitive heuristic using continuous instance-level quality evidence and collateral-effect checks.

  • 2. Related Work: Routing research commonly embeds learned components in defined procedures for constructive heuristics, neighborhood search, and hybrid or learning-guided routing.
  • 2. Related Work: Hyper-heuristics and evolutionary code-generation methods search over heuristics or executable programs, with systems such as FunSearch, EoH, and ReEvo combining generation with evaluation and feedback.
  • 2. Related Work: Recent methods broaden automated heuristic design through knowledge-guided search, complementary heuristic sets, reduced framework dependence, larger code regions, meta-optimization, and state-dependent selection.
  • 2. Related Work: Instance-space studies show that routing performance depends on structure, while strong results on a design distribution may reflect specialization rather than broad superiority.
  • 2. Related Work: RouteRepair treats diagnosis as an intervention hypothesis, defining repair targets from continuous solution-quality evidence and checking collateral effects where the parent already performs well.

3.1. Problem Setting

RouteRepair formulates automated routing-heuristic design as executable-component search inside fixed solver skeletons. It retains instance-level losses alongside their aggregate mean so diagnosis can target locally weak parents without abandoning population-level ranking.

  • 3.1. Problem Setting: The LLM supplies a designated executable component while a fixed solver skeleton controls feasibility and the broader routing search process.The component may rank the next customer, select a GLS edge for penalization, or provide an edge-desirability prior.
  • 3.1. Problem Setting: The inner diagnosis-repair process supplements aggregate evolutionary search for strong parents that fail repeatedly on structurally coherent subsets of instances.
  • 3.1. Problem Setting: For each routing instance, the fixed solver combines the generated heuristic with the instance, returns a feasible solution, and evaluates its objective value.
  • 3.1. Problem Setting: Normalized excess cost is minimized, with zero indicating that the reference objective is matched.The reference may be an optimum, best-known value, or protocol-defined fixed value, while ε prevents division by zero.
  • 3.1. Problem Setting: RouteRepair retains the complete vector of N instance-level losses and its arithmetic mean, using the vector for parent-specific failure diagnosis and the mean for population ranking.

3.2. Framework of RouteRepair

RouteRepair is organized as a nested framework: an outer evolutionary loop generates and ranks executable heuristics, while an inner loop diagnoses recurrent instance-specific weaknesses and applies bounded repairs. The complete performance profile is retained to guide both repair and subsequent search.

  • 3.2. Framework of RouteRepair: The outer loop generates executable routing heuristics, removes invalid programs, evaluates candidates in fixed TSP or CVRP backbones, and selects using aggregate route quality.
  • 3.2. Framework of RouteRepair: The inner loop targets competitive parents with recurrent weaknesses on patterns such as elongated distributions, sparse layouts, long edges, or capacity-stressed demand.
  • 3.2. Framework of RouteRepair: A Failure Diagnosis Expert combines route outcomes, instance descriptors, solver behavior, and program context into a repair hypothesis, while risk review identifies behavior to preserve.
  • 3.2. Framework of RouteRepair: The repair brief is frozen before a Targeted Repair Expert modifies only the designated scoring rule or edge-prior function, after which parent and child receive identical evaluation conditions.

3.3. Heuristic Representation and Routing Adapters

RouteRepair uses fixed solver backbones with one designated heuristic interface exposed for LLM-generated components. The adapters cover constructive scoring, GLS edge prioritization, and ACO edge-prior matrices while keeping feasibility and solver dynamics fixed.

  • Fixed-backbone representation: The fixed-backbone representation changes only a designated heuristic interface while the surrounding solver retains feasibility, state transitions, neighborhood operations, and termination.This separation enables meaningful parent-child comparisons because the solver remains unchanged during repair.
  • Constructive adapters: Constructive adapters score feasible candidate actions, with CVRP removing capacity-infeasible customers before the generated rule ranks preferences.Constructive TSP scores unvisited cities, while constructive CVRP preserves feasibility through the fixed candidate filter.
  • TSP-GLS adapter: The TSP-GLS adapter assigns relative priority to existing tour edges, while penalty updates, neighborhood search, and termination remain fixed.The generated function uses edge, path, distance, penalty, coordinate, and restricted solver-state information.
  • ACO adapters: ACO adapters generate deterministic n×n edge-prior matrices that are converted to nonnegative desirabilities and combined with pheromone information by the fixed solver.The TSP prior uses the distance matrix, whereas CVRP additionally uses coordinates, demands, vehicle capacity, and depot index.
  • Fixed solver boundary: Generated ACO priors cannot alter pheromone evaporation, elite deposits, exponents, ant counts, iterations, random seeds, or CVRP feasibility handling.In CVRP-ACO, visit status and remaining capacity remain hidden from the generated function.

3.4. Parent-Specific Case Construction

RouteRepair constructs evidence sets from each selected parent’s own instance-level performance rather than from globally difficult cases. Failure cases target intervention, strength cases describe behavior to preserve, and the broader protection set evaluates collateral damage using routing and solver descriptors.

  • Parent-specific ranking: Parent-specific ranking identifies failures relative to each heuristic’s own outcomes within problem-scale groups, avoiding a fixed list of globally difficult instances.Within each scale group, rank 1 denotes the parent’s worst outcome.
  • Failure and strength sets: Failure sets contain the parent’s worst-ranked cases, while strength sets sample its best-performing cases from the same performance profile.The failure fraction qf and strength fraction qs determine the respective set sizes.
  • Protection set: The protection set contains all non-failure instances, making collateral-damage evaluation broader than the compact strength subset shown to the LLM.The complete protection set is reserved for external acceptance testing.
  • Routing evidence: Diagnosis combines instance structure, demand structure, solution behavior, and generated score or prior statistics from deterministic evaluator data.These descriptors distinguish compact and uniform cases from elongated, clustered, or capacity-stressed instances.

3.5. Failure Diagnosis and Targeted Repair

RouteRepair separates failure diagnosis from code generation through a frozen, evidence-constrained repair brief. A diagnosis expert links repeated routing outcomes to the editable component, while a targeted repair expert makes a bounded change under fixed interface and solver constraints.

  • Failure diagnosis: The Failure Diagnosis Expert uses parent code, selected failure and strength cases, routing evidence, rankings, and matched baselines to state a bounded repair objective without generating code.The diagnosis is treated as a testable program-level hypothesis rather than established causality.
  • Structured diagnosis report: The structured diagnosis report records failure evidence, weak behavior, root cause, repair objective, repair risk, and one to three repair families.Its fixed schema converts instance-level evidence into bounded repair directions instead of general commentary or repeated coefficient tuning.
  • Risk review: An internal review checks evidence, preservation and overfitting risks, and duplicate directions before freezing the brief for repair.The review remains within the diagnosis stage and prevents the repair expert from redefining the weakness after seeing code-generation context.
  • Targeted repair: The Targeted Repair Expert receives one frozen repair family and must make a local or bounded structural change while preserving the adapter interface.GLS and constructive adapters return finite scalar scores, whereas ACO adapters return deterministic finite edge-prior matrices with distance-matrix shape.

3.6. Strength-Preserving Matched Validation and Outcome-Aware Memory

RouteRepair validates repairs through matched parent-child evaluation that separately measures recovery on failures and degradation across the complete non-failure protection set. Only children meeting both thresholds count as verified targeted repairs, and outcomes are stored for later reuse.

  • Failure recovery: Failure-set recovery measures the mean reduction in normalized loss, with positive values indicating that the child improves cases targeted by the diagnosis.RouteRepair also uses a recovery rate relative to the parent’s initial failure severity.
  • Strength preservation: Collateral degradation is measured over the complete non-failure protection set, and improvements on some protected cases cannot offset newly created damage on others.The one-sided degradation measure therefore focuses on newly worsened protected instances.
  • Verification criteria: A repair is verified only when failure-set recovery reaches τF and protection-set collateral degradation remains at or below τA.Syntax, interface, and numerical validation precede matched evaluation under identical conditions.
  • Outcome-aware memory: Targeted-repair success is kept separate from population entry, so an aggregate evolutionary benefit does not make an intervention a verified repair if either condition fails.Each intervention stores its diagnosis, strategy, parent-child outcomes, recovery, collateral degradation, and verification result.

4. Experimental Evaluation

Across TSP and CVRP adapters, RouteRepair improved heuristic components under fixed solver backbones, transferred to held-out instances, and benefited from instance-level diagnosis, memory, and targeted repair.

  • TSP-GLS Under a Common Solver Scaffold: 0.7587% mean TSP optimality gap made RouteRepair-GLS the strongest method under the common GLS scaffold, improving 56.6% over Standard GLS.The largest gain occurred on TSP200, where the gap fell from 3.5791% to 1.6897%.
  • Transfer to TSPLIB: 1.8742% full-pool TSPLIB gap made RouteRepair-GLS better than Standard GLS at 2.0492%, while RouteRepair + 2-opt reached 3.9244% versus 4.3187% for NN + 2-opt.Transfer used complete 30-instance pools without retraining.
  • TSP-ACO Edge-Prior Generation: 5.145% equal-scale TSP-ACO gap and 6.688% weighted gap both beat ReEvo at 5.341% and 6.829%, respectively, although neither method dominated every size.RouteRepair performed better on TSP50 and TSP100, while ReEvo was slightly better on TSP20, TSP200, and TSP500.
  • CVRP-ACO Capacity-Aware Priors: 3.32% lower mean cost across 16 CVRP50-CVRP500 instances came from improvements in 14 cases, with wins at every CVRP200 and CVRP500 comparison.RouteRepair lowered mean cost from 29,253.0 to 28,184.9 and reduced cost at every held-out scale.
  • CVRP-ACO Capacity-Aware Priors: 3.59% lower mean cost on CVRP1000 showed that the CVRP-ACO improvement transferred to larger unseen instances under unchanged vehicle counts and capacity utilization.Mean cost decreased from 103,785.8 to 100,039.1 through improved edge ordering within the fixed feasible construction process.
  • Ablation Study: 1.70%-1.75% gaps after removing memory, targeted repair, or failure attribution showed that linking parent-specific evidence to bounded repair was central to performance.Figure 12 further showed deterioration of roughly 2.4%-3.5% on TSP100 and TSP200 when these components were removed.

5. Conclusions

RouteRepair replaces aggregate-fitness-driven replacement with instance-level diagnosis and targeted repair, evaluating revised heuristics against their parents under matched conditions. Across TSP and CVRP methods, it improves difficult-instance performance while explicitly checking for collateral degradation, though its dominance is not universal.

  • Matched parent-child evaluation uses identical instances, solver settings, random seeds, and computational budgets to assess recovery on difficult cases alongside degradation elsewhere.
  • RouteRepair improves routing heuristics across constructive search, guided local search, and ACO for both TSP and CVRP.RouteRepair-GLS reduces the mean TSP gap from 1.7476% to 0.7587%; constructive CVRP cost falls 1.91% versus the savings heuristic, and repaired ACO priors outperform matched hand-designed priors.
  • Instance-level attribution, targeted repair, and outcome-aware memory become particularly important as routing scale increases.
  • RouteRepair is not guaranteed to dominate every method or routing instance, with some comparisons against ReEvo remaining modest or scale-dependent.
  • Future work should test richer vehicle-routing constraints, dynamic and stochastic operations, repeated seeds, additional LLM families, and adaptive failure-selection criteria.
Loading 2609.11452v1…