劉影，周一葉，甘旭升，楊捷

(1.西京學(xué)院 信息工程學(xué)院，西安 710123) (2.中國人民解放軍95746部隊，成都 611531) (3.空軍工程大學(xué) 空管領(lǐng)航學(xué)院，西安 710051)

0 引 言

基于樞紐軸輻式網(wǎng)絡(luò)的穿越走廊基本網(wǎng)絡(luò)規(guī)劃，是指將穿越走廊按一定方式連接而形成的樞紐軸輻式網(wǎng)絡(luò)結(jié)構(gòu)系統(tǒng)，是空戰(zhàn)場航空軍事運輸活動進行與發(fā)展的基礎(chǔ)。穿越走廊質(zhì)量或穿越走廊網(wǎng)絡(luò)結(jié)構(gòu)的質(zhì)量是航空軍事運輸支援保障能力的主要指標(biāo)之一，因此對穿越走廊網(wǎng)絡(luò)進行科學(xué)、合理地布局規(guī)劃是保障戰(zhàn)場空運順利進行的重要手段。

1996年，J.F.Campbell[1]針對樞紐軸輻式網(wǎng)絡(luò)中的單分配多樞紐中位問題首先提出了線性整數(shù)規(guī)劃模型；1998年，P.J.Lederer等[2]根據(jù)起訖點間飛行流量矩陣和距離矩陣對航線網(wǎng)絡(luò)中的全連通網(wǎng)絡(luò)(即點對點式網(wǎng)絡(luò))、環(huán)形網(wǎng)絡(luò)、樞紐軸輻式網(wǎng)絡(luò)和子環(huán)形網(wǎng)絡(luò)四種類型進行了定量分析，提出了航向網(wǎng)絡(luò)設(shè)計中需要注意的一些主要參考因素；2000年，E.Pels等[3]將點對點式航向網(wǎng)絡(luò)與樞紐軸輻式航線網(wǎng)絡(luò)進行了成本比較分析，指出樞紐軸輻式航線網(wǎng)絡(luò)在降低成本方面的有效性；同年，耿淑香[4]對點對點式航線網(wǎng)絡(luò)和樞紐軸輻式航線網(wǎng)絡(luò)進行了詳細(xì)分析，指出樞紐軸輻式網(wǎng)絡(luò)能夠更好地利用空域資源以及進行新航線的開辟，具有良好的魯棒性；2006年，柏明國[5]提出了基于多屬性決策法的樞紐集候選方法，對樞紐軸輻式航線網(wǎng)絡(luò)中的樞紐機場進行選擇；2007年，T.Kelly等[6]針對樞紐軸輻式航線網(wǎng)絡(luò)模型特點，將遺傳算法應(yīng)用于模型求解；2010年，楊晗熠[7]以航空貨運成本最小化為目標(biāo)，建立了基于樞紐軸輻式航線網(wǎng)絡(luò)的中國民航運輸網(wǎng)絡(luò)設(shè)計模型；2011年，楊年等[8]提出了基于混合集合規(guī)劃的樞紐航線網(wǎng)絡(luò)設(shè)計方法；2012年，葛偉等[9]針對樞紐軸輻式網(wǎng)絡(luò)中的非必要中轉(zhuǎn)問題，設(shè)計了蛛式航線網(wǎng)絡(luò)模型及相關(guān)算法，是國內(nèi)較早的針對蛛式航線網(wǎng)絡(luò)的定量研究成果。綜上研究表明，樞紐軸輻式航線網(wǎng)絡(luò)憑借其良好的網(wǎng)絡(luò)結(jié)構(gòu)，國內(nèi)外學(xué)者將大部分研究都聚焦于該類航線網(wǎng)絡(luò)的規(guī)劃設(shè)計，但更多關(guān)注于理想運行環(huán)境中航線網(wǎng)絡(luò)的經(jīng)濟效益和服務(wù)質(zhì)量，而對空戰(zhàn)場條件下的穿越走廊基本網(wǎng)絡(luò)規(guī)劃設(shè)計問題研究甚少[10-11]。國內(nèi)外大多數(shù)學(xué)者對樞紐軸輻式航線網(wǎng)絡(luò)進行研究，所構(gòu)建模型常為混合整數(shù)規(guī)劃的SUMApHMP模型[12]，在問題規(guī)模較小時可利用精確算法求得最優(yōu)解，但是對于解決戰(zhàn)場空域內(nèi)機場數(shù)目多，且飛行流量大的穿越走廊基本網(wǎng)絡(luò)規(guī)劃問題，還存在一定難度。

