Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instances
This work provides a method to improve the scalability and generalization of machine learning solutions for the Traveling Salesman Problem, which is a significant challenge for logistics and optimization.
This paper addresses the generalization problem in supervised learning for the Traveling Salesman Problem (TSP) by training a small model that can generate heat maps for arbitrarily large TSP instances. These heat maps are then used to guide a Monte Carlo tree search, resulting in superior performance compared to existing machine learning-based TSP algorithms on instances up to 10,000 vertices.
For the traveling salesman problem (TSP), the existing supervised learning based algorithms suffer seriously from the lack of generalization ability. To overcome this drawback, this paper tries to train (in supervised manner) a small-scale model, which could be repetitively used to build heat maps for TSP instances of arbitrarily large size, based on a series of techniques such as graph sampling, graph converting and heat maps merging. Furthermore, the heat maps are fed into a reinforcement learning approach (Monte Carlo tree search), to guide the search of high-quality solutions. Experimental results based on a large number of instances (with up to 10,000 vertices) show that, this new approach clearly outperforms the existing machine learning based TSP algorithms, and significantly improves the generalization ability of the trained model.