Exposing Local Vulnerabilities in Neural Routing Solvers with an Efficient Black-Box Attack

Neural routing solvers combine high solution quality with fast inference, yet a simple greedy probing attack exposes substantial local vulnerabilities: bounded coordinate perturbations subject to geometric constraints raise the mean solution gaps of representative neural solvers to roughly 4–35 times their original values on TSP instances with 100 nodes. To find stronger adversarial instances efficiently, we propose the **R**eference-Route **R**euse **A**ttack (RRA), a constrained black-box attack that maximizes the solution gap. Its Adam-ES update combines evolution strategies with adaptive momentum to aggregate candidate feedback within and across iterations. RRA further exploits local coordinate changes to reuse recent reference routes for candidate scoring, refreshing the reference after each update. At the same model-query budget, RRA increases the observed mean best-found gap over the greedy attack by 20–31% across three solvers on these instances. Relative to its full-reference variant, it reduces search-time reference solves by 96.94%, yielding 2.37–2.52× speedups on this TSP benchmark and 6.9–12.2× on CVRP with 50 customers. Fine-tuning a neural solver on these adversarial instances lowers its gaps under renewed fixed-budget attacks, linking local vulnerability analysis to model improvement.