基于大鄰域搜索的旅行商問題求解

Abstract：Asaclasscal problem incombinatorial optimization，TravellingSalesman Problem（TSP）hasa widerangeof practicalapplications inlogistics，path planningandother fields.Traditional exactsolving methods facethechallngeof computational ineficiency when dealing with large-scale problems，while heuristic algorithms have become the mainstream methodsforsolving TSPproblemsdue totheirflexibilityandeficiency.Inthis paper，aTSPsolving method basedonLarge NeighborhoodSearch（LNS）isadopted，which iterativelyoptimizes thesolutionthrough destructionandrepairoperators to balance he breadth and depth of the search.Experiments are carriedoutbased on several standard instances inthe TSPLib database，andtheresultsshowthattheproposed method exhibitsexcelentsolutionperformanceondatasetsofdiferentsizes and distributional characteristics，and is able to quickly converge to high-quality solutions.

Key words：Traveling Salesman Problem;Large Neighborhood Search;destructionoperator;repairoperator;combinatorial optimization

旅行商問題（TravellingSalesmanProblem，簡稱TSP）是組合優(yōu)化問題中一類經(jīng)典的NP完備問題，具有較高搜索空間和復雜度。它的理論全搜索復雜度為O（n?。?。經(jīng)典的旅商問題描述為：一位旅行商從起始城市出發(fā)，訪問每個城市有且僅一次，最終回到起始城市，同時使得經(jīng)過的總路程最小。盡管旅行商問題的規(guī)則簡單，但在處理大規(guī)模問題時變得異常復雜。舉例來說，考慮到50個城市的情況，如果要枚舉所有可能路徑以確定最佳行程，路徑數(shù)量將變得極其龐大且不易計算。旅行商問題在實際應用中具有重要意義，它可以模擬諸如銷售員派送貨物、旅游路線規(guī)劃、電路板設計、郵件分發(fā)等各種實際場景，對于提高資源利用率、降低成本、提升效率具有重要意義。因此，有效地解決該問題不僅能優(yōu)化物流配送路線，減少行駛距離和時間成本，還能改善城市交通擁堵情況，提高交通運輸效率。

旅行商問題自提出以來，一直是組合優(yōu)化領域的研究熱點。早期的研究主要集中在精確算法上，如精確方法主要包括動態(tài)規(guī)劃算法[1]（DynamicProgramming，DP）、分支限界法[2]（BranchandBound，BB）和整數(shù)線性規(guī)劃算法[3]（IntegerLin-earProgramming，ILP）。作為運籌學的一項重要分支，動態(tài)規(guī)劃算法被視為解決決策問題的最佳數(shù)學方法。動態(tài)規(guī)劃算法解決TSP的基本思想是從局部最優(yōu)解來挑選出全局最優(yōu)解。Bellman基于動態(tài)規(guī)劃思想使用Held-Karp算法，4]將求解旅行商問題的復雜度降低，但對于大規(guī)模的問題仍難以解決。上述方法皆為精確方法，當算例規(guī)模較小時，精確算法能夠在合理的時間范圍內(nèi)找到最優(yōu)解，但拓展到大規(guī)模旅行商時所需時間太長，并且會導致較大的時間復雜度。

