An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem
This work addresses the problem of efficiently solving TSP for researchers and practitioners in combinatorial optimization, though it is incremental as it builds on existing deep learning methods and does not surpass traditional solvers.
This paper tackles the Travelling Salesman Problem on 2D Euclidean graphs by introducing a learning-based approach using Graph Convolutional Networks and non-autoregressive beam search, achieving significant improvements such as reducing the average optimality gap from 0.52% to 0.01% for 50 nodes and from 2.26% to 1.39% for 100 nodes.
This paper introduces a new learning-based approach for approximately solving the Travelling Salesman Problem on 2D Euclidean graphs. We use deep Graph Convolutional Networks to build efficient TSP graph representations and output tours in a non-autoregressive manner via highly parallelized beam search. Our approach outperforms all recently proposed autoregressive deep learning techniques in terms of solution quality, inference speed and sample efficiency for problem instances of fixed graph sizes. In particular, we reduce the average optimality gap from 0.52% to 0.01% for 50 nodes, and from 2.26% to 1.39% for 100 nodes. Finally, despite improving upon other learning-based approaches for TSP, our approach falls short of standard Operations Research solvers.