基于此，針對不考慮限制空域影響的穿越走廊基本網(wǎng)絡(luò)規(guī)劃問題特點，本文將禁忌搜索算法與Floyd算法有機結(jié)合，提出一種組合的SUMApHMP模型求解算法，并驗證算法有效性。

1 基本網(wǎng)絡(luò)規(guī)劃模型描述

通過樞紐機場的中轉(zhuǎn)集散，樞紐軸輻式航線網(wǎng)絡(luò)內(nèi)的運輸機裝載效率明顯提高，從而達到減少飛行批次，節(jié)約運力成本的目的，提高了航空軍事運輸?shù)膽?zhàn)場保障能力。然而，樞紐軸輻式航線網(wǎng)絡(luò)自身也存在一定的缺陷：所有非樞紐機場起飛的運輸機，不論是否滿載，不論起訖機場距離遠(yuǎn)近，都必須經(jīng)過樞紐機場中轉(zhuǎn)；大批裝備物資裝卸和分揀需要在樞紐機場進行，需要占用大量的人力物力來確保規(guī)定空運投送任務(wù)時間內(nèi)的保障水平。因此，本文在基本樞紐軸輻式航線網(wǎng)絡(luò)中采取多重分派的方式，即個別流量較大的非樞紐機場可以同時連接多個樞紐機場，對物資運輸進行攤派，減少對單個樞紐機場保障水平的影響，構(gòu)建多重分派航線網(wǎng)絡(luò) (非樞紐機場能與多個樞紐機場直接相連)如圖1所示。

圖1 多重分派航線網(wǎng)絡(luò)Fig.1 Multi-assignment aviation network

無容量限制的嚴(yán)格型多重分派樞紐軸輻式航線網(wǎng)絡(luò)實際運作情況較為復(fù)雜，為方便研究，符合實際情形，將假設(shè)條件和已知條件陳述如下：某戰(zhàn)區(qū)中有n個機場，預(yù)置樞紐機場p個；樞紐機場之間的穿越走廊為點對點式全連通型，非樞紐機場之間的連接需要經(jīng)過樞紐機場進行中轉(zhuǎn)；樞紐機場和航線上不存在運輸容量的限制，能夠為大批量運輸機的起降、物資裝卸、飛行情報服務(wù)提供保障；運輸機從起始機場起飛到達目的機場，只能沿路徑最短的穿越走廊飛行；一個非樞紐機場可以和多個樞紐機場直接連接(多重分派)；樞紐機場之間的空運成本存在一個折扣系數(shù)ρ(0<ρ<1)；由于航空軍事運輸活動對時效性的要求，最多只允許兩次經(jīng)過樞紐機場進行中轉(zhuǎn)。

根據(jù)ρ-HM-MA模型[8]，可針對不考慮限制空域(火力打擊區(qū)、禁飛區(qū)、殺傷盒、危險區(qū)等)影響的穿越走廊基本網(wǎng)絡(luò)規(guī)劃建立SUMApHMP模型。

目標(biāo)函數(shù)：

(1)

(2)

(3)

(4)

(5)

Hk∈{0,1} (?k∈N)

(6)

xiklj≥0 (?i,k,l,j∈N)

(7)

式中：wij為機場i到機場j的O-D流；xiklj為從機場i流經(jīng)樞紐機場k到終點機場j的交通流量占wij的比例；cij為機場i到機場j的直達單位運輸成本代價；Hk為樞紐機場選擇變量，當(dāng)機場k為樞紐機場時，Hk=1，當(dāng)機場k不是樞紐機場時，Hk=0。

目標(biāo)函數(shù)如式(1)所示，為了使網(wǎng)絡(luò)運行總成本最小化，由cik+ρckl+cij可以看出，總成本分為三項：第一項非樞紐機場至樞紐機場運輸成本，第二項為樞紐機場之間中轉(zhuǎn)運輸成本，第三項為樞紐機場至非樞紐機場運輸成本。樞紐機場數(shù)目約束如式(2)所示，即樞紐機場個數(shù)預(yù)置為p；運輸方式限制如式(3)所示，任意非樞紐機場之間的運輸任務(wù)需要通過樞紐機場中轉(zhuǎn)完成；非樞紐機場約束如式(4)～式(5)所示，即當(dāng)某個機場不是樞紐機場時，運輸機不能經(jīng)該機場中轉(zhuǎn)。

