基于禁忌搜索算法的改进最短路径算法

张健龙　林荣霞　邱恩超　莫浩明　余泽煌

【摘 要】目前的网络已经十分庞大而链路更易发生变化但Dijkstra算法仍存在着慢收敛问题，从而影响了路由器的性能。本课题通过建立禁忌搜索算法求解最短路径优化问题的数学模型框架和各利用禁忌搜索算法的基本框架，设定禁忌表的大小，控制算法最大迭代次数范围并经过多组数据测试并验证该算法。解决Dijkstra算法最短路径的优化问题，符合现代人工智能路由器发展的趋向。

【关键词】禁忌搜索算法；最短路径优化算法；智能路由；Dijkstra算法

Improvement The Shorest-Path Algorithm Based on Tabu Search

ZHANG Jian-long LIN Rong-xia QIU En-chao MO Hao-ming YU Ze-huang

（Huali College，Guangdong University of Technology， Guangzhou Guangdong 511325， China）

【Abstract】The network is very large and link are more likely to change but the Dijkstra algorithm is still slow convergence problem， which affects the performance of the router.This topic through the establishment of the tabu search algorithm to solve the optimization problem of shortest path model framework and the basic frame of the tabu search algorithm， set the size of the tabu list， control algorithm of maximum number of iterations and through multiple sets of data to test and verify the algorithm. Solve the problem of Dijkstra algorithm of shortest path optimization， conforms to the tendency of the development of modern artificial intelligence router.

【Key words】Tabu search； The shortest path algorithm； Intelligent routing； Dijkstras algorithm

0 引言

计算机网络的运行质量与路由的选择方法密切相关。不同的信息传输要求可以选择和采用不同的路由选择方法。目前的网络已经十分庞大，并且以后发展的趋势会越来越大，传统的互联网络路由协议会显得有些力不从心，因此使用禁忌搜索算法对路由（链路-状态路由选择算法（Link-State Routing，L-S））进行优化，有着十分重要的作用。禁忌搜索算法是人工智能的一种体现，是局部领域搜索的一种扩展。禁忌搜索最重要的思想是标记对应已搜索的局部最优解的一些对象，并在进一步的迭代搜索中尽量避开这些对象，从而保证对不同的有效搜索途径的探索。该算法优化最短路径算法不仅能够优化路由的选路方式和选路速度，还能对路径上Qos进行优化，使网络发挥到最大的性能。

1 禁忌搜索算法求解最短路径优化问题的数学模型框架

假设：已知整个网络的拓扑结构和各链路的长度，求网络中任意2个给定节点之间的最短通路。若将已知的各链路的长度改为路由时延或其他参数，例如，带宽，经过的节点数，平均通信量，平均队列长度等因素及其给组合，就相当于求任意2个节点之间且有最小时延或最小代价的通路。因此，求最短通路的算法且有普遍意义。

输入：图G=（B（G），E（G））有一个源顶点s和一个汇顶点t，以及对所有的边ij∈E（G）的非负边长Cij。

输出：G中从S到T的最短路径的长度。

第0步：从对每个顶点做临时标记L开始，做法如下：L（S）=0，且对除S外所有的顶点L（I）=∞。

第1 步：找带有最小临时标记的顶点（如果有结，随机地取一个）。使该标记变成永久标记，即该标记不再改变。

第2步：对每个没有永久标记但是又带有永久标记的顶点相邻的顶点 j，按如下方计算一个新的临时标记：L（j）=Min{L（i）+Cij}，求最小是对所有带有永久标记的顶点 i做的。

第3步：判断最新永久顶点y与最新临时顶点x是否相等，如果相等则标记此路径为冗余路径：H=Dis{L（y）-L（x）}。再判断顶点y，x延伸节点集合里是否分别存在x，y顶点.如果是则将之删除。重复第2步和第3步，直到所有的顶点都打上了永久标记为止。

2 禁忌搜索算法的基本框架

2.1 初始化阶段

步骤1：加载问题相关数据，初始化变量，生成初始解x0∈X（X为可行解空间），清空禁忌表，设计数器为0。

2.2 搜索阶段

步骤1：搜索不在禁忌表内或满足藐视法则的邻域移动x*∈N（x0）？奂X，其中f（x*）≤f（x），？坌x∈N（x0），而N（x0）是x0的所有邻域解。

