空戰場穿越走廊基本網絡規劃的混合禁忌搜索算法

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

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

0 引 言

基于樞紐軸輻式網絡的穿越走廊基本網絡規劃，是指將穿越走廊按一定方式連接而形成的樞紐軸輻式網絡結構系統，是空戰場航空軍事運輸活動進行與發展的基礎。穿越走廊質量或穿越走廊網絡結構的質量是航空軍事運輸支援保障能力的主要指標之一，因此對穿越走廊網絡進行科學、合理地布局規劃是保障戰場空運順利進行的重要手段。

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

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

1 基本網絡規劃模型描述

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

圖1 多重分派航線網絡Fig.1 Multi-assignment aviation network

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

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

目標函數：

(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流經樞紐機場k到終點機場j的交通流量占wij的比例；cij為機場i到機場j的直達單位運輸成本代價；Hk為樞紐機場選擇變量，當機場k為樞紐機場時，Hk=1，當機場k不是樞紐機場時，Hk=0。

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

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

2 混合禁忌搜索算法設計

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

(1) 編碼及初始解構造

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

(8)

式中：α、β為加權系數，且有α+β=1。

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

選擇權值最大的前p個機場節點作為樞紐，并利用Floyd最短路徑算法對機場節點之間的穿越走廊路徑進行安排，以求得的所有機場節點間的穿越走廊最短路徑，作為禁忌搜索算法的初始解。由模型可知，共有p個樞紐機場節點在穿越走廊網絡中起中轉作用，因此，當實際應用于求解該模型時，Floyd最短路徑算法運算過程只需要迭代p次。

(2) 適配值函數設計

(3) 鄰域結構及其候選解

本文的鄰域結構依靠單點交換方式，即移動當前解中的樞紐機場節點。假設S為初始解，S中有p個元素，即p個樞紐機場節點，則還有n-p個機場節點等待替換S內的樞紐機場節點。當初始解S以外的n-p個機場節點替換初始解S中的某個節點后就產生了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}。如此得到的四個鄰域解將作為候選解以產生下一步解。

(4) 禁忌對象選擇

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

(5) 禁忌長度確定

(6) 特赦準則

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

(7) 停止準則

當達到算法預定的最大迭代次數或者目標函數的最優值在設定迭代次數內無法改進時，算法停止。

3 算例分析

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

表1 機場節點坐標Table 1 Coordinate of each airport node

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

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

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

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

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

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

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

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

根據路徑安排結果，可設計出10個機場節點在不考慮限制空域情況下穿越走廊網絡圖，如圖3所示。

圖3 不考慮限制空域的穿越走廊基本網絡規劃結果Fig.3 Planning result of TC basic network without considering the restricted airspace

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

至此，不考慮限制空域影響的穿越走廊基本網絡初步規劃已完成。下一步，需要對加入限制空域的穿越走廊基本網絡進行重規劃，模擬空戰場實際，考慮穿越走廊網絡與空中限制區、禁飛區和對空火力打擊區等限制空域之間的結構關系，避免出現空域沖突，造成己方火力誤擊誤傷的嚴重后果。在加入限制空域后，穿越走廊網絡的空域運行情況如圖4所示。

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

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

4 結 論

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

(2) 根據混合禁忌搜索算法優化結果，設計出不考慮限制空域情況下的穿越走廊網絡圖，驗證了模型求解結果的正確性，也為考慮限制空域的穿越走廊可行網絡規劃搭建了基本框架。

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