基于球面距離的旅行商問題及其應用

吳皓華，曹 茜 （上海電力大學，上海 200090）

旅行商問題（Traveling Salesman Problem，TSP）可以概括為：無論是在平面還是在空間內，如何一次性用最短的路徑走完所有節點，并從最末點回到出發點，同時所走的路徑中只存在一個循環，不含任何子循環。

旅行商問題雖然是一個基礎性問題，但是其對于問題處理的思維方式在其他問題的研究中也有重要的借鑒意義。而且基于其在工業和科學技術方面的重要應用，直到現在TSP及其衍生問題都始終被作為熱門的研究對象。同時TSP作為公認的NP完全問題，其解法和答案的多樣性說明了這個問題有待開發的巨大潛力。

1 旅行商問題

旅行商問題（TSP）的發展從未停止過，針對這個問題的傳統解決思路是通過有限次的數學迭代計算來得出一個相對可行解。隨著計算機技術的發展以及各種學科之間的交互加深，新的算法和對原算法的改進也就隨之產生了。比如由戚遠航和蔡延光等[1]提出的將初始化步驟混沌化從而可以得出小范圍數據內的精確解和大范圍數據內的優化近似解的混沌混合離散蝙蝠算法，以及Hui Yang、Li-shan Kang和Yu-ping Chen等人[2]將從最小跨距樹中的相關數據歸納而成的基因庫應用到基因算法之上來減小誤差的基因庫改良。這些算法和思路在最初設計時就借鑒了其他學科的內容，同時得益于先進計算設備的幫助，它們的處理對象可以是更加復雜和多樣的內容。而算法真正體現價值的時刻就是能夠脫離理論、應用于實際問題的時刻。比如程嘉、羅希和陸大明等人[3]在將TSP的計算范圍從理論拓展到公交系統規劃的過程中做出了貢獻。

2 球面距離

在傳統的旅行商問題中，距離計算都是基于歐幾里得距離，本文則采用球面距離。球面距離的核心思想來源于球面三角學，作為非歐幾何的一個重要組成部分，球面幾何學對于天文學、航海學和地理學的貢獻無法估量。

地理學上人為地依據赤道（即0°緯線）將地球分為南北半球，依據西經20°和東經160°兩條經線將地球分為東西半球。此分法是按照將地球看作為一個標準的正球體，從地球球心出發，規定垂直和水平兩個平面，然后將垂直平面按軸線逐漸翻動、水平面向上下平移成一組平行平面，隨即就能在地球表面出現數條經緯線的步驟進行的。這樣一來，地球表面就由這數條經緯線構成了一個坐標系。地球表面的任一位置都可以由一個維度和一個經度所組成的信息來表示。

于是，假設地球表面存在A、B兩個位置，其坐標信息分別為A（ xi, yi）、B（ xj, yj），前者代表緯度、后者代表經度，同時用R表示近似看成正球體時的地球半徑，則根據三角函數的內容，球面上兩者間的距離可以表示為：

此時，dAB的大小就是球面上A、B兩點之間的距離。

3 案例概述

自從第二次世界大戰以來，美國就一直維持著數量龐大的軍事基地，從本土到海外，這些軍事基地分布于世界各地。以下是美國目前公布的部分軍事基地坐標的其中25個（角度制的換算規則為：1°=60'，1'=60″），羅列如下：

A.安德魯斯空軍基地：38°48'31.72"N，76°51'35.28"W（美國華盛頓哥倫比亞特區）；

B.陸軍劉易斯堡：47°4'57.21"N，122°35'2.78"W（美國華盛頓州）；

C.廷克空軍基地：35°25'29.94"N，97°23'29.92"W（美國俄克拉荷馬州）；

D.威洛格羅夫空軍后備航空站：40°12'13.59"N，75°8'53.78"W（美國賓夕法尼亞州）；

E.陸軍本寧堡：32°21'37.75"N，84°58'8.85"W（美國佐治亞州）；

F.斯特科空軍基地：38°32'20.37"N，89°51'18.02"W（美國伊利諾斯州）；

G.西點軍校：41°23'30.32"N，73°57'26.95"W（美國紐約州）；

H.坎貝爾堡101空降師司令部：36°38'20.56"N，87°26'58.37"W（美國肯塔基州）；