步骤2：更新禁忌表T及目前最优解的记录，执行邻域移动x0←x*。

步骤3：判断是否已达到终止条件。如过达到，则终止搜索并输出最优解；否则，计数器记录累加1并返回此阶段步骤1继续执行。

3 算法验证

在此验证测试中，通过设置不同的算法参数，分别对10个例题重复进行求解，将得出的结果进行统计分析，以获得算法最优参数设置的方法。

4 禁忌表的大小

禁忌表的长度过小会导致搜索迂回进行，从而陷入局部最优的状态；而禁忌表长度过长，则会对搜索进行过度的限制，从而导致可能会错过获得最优解的机会。将禁忌表的长度设置为0.5n至3n之间，并且将该区域平均分为5个区间，区间的界限为（0.5+2.5/4 x）n， （x∈[0，4]）取整的结果，其中n为顶点数目，x为禁忌表长度系数。

5 算法最大迭代次数

在此参数的测试中，我会先给一个较大的迭代次数作为迭代上限，如顶点数目在50个以下的实例中设置为2000，顶点数目大于50的时候设置为4000。然后在算法执行的时候记录各个实例达到最优解的时候经历的迭代次数，这个迭代次数称为最优迭代值，以所有例题中最大的最优迭代值作为推荐使用的算法最大迭代次数值。这个方法能够精确地测出各个实例达到最优解时所需的迭代次数。

6 测试方法

本次测试中，使用10个例题进行，每一个实例均使用上述5种禁忌长度及3种初始解构建方法进行测试。同时为了获得更加准确的数据，上述测试会重复5次。因此，在本次测试中会产生10×5×3×5=750组数据。

利用测试所获得的数据制作了“禁忌表长度与初始解生成算法的相互作用下对各个例题的影响程度图”（图1）。横轴代表了禁忌长度系数；纵轴则表示了与例题已知最优解偏离百分比。偏离百分比的计算公式是ε=（C-C*）/C*×100%。其中，C为算法计算出的路径总距离，C*为问题已知的最优解的总距离。

根据图1制作了“禁忌表长度系数及初始解生成算法的相互作用下对最终解的影响图”（图2）。我把横轴设为各个初始解生成算法，而纵轴依然表示了与例题已知最优解偏离百分比，图表中的各条折线，表示了在各个禁忌表长度系数下不同的初始解生成算法的变化。

图2可以总结出，当禁忌表长度系数为3（即禁忌表长度为顶点数目的2.375倍）时，并且使用任意内接法作为初始解生成方法，所获得的最终解与目前已知最优解之间的平均偏离百分比是最低的（0.67%）。

当两个参数的组合达到较低的偏离百分比时，我们希望能通过最少的迭代次数来获得较低的偏离百分比，所以，平均最低的最优迭代值是各个例题的最优参数的组合。

图1 参数相互作用下对各个例题的影响程度图

图2 禁忌表长度系数及初始解生成算法的相互作用下

对最终解的影响图

至于算法最大迭代次数的测试方法，我先对表1中的十个最短路径问题按顶点数量分成两组，分别为“顶点数目不大于50”及“顶点数目在50以上”。然后分别对两组中各例题的最优迭代值进行比较，从中选出最大的最优迭代值作为该组的算法最大迭代次数。测试的数据和各组的最优迭代值在表1中。

表1 两组顶点的最优迭代值分析表

注：表中的数据是在禁忌表长度为3、使用任意内接法生成初始解的情况下获得的.

从表1中可以获悉当顶点数目不大于50时，用任意内接法生成初始解，且禁忌表长度系数为3时，若要获得质量较佳的解算法所需的最大迭代次数至少为1306次；同样道理，当顶点数目大于50时，若要获得质量较佳的解算法所需的最大迭代次数至少为3590次。由此，我建议当顶点数目不大于50时，算法最大迭代次数应设为2000次；当顶点数目大于50时，算法最大迭代次数应设为4000次。

编译环境及所描述的测试环境，均在同一台机器上执行。机器的硬件如下，处理器为Intel Core i7-2610UE Processor （1.5 GHz）、内存4GB。值得一提的是，此程序在运行时，中央处理器并不是满负载运行，故处理器的时钟频率不能用来计算程序执行的时间及效率。

7 测试小结

虽然课题并未通过大规模的测试来获得算法参数的精确设定方法，但通过前面几个小节的测试和分析，可以总结出以下结论：