本文在研究中沒有考慮限制空域(火力打擊區(qū)、禁飛區(qū)、殺傷盒、危險區(qū)等)的影響，僅考慮了機場布局、交通流量、各機場對距離等的影響，對戰(zhàn)場航空軍事運輸網(wǎng)絡(luò)進行初步規(guī)劃。

2 混合禁忌搜索算法設(shè)計

本文研究的不考慮限制空域的穿越走廊基本網(wǎng)絡(luò)模型屬于NP-hard問題，且求解規(guī)模較大，因此，在利用禁忌搜索算法[13]選取樞紐機場節(jié)點的同時，不能隨機生成初始解，需要對初始解進行構(gòu)造，這樣可使算法具有較快的收斂速度，并且確保算法不會陷入局部最優(yōu)。采用Floyd最短路徑算法[14]對機場節(jié)點之間的穿越走廊路徑進行安排，并以求得的所有機場節(jié)點間的穿越走廊最短路徑作為禁忌搜索算法的初始解。

(1) 編碼及初始解構(gòu)造

模型采用自然數(shù)編碼，集合N={1,2,3,…,n}表示n個機場節(jié)點形成的樞紐軸輻式網(wǎng)絡(luò)，每個自然數(shù)對應(yīng)一個機場接點。由于網(wǎng)絡(luò)中的飛行流量和機場間距離矩陣等因素對樞紐機場的選取過程會產(chǎn)生直接的影響，因此在選取初始解的樞紐機場時需要選取合理的辦法對待規(guī)劃空域內(nèi)的所有機場節(jié)點進行排序。本文采用的指標(biāo)評價各機場節(jié)點[7]如式(8)所示：

(8)

式中：α、β為加權(quán)系數(shù)，且有α+β=1。

可以看出，某機場飛行流量越大，且到其它各機場距離之和越小，則該機場節(jié)點權(quán)值越大，即成為樞紐機場的概率越高。

選擇權(quán)值最大的前p個機場節(jié)點作為樞紐，并利用Floyd最短路徑算法對機場節(jié)點之間的穿越走廊路徑進行安排，以求得的所有機場節(jié)點間的穿越走廊最短路徑，作為禁忌搜索算法的初始解。由模型可知，共有p個樞紐機場節(jié)點在穿越走廊網(wǎng)絡(luò)中起中轉(zhuǎn)作用，因此，當(dāng)實際應(yīng)用于求解該模型時，F(xiàn)loyd最短路徑算法運算過程只需要迭代p次。

(2) 適配值函數(shù)設(shè)計

(3) 鄰域結(jié)構(gòu)及其候選解

本文的鄰域結(jié)構(gòu)依靠單點交換方式，即移動當(dāng)前解中的樞紐機場節(jié)點。假設(shè)S為初始解，S中有p個元素，即p個樞紐機場節(jié)點，則還有n-p個機場節(jié)點等待替換S內(nèi)的樞紐機場節(jié)點。當(dāng)初始解S以外的n-p個機場節(jié)點替換初始解S中的某個節(jié)點后就產(chǎn)生了S的一個鄰域解S*，顯然初始解S的鄰域解集合N(S)中總共有p(n-p)個鄰域解。例如S={1,2}，N={1,2,3,4}，則S*={1,3}，{1,4}，{2,3}，{2,4}。如此得到的四個鄰域解將作為候選解以產(chǎn)生下一步解。

(4) 禁忌對象選擇