隨著智能優(yōu)化算法的發(fā)展，各種啟發(fā)式算法和元啟發(fā)式算法被廣泛應用于TSP的求解。啟發(fā)式算法主要包括可變鄰域搜索算法[5]（Variable Neigh-borhoodSearch，VNS）、模擬退火算法[（SimulatedAnnealing，SA）、禁忌算法[7]（Tabu Search，TS）、蟻群優(yōu)化算法[8]（Ant Colony Optimization，ACO）、遺傳算法[9]（Genetic Algorithms，GA）和粒子群優(yōu)化[10]（Particle Swarm Optimization，PSO）等。Patrick K[11]首次基于模擬退火思想對組合優(yōu)化問題進行研究。胡小兵[12]等人提出了一種改進的遺傳算法，通過引入“幼代”的種群，并模擬其生長，從而提高了解的質(zhì)量。 Yu^[13] 等對蟻群優(yōu)化算法進行，對車輛路徑問題的求解結果優(yōu)于啟發(fā)式算法的解。

1大鄰域搜索算法基本架構

大鄰域搜索（LNS）是一種基于破壞和修復操作的啟發(fā)式算法，其基本思想是通過破壞當前解的部分結構并重新修復，逐步優(yōu)化解的質(zhì)量。LNS算法的核心在于破壞和修復算子的設計。破壞算子通過隨機刪除解中的部分元素，生成一個不完整的解；修復算子則通過某種策略將刪除的元素重新插入到解中，生成一個新的解。通過不斷迭代破壞和修復操作，LNS算法能夠在解空間中搜索到更優(yōu)的解。LNS算法的關鍵在于破壞和修復策略的設計。破壞策略決定了搜索空間的大小和搜索方向，而修復策略則決定了新解的質(zhì)量和搜索效率。因此，如何設計合理的破壞和修復策略是LNS算法研究的核心問題。

2 動態(tài)方程及求解

本文提出了一種基于大鄰域搜索（LNS）的TSP求解框架，其核心流程包括以下步驟：首先，通過隨機生成或啟發(fā)式方法構造初始解；其次，利用破壞算子隨機刪除部分城市節(jié)點，生成不完整解；接著，采用貪婪插入策略對刪除節(jié)點進行修復，生成新解；然后，根據(jù)接受準則判斷是否接受新解，若新解優(yōu)于當前解則接受，否則以一定概率接受；最后，通過迭代執(zhí)行破壞、修復和接受操作，直至達到預定的迭代次數(shù)或解的質(zhì)量趨于穩(wěn)定。該框架通過破壞與修復策略在全局與局部搜索之間實現(xiàn)有效平衡，顯著提升了求解效率與解的質(zhì)量。

2.1 數(shù)學模型

給定一個帶權完全無向圖 G=（V，E） ，其中V 是城市節(jié)點的集合，E是邊的集合，表示兩城市之間的連接。設 d_ij 表示城市 v_i 到城市 v_i 的距離，TSP問題的目標函數(shù)可以表示為：

式中， π 是一個排列，表示旅行商的訪問順序，且 π（n+1）=π（1） 。

2.2 破壞算子

本文提出了一種基于大鄰域搜索（LNS）的TSP求解框架，其核心流程包括以下步驟：首先，通過隨機生成或啟發(fā)式方法構造初始解；其次，利用破壞算子隨機刪除部分破壞算子通過隨機刪除解中的部分城市節(jié)點，生成一個不完整的解。設當前解為，破壞算子刪除個城市節(jié)點，生成一個新的不完整解。破壞算子的數(shù)學表達式為：

式中， 是隨機選擇的 k 個城市節(jié)點。

2.3 修復算子

修復算子通過貪婪插入策略將刪除的城市節(jié)點重新插入到解中，生成一個新的解。設當前不完整解為 π^′ ，修復算子將刪除的城市節(jié)點 重新插入到 π^′ 中，生成一個新的完整解 π^′′ 。修復算子的數(shù)學表達式為：

式中， π 是通過貪婪插入策略生成的新解。

2.4接收準則

接收準則用于決定是否接受新生成的解。如果新生成的解優(yōu)于當前解，則接受新解；否則，以一定概率接受新解。接收準則的數(shù)學表達式為：

式中， f（π） 是解 π 的目標函數(shù)值，T是溫度參數(shù)，控制接受劣解的概率。

2.5算法復雜度分析

設城市總數(shù)為 Π_n ，迭代次數(shù)為T，破壞程度為k（k為城市總數(shù)的百分比）。則算法的時間復雜度主要取決于破壞操作、修復操作和局部優(yōu)化的時間復雜度。

破壞操作：時間復雜度為 0（k） ，因為需要從當前解中隨機刪除 k 個城市。

修復操作：時間復雜度為 O（n²k） ，因為對于每個未訪問的城市，需要計算將其插入路徑中每個可能位置后的路徑長度增加量，并選擇路徑長度增加量最小的位置進行插入。

局部優(yōu)化：時間復雜度為 O（n²） 或 O（n³） ，取決于使用的局部優(yōu)化方法（如2-opt的時間復雜度為0（n²），3-opt 的時間復雜度為 O（n³） 。

總時間復雜度：由于迭代次數(shù)為T，因此總時間復雜度為 ）或 ）。

3 實驗結果及分析

3.1實驗環(huán)境與數(shù)據(jù)集

為驗證本文提出的基于大鄰域搜索的旅行商問題（TSP）求解算法的有效性，我們在TSPLib數(shù)據(jù)庫中選取了六個具有代表性的城市實例進行實驗。實驗在Python3.8環(huán)境下進行，利用NumPy庫進行數(shù)值計算，并通過Matplotlib庫實現(xiàn)結果的可視化展示。算法參數(shù)設置如下：迭代次數(shù) T=300 ，破壞程度 k=20% ，局部優(yōu)化方法采用2-opt算法。

3.2 評價指標

算法求得的最優(yōu)值。這個指標可以觀察算法的全局搜索性能，該值越小，算法的全局搜索能力越強。

誤差率（Er）。誤差率的計算如下式：

其中，OpS是算法求得的最優(yōu)解，KOpS是該TSP實例已知最優(yōu)解。誤差率越小說明算法越接近已知最優(yōu)解，尋優(yōu)精度越高。

3.3 實驗結果

本文基于大鄰域搜索的旅行商問題求解算法在多個TSPLib標準數(shù)據(jù)集上進行了實驗驗證，實驗結果如表1所示。從表中可以看出，算法在不同規(guī)模、不同分布特性的數(shù)據(jù)集上均表現(xiàn)出較好的性能。

具體而言，在berlin52實例中，算法求得的最優(yōu)解與官方最優(yōu)解完全一致，偏差率為 0.0% ，表明算法在中等規(guī)模、聚類分布的城市數(shù)據(jù)集上具有極高的求解精度。在 pr76 實例中，算法求得的最優(yōu)解為107470，優(yōu)于官方最優(yōu)解108159，偏差率為-0.64% ，進一步驗證了算法在特定分布類型上的優(yōu)越性。對于大規(guī)模數(shù)據(jù)集，如 a280 和 tsp225 ，算法的偏差率分別為 1.78% 和 0.17% ，表明算法在大規(guī)模、復雜分布的城市數(shù)據(jù)集上仍能保持較高的求解精度。

圖1展示了六個不同TSPLib實例的最優(yōu)路徑可視化結果。每個子圖展示了一個TSP實例的路徑，其中每個節(jié)點通過線條依次連接，形成一個閉合路徑。每個子圖都有橫軸和縱軸代表路徑坐標位置的坐標軸。從圖中可以看出，不同TSPLib實例的路徑規(guī)劃特征反映了城市分布與問題復雜性的差異。大規(guī)模實例（如“ a280^?? ）路徑曲折纏繞，表明跨區(qū)域移動頻繁；中等規(guī)模實例（如“berlin52\"）路徑簡潔規(guī)整，體現(xiàn)聚類分布的高效性；而無規(guī)律分布實例（如\"eil101\"）路徑凌亂，凸顯路線選擇的復雜性?？傮w而言，可視化結果直觀展示了路徑規(guī)劃的多樣性及算法對不同分布特性的適應性。TSPLib實例最優(yōu)解隨迭代次數(shù)的收斂曲線（圖2）直觀展示了算法在全局尋優(yōu)和局部優(yōu)化之間的有效平衡。

4結論

本文提出的基于大鄰域搜索的旅行商問題求解算法，通過破壞和修復策略在解空間中進行大規(guī)模搜索，顯著提升了全局尋優(yōu)能力。實驗結果表明，該算法在TSPLib數(shù)據(jù)庫中的多個城市規(guī)模問題上均表現(xiàn)出較強的魯棒性，能夠穩(wěn)定找到接近官方最優(yōu)解的高質(zhì)量解。特別是在中等規(guī)模問題上，算法的求解精度和收斂速度均達到了較高水平。

參考文獻：

[1]Bertsekas D. Dynamic programming and optimal control：Volume I[M].Athena scientific，2012.

[2]He H，Daume III H，Eisner J M. Learning to search in branch and bound algorithms[J].Advances inneural information processing systems，2014 ：27.

[3]Aycock J. Strung Out：Printable Strings in Atari 26OO Games [J].University of Calgary，TechnicalReport，2014，2014- 1062-13.

[4] Karp HR M.A Dynamic Programming Approach to Sequencing Problems[J]. Journal of the Societyfor Industrial amp; Applied Mathematics，1962，10（1） ：196-210.

[5]ZhangG H，Zhang L J，Song X H，et al.A variable neighborhood search based genetic algorithm forflexible job shop scheduling problem[J]. Cluster Computing，2019，22（5）： 11561-11572.

[6]Lin Y，Bian Z，Liu x. Developing a dynamic neighborhood structure for an adaptive hybrid simulatedannealing-tabu search algorithm to solve the symmetrical traveling salesman problem[J].Applied SoftComputing，2016（49）：937-952.

[7]Basu S.Tabu search implementation on traveling salesman problem and itsvariations：a literaturesurvey[J].American Journal of Operations Research，2012，2（2）：163-173.

[8]Deng W，Xu J J，Zhao H M.An improved ant colony optimization algorithm based on hybridstrategies for scheduling problem[J].IEEE Access，2019（7） ：20281-20292.

[9]Lin B，Sun X Y，Salous S.Solving travelling salesman problem with animproved hybrid geneticalgorithm[J]. Journal of Computer and Communications，2016，4（15） ：98-106.

[10] Zhong Y W，Lin J，Wang L J，et al. Discrete comprehensive learning particle swarm optimizationalgorithm with Metropolis acceptance criterion for traveling salesman problem[ J]. Swarm andEvolutionary Computation，2018（42） ：77-88.

[11]Kirkpatrick S，Gelatt C D，Vecchi M P. Optimization by simulated annealing[J].science，1983，220（4598）： 671-680.

[12]胡小兵，吳樹范.TSP的一種改進遺傳算法［J].計算技 術與自動化，2000（4）：34-38.

[13]Yu B，Yang Z Z. An ant colony optimization model：The period vehicle routing problem with timewindows[J].Transportation Research Part E：Logistics and Transportation Review，2011，47（2） ：166-181.

（責任編輯 陳潤梅）