期刊名称：International Journal of Computer Science and Network Security
印刷版ISSN：1738-7906
出版年度：2021
卷号：21
期号：4
页码：33-40
DOI：10.22937/IJCSNS.2021.21.4.5
出版社：International Journal of Computer Science and Network Security
摘要：The traveling salesman problem (TSP) is one of the well-known and extensively studied NPC problems in combinatorial optimization. To solve it effectively and efficiently, various optimization algorithms have been developed by scientists and researchers. However, most optimization algorithms are designed based on the concept of improving route in the iterative improvement process so that the optimal solution can be finally found. In contrast, there have been relatively few algorithms to find the optimal solution using route construction mechanism. In this paper, we propose a route construction optimization algorithm to solve the symmetric TSP with the help of ratio value. The proposed algorithm starts with a set of sub-routes consisting of three cities, and then each good sub-route is enhanced step by step on both ends until feasible routes are formed. Before each subsequent expansion, a ratio value is adopted such that the good routes are retained. The experiments are conducted on a collection of benchmark symmetric TSP datasets to evaluate the algorithm. The experimental results demonstrate that the proposed algorithm produces the best-known optimal results in some cases, and performs better than some other route construction optimization algorithms in many symmetric TSP datasets.
关键词：Combinatorial Optimization; Traveling Salesman Problem; Ratio Value; Constructive Algorithm.
