Combining 3-Opt and Improved Discrete Cuckoo Search Algorithm for the Traveling Salesman Problem

Abstract

The traveling salesman problem (TSP) is a well-known NP-hard combinatorial optimization problem. In TSP, the objective is to find the shortest distance to the most appropriate route to the starting city. Finding an optimal solution in a reasonable time becomes difficult as the number of cities increases. In recent years, metaheuristic methods obtained optimal or near-optimal solutions in TSP in an acceptable time. This paper proposes a new hybrid metaheuristic method for solving the TSP. The proposed method is developed by combining the 3-Opt method and the improved discrete cuckoo search algorithm. The performance of the proposed method is tested on 39 different benchmark problems in the TSPLIB library. For the 39 different benchmark problems with a size of less than 150 cities, the proposed hybrid method found optimal solutions. In addition, it was observed that as the problem size increases, the results obtained are closer to the optimum compared to other methods. When compared to studies in the literature using the same problem, similar or better results were obtained. For 500 iterations, the average best solution of the proposed method differed from the average optimal solution by 0.07%. In the results of the improved discrete cuckoo search algorithm (CSA), this rate was calculated to be 0.08%. In terms of processing time, the average time of the proposed algorithm was 11.46 seconds, while the average time of the improved discrete CSA was 92.86 seconds. For 1000 iterations, the deviation of the proposed method from the average optimal solution is 0.05%, and the average processing time is 23.72 seconds. The experimental results showed that the proposed new hybrid-improved discrete CSA is effective for solving TSP.