（1）参数的设置会因问题的实例不同而有所差异；

（2）总的来说，初始解的生成算法对最终解的质量并无明显的影响，但建议使用任意内接法；

（3）禁忌表长度对最终解的质量有明显的影响，当禁忌表长度系数为3（即禁忌表长度为顶点数目的2.375倍）时，所获得的最终解的偏离值是最低的；

（4）当顶点数目不大于50时，最大迭代次数设为2000；当顶点数目大于50时，最大迭代次数应设为4000。

8 总结

在实际应用中，没有一种算法对任何问题都是有效的，不同的算法有不同的适用领域，也有它不适合求解的问题类型。因此，算法的混合就成为了扩展算法的适用范围、提高算法的效率的有效途径。针对本文的研究结果，以下几点是在未来我研究的主要方向：

（1）在本文中的禁忌搜索算法主要使用了全邻域搜索，所以当顶点数目增加时，算法的搜索速度会变得较慢，在未来的研究，我会尝试使用各种算法缩小邻域的搜索范围，以增加搜索速度。

（2）对算法加入多样性和集中性策略，以加快跳出局部最优的能力。

（3）将禁忌搜索算法与算法进行混合，拓展算法的适用域，提高算法的性能。

以上几点将会作为我对禁忌搜索算法的进一步的研究，希望能在不久的将来，能把该算法改进以更好地解决最短路径优化问题。

【参考文献】

[1]邓俊辉.数据结构（C++语言版）[D].3版.清华大学，2013.

[2]M.HAlsuwaiyel.Algorithms Design Techniques and A nalysis（英文版）[M].电子工业出版社，2013.

[3]阮晓青，周义仓.数学建模引论[M].高等教育出版社，2007.

[4]赵鹤群，王鹏宇，李磊.禁忌搜索算法的参数选择及其收敛特性分析[D].91550部队，2013.

[5]欧雪雯.智能路由器：下一个超级入口[N].中国文化报，2013-8-13.

[6]关德新，王伟.一种用于链路状态路由算法的新型数据结构[D].北京航空航天大学，2002.

[7]陈文兰，戴树贵.旅行商题算法研究综述[D].滁州学院，2006.

[8]Frank R.Giordano William P.Fox.A First Course in Mathematical Modeling[M].机械工业出版社，2009.

[9]Glover F. Tabu search： a tutorial[J]. Interfaces，1990（20）：74-94.

[10]Glover F. Tabu search： Part I[J]. ORSA Journal on Computing，1989（1）：190-206.

[11]Glover F. Tabu search： Part II[J]. ORSA Journal on Computing，1990（2）：4-32.

[12]郭娜，曹晓东.基于节约算法和移动方向的禁忌搜索算法[D].大连理工大学，2009.

[13]董宗然，周慧.禁忌搜索算法评述[J].软件工程师，2010（2）：96-98.

[14]颜鹤.局部搜索算法的改进及其应用[D].上海大学，2004.

[15]郑列，朱永松.数学模型[M].科学出版社，2013.

[责任编辑：汤静]

3 算法验证

在此验证测试中，通过设置不同的算法参数，分别对10个例题重复进行求解，将得出的结果进行统计分析，以获得算法最优参数设置的方法。

4 禁忌表的大小

禁忌表的长度过小会导致搜索迂回进行，从而陷入局部最优的状态；而禁忌表长度过长，则会对搜索进行过度的限制，从而导致可能会错过获得最优解的机会。将禁忌表的长度设置为0.5n至3n之间，并且将该区域平均分为5个区间，区间的界限为（0.5+2.5/4 x）n， （x∈[0，4]）取整的结果，其中n为顶点数目，x为禁忌表长度系数。

5 算法最大迭代次数

在此参数的测试中，我会先给一个较大的迭代次数作为迭代上限，如顶点数目在50个以下的实例中设置为2000，顶点数目大于50的时候设置为4000。然后在算法执行的时候记录各个实例达到最优解的时候经历的迭代次数，这个迭代次数称为最优迭代值，以所有例题中最大的最优迭代值作为推荐使用的算法最大迭代次数值。这个方法能够精确地测出各个实例达到最优解时所需的迭代次数。

6 测试方法

本次测试中，使用10个例题进行，每一个实例均使用上述5种禁忌长度及3种初始解构建方法进行测试。同时为了获得更加准确的数据，上述测试会重复5次。因此，在本次测试中会产生10×5×3×5=750组数据。

