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

Solving TSP problem based on improved tabu search algorithm

摘要

针对禁忌搜索算法（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.

关键词

TSP问题 / 禁忌搜索算法 / 贪婪算法 / 邻域变换 / 组合优化

Key words

TSP problem / tabu search algorithm / greedy algorithm / neighborhood transformation / combinatorial optimization

旅行商问题（travelling salesman problem，TSP）是组合优化中典型的NP-hard问题^［1］，在实际生活中有广泛的应用，如：电网规划、车辆调度和机器人控制等^［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数据库中的算例进行计算，实验结果验证了本文算法的有效性。

1 TSP问题数学模型

TSP问题可描述为：假设有一个旅行商要访问n座城市，各城市间距离已知，路径限制是每个城市只能被访问一次，旅行商从初始城市出发，在遍历所有城市后，最后返回初始城市，求最短路径的巡回方案。

TSP问题数学模型^［14］如式（1）所示

g ( x ) = {\displaystyle \sum _{i=\mathrm{1}}^{n-\mathrm{1}}} d(y_i,y_{i+\mathrm{1}})+d(y_n,y_{\mathrm{1}}) （1）

式中：g（x）为路径总长度；d（y_i，y_{i +1}）为第i个访问城市到第i+1个访问城市的距离；y=（y ₁，y ₂，…，y_n ）表示访问城市的顺序；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问题基本原理如下：生成一条只包含起始点和终止点的初始路径，从所有需要访问城市中随机选择一个城市插入到初始路径中，计算剩余城市在所有可能插入位置的节约值，将节约值从大到小降序排列，把节约值最大的城市插入到最佳可行位置，直至车辆经过所有需要访问的城市后返回出发城市。

贪婪算法^［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，最大迭代次数为T _max；

步骤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 本文算法参数设置

本文比较了在不同禁忌长度和候选集规模组合下的最优解结果，并确定了禁忌长度和候选集规模的最优参数。

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次计算结果平均值，具体计算结果如表2和图7所示。

从表2可知，当K=200时，计算得到路径最短距离平均值最小，最短路径平均长度为15 466。因此，在其他参数固定条件下，本文将候选解的数量设置为200。由图7可知，在其他参数固定时，候选集数量从50增大到200，所得最短距离逐渐减小。

3.2 初始解选择

TS算法对初始解依赖性较强，好的初始解能提高算法计算效率。本文采用文献［12］、［13］中算例，分别采用随机生成初始解算法、ICA算法、CW节约算法和贪婪算法生成初始解，并选择计算效果最佳算法作为本文算法初始解。

3.2.1 文献［13］算例

文献［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 文献［12］算例

实验采用文献［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。因此，本文选择贪婪算法作为算法初始解。

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 文献［12］算法与本文算法计算结果比较

为保证实验结果的可靠性，本文算法参数设置与文献［12］一致。设文献［12］算法与本文算法最优值分别为a和b，偏差率计算公式如式（2）所示

偏差率= \frac{a-b}{b} \times \mathrm{100} \mathrm{\%} （2）

在迭代次数分别为100、500和1 000时，重复运行5次实验，计算结果如表6所示。从表6可知，迭代次数为100、500和1 000时，本文算法计算结果均优于文献［12］算法计算结果。在求解精度上，本文算法与文献［12］算法相比有很大的提高。迭代次数从100增加到1000，偏差率逐渐减小。当迭代次数为1 000时，本文算法计算结果最优，最短路径长度为15 382。最短路径方案如图8所示，迭代次数与最优解变化关系如图9所示。

3.4.2 TSPLIB数据库算例与本文算法计算结果的比较

本文采用TSPLIB数据库中的Dantzig42、Berlin52、St70进行算例测试，重复运行5次实验，其中n为城市数量，AVG为5次计算结果平均值，opt为本文算法最优值，ref为TSPLIB参考值，计算结果如表7所示。参考值为TSPLIB数据库中相应最优值，偏差率计算方法如式（3）所示

\mathrm{偏差} \mathrm{率} = \frac{\mathrm{本文}\mathrm{最优}\mathrm{值}-\mathrm{参考}\mathrm{值}}{\mathrm{参考}\mathrm{值}} \times \mathrm{100} \mathrm{\%} （3）

从表7可知，本文算法计算Dantzig42实例的最优解达到TSLIB标准库的最优解。Berlin52和St70实例的最优解与TSPLIB标准库中的最优解相比，偏差率在3%以内，本文算法在小规模案例下，计算结果较为理想。

4 结论

本文针对TSP问题的特点，通过随机生成初始解算法、ICA算法、CW节约算法和贪婪算法生成初始解，选择计算结果最优的贪婪算法对TS算法的初始解进行优化，提出一种改进的禁忌搜索算法。仿真实验中，通过不同情况下参数比较，确定禁忌长度和候选集的最优参数。仿真实验结果表明：相较文献［12］中算法的最优解，本文算法的最优解更接近全局最优解，说明本文算法能够有效解决TSP问题。在与TSPLIB标准库算例比较中，本文算法在小规模算例中计算结果与TSPLB标准库参考值之间的偏差率不超过3%，验证了本文算法求解TSP问题的有效性和可行性。

参考文献

[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.

[7] Prayudani 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.

[8] Wu 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.

[9] Umam M S， Mustafid M， Suryono S.A hybrid genetic algorithm and tabu search for minimizing makespan in flow shop scheduling problem［J］.Journal of King Saud University-Computer and Information Sciences，2022，34（9）：7459-7467.

[10] Alotaibi 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问题［J］.科学技术创新，2022（4）：154-157.

[13] Guo 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.

[15] Glover F.Future paths for integer programming and links to artificial intelligence［J］.Computers & Operations Research，1986，13（5）：533-549.

[16] 王海英.图论算法及其MATLAB实现［M］.北京：北京航空航天大学出版社，2010.

[17] Clarke 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.

基金资助

国家自然科学基金(61972266)

辽宁省自然科学基金(2020-MS-233)

辽宁省兴辽英才计划项目(XLYC2002017)