改進自適應大鄰域搜索算法及其在旅行商問題中的應用

Improved adaptive large neighborhood search algorithm and its application to traveling salesman problem

Ao Hongruila， Zhang Jihuila，1bt，Chen Shengzong2 （1.aScholofutomaindongKeybotoryfdstralControlTologingdoUnesityQingdaSd China；2.School of Economicsamp; Management，Beihang University，Beijing 10o191，China）

Abstract：Thisstudyenhancedthetraditionaladaptivelargeneighborhoodsearch algorithm（ALNS）toaddressthechallngesof initial temperaturesetingandlowaccuracywhensolving large-scaletravelingsalesman problems.Firstly，this paper proposedtwoadditional directionalremovaloperators basedonnearestneighborinformation：thenearest neighborremoval operator forregionalsolutionremovalandthenonnearestneighborremovaloerator forsinglepointremoval，which improved search efciency.Secondly，Itreplacedthetraditional Metropolis criterion withanimprovedRRTaceptance criterion，eliminatingtheneedforinitialtemperatureparametersandenhancingthealgorithm’suniversalityFinally，experimentalesults fromvarious testcases in the TSPLIBdatabase showthattheimprovedALNS performs wellin termsof acuracy andconvergence speed， indicating its potential for handling large-scale instances.

Keywords：improved adaptive large neighborhood search algorithm；neighbor operator；RRTacceptance criteria；traveling salesman problem（TSP）

0 引言

