Hybrid neural–heuristic TSP solver with attention-guided refinement for real-time AMR coordination
Francesco Nucci, Gabriele Papadia · Results in Control and Optimization · 2026
Autonomous mobile robot (AMR) fleets in warehouses must solve hundreds of Traveling Salesman Problem (TSP) instances per second within strict latency budgets. Classical heuristics such as Lin–Kernighan achieve near-optimal tour quality but violate the 50–100 ms deadlines imposed by 10–20 Hz control loops; neural combinatorial optimization methods offer fast inference but exhibit 10%–25% optimality gaps that are economically unacceptable in production logistics. This paper introduces a hybrid neural–heuristic TSP solver that couples a Transformer-based encoder–decoder for constructive tour generation with an attention-guided 2-opt refinement stage. The attention matrix from the final encoder layer provides learned geometric priors that reduce the number of 2-opt candidates evaluated from the exhaustive O ( N 2 ) set to an O ( N ) -sized filtered subset per iteration. An adaptive curriculum learning strategy is accompanied by a convergence analysis under standard smoothness and bounded-gradient assumptions, and we derive assumption-dependent bounds relating attention Precision@K to attainable post-refinement solution quality. The solver is validated on 600 synthetic Euclidean instances ( N = 20 –200), 847 real warehouse mission trajectories collected over six months from an industrial logistics partner, and a six-month production deployment with a 15-robot AMR fleet. It achieves 3.2–8.7% optimality gaps relative to Concorde optimal, 6.3–18.5 × speedups over Lin–Kernighan, and deterministic sub-80 ms latency for N ≤ 100 on embedded hardware, with sub-130 ms probabilistic compliance for N ≤ 150 . Field deployment yields 22% throughput improvement, 18% energy reduction, and no recorded failures over 18,400 robot-hours, establishing hybrid neural–heuristic solvers as a practical and theoretically principled paradigm for real-time combinatorial optimization in cyber–physical systems.