當(dāng)一個非樞紐機場Spoke和一個樞紐機場Hub進行單點交換后，便將機場Hub放入禁忌表中，此時禁忌對象就是機場Hub，處于被禁忌狀態(tài)。當(dāng)未達到預(yù)置迭代次數(shù)，即禁忌長度不為零，機場Hub不會被釋放到搜索空間中(滿足特赦準(zhǔn)則的情況除外)，避免了迂回搜索的情況發(fā)生。本文以先進先出(First in First Out)作為禁忌表的狀態(tài)更新原則。由此可知，禁忌解的鄰域結(jié)構(gòu)是通過機場節(jié)點的換入換出產(chǎn)生的，因此對解的變化進行禁忌可以通過對S中的換出節(jié)點進行禁忌來實現(xiàn)。仍以S={1,2}為例，表示機場1、2為模型中的樞紐機場，當(dāng)變換S={1,4}時，表示機場4成為了樞紐機場，機場2變成了非樞紐機場，這時選擇機場2作為禁忌對象，它作為曾經(jīng)的樞紐機場節(jié)點，在未來的一定迭代次數(shù)內(nèi)會避免其再次成為樞紐機場節(jié)點，從而可以使算法輕易跳出局部最優(yōu)解。

(5) 禁忌長度確定

(6) 特赦準(zhǔn)則

本文將特赦準(zhǔn)則分三種情形進行分析：①在禁忌表中的候選解優(yōu)于當(dāng)前最優(yōu)解時，則將該解從禁忌表中釋放，作為當(dāng)前最優(yōu)解繼續(xù)參與搜索；②在當(dāng)前最優(yōu)解優(yōu)于禁忌表中的候選解以及搜索空間中的候選解時，則將搜索空間中的最優(yōu)解作為當(dāng)前解，以便跳出局部最優(yōu)；③在所有候選解均被禁忌時，釋放禁忌表中的最優(yōu)解作為當(dāng)前解，使得搜索能夠繼續(xù)。

(7) 停止準(zhǔn)則

當(dāng)達到算法預(yù)定的最大迭代次數(shù)或者目標(biāo)函數(shù)的最優(yōu)值在設(shè)定迭代次數(shù)內(nèi)無法改進時，算法停止。

3 算例分析

為了驗證模型和算法的有效性，本文選取10個機場節(jié)點作為研究對象，采用MATLAB 2014a作為程序開發(fā)平臺，編寫程序?qū)崿F(xiàn)禁忌搜索算法和Floyd最短路徑算法求解基于樞紐軸輻式理論的穿越走廊基本網(wǎng)絡(luò)規(guī)劃模型，輸出最佳樞紐機場布局和穿越走廊路徑分配。各機場節(jié)點的(x,y)坐標(biāo)值以及機場對之間飛行流量如表1和表2所示(表中數(shù)據(jù)根據(jù)文獻[17]整理獲得)，為簡化運算，機場之間的物資流量對稱一致。機場節(jié)點空間分布如圖2所示。下面利用所提出方法對10個機場節(jié)點的穿越走廊基本網(wǎng)絡(luò)進行構(gòu)建。

表1 機場節(jié)點坐標(biāo)Table 1 Coordinate of each airport node

圖2 機場節(jié)點空間分布Fig.2 Space distribution of airport nodes

表2 機場節(jié)點間的飛行流量Table 2 Flight flow between airport nodes

表3 機場節(jié)點間的距離矩陣Table 3 Distance matrix between airport nodes

根據(jù)10個機場節(jié)點的流量矩陣和距離矩陣，對混合禁忌搜索算法的求解效果進行驗證分析，其中樞紐機場數(shù)目分別取p={2,3,4}，折扣系數(shù)分別取值ρ={0.4,0.6,0.8}。該驗證基于MATLAB 2014a編程實現(xiàn)，且混合禁忌搜索算法的運算終止條件為最大迭代次數(shù)超過max_int=30或連續(xù)4次得到相同解。為驗證算法準(zhǔn)確性，本文利用Lingo 9.0對模型求解的最優(yōu)解和混合禁忌搜索算法的計算結(jié)果進行比較分析，對比結(jié)果如表4所示，可以看出：利用混合禁忌搜索算法和Lingo 9.0軟件都能得到模型的最優(yōu)解；在求解速度上，利用混合禁忌搜索算法的求解時間遠(yuǎn)遠(yuǎn)少于利用Lingo 9.0的求解時間。另外，當(dāng)折扣系數(shù)ρ確定后，隨著樞紐機場數(shù)目p增大，穿越走廊網(wǎng)絡(luò)的運行總代價會變小。然而，樞紐機場通常會被敵方列入高價值目標(biāo)清單進行打擊，實戰(zhàn)時的穿越走廊網(wǎng)絡(luò)設(shè)計并不是樞紐機場越多越好，較多的樞紐機場增加了機場的防御難度，而且在現(xiàn)實中樞紐機場的設(shè)置與維護需要大量財力、物力和人力的投入。

