A systematic literature review on the use of machine learning in traveling salesman problems

Abstract

The Traveling Salesman Problem (TSP) has been documented in the history of combinatorial optimization since the 18th century. TSP is a well-known NP-hard problem that has been extensively studied, where a salesman aims to visit each of a set of cities exactly once and return to the starting city with minimal distance traveled. The significance of the TSP lies in its applicability to many real-life scenarios. Machine Learning (ML) addresses the question of how tobuild computers that improve automatically through experience. In the last two decades, ML has been applied in many areas. The scope of this paper is to bridge this gap by providing a comprehensive survey of ML usage in TSP. The paper is organized around the following topics: an introduction to the subject, TSP definition, variations and some related works, ML definition and methods, the research methodology used, and results. Additionally, we discuss certain open problems and potential research directions.