旅行商問題（TSP）是一個經典的組合優化問題。該問題可以描述為：給定一組城市以及它們之間的距離，目標是找到一個最短的路徑，使得從某個起始城市出發，訪問每一個城市恰好一次，并最終返回到出發點。眾所周知，TSP是經典的NP難題，具有廣泛的應用背景，如物流運輸、車輛路線規劃和管道鋪設等，針對不同的實際應用場景，存在多種TSP問題的變體和擴展模型。近年來，智能優化算法的快速發展為解決TSP提供了新的視角和方法，如模擬退火算法[1]、蟻群算法[2]、遺傳算法[3]和布谷鳥算法[4]等。高海昌等人[5]討論了幾種求解TSP熱門的啟發式算法和元啟發式算法，指出2-opt和3-opt等局部啟發式優化算法單獨使用時雖然操作簡單但是易陷入局部最優，元啟發式算法通過特定策略賦予算法跳出局部最優的能力，提高求解精度。陳晟宗等人[提出了一種波動溫控模擬退火算法，將退火過程中的降溫函數替換為波動函數，使得整個算法在總體上溫度逐漸降低，且實現多次的溫度升降，減少算法陷入局部最優解的情況。陳科勝等人[7]提出了一種自適應升溫模擬退火算法，通過升溫控制因子使得算法在求解過程中自適應地升高溫度，防止陷入局部最優。Wei等人[8]提出了一種具有反復升溫和降溫的模擬退火算法，根據歷史最優解定義最佳溫度，通過在最佳溫度附近反復升溫降溫實現跳出局部最優。王育潔等人提出結合評估獎懲機制和鄰域動態退化的協同蟻群算法，通過路徑評估值將路徑分為活躍路徑和舍棄路徑，對活躍路徑進行信息素獎勵，對舍棄路徑進行信息素懲罰，加快算法的收斂速度。Huang等人[10]提出了一種基于群體挖掘的并行社交蜘蛛算法，通過數據挖掘技術提取動態啟發式信息，增強了算法的智能性和適應性。陳加俊等人[1]提出一種單親遺傳算法，針對同優個體組設計了基于最近鄰變異的跳躍策略，兼顧局部優化與避免早熟。沈孝凱等人[12]將黑猩猩優化算法應用到TSP中，提出了一種新的鄰域搜索方式一一近鄰牽引算子，有效地加快了算法的收斂速度。

盡管改進后的啟發式算法在處理離散問題上表現出色，但在求解大規模TSP時，仍存在收斂速度較慢的缺點。而新提出的啟發式算法雖然引入了多種創新機制，但求解精度并不理想。先前已有眾多研究文獻探討了將自適應大鄰域搜索算法（adaptivelargeneighborhoodsearchalgorithm，ALNS）應用于路徑規劃領域：Pisinger等人[13]基于大鄰域搜索算法提出了ALNS，通過自適應組合多種移除/修復算子增強了全局尋優能力。陸永亮等人[14]應用ALNS求解旅行商問題，并結合局部搜索以提升性能。文獻[15]對ALNS進行了總結，強調了算子在算法性能中的關鍵作用，并詳細介紹了常用的移除/修復算子。Santini等人[1通過實驗對比分析了ALNS九種不同的接受準則，實驗結果顯示，RRT接受準則表現最佳。Lei等人[17]提出了一種改進ALNS，采用RRT接受準則來替代傳統Metropolis接受準則，用于解決旅行商問題，結果表明這一改進顯著提升了算法性能。Hemmati等人[i8]提出一種線性遞減的改進RRT接受準則，增強了算法后期的收斂效果。雖然文獻[13]求解小規模問題時具有較高精度且收斂速度快，但在求解大規模TSP時效果有限。文獻［14]采用結合局部搜索提升算法的求解精度，但在大規模問題中存在收斂速度慢的問題。文獻[15]提出多種移除/修復算子，但這些算子都是通用的經典算子，并沒有針對TSP的特點進行設計。文獻[16]采用經典的RRT接受準則確實在性能上優于傳統的Metropolis準則，但在后期收斂效果較差，求解精度不高。文獻[17，18]雖然對傳統的RRT接受準則進行了改進，但將其應用到求解TSP中性能提升仍然有限。為解決上述問題，提出了改進ALNS。

1改進的自適應大鄰域搜索算法

1.1 解的表達方式

采用整數編碼的方式對解進行路徑表示，設訪問城市順序為C1-C4-C3-C2-C5-C1，則解記作（1，4，3，2，5）。

1.2 近鄰算子

近鄰算子會優先處理距離較近的城市，因為根據文獻[19]實驗統計，在目前的算例中，最優路徑中的相鄰城市通常位于彼此距離較近的前20個城市之內。在使用該算子之前，首先需要計算所有城市之間的距離矩陣，然后依次遍歷每個城市，將其最接近的 j 個城市集合存人近鄰表中（若有等距離情況，則所有等距離城市均存人）。

a）近鄰移除算子。從當前解中隨機選擇一個城市，并從該城市的近鄰表中隨機選擇一些城市一同移除。如果移除的城市數量超過了近鄰參數 j， 那么剩下的需要移除的城市將在當前解中隨機選擇。如圖1所示，當移除數量為3時，從當前解中隨機選擇了城市3，然后找出城市3對應的近鄰表中近鄰城市集合4＼～6，從中隨機選取了城市4、5，然后將其與城市3一同移除。該算子的時間復雜度為 O（n） 。

b）非近鄰移除算子。從當前解中隨機選擇一個城市，若其左右相鄰城市均在近鄰表內，移除概率為 P₁ ，若僅一個相鄰城市在近鄰表內，移除概率為 P₂ ，若兩側城市均不在近鄰表內，移除概率為 P₃ 。該算子的時間復雜度為 O（nj） 。

1.3 移除算子

a）隨機移除算子。從當前解中隨機選取一定數量的城市（與總城市數量有關，需根據具體問題設定），將其直接從當前解中移除。如圖2所示，從當前解中隨機選擇了城市3和5，然后將其移除。該算子的時間復雜度為 O（n） 。

b）路徑移除算子。根據移除城市數量，從當前解中隨機選擇一個城市片段，將其直接移除。如圖3所示，移除城市數量為3時，從當前解中隨機選擇城市片段3、6、7，然后將其移除。該算子的時間復雜度為 O（n） 。

c）最壞邊移除算子。從當前解中計算移除每個城市剩余路徑的長度，通過排序找到最短的剩余路徑，將對應城市從當前解中移除。如圖4所示，經過計算以后，從當前解中移除城市2后總路徑長度減少的值最大，因此將其移除。該算子的時間復雜度為 O（n²） 。

1.4修復算子

a）貪婪修復算子。從待修復解中計算每個修復節點修復后的路徑長度，通過排序找到路徑長度最小的修復節點，將其修復。如圖5所示，經過計算，城市6和7之間修復城市2總路徑最短，因此在城市6和7之間修復城市2，該算子的時間復雜度為 O（n²） 。

b）噪聲貪婪修復算子。此運算符是在貪婪修復算子的基礎上，在計算城市修復后的總路徑長度時增加噪聲系數 Ω_u 。

其中： u 是噪聲系數； r 是在[-1，1]均勻分布的隨機數;realcost是實際的適應度值； d_max 為距離矩陣中最大值。該算子的時間復雜度為 O（n²） 。

1.5自適應概率調控機制

每次迭代中，根據算子被選擇的概率通過輪盤機制選擇移除和修復算子。在移除算子數量較多時，自適應概率調控機制對算法精度提升明顯[20]，這里仍采用該機制。求解TSP的關鍵是在于鄰域結構的使用，移除算子集合 的選擇概率設定為 P∈{P₁，P₂，P₃，P₄，P₅} ，修復算子集合 的選擇概率可以設定為 P∈{P₆，P₇} ，每一次的內循環迭代后算子被使用的概率按式（2）更新。

其中： ?_：i 是當前內循環迭代次數； λ 為控制概率更新的反應系數， λ 越大則算子更新概率變化受當前效果得分的影響越大，反之算子概率變化受到以往歷史概率的影響更大； P_nⁱ⁺¹ 代表第i+1 次內循環時第 n 個算子的概率值； g_n 代表的是第 n 個算子在當前內循環中的得分； t_n 代表的是第 Ω_n 個算子當前內循環的使用次數; 代表的是當前內循環中所有移除/修復算子的期望得分總和； k 是移除或修復算子的總個數。分數的迭代將按照以下規則進行更新：算子改進當前解且優于歷史最優解則增加 g₁ 分；算子改進當前解則增加 分；算子擾動得到的解被接受加 分。 g₁…_g2 和 g₃ 的取值分別設為4、2和1。

1.6 接受準則的改進

使用ALNS解決TSP時，多數研究采用了Metropolis準則來接受較差的解。然而，溫度參數的設定并沒有統一的方法。為此，引入RRT方法[21]作為接受準則，并針對TSP進行了改進，減少算例變化時參數的設置與調試所花費的時間。傳統RRT是在滿足 f（x）*）+δf（x^*） 的條件下接受劣解，其中x 是新生成的解， x^* 是歷史最優解，這里的偏差δ通常是固定取值[17]或是線性減少的[18]，但這樣的設定效果并不理性。因此本文將偏差參數 δ 設置為 δ=δ₀×a^m ，使得 δ 在后期衰退的速度慢于前期，花費更多的時間來精細地搜索有希望的區域，提升搜索的精度。其中： m 是當前外循環次數； δ₀ 是一個固定值； a 是衰退系數。

1.7算法流程

a）算法初始化，移除算子集合 ，修復算子集合 ，設定初始參數（內循環次數 L ，外循環總次數 M ，初始偏差 δ_?0 ，降溫系數 a ）。

b）在解空間中生成一個可行解 s ，并記作當前解和歷史最優解 s^* ，平均分配各算子初始概率值。

c）使用輪盤賭方法從移除算子集合和修復算子集合中依概率隨機選擇一組修復算子和移除算子，并用其對當前解 s 進行擾動得到一個新解，記作 S^′ 。

d）計算 S^′ 的路徑長度，根據RRT準則決定是否接受當前解，接受概率 p 的計算公式如式（3）所示，如果新解的路徑長度小于歷史最優解，則更新 s^* 。

e）判斷是否滿足內循環結束條件，若不滿足則返回步驟c），否則更新偏差值 δ ，然后根據各個算子在此次內循環中的使用次數和分數更新算子被選擇的概率。

f）判斷是否滿足算法達到外循環總次數，若滿足則結束并輸出歷史最優解，若不滿足則返回步驟c）。

1.8 時間復雜度分析

首先，近鄰表作為指引近鄰算子的信息，生成其時間復雜度為 O（n²+n²j） ;其次，每個算子的時間復雜度已在之前介紹過，而組合使用移除-修復算子來更新當前解的時間復雜度最大為 O（n²+n²） ，因此，整個算法的總體時間復雜度為 O（n²） 。在表1中，本文算法與其他算法時間復雜度進行了比較。

2實驗分析及結果對比

算法測試環境為：Windows11操作系統， Intel^°ledast Core^TMi7 12700CPU處理器，Python3.7編程語言，VisualStudioCodeversion1.83開發環境。參數設置如下： M=150，u=0. 1，δ₀= 0.2，非近鄰移除算子三種情況的移除概率 P₁，P₂，P₃ 依次為0.5，0.7，0.9 。因為移除城市的數量上限參數 ξ_l 與近鄰參數 j 會隨著算例城市數量的增加而變化，其設置如表2所示。

a）實驗1：采用控制變量方法對經典的算例進行測試并對比，以驗證設計的近鄰移除與非近鄰移除算子的有效性。

b）實驗2：對自適應概率調控策略中的參數 λ 靈敏度進行

分析，找到合適的取值范圍。

c）實驗3：對接受準則中的參數 Ψ_a 進行靈敏度分析，找到合適的取值區間，并與其他接受準則進行對比實驗。

d）實驗4：將算法中改進的RRT接受準則與Metropolis準則和其他文獻中改進RRT準則進行測試對比，驗證其在求解精度上的優勢。

e）實驗5：為了全面地測試改進ALNS的性能，選取了24個不同規模的算例進行測試。

f實驗6：將本文算法與典型元啟發式算法和其他新型元啟發式算法的求解結果進行對比，驗證算法的性能。

2.1 實驗1

采用標準TSPLIB數據庫的三個算例進行測試，將傳統移除算子加入近鄰移除與非近鄰移除兩種新的移除算子前后算法性能進行對比，對最優值、平均值、最差值和標準差進行分析，每個算子的實驗獨立運行20次，運行結果如表3所示。

根據表3的結果，加人近鄰移除算子后，算法的最優值和平均值均優于未加入情況，且隨著問題規模的增大，這種優勢更加明顯。圖6展示了在求解Rat783算例時，五種移除算子的被選擇概率變化，橫坐標表示迭代次數。由于ALNS中自適應概率調控策略可以根據算子當前的表現，增加效果較好的算子被選擇使用的概率，進而提升求解效率，p4（近鄰移除算子）概率幾乎全程優于其他算子，說明其對算法性能的提升更為有效。圖7對比了加入近鄰移除算子前后算法的收斂過程，結果顯示加入后（line1）的收斂速度和求解精度都明顯優于未加人前（line2）。這表明本文設計的兩種移除算子有效地豐富了算法的鄰域結構，提升了算法的求解精度和收斂效率。

2.2 實驗2

以公差為0.1從0.1＼～0.9中取9個不同的參數 λ ，并選取了標準TSPLIB數據庫的三個經典算例各進行20次實驗，對最優解和平均解進行記錄，各算例實驗結果如圖8所示。當參數入的取值在0.3附近時算法結果的平均解（黑色曲線）最優，隨著參數 λ 的取值遠離0.3，算法性能越來越差；但最優解（如圖紅色曲線）的變化卻呈現波動的變化，參數入的取值在0.3附近時最優解相對較好，說明將參數 λ 的取值設置為0.3附近有利于提高算法求解的穩定性與精度（見電子版）。

圖9、10是自適應概率調控策略參數 λ 的取值設置為0.3時，求解A280算例時五種移除算子和兩種修復算子概率變化圖。其中：圖9中曲線依次分別表示隨機移除、路徑移除、最壞邊移除、近鄰移除、隨機近鄰移除五種算子概率變化曲線；圖10中曲線依次分別表示貪婪修復和貪婪噪聲修復兩種算子的概率變化曲線;圖11是各個移除/修復算子等概率混合使用和自適應概率調控策略最優解的收斂對比，說明了參數入取值合理的自適應概率調控策略對算法求解的精度具有提升效果，因此后續實驗均設置為0.3。

2.3 實驗3

參考文獻[21]將 δ₀ 參數取值設置為0.2。為了更好地觀察接受準則中參數 a 的靈敏度，以便更好地平衡算法的求解精度和算法求解所需時間，對從 0.94～0.99 的6組不同參數 Ψ_a 進行實驗，在其它參數都相同的情況下以St70、A280和Att532算例為例，每個測試算例都獨立運行20次，結果如表4所示，可以看出當 Φ_a 的取值在[0.96，0.98]時算法求解的效果較好。

表4不同參數 a 衰減方式求解TSP算例

為了驗證本文改進接受準則對性能的提升效果，選取了算例A280，參數設置為 δ₀=0.2，a=0.96 ，將改進后的RRT接受準則與文獻[17，18]進行對比，每個接受準則獨立運行20次，實驗結果如表5所示。可以看出，本文的接受準則策略求解效果明顯優于其余兩者。圖12展示了三種不同的RRT接受準則在求解A280算例時全局最優解的變化對比。從圖中可以看出，如果使用傳統的RRT算法（曲線bestvalue1）且參數δ固定為0.1，算法收斂效果較差。而文獻[18]采用線性降低參數δ的方式（曲線bestvalue2），相比傳統RRT算法有所提升，但前期收斂速度較慢。本文則采用等比方式對參數δ進行衰減（曲線bestvalue3），進一步提高了求解效果，在保證收斂速度的同時增強了算法全局尋優的能力。

2.4實驗4

將文獻[6，13，25]中的溫控機制結合Metropolis接受準則與RRT接受準則進行對比，算例規模從225到783。所有算法均運行相同的迭代次數（150），每個算法在四個不同規模測試算例中獨立運行20次，結果如表6所示。結果表明，在這四個經典算例中，改進的ALNS在求解精度和穩定性方面均優于其他算法。這表明RRT接受準則在解決TSP時同樣具有優勢。圖13是四種不同接受準則求解TSP算例過程中適應度變化的對比。其中：line1代表文獻[25]中的收斂曲線；line2代表文獻[6]的收斂曲線；line3代表文獻[13]的收斂曲線；而line4則代表本文算法的收斂曲線。通過比較這些收斂曲線可以觀察到，由于ALNS算法的擾動算子具有明確的指向性，所以在算法的早期階段四種算法都能迅速收斂到一個較優的值。然而，在算法的中后期，與傳統的Metropolis接受準則相比，RRT接受準則對最優解附近的滿足條件的較優解采取完全接受的策略，從而能夠在每個歷史最優解的鄰近區域探索更多有潛力的解空間。通過放大并對比算法后期的收斂曲線可以發現：即便在收斂階段末期，RRT接受準則依舊具備跳出局部最優的能力。這一現象表明，改進后的RRT接受準則能夠使算法在前期迅速收斂到一個較優解附近，并在后期有效避免陷入局部最優中展現出更強的性能。

2.5 實驗5

選用24個不同城市規模的算例，每個算例獨立運行20次以確保可靠性。記錄每次運行的最優值、平均值、平均偏差率和最優偏差率及求解時間。其中最優偏差率和平均偏差率的計算公式如式（4）所示，PDA為平均值偏差率，average為實驗得出的平均路徑長度，optimal為TSPLIB數據集中已知的最優解，PDB為最優值偏差率，best為實驗中求得的最優路徑長度。部分實驗結果如表7所示。

表7改進自適應大鄰域搜索算法求解TSP算例的結果

表7可以看出：改進后算法在求解小規模的TSP時，可以很快地收斂到最優解；而在求解中大規模的TSP時，也可以在可以接受的時間內收斂到滿意解。如圖14、15，在532和280個城市的算例中，本文算法找到了算例已知最優解的路徑圖。此外，研究還嘗試將該算法應用于超過 11 000 個城市的案例，并在可接受的時間內取得了較好的效果。這表明，經過改進后的算法不僅性能有所提升，而且具備解決大規模問題的能力。

2.6實驗6

將本文算法與改進模擬退火算法（SA）[6]、改進蟻群算法（CDMACA）[23]黑猩猩優化算法（DChOA）[12]、集群模擬退火（DCAP）[26]、離散人工蜂群算法（DABC-FNS）[24]、科莫多算法（KMA）[27]、蟻群麻雀算法（ISSACO）[28]進行對比，結果如表8所示（每個算例中最優的數據均加粗表示）。結果表明，改進算法在處理不同規模的TSP問題時均能接近最優解，且其偏差最小。在A280、Eil51、St70和Berlin52這四個算例上，算法成功找到了最優解，充分展示了其強大的求解精度。從平均值來看，在部分小規模算例中，算法的數據略高于其他算法，表明蟻群算法在小規模問題上具有較好的穩定性。然而，在大規模算例中，改進ALNS明顯優于其他算法，顯示出其在解決大規模TSP問題上的潛在優勢。

3結束語

針對ALNS求解大規模TSP時存在的不足，提出了一種改進的ALNS。其中，基于最近鄰信息設計了兩種具有指向性的移除算子，增強了算法的求解精度，提高了算法的求解效率；為了減少算法的調參難度，將改進RRT接受準則與ALNS結合，保證了算法求解精度的同時提升了算法的通用性。盡管本文算法的參數已通過靈敏度分析實驗得到確定，且其性能在調試過程中展現出了一定程度的穩定性，但無法確保當前參數配置為最優解。未來研究將聚焦將本文算法拓展應用于TSP的變體及其他類型的組合優化問題，旨在探索其更廣泛的應用潛力與效率提升的可能性。

參考文獻：

[1]IngberL.Very fast simulated re-annealing[J].Mathematical and ComputerModelling，1989，12（8）：967-973.

[2]吳慶洪，張紀會，徐心和．具有變異特征的蟻群算法［J]．計算 機研究與發展，1999，36（10）：1240-1245．（Wu Qinghong， Zhang Jihui，Xu Xinhe.An ant colony algorithm with mutation features[J].Journal of Computer Research and Development， 1999，36（10）：1240-1245.）

