Position: Rethinking Post-Hoc Search-Based Neural Approaches for Solving Large-Scale Traveling Salesman Problems

最近在解决大规模旅行商问题（TSP）方面的进展，采用了热力图引导的蒙特卡罗树搜索（MCTS）范式，其中机器学习（ML）模型生成热力图，指示每条边成为最优解的概率分布，以指导MCTS寻找解决方案。然而，我们的理论和实验分析对基于ML的热力图生成方法的有效性提出了质疑。为此，我们证明了一个简单的基准方法在热力图生成方面可以胜过复杂的ML方法。此外，我们还质疑了热力图引导的MCTS范式的实际价值。为了证实这一点，我们的发现表明，尽管该范式依赖于问题特定的手工策略，但其劣势仍不如LKH-3启发式算法。对于未来，我们建议研究方向集中在开发更具理论基础的热力图生成方法，并探索自主的、可推广的ML方法用于组合问题。代码可供查看：https://github.com/xyfffff/rethink_mcts_for_tsp。

ML-based heatmap generation in TSP problem and the effectiveness of heatmap-guided MCTS paradigm

The effectiveness of ML-based heatmap generation in guiding Monte Carlo tree search (MCTS) in solving large-scale TSP problems is questioned, and a simple baseline method is shown to outperform complex ML approaches. The heatmap-guided MCTS paradigm is also found to be inferior to the LKH-3 heuristic despite its reliance on problem-specific, hand-crafted strategies.

The experimental analysis raises doubts about the practical value of the heatmap-guided MCTS paradigm and suggests research directions focused on developing more theoretically sound heatmap generation methods and exploring autonomous, generalizable ML approaches for combinatorial problems. The code is available for review on GitHub.

Recent related studies include 'A hybrid algorithm for the traveling salesman problem using a neural network and a local search' and 'A genetic algorithm for the traveling salesman problem using adjacency matrix representation'.