吳文浩， 張學軍， 顧博， 朱曉輝

(1. 北京航空航天大學電子信息工程學院, 北京 100083； 2. 國家空域管理中心, 北京 100094)

空中交通管理部門根據(jù)航路航線、機場和通信導航監(jiān)視等設施設備布局，將空域劃分成若干個管制扇區(qū)，以扇區(qū)為單位向各類飛行活動提供管制指揮、告警、氣象等服務，以確保飛行流量的安全、高效、有序運行。隨著中國民用航空和軍事航空飛行量的持續(xù)快速增長，有限的空域資源導致軍民航間飛行矛盾日益凸顯，產(chǎn)生了大量的航班延誤、空中擁堵和額外的管制負荷。隨著軍民融合發(fā)展上升為國家戰(zhàn)略，如何統(tǒng)一組織、全局優(yōu)化、兼顧軍民航飛行活動各自特點實施飛行流量協(xié)同調(diào)控，最大限度降低擁堵、減少延誤、提高空域資源利用率，已成為空中交通管理領域的一個熱點和焦點問題。

全局飛行流量協(xié)同優(yōu)化是一類典型的面向實際應用的工程優(yōu)化問題，由于緩解空中交通擁堵與減少飛行延誤在實際中往往是相互沖突的，因此該問題實質(zhì)上是一個多目標優(yōu)化問題。求解此類問題的難點主要是：一方面，由于扇區(qū)網(wǎng)絡中同時運行著幾千個航班，每個航班至少包括飛行路徑和起飛時間2個變量，因此該問題是一個大規(guī)模優(yōu)化問題；另一方面，表征扇區(qū)網(wǎng)絡擁堵的目標函數(shù)是不可微且難分解的，傳統(tǒng)優(yōu)化算法難以處理，這將在后續(xù)詳細介紹。

20世紀90年代以來，歐美等地區(qū)學者就開展了空中交通流量網(wǎng)絡運行優(yōu)化問題研究，將地面等待、空中等待、空中改航、航班取消等策略覆蓋到每個航班所有階段，提出了0-1整型規(guī)劃[1-3]、混合0-1整數(shù)規(guī)劃、BLO等模型[4-7]，馬正平等提出了短期空中交通流量管理問題的整數(shù)規(guī)劃模型[8]，蔡開泉、管祥民、肖明明等提出了航班飛行路徑與起降時隙的協(xié)同分配、飛行流量魯棒優(yōu)化等模型算法[9-11]，有效解決了民用航空特別是同質(zhì)化飛行活動條件下飛行流量優(yōu)化問題。

軍事航空飛行活動主要包括戰(zhàn)斗飛行、任務飛行、訓練飛行等，由于其在活動范圍、飛行路徑、管制間隔等方面有著區(qū)別于民用航空的特殊要求，特別是由于政治、軍事、外交等方面因素導致延誤、改航等措施對其飛行活動影響的代價也遠遠高于民用航空飛行活動。統(tǒng)籌民用航空和軍事航空需求實施全局飛行流量調(diào)控，將是一種在異質(zhì)化飛行活動條件下的飛行流量協(xié)同優(yōu)化問題，傳統(tǒng)的同質(zhì)化飛行流量協(xié)同優(yōu)化模型將在目標函數(shù)設置、條件約束等方面難以滿足異質(zhì)化飛行流量調(diào)控要求。同時，傳統(tǒng)遺傳算法在處理高維問題時，容易過早陷入局部最優(yōu)，產(chǎn)生“維數(shù)詛咒”，實際應用效果往往不太理想。

本文貫徹軍民融合發(fā)展思想，首先設計了全局飛行流量多目標協(xié)同優(yōu)化模型——CMI模型；其次，提出了動態(tài)自適應多目標遺傳算法(DA-MOGA)和基于聚集距離與種群多樣性的交叉變異概率動態(tài)調(diào)整機制；最后，通過實際數(shù)據(jù)對DA-MOGA的有效性進行驗證。

1 全局飛行流量協(xié)同優(yōu)化模型

在飛行活動中，航空器一般沿著各自規(guī)劃的航線從起飛機場飛往目的機場，管制員以空域扇區(qū)為單元實施飛行管制，保證飛行活動安全、高效、有序運行。機場、扇區(qū)構成了空域運行的基本單元。由于機場運行能力和管制員工作負荷等原因，機場和扇區(qū)的容量是有限的。空中交通流量網(wǎng)絡優(yōu)化主要是對飛行活動中的起降時間和飛行路徑進行調(diào)控，以達到網(wǎng)絡運行經(jīng)濟性和安全性的整體最優(yōu)。