[3]Tsai CF，Tsai CW，Yang T.Amodified multiple-searching method to genetic algorithms for solving traveling salesman problem[C]// Proc of IEEE International Conference on Systems，Man and Cybernetics.Piscataway，NJ：IEEE Press，2OO2：1-6.

[4]OuaarabA，AhiodB，YangXinshe.Discrete cuckoo search algorithm for the travelling salesman problem[J].Neural Computing and Applications，2014，24（7）：1659-1669.

[5］高海昌，馮博琴，朱利．智能優化算法求解 TSP問題［J]．控制 與決策，2006，21（3）：241-247，252.（Gao Haichang，Feng Boqin，Zhu Li.Reviews of the meta-heuristic algorithms for TSP[J]. Control and Decision，2006，21（3）：241-247，252.）

[6］陳晟宗，張紀會，于守水，等．求解旅行商問題的波動溫控模擬 退火算法[J]．控制與決策，2023，38（4）：911-920.（Chen Shengzong，Zhang Jihui，Yu Shoushui，et al.A simulated annealing algorithmwith wave temperature control for the traveling salesman problem[J].Control and Decision，2023，38（4）：911-920.）

[7］陳科勝，鮮思東，郭鵬．求解旅行商問題的自適應升溫模擬退火 算法［J].控制理論與應用，2021，38（2）：245-254.（Chen Kesheng，Xian Sidong，Guo Peng.Adaptive temperature rising simulatedannealing algorithm for traveling salesman problem[J].Control Theoryamp; Applications，2021，38（2）：245-254.）

[8]Wei Lijun，Zhang Zhenzhen，Zhang Defu，et al.A simulated annealing algorithm for the capacitated vehicle routing problem with twodimensional loading constraints[J].European Journal of Operational Research，2018，265（3）：843-859.

[9］王育潔，游曉明，劉升．結合評估獎懲機制和鄰域動態退化的協 同蟻群算法［J]．系統仿真學報，2024，36（6）：1475-1492. （Wang Yujie，You Xiaoming，Liu Sheng. Cooperative ant colony algorithm combining evaluation reward and punishment mechanism and neighborhood dynamic degradation[J]. Journal of System Simulation，2024，36（6）：1475-1492.）

[10]Huang Zhibin， Chen Yiming，Huang Tianliang. A paralel social spideralgorithm based on population mining[J].Applied Soft Computing，2024，166：112136.

[11］陳加俊，譚代倫．求解旅行商問題的探索—開發—跳躍策略單親 遺傳算法［J]．計算機應用研究，2023，40（5）：1375-1380. （ChenJiajun，Tan Dailun.Partheno-genetic algorithm basedon explore-develop-jump strategy for solving traveling salesmanproblem [J].Application Research of Computers，2023，40（5）：1375- 1380.）

[12]沈孝凱，張紀會，郭乙運，等．基于近鄰牽引算子的離散黑猩猩 優化算法[J]．控制與決策，2024，39（4）：1133-1141.（Shen Xiaokai，Zhang Jihui，Guo Yiyun，et al.Discrete chimp optimization algorithm based on neighbour traction operator[J]. Control and Decision，2024，39（4）：1133-1141.）

[13]Pisinger D，Ropke S.A general heuristic for vehicle routing problems [J].Computersamp; OperationsResearch，2007，34（8）：2403- 2435.

[14］陸永亮，吳慶華，李建斌，等．自適應大鄰域搜索求解著色旅行 商問題[J]．運籌與管理，2024，33（7）：57-64.（Lu Yongliang， Wu Qinghua，Li Jianbin，et al.Adaptive large neighborhood search for the colored traveling salesmen problem [J]. Operations Research and Management Science，2024，33（7）：57-64.）

[15]Windras Mara S T，Norcahyo R， Jodiawan P，et al.A survey of adaptive large neighborhood search algorithms and applications[J]. Computersamp;Operations Research，2022，146：105903.

[16] Santini A，Ropke S，Hvattum L M.A comparison of acceptance criteria for the adaptive large neighbourhood search metaheuristic[J]. Journal of Heuristics，2018，24（5）： 783-815.

[17]Lei Hongtao，LaporteG，Liu Yajie，et al.Dynamic design of sales territories[J].Computers amp; Operations Research，2015，56： 84-92.

[18]Hemmati A，Hvattum L M.Evaluating the importance of randomization in adaptive large neighborhood search[J].International Trans in Operational Research，2017，24（5） ： 929-942.

[19］王宇平，李英華．求解 TSP的量子遺傳算法［J]．計算機學報， 2007，30（5）：5748-5755.（WangYuping，Li Yinghua.Anovel quantum genetic algorithm for TSP[J]. Chinese Journal of Computers，2007，30（5）：5748-5755.）

[20]Turkeamp; R， Sorensen K，Hvattum L M. Meta-analysis of metaheuristics：quantifying the effect of adaptiveness in adaptive large neighborhood search [J]. European Journal of Operational Research， 2021，292（2）： 423-442.

[21]Dueck G. New optimization heuristics the great deluge algorithm and the record-to-record travel[J].Journal of Computational Physics，1993，104（1）：86-92.

[22] Zhao Lei，Bi Xinhua，Li Gendao，et al.Robust traveling salesman problem with multiple drones：parcel delivery under uncertain navigation environments[J].Transportation Research Part E：Logistics and Transportation Review，2022，168：102967.

[23]Wu Lisheng，You Xiaoming，Liu Sheng.Multi-ant colony algorithm based on cooperative game and dynamic path tracking [J]. Computer Networks，2023，237：110077.

[24]Li Xing， Zhang Shaoping，Shao Peng.Discrete artificial be colony algorithm with fixed neighborhood search for traveling salesman problem[J]．Engineering Applications of Artificial Intelligence， 2024，131：107816.

[25］張子成，韓偉，毛波．基于模擬退火的自適應離散型布谷鳥算法 求解旅行商問題[J]．電子學報，2018，46（8）：1849-1857. （Zhang Zicheng，Han Wei，Mao Bo. Adaptive discrete cuckoo algorithmbased on simulated annealing for solving TSP[J].Acta Electronica Sinica，2018，46（8）：1849-1857.）

[26]Huang Zhanhong，Zhang Yang，Wang Xiangrui，et al.DCAP：a scalable decoupled-clustering annealing processor for large-scale traveling salesman problems [J]. IEEE Trans on Circuits and Systems I：Regular Papers，2024，71（12）： 6349-6362.

[27]Jati GK，Kuwanto G，Hashmi T，etal.Discrete Komodo algorithm for traveling salesman problem[J]. Applied Soft Computing， 2023，139：110219.

[28]Tian Yangyang，Zhang Jiaxiang，Wang Qi，et al.Aplication of hybrid algorithm based on ant colony optimization and sparrow search in UAV path planning[J]. International Journal of Computational Intelliaence Svstems.2024.1771）：286.