Tackling Travelling Salesman Problem with Graph Neural Network and Reinforcement Learning

Type: Project

Status: finished

Date: May 15, 2023 - October 20, 2023

Supervisors: Linda-Sophie Schneider, Andreas Maier

This project focuses on solving the Travelling Salesman Problem using Graph Neural Network combined with Reinforcement Learning algorithms. Two variants of Graph Neural Network are tested, including Graph Pointer Network and Hybrid Pointer Network, both trained in Actor-Critic algorithm and double Q-learning algorithm separately. Double Q-learning is tried carefully as it is rarely applied in the training of Graph Neural Network compared with Actor-Critic. The models are tested on various types of TSP instances, showing that double Q-learning algorithm is a potential competitor in the improvement of
Graph Neural Networks.