Travelling Salesman Problem with Reinforcement Learning

by Victor De Lima (vad49)

The Traveling Salesman Problem (TSP) is a well-studied optimization problem with a wide variety of applications and approaches to solving it. The methods and tools of Reinforcement Learning (RL) offer a distinctive strategy for approaching the TSP due to the ease with which its reward structure can be modified. Using data obtained from Skyscanner, this study examines how Q-learning, an RL technique, can optimize a travel route through 42 Asian cities. We first provide a theoretical background into the tools discussed, followed by an exposition of the methodology and experiments. The study's results show that Q-learning is a very effective method for solving the TSP. We also discuss the model's limitations and how it can be extended in future work.

Repo Structure

• Code: includes data cleaning and gathering files, and the main working file on the TSPWithRL folder.
• Data: includes the preliminary and clean data used for modeling.
• Outputs: includes static and interactive visualizations generated by the code.