  Algorithm selection is a well-known problem where researchers investigate how
to construct useful features representing the problem instances and then apply
feature-based machine learning models to predict which algorithm works best
with the given instance. However, even for simple optimization problems such as
Euclidean Traveling Salesman Problem (TSP), there lacks a general and effective
feature representation for problem instances. The important features of TSP are
relatively well understood in the literature, based on extensive domain
knowledge and post-analysis of the solutions. In recent years, Convolutional
Neural Network (CNN) has become a popular approach to select algorithms for
TSP. Compared to traditional feature-based machine learning models, CNN has an
automatic feature-learning ability and demands less domain expertise. However,
it is still required to generate intermediate representations, i.e., multiple
images to represent TSP instances first. In this paper, we revisit the
algorithm selection problem for TSP, and propose a novel Graph Neural Network
(GNN), called GINES. GINES takes the coordinates of cities and distances
between cities as input. It is composed of a new message-passing mechanism and
a local neighborhood feature extractor to learn spatial information of TSP
instances. We evaluate GINES on two benchmark datasets. The results show that
GINES outperforms CNN and the original GINE models. It is better than the
traditional handcrafted feature-based approach on one dataset. The code and
dataset will be released in the final version of this paper.