利用测试所获得的数据制作了“禁忌表长度与初始解生成算法的相互作用下对各个例题的影响程度图”（图1）。横轴代表了禁忌长度系数；纵轴则表示了与例题已知最优解偏离百分比。偏离百分比的计算公式是ε=（C-C*）/C*×100%。其中，C为算法计算出的路径总距离，C*为问题已知的最优解的总距离。

根据图1制作了“禁忌表长度系数及初始解生成算法的相互作用下对最终解的影响图”（图2）。我把横轴设为各个初始解生成算法，而纵轴依然表示了与例题已知最优解偏离百分比，图表中的各条折线，表示了在各个禁忌表长度系数下不同的初始解生成算法的变化。

图2可以总结出，当禁忌表长度系数为3（即禁忌表长度为顶点数目的2.375倍）时，并且使用任意内接法作为初始解生成方法，所获得的最终解与目前已知最优解之间的平均偏离百分比是最低的（0.67%）。

当两个参数的组合达到较低的偏离百分比时，我们希望能通过最少的迭代次数来获得较低的偏离百分比，所以，平均最低的最优迭代值是各个例题的最优参数的组合。

图1 参数相互作用下对各个例题的影响程度图

图2 禁忌表长度系数及初始解生成算法的相互作用下

对最终解的影响图

至于算法最大迭代次数的测试方法，我先对表1中的十个最短路径问题按顶点数量分成两组，分别为“顶点数目不大于50”及“顶点数目在50以上”。然后分别对两组中各例题的最优迭代值进行比较，从中选出最大的最优迭代值作为该组的算法最大迭代次数。测试的数据和各组的最优迭代值在表1中。

表1 两组顶点的最优迭代值分析表

注：表中的数据是在禁忌表长度为3、使用任意内接法生成初始解的情况下获得的.

从表1中可以获悉当顶点数目不大于50时，用任意内接法生成初始解，且禁忌表长度系数为3时，若要获得质量较佳的解算法所需的最大迭代次数至少为1306次；同样道理，当顶点数目大于50时，若要获得质量较佳的解算法所需的最大迭代次数至少为3590次。由此，我建议当顶点数目不大于50时，算法最大迭代次数应设为2000次；当顶点数目大于50时，算法最大迭代次数应设为4000次。

编译环境及所描述的测试环境，均在同一台机器上执行。机器的硬件如下，处理器为Intel Core i7-2610UE Processor （1.5 GHz）、内存4GB。值得一提的是，此程序在运行时，中央处理器并不是满负载运行，故处理器的时钟频率不能用来计算程序执行的时间及效率。

7 测试小结

虽然课题并未通过大规模的测试来获得算法参数的精确设定方法，但通过前面几个小节的测试和分析，可以总结出以下结论：

（1）参数的设置会因问题的实例不同而有所差异；

（2）总的来说，初始解的生成算法对最终解的质量并无明显的影响，但建议使用任意内接法；

（3）禁忌表长度对最终解的质量有明显的影响，当禁忌表长度系数为3（即禁忌表长度为顶点数目的2.375倍）时，所获得的最终解的偏离值是最低的；

（4）当顶点数目不大于50时，最大迭代次数设为2000；当顶点数目大于50时，最大迭代次数应设为4000。

8 总结

在实际应用中，没有一种算法对任何问题都是有效的，不同的算法有不同的适用领域，也有它不适合求解的问题类型。因此，算法的混合就成为了扩展算法的适用范围、提高算法的效率的有效途径。针对本文的研究结果，以下几点是在未来我研究的主要方向：

（1）在本文中的禁忌搜索算法主要使用了全邻域搜索，所以当顶点数目增加时，算法的搜索速度会变得较慢，在未来的研究，我会尝试使用各种算法缩小邻域的搜索范围，以增加搜索速度。

（2）对算法加入多样性和集中性策略，以加快跳出局部最优的能力。

（3）将禁忌搜索算法与算法进行混合，拓展算法的适用域，提高算法的性能。

以上几点将会作为我对禁忌搜索算法的进一步的研究，希望能在不久的将来，能把该算法改进以更好地解决最短路径优化问题。

【参考文献】

[1]邓俊辉.数据结构（C++语言版）[D].3版.清华大学，2013.

