Efficient routing optimization is critical for freight transport, urban logistics, and shared mobility, where high‑quality heuristics must be produced under tight computational budgets. Recent large language model (LLM)‑driven automated heuristic design can generate effective routing rules, yet aggregate evaluation often hides recurring failures on particular instance structures. To overcome this limitation, we introduce RouteRepair, which diagnoses parent‑specific weaknesses from instance‑level performance and applies targeted modifications to the corresponding heuristic components while preserving behavior that already works well.
RouteRepair combines routing evidence, solver behavior, and program context to define bounded repair objectives. Each intervention is validated through matched parent‑child experiments, measuring both failure recovery and any collateral degradation of existing performance. Experiments span the traveling salesman problem (TSP) and capacitated vehicle routing problem (CVRP), covering constructive search, guided local search (GLS), and ant colony optimization (ACO).
On TSP, RouteRepair‑GLS reduces the mean optimality gap from $1.7476\%$ to $0.7587\%$. For CVRP, the constructive heuristic lowers average route cost by $1.91\%$ relative to the savings heuristic, and the generated ACO priors outperform matched hand‑designed priors.
These findings demonstrate that failure‑aware, evidence‑constrained refinement can improve routing heuristics on difficult instances while preserving performance on cases they already solve well.
Review