TSSIA: A Novel Tabu Search Segment Improvement Algorithm for the Traveling Salesman Problem in Türkiye

Abstract

In the traveling salesman problem, the aim is for a salesperson to start from one province, pass through each province only once, and come back to the same province. However, this problem can be reached by discovering the shortest possible route in total. When the number of provinces is large, it is a very difficult and time-consuming problem to solve. Therefore, it is generally attempted to be solved with metaheuristic methods. In this work, the traveling salesman problem was attempted to be solved using the distances between the provinces of Türkiye with Ant Colony, Artificial Bee Colony, and Tabu Search algorithms. The shortest routes were found for each method, and these methods have been compared with each other. As a result, it was seen that the most successful method was the Tabu Search algorithm. In addition, the best-known route has been determined by adding segment improvement to the Tabu Search algorithm. While the best-known route for the Traveling Salesman Problem involving Turkish cities was previously 9,966 km, it has been reduced to 9,906 km using the Tabu Search Segment Improvement algorithm proposed in this study, achieving a reduction of 60 km.