Alternating Exploration and Repair via Split Search for Hard-Constrained Routing

Hard-constrained routing seeks low-cost routes that satisfy operational restrictions, but reducing travel cost can conflict with restoring feasibility. We introduce ALTER, a neural solver that repeatedly alternates cost-oriented exploration and feasibility-oriented repair. Each selected route serves as the reference for the other role's next proposals. Accumulated disagreement carries their interaction across iterations, while a learned state-dependent coupling strength controls how strongly the two searches are coordinated. Our analysis characterizes coupling intervals under which finite-pool selection yields a feasible cost improvement. Experiments cover synthetic single- and multi-vehicle routing. On hard 100-customer draft-limit instances, ALTER produces a feasible output for 99.97% of instances and obtains the lowest gap among tested neural methods. It also obtains the lowest reported costs on the multi-vehicle benchmark.