Learned edge rankings as advice for local search on the Traveling Salesman Problem in minor-free graphs, with a worst-case fallback

Graphs that exclude a fixed minor have small separators and tree decompositions, and the Traveling Salesman Problem (TSP) on them admits approximation schemes that are rarely used in practice. Learned TSP heuristics, on the other hand, are designed for Euclidean instances and offer no worst-case guarantee. We study a simple learning-augmented heuristic for the metrics of minor-free graphs. A graph neural network scores candidate edges from the input graph and, optionally, from the bag graph of a min-degree tree decomposition. The scores order the edges of a greedy decoder and form the neighbour lists of a 2-opt/Or-opt local search, and a double-tree tour serves as a fallback. The algorithm is $2$-robust for every prediction. It is $1$-consistent when every non-tour candidate edge is ranked below both tour edges at one of its ends, a local condition weaker than global separation, and it is stable under perturbations smaller than half the margin. We test it on $480$ planar, series--parallel ($K_4$-minor-free) and apex ($K_6$-minor-free) graphs with up to $500$ vertices. The hybrid is $3.49\%$ above near-optimal LKH tours, against $3.91\%$ for the same local search started from a greedy-edge tour, $4.75\%$ from nearest neighbour and $5.61\%$ from a double tree. The gain over the strongest classical baseline is small ($0.41$ points, $p=0.001$) and comes mostly from a better start tour. It is concentrated on series--parallel graphs and absent on planar ones. Over five training seeds, the tree decomposition gives no measurable benefit, and a scorer that sees only the metric performs almost as well. The gains carry over to 5-apex graphs of larger width but not reliably to real road networks. The trained scores never meet the consistency condition, and LKH restricted to the same budget remains far better. All code, data and results are released.