基于禁忌搜索算法的改進最短路徑算法

張健龍　林榮霞　邱恩超　莫浩明　余澤煌

【摘 要】目前的網絡已經十分龐大而鏈路更易發生變化但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.

[責任編輯：湯靜]