Recent advancements in solving large-scale traveling salesman problems (TSP)
utilize the heatmap-guided Monte Carlo tree search (MCTS) paradigm, where
machine learning (ML) models generate heatmaps, indicating the probability
distribution of each edge being part of the optimal solution, to guide MCTS in
solution finding. However, our theoretical and experimental analysis raises
doubts about the effectiveness of ML-based heatmap generation. In support of
this, we demonstrate that a simple baseline method can outperform complex ML
approaches in heatmap generation. Furthermore, we question the practical value
of the heatmap-guided MCTS paradigm. To substantiate this, our findings show
its inferiority to the LKH-3 heuristic despite the paradigm's reliance on
problem-specific, hand-crafted strategies. For the future, we suggest 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:
this https URL

针对大规模旅行推销员问题，研究了热力图引导的蒙特卡罗树搜索模型，发现机器学习方法生成的热力图的有效性存在疑问，提出了一个简单基准方法可以胜过复杂的机器学习方法；同时，热力图引导的蒙特卡罗树搜索模型在实践中表现不如 LKH-3 启发式方法；未来建议基于更具理论支撑的热力图生成方法和探索自主、具有普适性的机器学习方法解决组合问题。