Deep Reinforcement Learning for TSP

Machine learning and artificial intelligence are more than ever changing how we perceive the relationship between humans and technology. In the past few years we witnessed a consistent surge in attention by the STEM community towards this field, which subsequently led to substantial improvements and new walls being broken. As much as learning methods based on large pre-existent datasets are effective, have been proven to be reliable and have been applied in many fields, many researchers’ attention has been leaning towards Reinforcement Learning techniques because of the potential freedom it enables. Reliance on data can be a critical constraint for certain problems. The information chosen may be warped, influenced by temporary actors, may not be feature rich or may not be of a satisfying size. Simply put, in RL the aim is to model the problem with the appropriate and realistic inputs and outputs, well enough to enable the entity to learn from its (generally simulated) surroundings, in order to be able to solve problems in a real setting. Reinforcement Learning techniques endow the designer with the power to build entities capable of solving several problems, without the limit of large amounts of pre-existing data. Combinatorial problems have recently sparked the interest of the RL community. Problems such as the Travelling Salesman Problem (TSP) and the Vehicle Routing Problem (VRP) are not a mistery and have been previously solved, but when the dimensions of the problem explode, current approaches cannot keep up with the enormous number of calculations that need to be performed. For the uninitiated, TSP asks the following : ”Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?” The goal of this document is to explore and describe approaches to tackle the Travelling Salesman Problem by taking advantage of Reinforcement Learning principles.