Graph Neural Network - Local Search for Solving Traveling Salesman Problem
Robieth Sohiburoyyan, Salamet Nur Himawan, and Iryanto

Politeknik Negeri Indramayu, jalan lohbener lama no.08

Abstract

Travelling salesmen problem (TSP) is a famous research field in optimization problems. Despite its simplicity, solving
the problem for large amount of city is computationally infeasible. In this case, finding the optimal solution can be extremely
difficult and quite challenging. Given the widespread applications of TSP and the need of improved methods to solve the problem,
further research is needed. Main purpose of this research is to implement the Graph Neural Network (GNN) and local search, 2
and 3 optimal algorithm, in addressing the TSP. To see performance of the hybrid methods, several simulations are carried out such
benchmark test in TSPLIB, the square grid TSP, and practical applications. Results of this research show that the hybrid methods
have promising results in solving the problems. Existence of the local search increases quality of the solutions. For instance, the
best relative error of the GNN-2-3 optimal algorithm is within range 0 - 4.31% in solving several cases of the TSP benchmark in
TSPLIB. Further, the hybrid method can find five of seven exact solutions of the square grid TSP.

Keywords: Travelling salesmen problem, Graph Neural Network, local search

Topic: Artificial Intelligence (AI)