SpecAHD: Localize to Specialize for Automated Heuristic Design in Large-Scale Routing Problems

Large-scale routing problems are typically optimized using Large Neighborhood Search (LNS), which requires two decisions: which part of a solution to expose (destroy) and how to reconstruct it (repair). Existing Automated Heuristic Design (AHD) methods often treat these as independent problems or optimize heuristics across complete instances. SpecAHD addresses the challenge of within-instance specialization, asking: can we jointly learn where to expose regions and which specific heuristic is best suited for the local structure of each exposed region?

SpecAHD introduces a coupled bilevel framework that alternates between two search processes. The upper-level search evolves programs that identify bounded repair regions within an incumbent solution, while the lower-level search evolves a repertoire of executable constructive heuristics.

Key to this approach is a Repair Response Archive that stores the outcomes of heuristic-task pairs. When a region is exposed, the system uses a deterministic, non-parametric router to query this archive, selecting the heuristic that has performed best on structurally similar regions. The framework uses a monotone submodular objective to select a complementary repertoire of heuristics, ensuring that the set covers different types of local structures effectively. Every repair is validated by an exact problem-specific checker, and failed or infeasible repairs are rolled back to maintain solution integrity.

SpecAHD demonstrates significant improvements over existing AHD baselines across four routing problems (CVRP, TSP, VRPTW, and SDVRP). By moving specialization inside the instance, the framework reduces held-out objective costs by up to 57.7% compared to the strongest competing baseline. The results indicate that the ability to match specific repair heuristics to local region structures—rather than relying on a single global heuristic—is critical for optimizing large-scale routing instances.