Efficient graph neural networks for travelling salesman problem using multilevel clustering

Abstract

The goal of the Travelling Salesman Problem is to find the shortest route that visits each city exactly once and returns to the origin, given a list of cities and the distances between each pair of cities. Such combinatorial optimization problems are difficult to solve efficiently given large problem sizes. Algorithms that solve such problems have applications in many fields such as transportation, operations, and networks. Most solutions formulate heuristics which are policies used by algorithms to search for approximate solutions. These heuristics are designed manually and require specialized knowledge. Graph neural networks have recently been used to automate the creation of these heuristics. However, current state-of-the-art graph neural networks have slow training and inference times due to their O(n2) time complexity. In this paper, we introduce a Multilevel Graph Neural Network (MGNN) for approximating solutions to the TSP by using graph clustering which solves the TSP at multiple resolutions. We train our models on input graph sizes of up to 128 nodes and measure the accuracy as well as experimental time complexity with respect to the graph size. Our divide-and-conquer strategy effectively combats combinatorial explosion by enabling a linear runtime of O(n) at the cost of model accuracy.