MSLC: Monte Carlo Tree Search Sampling Guided Local Construction for Solving Large-Scale Traveling Salesman Problem

Zuoyou Liao, Jinshan Zhang, Paul Weng, Feng Wang, Jianwei YinOpenReview 2025 · Submission to ICLR 2025 · Withdrawn · OpenReview

Its authors withdrew this paper, so there is no full text to read or summarize.

Abstract

Neural solvers have achieved promising results in solving small-scale Travelling Salesman Problems (TSP), but inefficiencies arise when tackling larger instances. This paper proposes the MSLC (\textbf{M}onte Carlo Tree Search \textbf{S}ampling Guided \textbf{L}ocal \textbf{C}onstruction) framework, which innovatively integrates a predictive sampling module into the global coarse-grained selection module, MCTS, to achieve mutual integration with the fine-grained local construction module. This integration effectively balances coarse-grained exploration with fine-grained adjustment, thereby improving overall efficiency. This framework offers a novel way to combine autoregressive and non-autoregressive models. Experimental results demonstrate that MSLC effectively balances time and solution quality, outperforming state-of-the-art neural solvers. The performance gap of MSLC is reduced by at least 29.4\% (resp. 34.7\% or 28.5\%) on TSP-500 (resp. TSP-1000 or TSP-10000), compared to the SOTA neural methods.
BibTeX
@misc{liao2025mslc,
  author = {Zuoyou Liao and Jinshan Zhang and Paul Weng and Feng Wang and Jianwei Yin},
  title = {{MSLC: Monte Carlo Tree Search Sampling Guided Local Construction for Solving Large-Scale Traveling Salesman Problem}},
  year = {2025},
  url = {https://openreview.net/forum?id=s324bLSKui},
  howpublished = {OpenReview},
  note = {Submitted to ICLR 2025},
}

Loading related content...

Figure