1.1 目標函數(shù)

全局飛行流量協(xié)同優(yōu)化在空域扇區(qū)網(wǎng)絡多目標優(yōu)化模型基礎上，考慮了軍民航異質(zhì)化飛行活動管制要求和差異化調(diào)配方法與代價，兼顧了軍民航管制員各自工作特點，決策變量采用飛行計劃的起飛時刻和飛行路徑，目標函數(shù)則是扇區(qū)網(wǎng)絡的空中交通擁堵和總體飛行延誤代價。

1.1.1 空中交通擁堵

空中交通擁堵通過對負責空域扇區(qū)的管制員工作負荷進行量化，對扇區(qū)網(wǎng)絡的所有扇區(qū)的管制員工作負荷進行累加，綜合考慮各扇區(qū)的最大擁堵水平和平均擁堵水平，引用經(jīng)典方法[6]得到以下目標函數(shù)：

(1)

式中：φ∈[0,1]為最大擁堵和平均擁堵間的權重；n為空域內(nèi)扇區(qū)總數(shù)；T為空域扇區(qū)網(wǎng)絡優(yōu)化時間區(qū)間；ωi(t)為扇區(qū)i在第t個時隙的管制員工作負荷。

(2)

其中：ni(t)為扇區(qū)i在第t個時隙的飛機數(shù)。

其中：Ci(t)為扇區(qū)i在第t個時隙的容量。

1.1.2 總體飛行延誤代價

總體飛行延誤代價由起飛延誤導致的地面延誤代價和由空中等待、減速或飛行路徑變更產(chǎn)生的空中延誤代價組成。

(3)

式中：f2為總體飛行延誤代價；gf為飛行活動f的延誤代價；模型中設計了ni和nc分別為相應類別軍航飛行活動FMi和民航飛行FC的延誤代價權重。

飛行活動F包括民航飛行FC和軍航飛行FM，F(xiàn)M主要包括了戰(zhàn)斗飛行、專機和重要任務飛行、一般任務飛行、轉場飛行、場內(nèi)場外飛行等。軍航本場訓練飛行(含場內(nèi)場外)因大都不涉及跨扇區(qū)飛行，戰(zhàn)斗飛行因其特殊凈空要求，因此不納入扇區(qū)網(wǎng)絡流量優(yōu)化范疇。其他軍航飛行計劃劃分為專機飛行計劃FM1、重要任務飛行計劃FM2、一般任務飛行計劃FM3和轉場飛行計劃FM4。

1.2 約束條件

考慮扇區(qū)網(wǎng)絡運行實際，還需要對模型中的空域容量、起飛時間、軍航特殊間隔要求和飛行距離等進行約束。

1.2.1 空域容量約束

空域扇區(qū)網(wǎng)絡中的各機場和扇區(qū)節(jié)點應全程滿足容量要求，即

(4)

1.2.2 起飛時間約束

(5)

1.2.3 軍航特殊任務約束

根據(jù)中國飛行管制有關規(guī)定，專機飛行活動由于極端安全要求須執(zhí)行特殊間隔規(guī)定，即加大橫向、縱向與水平飛行間隔。模型中，通過控制同一機場起飛時間間隔予以保證(即在專機起飛機場前后10 min內(nèi)應無其他飛機起飛)。

(6)

1.2.4 飛行距離約束

(7)

2 動態(tài)自適應多目標遺傳算法

從第1節(jié)問題模型可知，扇區(qū)網(wǎng)絡飛行流量協(xié)同優(yōu)化問題是一個目標函數(shù)不可微、決策變量難分解的大規(guī)模優(yōu)化問題，包含2個強耦合的子問題，即同時優(yōu)化起飛時間和飛行路徑。由于所有飛行計劃均在同一時空范圍內(nèi)活動，同一飛行計劃內(nèi)起飛時間與飛行路徑相互影響，不同飛行計劃之間起飛時間和飛行路徑也存在著相互耦合關系。

2.1 算法框架

Pi={η1,η2,…,ηs}

(8)

(9)

式中：|F|為飛行活動總數(shù)。

首先，在決策空間隨機生成個體構建初始種群，個體解碼后計算其目標函數(shù)并對種群個體進行排序；其次，進行“選擇”操作，基于擁擠錦標賽選擇法構建“交配池”；再次，進行“遺傳”操作，對種群實施交叉和變異，交叉和變異概率將根據(jù)種子聚集距離和種群多樣性進行動態(tài)調(diào)整，并進行約束處理；最后，計算新的種群個體目標函數(shù)后，進行種族重組、選擇和更新，種群中的非支配解即構成Pareto最優(yōu)解集。

