Machine Learning Constructives and Local Searches for the Travelling Salesman Problem

The Travelling Salesman Problem (TSP) is one of the most investigated problems in the Combinatorial Optimization (CO) field. This is partly due to the fact that it belongs to the set of NP-Hard problems, which makes it particularly challenging. Moreover, the many practical problems that can be reduced to this - such as in Ratnesh et al. [10] where models of the TSP are presented to be used in the manufacture of microchips - make it even more attractive. At the same time, the full potentials of Machine Learning (ML) and Deep Learning (DL) techniques are becoming increasingly recognized in the CO field [2]. Mele et al. [17] recently introduced ML-Constructive, a promising constructive approach that computes fast solutions in two separate phases.