HeatACO uses neural heatmaps to solve TSP faster and better than MCTS

Bo-Cheng Lin, Yi Mei, and Mengjie Zhang (Victoria University of Wellington) propose HeatACO, a novel heatmap-to-tour decoder for the Traveling Salesman Problem (TSP). Non-autoregressive neural solvers produce an edge-confidence heatmap in one forward pass, but decoding a feasible Hamiltonian cycle from a quadratic number of scores is challenging. Existing methods like greedy edge merging are fast but yield low-quality tours, while Monte Carlo Tree Search (MCTS) over k-opt moves recovers better tours at high computational cost and requires predictor-specific tuning. HeatACO is predictor-agnostic: it uses a capped, degree-aware evidence factor that integrates a fixed heatmap into a Max-Min Ant System (MMAS), rewarding only edge confidence beyond a node's tour-degree capacity. The scaling is automatic from pheromone dynamic range, so one configuration works across different heatmap sources without retraining.

Across four heatmap sources, HeatACO produces higher-quality solutions in less decoding time than MCTS on TSP500, TSP1K, and TSP10K. It also outperforms matched standard MMAS baselines with the same search budget, and remains beneficial even with local search. HeatACO transfers competitively to several distribution shifts and asymmetric TSP (ATSP). The paper’s post-hoc analysis identifies measurable heatmap properties linked to performance variation. This work offers a practical, efficient bridge between neural TSP predictors and high-quality tour generation, with potential applications in logistics, circuit design, and route planning.