Graph Neural Network - Variable Neighborhood Search for Solving Symmetric Traveling Salesman Problem

The goal in optimization is to discover the nearest optimum that satisfies particular constraints. The traveling salesman problem (TSP) is a well-known challenge in combinatorial optimization, widely applicable in various engineering domains. TSP focuses on organizing a trip among cities at the lowest cost, where costs may represent distance or time. Despite its simplicity, the time complexity for solving the algorithm can increase exponentially with the number of cities. In this case, finding optimal solution of the problem can be so difficult and challenging. So far there is no flawless approach for addressing TSP. The available methods can only deliver approximate solutions close to the optimal solution within a reasonable time frame. Therefore further study of the improved methods to address the problem is urgent to do. Main purpose of this study is to implement the Graph Neural Network (GNN) and Variable Neighborhood Search (VNS) in addressing the TSP. To see performance of the hybrid methods, numerical tests are carried to solve several cases of symmetric TSP. Results of this research show that the proposed method has good accuracy in finding the best-known solution of the cases. Moreover the proposed method has superior performance compared to hybrid GNN-2 Opt and GNN-3 Opt according to the best, average and the worst relative error. For instances the proposed method has the best, average, and the worst relative error within range 0 - 0.0486, 0.025 - 0.091, 0.0906 - 0.1715, respectively.