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

第40卷 第4期2 0 2 3 年 8 月沈 阳 航 空 航 天 大 学 学 报Journal of Shenyang Aerospace UniversityVol.40 No.4Aug.2 0 2 3基于改进禁忌搜索算法求解TSP问题冉令龙a，李琳a，郑学东b（沈阳航空航天大学 a.理学院，b.计算机学院，沈阳 110136）摘要：针对禁忌搜索算法（tabu search algorithm，TS）对初始解依赖性较强的问题，提出一种改进的禁忌搜索算法求解TSP问题。在分析TSP问题特点后，分别采用随机生成初始解算法、改良圈算法、CW节约算法和贪婪算法生成初始解并比较4种算法的计算效果，从中选出最优解作为TS算法的初始解。在禁忌搜索过程中比较Insert邻域、Swap邻域和2-opt邻域的改进效果，选择最优的邻域变换模式得到改进解。在仿真实验中，设置合适的参数，通过与相关文献实验结果的对比，验证了该算法的有效性。关键词：TSP问题；禁忌搜索算法；贪婪算法；邻域变换；组合优化中图分类号：TP301 文献标志码：Adoi：10.3969/j.issn.2095-1248.2023.04.011Solving TSP problem based on improved tabu search algorithmRAN Linglonga，LI Lina，ZHENG Xuedongb（a.College of Science，b.College of Computer Science，Shenyang Aerospace University，Shenyang 110136，China）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.Key words：TSP problem；tabu search algorithm；greedy algorithm；neighborhood transformation；combinatorial optimization旅行商问题（travelling salesman problem，TSP）是组合优化中典型的NP-hard问题1，在收稿日期:2023-05-27基金项目:国家自然科学基金(项目编号:61972266,61403260);辽宁省自然科学基金(项目编号:2020-MS-233);辽宁省兴辽英才计划项目(项目编号:XLYC2002017)作者简介:冉令龙(1999-),男,黑龙江哈尔滨人,硕士研究生,主要研究方向:智能优化算法,E-mail:;李琳(1978-),女,吉林吉林人,教授,博士,主要研究方向:生产计划与调度、智能优化算法,E-mail:LL。文章编号：2095-1248（2023）04-0080-08冉令龙，等：基于改进禁忌搜索算法求解TSP问题第 4 期实际生活中有广泛的应用，如：电网规划、车辆调度和机器人控制等2-3。研究TSP问题的求解具有重要的意义。目前求解 TSP问题的算法主要分为精确算法和启发式算法两类。精确算法有分支定界、线性规划和动态规划法等4-5。精确算法可求得小规模TSP问题最优解，在处理大规模问题时，很难在有限时间内得到问题的最优解。随着问题规模的增大，许多研究6-8多采用启发式算法进行求解。启发式算法包括蚁群算法（ant colony optimization，ACO）、遗传算法（genetic algorithm，GA）、模拟退火算法（simulated annealing，SA）以及禁忌搜索算法等。TS作为一种启发式算法，在求解函数优化问题中表现出优良的性能9-11，但同时也存在对初始解依赖较强的缺陷，好的初始解对TS算法求解有较大的帮助。本文在基本禁忌搜索算法的基础上，分别采用随机生成初始解算法、改良圈算法（modified circle algorithm，ICA）、CW节约算法和贪婪算法（greedy algorithm）产生初始解，选择 4种算法中效果最佳的算法生成初始解，将其作为TS算法的初始解。在邻域变换过程中，比较Insert 邻域、Swap 邻域和 2-opt 邻域的计算效果，选择计算效果最优的邻域结构。仿真实验分别采用文献12、13中的算例与标准TSPLIB数据库中的算例进行计算，实验结果验证了本文算法的有效性。1TSP问题数学模型TSP问题可描述为：假设有一个旅行商要访问n座城市，各城市间距离已知，路径限制是每个城市只能被访问一次，旅行商从初始城市出发，在遍历所有城市后，最后返回初始城市，求最短路径的巡回方案。TSP问题数学模型14如式（1）所示g(x)=i=1n-1d(yiyi+1)+d(yny1)（1）式中：g（x）为路径总长度；d（yi，yi+1）为第i个访问城市到第 i+1个访问城市的距离；y=（y1，y2，yn）表示访问城市的顺序；n为访问城市个数；1，2，n表示访问城市序号。TSP问题按其距离矩阵分为对称和非对称性TSP问题，本文研究对称性TSP问题。2改进的禁忌搜索算法TS算法是由美国科罗拉大学Fred Glover教授在1986年首次提出15。TS算法通过引入相应的禁忌表来避免重复搜索，并对禁忌区域中的一些优良状态进行特赦，避免算法陷入局部最优，是一种全局迭代寻优的算法。TS算法具备强大的局部搜索能力和记忆功能，但其对初始解的依赖性较强，较好的初始解可使算法快速找到最优解。为降低初始解对算法的影响，提高TS算法的计算效率，本文比较了随机生成初始解算法、ICA算法、CW节约算法和贪婪算法4种方法生成初始解，将其中最好的初始解作为TS算法的初始解进行迭代，进而寻求最优解。ICA算法16求解TSP问题的基本思想是先随机生成路径，形成一个 Hamilton圈，随机交换 Hamilton圈内除起始点和终止点外的两个点位置，若交换后的路径总长度小于交换前的路径总长度，接受此次交换，成功交换次数加1，更新最短路径，直至成功交换次数达到设置的改良次数，结束搜索。ICA算法搜索随机性不高，较难得到全局最优解，易陷入局部最优。因此，该算法常用于构造初始解，并结合相关启发式算法求解TSP问题。CW 节约算法是 Clark 等17提出的一种解决车辆路径问题较为有效的启发式算法，其求解TSP问题基本原理如下：生成一条只包含起始点和终止点的初始路径，从所有需要访问城市中随机选择一个城市插入到初始路径中，计算剩余城市在所有可能插入位置的节约值，将81沈 阳 航 空 航 天 大 学 学 报第 40 卷节约值从大到小降序排列，把节约值最大的城市插入到最佳可行位置，直至车辆经过所有需要访问的城市后返回出发城市。贪婪算法18生成 TSP 问题初始解的方法为从第一个城市出发，每次在没有到达的城市中选择距离最近的一个城市访问，依次进行，直至经过所有访问城市，最后返回出发城市。根据TSP问题的特点，本文设计了3种邻域结构，从中选择计算效果最佳的邻域结构。Insert邻域：在生成的初始城市序列中随机选择两个不同位置a和b，将位置a对应的城市插入位置b，记为Insert（a，b）；如生成初始城市序列R=1，5，2，4，3，6，7，随机选取的城市为 5，3，则Insert邻域变换如图1所示。Swap邻域：在生成的初始城市序列中随机选择两个不同位置a和b，将位置a和b对应的城市交换，记为Swap（a，b）；如生成初始城市序列R=1，5，2，4，3，6，7，随机选取的城市为 5，3，则Swap邻域变换如图2所示。2-opt邻域：在生成的初始城市序列中随机选择两个不同位置a和b，将位置a和b对应的城市交换，将位置a和b对应城市之间的所有城市进行倒序排列；如生成初始城市序列R=1，5，2，4，3，6，7，随机选取城市为 5，3，则2-opt邻域变换如图3所示。改进的TS算法求解TSP的步骤如下：步骤1：设置算法基本参数，即禁忌表长度为TL，候选解个数为K，最大迭代次数为Tmax；步骤 2：用随机生成初始解算法、ICA 算法、CW算法和贪婪算法生成初始解，选择其中最优的初始解，判断它是否满足终止条件：若满足，则输出最优解，算法结束；否则，转入步骤3；步骤 3：用 Insert 邻域、Swap 邻域和 2-opt邻域结构产生邻域解，选择其中计算结果最优的邻域结构，在它生成的若干邻域解中挑选K个候选解，计算目标值，选取结果较好的候选解；步骤4：判断候选解是否满足特赦准则：若满足，特赦候选解，更新当前最优解，将其加入禁忌表，更新禁忌表；否则，选择候选解中未被禁忌的最优解作为当前最优解，更新禁忌表；步骤 5：重复步骤 3和步骤 4，直至满足程序终止条件，结束搜索。改进的TS算法流程图见图4所示。3仿真实验仿真实验分别采用了文献 12、13 中的算例与标准 TSPLIB数据库中的算例，将本文算法的计算结果与算例中的实验结果进行比较。本文算法用 Python实现，在 Window10操作系统，处理器为 Inter（R）Core（TM）i7-7700（2.80Ghz），8 GB内存的电脑上运行。文献 12 中的城市数为31，城市分布散点如图5所示。3.1本文算法参数设置本文算法参数设置本文比较了在不同禁忌长度和候选集规模组合下的最优解结果，并确定了禁忌长度和图32-opt邻域图1Insert邻域图2Swap邻域82冉令龙，等：基于改进禁忌搜索算法求解TSP问题第 4 期候选集规模的最优参数。3.1.1禁忌长度的选择禁忌长度的选择禁忌长度是禁忌搜索算法中的一个关键参数，作为放置在禁忌表中对象的禁忌周期，进行一次迭代，周期减少一次，直至周期为0时解除禁忌。禁忌长度的选择影响最终最优解的结果。文献 12 的算例采用随机生成初始解算法，设置K=200、N=100，采用2-opt邻域变换。本文算法的禁忌长度分别为 10、15、20、22，在不同禁忌长度下，重复运行 3 次程序，AVG为3次计算结果平均值，具体计算结果如表1所示，计算结果如图6所示。从图6可知，在其他参数固定的情况下，禁忌长度从10增大到20，计算结果逐渐减小；禁忌长度从20增大到22，计算结果相近。从表1可得，当TL=22时，计算结果平均值最小，最短路径平均长度为15 466。因此，在其他参数固定条件下，本文取TL=22。3.1.2候选集选择候选集选择候选集从邻域解中产生，随机选择几个邻域解或选表现较好的解作为候选解。本实验设置TL=22、N=100，采用2-opt邻域变换，设置候选解集个数分别为50、100、150和200。在不同候选解集下，重复运行3次程序，AVG为3次?，?，?，?，?，?，?、?、ICACW?，?、?、ICACW?，?图4改进的TS算法流程图3 5003 5003 0003 0002 5002 5002 0002 0001 5001 5001 0001 0005005001 5001 500 2 0002 000 2 5002 500 3 0003 000 3 5003 500 4 0004 000 4 5004 50030302929282811111010222223232424131312126 65 54 43 31 17 78 8181819192020212117172 216169 92525262627270 01414图531座城市分布散点图16 00016 00015 90015 90015 80015 80015 70015 70015 60015 60015 50015 50015 70015 70015 30015 30015 20015 20015 10015 1001 12 23 3?=15?=15?=20?=20?=22?=22?=10?=10?图6禁忌长度选择对比图表1本文算法禁忌长度选择对比结果TL10152022115 86915 60515 55315 477215 88715 76615 47515 455315 82415 58215 42815 468AVG15 86015 65115 48515 46683沈 阳 航 空 航 天 大 学 学 报第 40 卷计算结果平均值，具体计算结果如表 2和图 7所示。从表 2 可知，当 K=200 时，计算得到路径最短距离平均值最小，最短路径平均长度为15 466。因此，在其他参数固定条件下，本文将候选解的数量设置为200。由图7可知，在其他参数固定时，候选集数量从50增大到200，所得最短距离逐渐减小。3.2初始解选择初始解选择TS算法对初始解依赖性较强，好的初始解能提高算法计算效率。本文采用文献 12、13 中算例，分别采用随机生成初始解算法、ICA算法、CW节约算法和贪婪算法生成初始解，并选择计算效果最佳算法作为本文算法初始解。3.2.1文献文献 1313 算例算例文献 13 中有21个客户的位置坐标数据，本文算法设置参数 TL=10，N=100，K=30，邻域结构为2-opt，改良次数T=20，将不同算法得到初始解代入TS算法，重复运行5次实验，其中AVG为5次计算结果的平均值，计算结果如表3所示。从表3可知，贪婪算法计算结果平均值最小，最短路径平均长度为264.8，相较随机生成初始解算法、ICA算法和CW节约算法最短路径平均长度分别减少5.0、4.0和1.2。3.2.2文献文献 1212 算例算例实验采用文献 12 中的31个城市数据坐标，设置参数TL=22、N=100、K=200、T=20，邻域结构为2-opt，将不同算法得到初始解代入TS算法，重复运行5次实验，其中AVG为5次计算结果的平均值，计算结果如表4所示。从表4可知，贪婪算法计算结果平均值最小，最短路径平均长度为15 444，相较随机生成初始解算法、ICA算法和CW节约算法最短路径平均长度分别减少66、64和54。因此，本文选择贪婪算法作为算法初始解。表2候选解选择对比结果K50100150200115 81215 67215 53815 477215 80415 58315 52315 455315 82615 64415 55415 468AVG15 81415 63315 53815 46615 90015 90015 80015 80015 70015 70015 60015 60015 50015 50015 70015 70015 30015 30015 20015 2001 12 23 3?=50?=50?=100?=100?=150?=150?=200?=200?图7候选集选择对比图表3文献 13 算例实验结果算法随机生成初始解算法ICA算法CW节约算法贪婪算法12742682632682262262269269327126826526242742742712635274272262262AVG271268266264表4文献 12 算例实验结果算法随机生成初始解算法ICA算法CW节约算法贪婪算法115 55115 43315 55915 410215 60315 64115 59415 475315 39815 42815 38215 387415 47515 48215 45515 505515 52515 50815 55415 447AVG15 51015 49815 50815 44484冉令龙，等：基于改进禁忌搜索算法求解TSP问题第 4 期3.3邻域结构邻域结构为增加解的多样性，本文算法提出基于变邻域搜索的干扰机制，比较了Insert邻域、Swap邻域和2-opt邻域求解文献 12 中算例的近优解结果。设置TL=22、N=100、K=200，在不同邻域结构下，重复运行5次实验，AVG为5次计算结果平均值，计算结果如表5所示。从表5可知，当邻域结构为2-opt时，计算结果平均值最小，最短路径平均长度为15 427，相较采用 Insert邻域和 Swap 邻域所得最短路径平均长度分别减少84和12。因此，本文选择2-opt邻域结构。3.4算例比较算例比较本文采用文献 12 数据和算法、TSPLIB数据库中算例和结果来验证本文算法的有效性。3.4.1文文献献 1212 算法与本文算法计算结果算法与本文算法计算结果比较比较为保证实验结果的可靠性，本文算法参数设置与文献 12 一致。设文献 12 算法与本文算法最优值分别为a和b，偏差率计算公式如式（2）所示偏差率=a-bb100%（2）在迭代次数分别为100、500和1 000时，重复运行5次实验，计算结果如表6所示。从表6可知，迭代次数为100、500和1 000时，本文算法计算结果均优于文献 12 算法计算结果。在求解精度上，本文算法与文献 12 算法相比有很大的提高。迭代次数从100增加到1000，偏差率逐渐减小。当迭代次数为 1 000时，本文算法计算结果最优，最短路径长度为15 382。最短路径方案如图8所示，迭代次数与最优解变化关系如图9所示。表5不同邻域算法结果邻域InsertSwap2-opt115 53615 42915 398215 50115 44715 410315 49515 44915 457415 52815 39815 472515 49815 47415 399AVG15 51115 43915 427表6文献 12 与本文算法计算结果比较迭代次数1005001000实验次数123451234512345a16 90517 60917 70317 15217 39416 52616 58716 55016 85217 17815 80016 03715 38216 00615 824b15 48315 49815 53615 61915 52015 46415 38715 41015 42215 39915 43315 39815 38215 41015 382偏差率/%9.1813.6213.959.8112.076.877.807.409.2711.552.384.1503.872.873 5003 5003 0003 0002 5002 5002 0002 0001 5001 5001 0001 0005005001 5001 500 2 0002 000 2 5002 500 3 0003 000 3 5003 500 4 0004 000 4 5004 500图8本文算法最短路线方案17 00017 000?16 50016 50016 00016 00015 50015 50015 00015 00014 50014 5000 02002004004006006008008001 0001 000?图9迭代次数与最优解变化关系图85沈 阳 航 空 航 天 大 学 学 报第 40 卷3.4.2TSPLIBTSPLIB数据库算例与本文算法计算结数据库算例与本文算法计算结果的比较果的比较本文采用 TSPLIB数据库中的 Dantzig42、Berlin52、St70进行算例测试，重复运行5次实验，其中n为城市数量，AVG为5次计算结果平均值，opt为本文算法最优值，ref为TSPLIB参考值，计算结果如表7所示。参考值为TSPLIB数据库中相应最优值，偏差率计算方法如式（3）所示偏差率=本文最优值-参考值参考值100%（3）从表7可知，本文算法计算Dantzig42实例的最优解达到 TSLIB 标准库的最优解。Berlin52和St70实例的最优解与TSPLIB标准库中的最优解相比，偏差率在3%以内，本文算法在小规模案例下，计算结果较为理想。4结论本文针对TSP问题的特点，通过随机生成初始解算法、ICA算法、CW节约算法和贪婪算法生成初始解，选择计算结果最优的贪婪算法对TS算法的初始解进行优化，提出一种改进的禁忌搜索算法。仿真实验中，通过不同情况下参数比较，确定禁忌长度和候选集的最优参数。仿真实验结果表明：相较文献 12 中算法的最优解，本文算法的最优解更接近全局最优解，说明本文算法能够有效解决TSP问题。在与 TSPLIB标准库算例比较中，本文算法在小规模算例中计算结果与TSPLB标准库参考值之间的偏差率不超过 3%，验证了本文算法求解TSP问题的有效性和可行性。参考文献（References）：1陈文兰，戴树贵.旅行商问题算法研究综述 J.滁州学院学报，2006，8（3）：1-6.2曾琼燕，杨晟.基于模拟退火算法的共享单车动态调度问题研究 J.综合运输，2023，45（2）：75-79，132.3刘晗兵.基于GIS决策功能的物流配送TSP优化模型研究 J.电子设计工程，2017，25（18）：46-49.4但开，段隆振.基于最优插入子集的动态规划算法求解旅行商问题J.计算机应用与软件，2022，39（12）：26-265，297.5袁森，陈开奇，李江坤，等.最小最大圈覆盖问题的精确算法 J.中国科学：信息科学，2022，52（6）：960-970.6李眩，童百利，方婷婷.基于模拟退火思想的最优最差蚁群算法求解的 TSP 问题 J.山西师范大学学报（自然科学版），2023，37（2）：22-27.7Prayudani S，Hizriadi A，Nababan E B，et al.Analysis effect of tournament selection on genetic algorithm performance in traveling salesman problem（TSP）J.Journal of Physics：Conference Series，2020，1566（1）：012131.8Wu C Y，Fu X S，Pei J K，et al.A novel sparrow search algorithm for the traveling salesman problem J.IEEE Access，2021，9：153456-153471.9Umam M S，Mustafid M，Suryono S.A hybrid genetic algorithm and tabu search for minimizing makespan in flow shop scheduling problemJ.Journal of King Saud University-Computer and Information Sciences，2022，34（9）：7459-7467.10Alotaibi Y.A new meta-heuristics data clustering algorithm based on tabu search and adaptive search memory J.Symmetry，2022，14（3）：623.11管赛，熊禾根.混合禁忌搜索的车间调度遗传算法研究 J.智能计算机与应用，2023，13（5）：171-174.12唐文秀.基于改进禁忌搜索算法求解 TSP 问题表7TSPLIB最优解与本文算法实验结果比较算例Dantzig42Berlin52St70n425270AVG7057 694699opt6997 656692ref6997 542675偏差率/%01.512.5286冉令龙，等：基于改进禁忌搜索算法求解TSP问题第 4 期J.科学技术创新，2022（4）：154-157.13Guo Q G，Wang N M.The vehicle routing problem with simultaneous pickup and delivery considering the total number of collected goods J.Mathematics，2023，11（2）：311.14戚远航，蔡延光，蔡颢，等.旅行商问题的混沌混合离散蝙蝠算法 J.电子学报，2016，44（10）：2543-2547.15Glover F.Future paths for integer programming and links to artificial intelligence J.Computers&Operations Research，1986，13（5）：533-549.16王海英.图论算法及其 MATLAB 实现 M.北京：北京航空航天大学出版社，2010.17Clarke G，Wright J W.Scheduling of vehicles from a central depot to a number of delivery points J.Operations Research，1964，12（4）：568-581.18来学伟.贪心算法在TSP问题中的应用 J.许昌学院学报，2017，36（2）：41-44.（责任编辑：吴萍 英文审校：曹依菲）87