基于改进禁忌搜索算法求解TSP问题

冉令龙; 李琳; 郑学东

doi:10.3969/j.issn.2095-1248.2023.04.011

沈阳航空航天大学学报 ›› 2023, Vol. 40 ›› Issue (4) : 80 -87. DOI: 10.3969/j.issn.2095-1248.2023.04.011

基础科学和工程

基于改进禁忌搜索算法求解TSP问题

冉令龙 ^a ,
李琳 ^a ,
郑学东 ^b

作者信息 +

Solving TSP problem based on improved tabu search algorithm

Author information +

文章历史 +

PDF (764K)

摘要

针对禁忌搜索算法（tabu search algorithm，TS）对初始解依赖性较强的问题，提出一种改进的禁忌搜索算法求解TSP问题。在分析TSP问题特点后，分别采用随机生成初始解算法、改良圈算法、CW节约算法和贪婪算法生成初始解并比较4种算法的计算效果，从中选出最优解作为TS算法的初始解。在禁忌搜索过程中比较Insert邻域、Swap邻域和2-opt邻域的改进效果，选择最优的邻域变换模式得到改进解。在仿真实验中，设置合适的参数，通过与相关文献实验结果的对比，验证了该算法的有效性。

Abstract

For the problem that tabu search algorithm（TS） has strong dependence on the initial solution，an improved tabu search algorithm（TS algorithm）was proposed to solve traveling sales-man problem（TSP）.The initial solution was generated by random generation algorithm， improved circle algorithm， CW saving algorithm and greedy algorithm， and the results of the four algorithms were compared. The optimal solution was selected as the initial solution of TS algorithm. During TS， the improvement effects of insert neighborhood， swap neighborhood and 2-opt neighborhood were compared， and the optimal neighborhood transformation mode was selected to get the improved solution. In the simulation experiment， appropriate parameters were set， and the effectiveness of the proposed algorithm was verified by comparing with the experimental results of relevant literatures.