The travelling salesman problem (TSP) is a well-known combinatorial optimization problem with a variety of real-life applications. We tackle TSP by incorporating machine learning methodology and leveraging the variable neighborhood search strategy. More precisely, the search process is considered as a Markov decision process (MDP), where a 2-opt local search is used to search within a small neighborhood, while a Monte Carlo tree search (MCTS) method (which iterates through simulation, selection and back-propagation steps), is used to sample a number of targeted actions within an enlarged neighborhood. This new paradigm clearly distinguishes itself from the existing machine learning (ML) based paradigms for solving the TSP, which either uses an end-to-end ML model, or simply applies traditional techniques after ML for post optimization. Experiments based on two public data sets show that, our approach clearly dominates all the existing learning based TSP algorithms in terms of performance, demonstrating its high potential on the TSP. More importantly, as a general framework without complicated hand-crafted rules, it can be readily extended to many other combinatorial optimization problems.
The paper proposes an algorithm for the Travelling Salesman Problem that starts with a random tour and iteratively improves it using 2-opt local search, followed by Monte Carlo Tree Search with k-opt moves to search a larger neighborhood of solutions. Results show that the algorithm matches the optimal objective value on a dataset of 2D Euclidean TSP instances with 20, 50, and 100 cities, and achieves better objective value than S2V DQN on a subset of instances from TSPLIB with 50 to 318 cities. It is interesting that the algorithm is fairly simple (apart from the definition of the local moves) and still able to achieve competitive objective values on small instances.
The rating is a weak reject for the following reasons:
1. Domain knowledge: The proposed algorithm has significant domain knowledge about TSP hand-coded into it via the choice of 2-opt local search as well as the k-opt moves with top-10 nearest neighbor filtering used in MCTS. These types of moves are same/similar to the expert-designed ones used in state-of-the-art local search algorithms like LKH. This can give the proposed algorithm a significant advantage over S2V-DQN which does not have such built-in knowledge. So the comparison to S2V-DQN is unfair and improved results may not be due to any differences in the learning approaches at all. Perhaps a more generic definition of local moves that is not so TSP-specific would be a fairer comparison. This issue is particularly important because the definition of “local moves” appropriate for a problem domain is one of the main challenges in applying local search successfully. Bypassing that challenge can simplify the problem.
2. Baselines: Better comparisons to baselines are needed in Table 2. S2V-DQN was published two years ago, and since then many other learning-based have been proposed (which are referenced in the paper), but they are not included in Table 2. It would also be good to discuss non-learning local search algorithms that use same/similar local moves as the proposed algorithm and how they perform.
3. Scalability to large instances: TSP experts consider problems with hundreds of cities as practically “solved” by the current state-of-the-art solvers like Concorde and LKH, and it is not at all clear what benefit learning can provide on such small instances. Much larger instances (e.g., 10^4-10^6 cities) would have to be considered for improvements over the state-of-the-art to become plausible with learning. So if the goal is to improve on the state-of-the-art with learning (even if it is a long-term goal), then it is important to consider whether the proposed approach has a plausible path for scaling up to such sizes. But like most papers on learning-for-TSP, this paper does not consider scalability. 
Misc comments:
It would be useful to include the exact running times of Concorde in Table 2. The results given are “reported by Concorde within 1 hour for each instance”, but it would be good to know what the actual running time is.
Typo: “sub-decisions sequently”