2.2 動態(tài)自適應算子

2.2.1 種群平均聚集距離

進化第n代種群平均聚集距離為

(10)

式中：di為種群中第i個種子與第i+1個種子間的歐氏距離。

2.2.2 種群多樣性

種群多樣性為

(11)

2.3 交叉變異概率動態(tài)調(diào)整機制

遺傳過程中，交叉和變異概率決定了種群進化搜索方向。在進化之初，較高的交叉概率Pc和較低的變異概率Pv可使種群有效擴大搜索范圍，增強種群多樣性。

進化過程中，如種群平均聚集距離過大，意味著種子周圍的搜索空間沒有被充分搜索，往往不容易收斂，此時應盡快縮小搜索范圍(迅速降低交叉概率Pc、增大變異概率Pv)，使種群加快聚焦。如種群平均聚集距離過小，意味著種群“早熟”或陷入局部最優(yōu)，則應擴大搜索范圍(增大交叉概率Pc，降低變異概率Pv)，避免過快聚焦。

進化過程中，如種群平均聚集距離適中，若種子間隔也適中，即多樣性較好，則應保持交叉變異概率繼續(xù)進化；若種子間隔有大有小，不夠均勻，即多樣性分布不佳，意味著種子周圍空間沒有被充分搜索，則應縮小搜索范圍(降低交叉概率Pc、增大變異概率Pv)；如多樣性過差，則應盡快縮小搜索范圍(迅速降低交叉概率Pc、增大變異概率Pv)，以調(diào)整多樣性分布。具體為

(12)

(13)

(14)

(15)

3 實驗驗證

為了評價全局飛行流量協(xié)同優(yōu)化模型和動態(tài)自適應多目標遺傳算法的有效性，本節(jié)利用中國扇區(qū)網(wǎng)絡的實際數(shù)據(jù)進行對比實驗。

3.1 實驗數(shù)據(jù)及參數(shù)設置

為了評價3 種算法產(chǎn)生的解的收斂性、多樣性等特性，本文使用多目標進化算法性能評價的3 個經(jīng)典指標，綜合性指標、收斂性指標和多樣性指標來衡量算法性能[12]。

綜合性(Ih)[13]是對解集收斂性、均勻性以及廣泛性的綜合評價指標，可以用來反映非支配解集與 Pareto最優(yōu)前沿的逼近程度，綜合性指標越大，越是逼近 Pareto最優(yōu)前沿。

收斂性(Id)[14]是指算法搜索的非支配解集對 Pareto最優(yōu)前沿的逼近程度，收斂性指標越小，算法逼近問題 Pareto最優(yōu)解集的程度越好。

多樣性(Δ)[15]是評價算法求得非支配解集分布的離散程度和均勻性，多樣性指標越小，非支配解集分布的越均勻分散，解的多樣性越好。

本文實驗選取多目標遺傳算法MOGA和非支配排序遺傳算法NSGA-Ⅱ 2種經(jīng)典多目標遺傳算法進行了對比。MOGA和NSGA-Ⅱ算法經(jīng)過遍歷分別取解的綜合性系數(shù)最優(yōu)時的交叉、變異概率取值分別為0.5、0.09和0.7、0.07。為確保算法和實驗對比公平性，各算法設置相同的種群規(guī)模和適應值評價次數(shù)，并分別進行了25次獨立實驗。算法主要參數(shù)取值見表1。

表1 算法主要參數(shù)取值

3.2 實驗結果與對比分析

表2給出了3種算法25次獨立實驗中得到最好的指標值。其中就綜合性指標而言，DA-MOGA和MOGA均優(yōu)于NSGA-Ⅱ，且DA-MOGA性能最優(yōu)。這表明采用 MOGA在解決異質(zhì)化全局飛行流量協(xié)同優(yōu)化問題上優(yōu)于NSGA-Ⅱ，可以找到更優(yōu)的航班飛行路徑和飛行時間，使得空中交通擁堵和航班飛行延誤更低。就收斂性而言，DA-MOGA明顯優(yōu)于其他2種算法，這表明動態(tài)自適應算子及交叉變異概率動態(tài)調(diào)整機制可以有效改善算法局部搜索能力。