I.霍洛曼空軍基地：32°50'20.07"N，106°5'35.09"W（美國新墨西哥州）；

J.基斯勒空軍基地：30°24'26.09"N，88°55'26.79"W（美國密西西比州）；

K.布蘭丁陸軍訓練基地：29°56'16.71"N，81°58'47.63"W（美國佛羅里達州）；

L.卡納維拉爾角發射基地：28°35'11.35"N，80°39'6.68"W（美國佛羅里達州）；

M.奇威斯特海軍航空站：24°34'39.70"N，81°41'54.22"W（美國佛羅里達州）；

N.小石城空軍基地：34°54'38.12"N，92°8'56.40"W（美國阿肯色州）；

O.新奧爾良海軍航空站：29°49'41.99"N，90°1'32.46"W（美國路易斯安那州）；

P.美陸軍駐德國維斯柏頓第12航空旅：49°39'12.64"N，9°58'22.33"E（德國）；

Q.沖繩第3陸戰師基地：26°23'32.17"N，127°51'19.08"E（日本）；

R.喀布爾機場空軍基地：34°33'40.64"N，69°13'10.34"E（阿富汗）；

S.安德森空軍基地：13°34'29.41"N，144°55'19.91"E（關島）；

T.關塔那摩軍事基地19°54'59.96"N，75°7'50.48"W（古巴）；

U.常規軍需品倉庫51°28'15.58"N，1°24'11.53"W（英國）；

V.迪戈加西亞美軍基地7°18'53.88"S，72°25'6.18"E（駐印度洋）；

W.瑪那茲空軍基地43°3'29.76"N，74°28'18.45"E（吉爾吉斯斯坦）；

X.漢納巴德空軍基地：38°50'0.56"N，65°54'36.95"E（烏茲別克斯坦）；

Y.烏代德空軍基地：25°8'9.00"N，51°18'48.51"E（卡塔爾）。

假設需要給巡航飛機設計一條路線，從A出發且不重復經過任何已經路過的地點最后回到A，使得飛機巡航的總距離最小，下面把具體的航行路線設計出來。

4 利用Lingo求解

首先，需要進行單位統一。規定北緯數值為正值、南緯為負值，東經數值為正值、西經為負值。編寫Lingo代碼將原始信息中包含度、分、秒三個單位的數據統一轉換為以度為單位的新數據。可以得到如下新的坐標數據（單位：度/°）：

由于涉及到非平面的地球表面上的點，那么計算其上任何兩點之間的距離就應該考慮使用球面距離公式。進一步，可以繼續編寫Lingo代碼進行計算，但是這其中特別要注意，Lingo程序內的三角函數在計算時默認輸入值的單位為弧度，所以在使用函數時需要注意將角度轉化為弧度，于是可計算出每兩點之間的距離見表1。

最后，在得到距離矩陣之后，就可以開始進行路線優化計算。編制路線優化的Lingo代碼進行計算，結果如下：

表1 距離矩陣

最終計算出的最短里程見圖1。

整合以上計算結果，可以作出如下路線規劃：

A-D-G-U-P-W-X-R-Y-V-Q-S-B-I-C-N-F-H-E-J-O-M-TL-K-A，總的最短里程數為47 159.94千米，同時使用MATLAB繪制路線圖見圖2：

圖1 最短里程的計算結果

圖2 優化路徑

為了對計算結果進行驗證，現在使用網頁版百度地圖對相關距離進行測距。由于在地圖上手動取點精度不高，所以在地圖上的測距數值與前文的計算結果存在微小的誤差（單位：千米）。

表2 地圖測距與計算結果的對比

在網頁版百度地圖上將各點的測距軌跡連接起來，就可以得到圖像見圖3：

圖3 地圖測距軌跡（局部）

經過上述驗證，結合實際數據表明，在允許一定誤差的情況之下，以上的規劃方案在理論上是正確有效的。

5 結束語

本文研究了基于球面距離的旅行商問題在實際案例中的應用，以美國目前公布的其中二十五個軍事基地的坐標為例，對相關的問題建立了模型，并通過Lingo軟件對該模型進行求解，得到了巡航飛機最優的航行路線，同時對計算結果進行了驗證，證明了本文給出的求解方案是正確可行的。