Towards Feature-free TSP Solver Selection: A Deep Learning Approach
  The Travelling Salesman Problem (TSP) is a classical NP-hard problem and has
broad applications in many disciplines and industries. In a large scale
location-based services system, users issue TSP queries concurrently, where a
TSP query is a TSP instance with $n$ points. In the literature, many advanced
TSP solvers are developed to find high-quality solutions. Such solvers can
solve some TSP instances efficiently but may take an extremely long time for
some other instances. Due to the diversity of TSP instances, it is well-known
that there exists no universal best solver dominating all other solvers on all
possible TSP instances. To solve TSP efficiently, in addition to developing new
TSP solvers, it needs to find a per-instance solver for each TSP instance,
which is known as the TSP solver selection problem. In this paper, for the
first time, we propose a deep learning framework, \CTAS, for TSP solver
selection in an end-to-end manner. Specifically, \CTAS exploits deep
convolutional neural networks to extract informative features from TSP
instances and involves data argumentation strategies to handle the scarcity of
labeled TSP instances. Moreover, to support large scale TSP solver selection,
we construct a challenging TSP benchmark dataset with 6,000 instances, which is
known as the largest TSP benchmark. Our \CTAS achieves over 2$\times$ speedup
of the average running time, comparing the single best solver, and outperforms
the state-of-the-art statistical models.
