非完全圖TSP問題研究

張家善

摘要：指出了TSP問題是一種具有代表性的組合優化問題，在現實生活中有著廣泛的應用。不同于完全圖，非完全圖TSP問題中存在著某些節點之間沒有路徑直接相連，使得處于該節點位置時，其路徑選擇受到一定限制。受運籌學中大M法思想的啟發，提出了通過引入一個非常大的正數（即大M）來表示此類節點間的距離，從而將非完全圖TSP問題轉化成完全圖TSP問題，降低了問題求解的難度，并且驗證了該方法的有效性。

關鍵詞：TSP問題；非完全圖；大M法；仿真

中圖分類號：F57

文獻標識碼：A 文章編號：1674-9944（2016）05-0182-02

1 引言

旅行商問題（Traveling Salesman Problem，TSP），又稱貨郎擔問題或旅行推銷員問題，最早由美國的Rand公司提出。問題可簡單描述為： 設有n個城市（節點），若從某城市（節點）出發，遍歷各城市（節點）一次后返回原出發點，要求找出一條路線，使總路徑最短[1]。TSP問題的圖論描述為：設圖G=（V，E）， V代表頂點集，E代表由不同頂點組成的邊集，已知道各邊的長度dij，要找出一個Hamilton回路，使它的距離最短。現實生活中有很多問題可以歸結為旅行商問題，比如郵路問題、連鎖店的貨物配送路線問題、裝配線上的螺帽問題和產品的生產安排問題等[2]，其研究具有重要的理論意義和應用價值。

通過中國知網檢索發現，國內外學者就TSP問題進行了相關研究：Pintea等人[3]將蟻群優化算法應用于解決旅行商問題；李勇采用動態蟻群算法研究了TSP問題[4]；李如琦提出用MAX_MIN螞蟻算法解決中國旅行商問題[5]；國圓媛應用蟻群算法解決了浙江旅行商問題的最短路徑[6]；潘慶祥建立了有向圖TSP模型，并設計了算法進行求解[7]。

2 TSP問題分類

按照TSP路徑關系的不同特征，通常有以下兩種基本分類。

（1）根據任意兩個城市（節點）之間是否均存在路徑（邊）相連接，可分為完全圖TSP問題 與非完全圖問題。完全圖是指一個圖的每一對不同頂點恰有一條邊相連，基于完全圖的旅行商問題即為完全圖TSP問題；非完全圖是指存在兩個頂點之間沒有邊相連接，即n個端點的連接邊數少于n（n-1）/2條邊，基于非完全圖的旅行商問題 即為非完全圖TSP問題。

（2）根據任意兩個城市之間來回路徑均是否相等，可分為無向圖TSP問題和有向圖TSP問題。所謂無向圖，是指一個圖中的每條邊都沒有方向，往返的費用值相等，即dij=dji；所謂有向圖，是指一個圖中的每條邊有方向，往返的費用值不等，即dij≠dji

上述研究多是針對完全圖TSP問題，而完全圖是一種簡單圖，任何兩個頂點之間均有線路連接，處于當前節點時，可以選擇任意節點作為待訪問的后續節點，問題求解相對容易。但是，針對非完全圖的研究較少。

3 非完全圖TSP問題的數學模型

與完全圖TSP問題不同， 非完全圖TSP問題中存在城市之間沒有路徑連接，需要對問題進行轉換處理。一種設想是尋找一條經過第三個城市的最短路來間接地表示兩個城市之間的路徑關系[8]，即令

上式中，n為集合中所含圖的頂點數。約束（1）和（2）意味著對每個點而言，僅有一條邊進和一條邊出；約束（3）則保證了沒有任何子回路解的產生。于是，滿足約束（1）、（2）和（3）的解構成了一條Hamilton回路。

4 實例驗證

選取oliver30問題作為研究對象（節點坐標如表1所示），隨機選取節點17與20，22與26，28與4三對節點，設置其間沒有邊連接，將其改造成非完全圖TSP問題，如表1所示。根據前文所述，設置節點對17與20，22與26，28與4之間的距離d17.20，d22.26，d4.2S為M，考慮本例節點間距，取M=10000。

采用蟻群算法在計算機上仿真計算，得到最優路徑如圖1所示。

在非完全圖TSP問題中，搜索TSP路線的次數應等于或者少于完全圖TSP問題，所得到的TSP路線方案總數也應少于完全圖TSP情形。本例中，由于節點17與20沒有路徑直接相連接（可認為距離值非常大），如圖中虛線所示，只能途徑18，19號節點再到達20號節點。同樣，節點22與26，28與4之間，只能途徑其他節點繞道抵達。仿真計算得到最短路徑為：

20→ 21→22→23→25→24→26→27→28→29→30→ 2→ 1→ 3→ 4→ 5→ 6→ 7→ 8→ 9→10→11→12→13→14→15→16→17→18→19。

對應的路徑距離值：423.7406。

5 結語

非完全圖TSP問題中存在著某些城市（節點）之間沒有路徑直接相連，使得處于該節點位置時，其路徑選擇受到一定限制，這給問題的解決帶來了一些困難。受到運籌學中大M法思想的啟發，通過引入一個非常大的正數（即大M）來表示這些節點間的距離，從而將非完全圖TSP問題轉化成完全圖TSP問題，降低了問題求解的難度，使其變成規范化的、易于求解的TSP問題。需要指出的是，本文提出的這種將非完全圖TSP問題轉化成完全圖TSP問題的轉化思想，同樣適用于其他非標準TSP問題。

參考文獻：

[1]余詳宣，崔國華.計算機算法基礎[M] .武漢：華中科技大學，1998.

[2]李會玲.基于模擬退火的遺傳優化算法在TSP問題中的應用[J].熱處理技術與裝備，2007，28（6）：51～55.

[3]Pintea C M，Pop P C，Dumitrescu D.An ant-based technique for the dynamic generalized traveling salesman problem[C].Proceedings of the 7th WSEAS International Conference on Systems Theory and Scientific Computation，2007：257～261

[4]李 男，段正澄.動態蟻群算法求解TSP問題[J].計算機工程與應用，2003，39（17）：104～107.

[5]李如琦，蘇媛媛.用MAX_MIN螞蟻算法解決中國旅行商問題[J].湖南工業大學學報，2007（5）

[6]國圓媛，許延鑫，吳 江.浙江旅行商問題研究[J].中國新技術新產品，2009（22）：147～149.

[7]潘慶祥，徐自然.具有重復路徑的有向TSP問題[J].才智，2014（17）：103～106.

[8]徐心和.旅行商問題的一種新解法[J].東北工學院學報，1990，1（1）：68～74.