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

A. Sarucan, M. F. Berkaya and Palanivel M

Discrete Dynamics in Nature and Society, 2024, vol. 2024, 1-21

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.

Date: 2024
References: Add references at CitEc
Citations:

Downloads: (external link)
http://downloads.hindawi.com/journals/ddns/2024/1953277.pdf (application/pdf)
http://downloads.hindawi.com/journals/ddns/2024/1953277.xml (application/xml)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hin:jnddns:1953277

DOI: 10.1155/2024/1953277

Access Statistics for this article

More articles in Discrete Dynamics in Nature and Society from Hindawi
Bibliographic data for series maintained by Mohamed Abdelhakeem ().