表3給出了3種算法在分別考慮效率優(yōu)先和安全優(yōu)先情況下，得到的Pareto最優(yōu)解的目標函數(shù)值，并給出了DA-MOGA較MOGA和NSGA-Ⅱ算法在總體飛行延誤代價和空中交通擁堵2個目標函數(shù)值的減少程度。

表2 主要性能評價指標對比

在效率優(yōu)先情況下，DA-MOGA空中交通擁堵分別較MOGA和NSGA-Ⅱ算法減少了1.81%和14.82%，總體飛行延誤代價降低了12.79%和25.38%；在安全優(yōu)先情況下，DA-MOGA空中交通擁堵分別減少了1.22%和10.88%，總體飛行延誤代價降低了17.78%和30.41%。這表明DA-MOGA在解決空域扇區(qū)網(wǎng)絡飛行流量協(xié)同優(yōu)化問題上，可以有效降低軍民航總體飛行延誤代價、減少全局空中交通擁堵，這也從另一個方面表明，動態(tài)自適應算子及交叉變異概率動態(tài)調(diào)整機制發(fā)揮了重要作用，有效印證了DA-MOGA的正確性和有效性。

DA-MOGA是基于傳統(tǒng)MOGA改進而來的，兩者最大的區(qū)別在于動態(tài)自適應算子的使用，由于其時間復雜度遠小于遺傳操作復雜度，因而其時間和空間復雜度與傳統(tǒng)MOGA基本保持不變。DA-MOGA總的時間復雜度是O(N(|F|+|T|+N))，空間復雜度是O(N|T||F|)。其中，N為種群規(guī)模，|T|為全局優(yōu)化時隙總數(shù)。具體各步驟時間復雜度見表4。

為了更好地對比和評價3種算法的性能，圖1給出了在目標空間下3種算法經(jīng)過25次獨立實驗所獲得Pareto前沿，從中同樣可看出，DA-MOGA得到的非支配解明顯優(yōu)于NSGA-Ⅱ算法和MOGA。

圖2展示了隨著進化代數(shù)的增加，交叉和變異概率逐漸趨于收斂。

圖3展示了αcmi(2<αcmi<4)在不同取值條件下Pareto前沿面對比情況，可以看出過大或過小αcmi容易導致空中交通擁堵和總體延誤代價過度增大，從而無法得到較優(yōu)的Pareto面；當αcmi在取值區(qū)間向中點收斂過程中，所得Pareto面逐漸優(yōu)化；αcmi=3所得Pareto面明顯優(yōu)于其他解。這也反映了過于側重軍航飛行活動或過于側重民航飛行活動均無法得到全局飛行流量調(diào)控的整體最優(yōu)，而適中的軍民航飛行活動對比權重，即兼顧彼此的軍民融合更有益于全局的協(xié)同優(yōu)化，這也從一個側面印證了軍民融合、有機聯(lián)動的重要性。

表3 3種算法目標函數(shù)值對比

表4 DA-MOGA時間復雜度

圖1 3種算法Pareto前沿對比Fig.1 Comparison of pareto Front among three algorithms

圖2 DA-MOGA交叉、變異概率進化趨勢Fig.2 Evolutionary trend of crossover and variation probability for DA-MOGA

圖3 不同αcmi下的Pareto前沿對比Fig.3 Comparison of Pareto front at different αcmi

4 結 論

隨著航空業(yè)的快速發(fā)展以及軍事航空需求的不斷拓展，如何在國家空域運行全局，即軍民航飛行活動的共同安全與效益的全局中取得更好平衡以推進軍民融合深度發(fā)展，是本文研究的出發(fā)點和落腳點，主要創(chuàng)新有：

1) 設計了一種基于軍民航異質(zhì)化飛行活動管制要求、考慮差異化調(diào)配方法與代價、兼顧軍民航管制員各自工作特點、有效解決扇區(qū)網(wǎng)絡運行安全性和經(jīng)濟性問題的全局飛行流量多目標協(xié)同優(yōu)化模型。

2) 提出了一種動態(tài)自適應多目標遺傳算法(DA-MOGA)，考慮種群聚集距離及其多樣性，設計了算法交叉和變異概率自適應變化機制，實驗證明在Pareto前沿面和綜合性、收斂性等指標方面均優(yōu)于2種經(jīng)典遺傳算法。

考慮到軍航飛行活動穿越航路航線給民航飛行帶來的特定影響，基于軍民融合的全局飛行流量協(xié)同優(yōu)化后續(xù)研究中，將進一步深化研究軍航飛行活動對民航航路航線影響，以求更加科學、有效、精細化地調(diào)配空域資源。