[2]M.HAlsuwaiyel.Algorithms Design Techniques and A nalysis（英文版）[M].电子工业出版社，2013.

[3]阮晓青，周义仓.数学建模引论[M].高等教育出版社，2007.

[4]赵鹤群，王鹏宇，李磊.禁忌搜索算法的参数选择及其收敛特性分析[D].91550部队，2013.

[5]欧雪雯.智能路由器：下一个超级入口[N].中国文化报，2013-8-13.

[6]关德新，王伟.一种用于链路状态路由算法的新型数据结构[D].北京航空航天大学，2002.

[7]陈文兰，戴树贵.旅行商题算法研究综述[D].滁州学院，2006.

[8]Frank R.Giordano William P.Fox.A First Course in Mathematical Modeling[M].机械工业出版社，2009.

[9]Glover F. Tabu search： a tutorial[J]. Interfaces，1990（20）：74-94.

[10]Glover F. Tabu search： Part I[J]. ORSA Journal on Computing，1989（1）：190-206.

[11]Glover F. Tabu search： Part II[J]. ORSA Journal on Computing，1990（2）：4-32.

[12]郭娜，曹晓东.基于节约算法和移动方向的禁忌搜索算法[D].大连理工大学，2009.

[13]董宗然，周慧.禁忌搜索算法评述[J].软件工程师，2010（2）：96-98.

[14]颜鹤.局部搜索算法的改进及其应用[D].上海大学，2004.

[15]郑列，朱永松.数学模型[M].科学出版社，2013.

[责任编辑：汤静]

3 算法验证

在此验证测试中，通过设置不同的算法参数，分别对10个例题重复进行求解，将得出的结果进行统计分析，以获得算法最优参数设置的方法。

4 禁忌表的大小

禁忌表的长度过小会导致搜索迂回进行，从而陷入局部最优的状态；而禁忌表长度过长，则会对搜索进行过度的限制，从而导致可能会错过获得最优解的机会。将禁忌表的长度设置为0.5n至3n之间，并且将该区域平均分为5个区间，区间的界限为（0.5+2.5/4 x）n， （x∈[0，4]）取整的结果，其中n为顶点数目，x为禁忌表长度系数。

5 算法最大迭代次数

在此参数的测试中，我会先给一个较大的迭代次数作为迭代上限，如顶点数目在50个以下的实例中设置为2000，顶点数目大于50的时候设置为4000。然后在算法执行的时候记录各个实例达到最优解的时候经历的迭代次数，这个迭代次数称为最优迭代值，以所有例题中最大的最优迭代值作为推荐使用的算法最大迭代次数值。这个方法能够精确地测出各个实例达到最优解时所需的迭代次数。

6 测试方法

本次测试中，使用10个例题进行，每一个实例均使用上述5种禁忌长度及3种初始解构建方法进行测试。同时为了获得更加准确的数据，上述测试会重复5次。因此，在本次测试中会产生10×5×3×5=750组数据。

利用测试所获得的数据制作了“禁忌表长度与初始解生成算法的相互作用下对各个例题的影响程度图”（图1）。横轴代表了禁忌长度系数；纵轴则表示了与例题已知最优解偏离百分比。偏离百分比的计算公式是ε=（C-C*）/C*×100%。其中，C为算法计算出的路径总距离，C*为问题已知的最优解的总距离。

根据图1制作了“禁忌表长度系数及初始解生成算法的相互作用下对最终解的影响图”（图2）。我把横轴设为各个初始解生成算法，而纵轴依然表示了与例题已知最优解偏离百分比，图表中的各条折线，表示了在各个禁忌表长度系数下不同的初始解生成算法的变化。

图2可以总结出，当禁忌表长度系数为3（即禁忌表长度为顶点数目的2.375倍）时，并且使用任意内接法作为初始解生成方法，所获得的最终解与目前已知最优解之间的平均偏离百分比是最低的（0.67%）。

当两个参数的组合达到较低的偏离百分比时，我们希望能通过最少的迭代次数来获得较低的偏离百分比，所以，平均最低的最优迭代值是各个例题的最优参数的组合。

图1 参数相互作用下对各个例题的影响程度图

图2 禁忌表长度系数及初始解生成算法的相互作用下

对最终解的影响图

