MSLC: Monte Carlo Tree Search Sampling Guided Local Construction for Solving Large-Scale Traveling Salesman Problem
Its authors withdrew this paper, so there is no full text to read or summarize.
Lists
Only you see this
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...