文章基本信息

标题：Repetitive Nearest Neighbor Based Simulated Annealing Search Optimization Algorithm for Traveling Salesman Problem
本地全文：下载
作者：Md. Azizur Rahman ; Hasan Parvez
期刊名称：Open Access Library Journal
印刷版ISSN：2333-9705
电子版ISSN：2333-9721
出版年度：2021
卷号：8
期号：6
页码：1-17
DOI：10.4236/oalib.1107520
语种：English
出版社：Scientific Research Pub
摘要：The traveling salesman problem (TSP) is the most popular and most studied non-deterministic polynomial (NP) hard problem that has been used in various fields of science and technology. Due to the NP-hard nature, it is very difficult to solve this problem effectively and efficiently. For this reason, diverse appropriate optimization algorithms have been designed and developed in the last few decades. Among these algorithms, heuristic algorithms are much more suitable to tackle with this complex problem. In this paper, we propose a hybrid heuristic algorithm to solve the symmetric TSP problem by combining the search mechanism of repetitive nearest neighbor (RNN) heuristic and simulated annealing (SA) heuristic algorithms. In fact, a set of better routes are generated step by step by the RNN algorithm and these routes are improved through the iterative improvement process of the SA algorithm. The proposed algorithm is tested on a set of benchmark symmetric TSP datasets and compared with the basic RNN and SA algorithms as well as some other hybrid algorithms existing in the literature. It is demonstrated by the experimental results that the proposed algorithm is more effective than both the basic RNN and SA algorithms, and the obtained optimum results are in good agreement with the corresponding best-known optimum results. In addition, the proposed algorithm outperforms some other hybrid algorithms in terms of solution quality.
关键词：Combinatorial OptimizationTraveling Salesman ProblemRepetitive Nearest Neighbor AlgorithmSimulated Annealing AlgorithmNeighborhood StructureHybrid Algorithm