至于算法最大迭代次数的测试方法，我先对表1中的十个最短路径问题按顶点数量分成两组，分别为“顶点数目不大于50”及“顶点数目在50以上”。然后分别对两组中各例题的最优迭代值进行比较，从中选出最大的最优迭代值作为该组的算法最大迭代次数。测试的数据和各组的最优迭代值在表1中。

表1 两组顶点的最优迭代值分析表

注：表中的数据是在禁忌表长度为3、使用任意内接法生成初始解的情况下获得的.

从表1中可以获悉当顶点数目不大于50时，用任意内接法生成初始解，且禁忌表长度系数为3时，若要获得质量较佳的解算法所需的最大迭代次数至少为1306次；同样道理，当顶点数目大于50时，若要获得质量较佳的解算法所需的最大迭代次数至少为3590次。由此，我建议当顶点数目不大于50时，算法最大迭代次数应设为2000次；当顶点数目大于50时，算法最大迭代次数应设为4000次。

编译环境及所描述的测试环境，均在同一台机器上执行。机器的硬件如下，处理器为Intel Core i7-2610UE Processor （1.5 GHz）、内存4GB。值得一提的是，此程序在运行时，中央处理器并不是满负载运行，故处理器的时钟频率不能用来计算程序执行的时间及效率。

7 测试小结

虽然课题并未通过大规模的测试来获得算法参数的精确设定方法，但通过前面几个小节的测试和分析，可以总结出以下结论：

（1）参数的设置会因问题的实例不同而有所差异；

（2）总的来说，初始解的生成算法对最终解的质量并无明显的影响，但建议使用任意内接法；

（3）禁忌表长度对最终解的质量有明显的影响，当禁忌表长度系数为3（即禁忌表长度为顶点数目的2.375倍）时，所获得的最终解的偏离值是最低的；

（4）当顶点数目不大于50时，最大迭代次数设为2000；当顶点数目大于50时，最大迭代次数应设为4000。

8 总结

在实际应用中，没有一种算法对任何问题都是有效的，不同的算法有不同的适用领域，也有它不适合求解的问题类型。因此，算法的混合就成为了扩展算法的适用范围、提高算法的效率的有效途径。针对本文的研究结果，以下几点是在未来我研究的主要方向：

（1）在本文中的禁忌搜索算法主要使用了全邻域搜索，所以当顶点数目增加时，算法的搜索速度会变得较慢，在未来的研究，我会尝试使用各种算法缩小邻域的搜索范围，以增加搜索速度。

（2）对算法加入多样性和集中性策略，以加快跳出局部最优的能力。

（3）将禁忌搜索算法与算法进行混合，拓展算法的适用域，提高算法的性能。

以上几点将会作为我对禁忌搜索算法的进一步的研究，希望能在不久的将来，能把该算法改进以更好地解决最短路径优化问题。

【参考文献】

[1]邓俊辉.数据结构（C++语言版）[D].3版.清华大学，2013.

[2]M.HAlsuwaiyel.Algorithms Design Techniques and A nalysis（英文版）[M].电子工业出版社，2013.

[3]阮晓青，周义仓.数学建模引论[M].高等教育出版社，2007.

[4]赵鹤群，王鹏宇，李磊.禁忌搜索算法的参数选择及其收敛特性分析[D].91550部队，2013.

[5]欧雪雯.智能路由器：下一个超级入口[N].中国文化报，2013-8-13.

[6]关德新，王伟.一种用于链路状态路由算法的新型数据结构[D].北京航空航天大学，2002.

[7]陈文兰，戴树贵.旅行商题算法研究综述[D].滁州学院，2006.

[8]Frank R.Giordano William P.Fox.A First Course in Mathematical Modeling[M].机械工业出版社，2009.

[9]Glover F. Tabu search： a tutorial[J]. Interfaces，1990（20）：74-94.

[10]Glover F. Tabu search： Part I[J]. ORSA Journal on Computing，1989（1）：190-206.

[11]Glover F. Tabu search： Part II[J]. ORSA Journal on Computing，1990（2）：4-32.

[12]郭娜，曹晓东.基于节约算法和移动方向的禁忌搜索算法[D].大连理工大学，2009.

[13]董宗然，周慧.禁忌搜索算法评述[J].软件工程师，2010（2）：96-98.

[14]颜鹤.局部搜索算法的改进及其应用[D].上海大学，2004.

[15]郑列，朱永松.数学模型[M].科学出版社，2013.

[责任编辑：汤静]