Machine Learning Constructives and Local Searches for the Travelling Salesman Problem
This work addresses scalability issues in solving real-scale traveling salesman problems, but it is incremental as it builds upon an existing hybrid method.
The authors tackled the computational efficiency of the ML-Constructive heuristic for the traveling salesman problem by reducing the deep learning model's weight and adding a local-search phase, resulting in improved performance as shown in experimental results.
The ML-Constructive heuristic is a recently presented method and the first hybrid method capable of scaling up to real scale traveling salesman problems. It combines machine learning techniques and classic optimization techniques. In this paper we present improvements to the computational weight of the original deep learning model. In addition, as simpler models reduce the execution time, the possibility of adding a local-search phase is explored to further improve performance. Experimental results corroborate the quality of the proposed improvements.