MTSP 的改進模擬退火算法及其求解

畢少辰，石保東，劉小龍，張 蕾

（青島理工大學a.理學院；b.管理學院，山東 青島 266520）

0 引言

旅行商問題（Traveling Salesman Problem，TSP）是近代組合優化領域的一個典型難題。旅行商問題可以簡單描述為：一個旅行商遍歷城市節點集后返回原點的最優線路規劃問題。旅行商問題有重要的實際意義和工程背景，在印制電路板轉孔、衛星位置調整、電光纜布置、晶體結構分析等多領域得到應用。

受限于枚舉的計算限制，近代研究學者提出了一系列針對TSP 問題的算法方案。總體上可以分為基于已有成熟啟發式算法的改良算法和借助仿生學提出的新的啟發式算法。其中模擬退火算法是求解TSP 較為成熟的算法，具有最值結果質量高、初值魯棒性強、通用易實現等諸多優點。

模擬退火算法是現代優化算法，模擬退火算法的出現得益于材料統計力學的研究成果。在很多學者的研究中發現，粒子在高溫狀態下具有較高的能量，在緩慢降溫的過程中，粒子能量逐漸減少，粒子的狀態趨于穩定。模擬退火算法是基于物理學中固體物質的退火過程與一般優化問題的相似性，通過逐步迭代使中間解逐步向最優解收斂。基于模擬退火算法在求解旅行商問題上的優勢，研究并優化一般模擬退火算法以求解多旅行商問題有很大的應用價值。

優化問題可以轉化為目標函數的極值問題，對于多目標的優化問題，多目標優化時存在各優化目標之間的制約關系，在模擬退火改進過程中，優化一項目標會使另一項目標偏離。需要對優化的各個目標設置權重，協調各目標的影響程度。在實際問題中，考慮各種資源平衡的情況下，模擬退火算法使用起來往往得不到預期的最優規劃。

多旅行商問題（MTSP）是經典旅行商問題的推廣。在現實應用的過程中，多旅行商問題的影響因素往往更加復雜，單純考慮運行路徑的總長度會導致路徑之間極不均衡。結合模擬退火算法在求解旅行商問題上的優勢，本文通過改進模擬退火算法，在算法中引入綜合目標函數，對總運行路徑和其他影響因素進行綜合評價。改進模擬退火算法，可以綜合衡量多個因素對最終結果的影響程度。

1 模擬退火算法簡介與改進

1.1 綜合目標函數改進模擬退火算法

為解決路徑長度與子路徑均衡程度相沖突的問題，文章引入綜合目標函數：

公式（1）（2）中，Z 為綜合目標函數，用于綜合衡量路徑優劣程度，S 為路徑總長度，J 為子路徑的均衡度。a、b 分別為總路徑與均衡度的權重系數。

總路徑長度S 為：

L為第i 段子路徑的長度。

期望反映變量的平均取值的大小，偏差與方差均是衡量源數據與期望的離散程度的度量值。應用統計學中標準方差的表示形式，均衡度可通過式（4）進行衡量：

為了統一量綱和簡化計算，將均衡度J 定義為：

1.2 改進模擬退火算法流程

（1）給定初始溫度T、降溫系數α、終止溫度T并通過固定關鍵節點插值法與蒙特卡洛算法給定較優初始解。

（2）根據關鍵節點劃分子路徑，計算各子路徑長度L與各子路徑均衡程度J。

（4）進行2 變換、3 變換（交換解序列中任意2 或3個節點的位置），得到新解。

（6）在同一溫度下進行多次內循環，求得該溫度下的較優解。

（7）按降溫系數T-α·T 退火，當T=T時停止迭代。

2 數值算例

無線傳感器網絡（Wireless Sensor Network，WSN）在生活中被廣泛應用。無線傳感網絡，需要傳感器、數據中心和移動充電器三部分相互協同進行運作。高效的路由算法能有效降低網絡能量消耗，延長網絡壽命。為保證傳感器有足夠電量來正常工作，數據中心需要按時用充電器為傳感器充電。傳感器和數據中心分布在同一個二維平面內，數據中心與任意一個傳感器、任意傳感器之間都相互連通。數據中心和傳感器的位置可以通過水準測量以坐標的形式確定，也可基于自身定位設備確定。

傳感器電量消耗由充電器消耗和運行路程上的損耗兩部分組成，為減少能量損失，需要規劃移動充電器在傳感器之間的最短運行路線。為提高充電工作的效率，網絡中有四臺移動充電器為傳感器充電。求四臺充電器運行的最佳運行路線。

在原有路徑中設置D、D、D三個插入點作為充電器的出發點，得到距離矩陣。

單純以總路程最短為要求，求最優解，就會導致4個傳感器運行的線路極為不均衡。總路程最短情況下的不均衡運行線路見圖1。

如圖1 所示，總路程最短不一定能使各個充電器任務均衡。在4 個充電器總運行距離最短的情況下，求解出的不均衡的分布線路，雖然滿足充電器總能量損失最小，但總的時間周期加長，使體系的總體充電效率變低。

圖1 總路程最短變情況下的不均衡運行線路圖

總路徑長度S 為：

由于隨機的位置交換，可能改變插入節點的位置。所以在新路徑中，以插入的新節點出現的前后順序劃分四段子路徑，將四段子路徑的距離依次標記為L、L、L、L。

新得到的路徑的四段子路徑形成的距離矩陣表示為MaxL=（L，L，L，L）。

進行多次降溫模擬，得到權重系數為1∶1 情況下，綜合目標函數最小情況下的運行路徑，如圖2 所示。

圖2 4 個充電器運行路徑示意圖

4 個充電器的運行路徑長度分別為：

3 514.04 0 693 829 77 米、3 456.1 59 670 828 92米、3 780.35 8 008 895 60 米、3 488.70 6 674 434 52 米。

此時的總路徑長度為14 239 米。

最優解時綜合目標函數值Z＝14.68。

總路程極短（路徑長度系數a 遠大于均衡度系數b）情況下，運行路徑的總長度為12.833 2 千米。由前文分析得出，在一條路徑下運行距離最短，最短距離為11.483 2 千米。12.833 2 千米非常趨近于最優解。

在總路徑均衡（路徑長度系數a 遠低于均衡度系數b）的情況下，四段子路程的距離分別為3.666 5 千米、3.529 2 千米、3.727 8 千米、3.712 2 千米。這里使用統計學中標準方差的表現形式，體現四段子路徑對于均值的離散程度。

四段子路徑的均衡度為d（X）=0.078 211 168，趨近零值，即四段子線路的長度非常接近。

實際應用中，可根據具體問題對“路徑總長度”和“子路徑均衡度”的不同需求，為兩者選定不同的權重系數，從而求取相應條件下的最優解。

3 結論

本文改進的模擬退火算法，將多旅行商問題中的總路徑長度與子路徑均衡度同時參與迭代。綜合目標函數Z，可以根據對“路徑”和“均衡度”的重視程度設置權重。在求解路徑長度和子路徑的均衡度問題上，很容易通過系數的變化來掌控。通過這種方法可以求解多旅行商問題中“路徑盡可能短”“路徑盡可能均衡”以及“在盡可能均衡的條件下求最短”等類似問題。

例如：如果需要使總路徑盡可能短，即可增加路徑權重，降低均衡度權重。

同時保留了模擬退火算法在求解經典旅行商問題時其固有的全局尋優能力。最終求解方案的子路徑均衡，每個旅行商運行完各自路徑的時間相對接近，其綜合效率較高；改進后的模擬退火算法在求解時間和求解精度上都有較好的表現。