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

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

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

隨著智能優(yōu)化算法的發(fā)展，各種啟發(fā)式算法和元啟發(fā)式算法被廣泛應(yīng)用于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)化問題進(jìn)行研究。胡小兵[12]等人提出了一種改進(jìn)的遺傳算法，通過引入“幼代”的種群，并模擬其生長，從而提高了解的質(zhì)量。 Yu^[13] 等對蟻群優(yōu)化算法進(jìn)行，對車輛路徑問題的求解結(jié)果優(yōu)于啟發(fā)式算法的解。

1大鄰域搜索算法基本架構(gòu)

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

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

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

2.1 數(shù)學(xué)模型

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

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

2.2 破壞算子

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

式中， 是隨機(jī)選擇的 k 個(gè)城市節(jié)點(diǎn)。

2.3 修復(fù)算子

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

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

2.4接收準(zhǔn)則

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

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

2.5算法復(fù)雜度分析

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

破壞操作：時(shí)間復(fù)雜度為 0（k） ，因?yàn)樾枰獜漠?dāng)前解中隨機(jī)刪除 k 個(gè)城市。

修復(fù)操作：時(shí)間復(fù)雜度為 O（n²k） ，因?yàn)閷τ诿總€(gè)未訪問的城市，需要計(jì)算將其插入路徑中每個(gè)可能位置后的路徑長度增加量，并選擇路徑長度增加量最小的位置進(jìn)行插入。

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

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

3 實(shí)驗(yàn)結(jié)果及分析

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

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

3.2 評價(jià)指標(biāo)

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

誤差率（Er）。誤差率的計(jì)算如下式：

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

3.3 實(shí)驗(yàn)結(jié)果

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

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

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

4結(jié)論

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

參考文獻(xiàn)：

[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ìn)遺傳算法［J].計(jì)算技 術(shù)與自動(dòng)化，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.

（責(zé)任編輯 陳潤梅）