Graph Neural Network Guided Local Search for the Traveling Salesperson
  Problem
  Solutions to the Traveling Salesperson Problem (TSP) have practical
applications to processes in transportation, logistics, and automation, yet
must be computed with minimal delay to satisfy the real-time nature of the
underlying tasks. However, solving large TSP instances quickly without
sacrificing solution quality remains challenging for current approximate
algorithms. To close this gap, we present a hybrid data-driven approach for
solving the TSP based on Graph Neural Networks (GNNs) and Guided Local Search
(GLS). Our model predicts the regret of including each edge of the problem
graph in the solution; GLS uses these predictions in conjunction with the
original problem graph to find solutions. Our experiments demonstrate that this
approach converges to optimal solutions at a faster rate than three recent
learning based approaches for the TSP. Notably, we reduce the mean optimality
gap on the 100-node problem set from 1.534% to 0.705%, a 2x improvement. When
generalizing from 20-node instances to the 100-node problem set, we reduce the
optimality gap from 18.845% to 2.622%, a 7x improvement.
