吳皓華，曹 茜 （上海電力大學(xué)，上海 200090）

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

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

1 旅行商問題

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

2 球面距離

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

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

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

此時(shí)，dAB的大小就是球面上A、B兩點(diǎn)之間的距離。

3 案例概述

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

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

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.西點(diǎn)軍校：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.布蘭丁陸軍訓(xùn)練基地：29°56'16.71"N，81°58'47.63"W（美國佛羅里達(dá)州）；

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

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

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陸戰(zhàn)師基地：26°23'32.17"N，127°51'19.08"E（日本）；

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

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

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

U.常規(guī)軍需品倉庫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（卡塔爾）。

假設(shè)需要給巡航飛機(jī)設(shè)計(jì)一條路線，從A出發(fā)且不重復(fù)經(jīng)過任何已經(jīng)路過的地點(diǎn)最后回到A，使得飛機(jī)巡航的總距離最小，下面把具體的航行路線設(shè)計(jì)出來。

4 利用Lingo求解

首先，需要進(jìn)行單位統(tǒng)一。規(guī)定北緯數(shù)值為正值、南緯為負(fù)值，東經(jīng)數(shù)值為正值、西經(jīng)為負(fù)值。編寫Lingo代碼將原始信息中包含度、分、秒三個(gè)單位的數(shù)據(jù)統(tǒng)一轉(zhuǎn)換為以度為單位的新數(shù)據(jù)?？梢缘玫饺缦滦碌淖鴺?biāo)數(shù)據(jù)（單位：度/°）：

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

最后，在得到距離矩陣之后，就可以開始進(jìn)行路線優(yōu)化計(jì)算。編制路線優(yōu)化的Lingo代碼進(jìn)行計(jì)算，結(jié)果如下：

表1 距離矩陣

最終計(jì)算出的最短里程見圖1。

整合以上計(jì)算結(jié)果，可以作出如下路線規(guī)劃：

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，總的最短里程數(shù)為47 159.94千米，同時(shí)使用MATLAB繪制路線圖見圖2：

圖1 最短里程的計(jì)算結(jié)果

圖2 優(yōu)化路徑

為了對(duì)計(jì)算結(jié)果進(jìn)行驗(yàn)證，現(xiàn)在使用網(wǎng)頁版百度地圖對(duì)相關(guān)距離進(jìn)行測距。由于在地圖上手動(dòng)取點(diǎn)精度不高，所以在地圖上的測距數(shù)值與前文的計(jì)算結(jié)果存在微小的誤差（單位：千米）。

表2 地圖測距與計(jì)算結(jié)果的對(duì)比

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

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

經(jīng)過上述驗(yàn)證，結(jié)合實(shí)際數(shù)據(jù)表明，在允許一定誤差的情況之下，以上的規(guī)劃方案在理論上是正確有效的。

5 結(jié)束語

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