表4 混合禁忌搜索算法和Lingo 9.0求解模型結(jié)果的對比Table 4 Comparison of model solution results obtained by hybrid taboo search algorithm and Lingo 9.0

本文以p=3，ρ=0.4為例，不考慮限制空域的穿越走廊基本網(wǎng)絡(luò)進行規(guī)劃，由混合禁忌搜索算法求解得到最優(yōu)樞紐機場為：機場1、3和4，對應(yīng)的連接矩陣Rp如表5所示。

表5 連接矩陣Rp (p=3,ρ=0.4)Table 5 Connection matrix Rp (p=3,ρ=0.4)

表6 穿越走廊基本網(wǎng)絡(luò)路徑安排結(jié)果(p=3,ρ=0.4)Table 6 Results of TC basic network path arrangement(p=3,ρ=0.4)

根據(jù)路徑安排結(jié)果，可設(shè)計出10個機場節(jié)點在不考慮限制空域情況下穿越走廊網(wǎng)絡(luò)圖，如圖3所示。

圖3 不考慮限制空域的穿越走廊基本網(wǎng)絡(luò)規(guī)劃結(jié)果Fig.3 Planning result of TC basic network without considering the restricted airspace

從圖3可以看出：三個樞紐機場通過穿越走廊相互連接，構(gòu)成穿越走廊干線網(wǎng)絡(luò)；非樞紐機場中，機場9與三個樞紐機場直接連接，機場6和10與兩個樞紐直接鏈接，而機場2、5、7和8只與一個樞紐機場直接連接，這些構(gòu)成了穿越走廊網(wǎng)絡(luò)支線網(wǎng)絡(luò)。

至此，不考慮限制空域影響的穿越走廊基本網(wǎng)絡(luò)初步規(guī)劃已完成。下一步，需要對加入限制空域的穿越走廊基本網(wǎng)絡(luò)進行重規(guī)劃，模擬空戰(zhàn)場實際，考慮穿越走廊網(wǎng)絡(luò)與空中限制區(qū)、禁飛區(qū)和對空火力打擊區(qū)等限制空域之間的結(jié)構(gòu)關(guān)系，避免出現(xiàn)空域沖突，造成己方火力誤擊誤傷的嚴(yán)重后果。在加入限制空域后，穿越走廊網(wǎng)絡(luò)的空域運行情況如圖4所示。

圖4 加入限制空域后的穿越走廊基本網(wǎng)絡(luò)運行情況Fig.4 Operation of TC basic network after the restricted airspace is added

從圖4可以看出：加入限制空域后，各機場對之間共有7條穿越走廊與限制空域交匯，存在明顯的沖突隱患。記path(i,j)表示連通機場i和機場j之間的穿越走廊，obstacle_paths表示戰(zhàn)場空域環(huán)境中存在空域沖突的穿越走廊的集合，則根據(jù)圖中信息可知，obstacle_paths={path(1,3),path(1,4),path(1,9),path(1,10),path(3,9),path(4,5),path(4,6)}。

4 結(jié) 論

(1) 對不考慮限制空域的穿越走廊基本網(wǎng)絡(luò)規(guī)劃的SUMApHMP數(shù)學(xué)模型，提出了一種混合禁忌搜索求解算法。算例分析表明，所提出算法和Lingo 9.0軟件都能求得最優(yōu)解，但前者在求解時間上要遠(yuǎn)遠(yuǎn)少于后者。

(2) 根據(jù)混合禁忌搜索算法優(yōu)化結(jié)果，設(shè)計出不考慮限制空域情況下的穿越走廊網(wǎng)絡(luò)圖，驗證了模型求解結(jié)果的正確性，也為考慮限制空域的穿越走廊可行網(wǎng)絡(luò)規(guī)劃搭建了基本框架。

(3) 出于說明模型和算法的需要，在研究空戰(zhàn)場條件下的穿越走廊基本網(wǎng)絡(luò)規(guī)劃問題時沒有考慮限制空域情況，僅僅初步規(guī)劃了空戰(zhàn)場航空軍事運輸網(wǎng)絡(luò)，而加入限制空域后，穿越走廊基本網(wǎng)絡(luò)規(guī)劃問題將更為復(fù)雜，也是下一步需要深入研究的問題。