  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.
