基于軍民融合的全局飛行流量協同優化方法

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

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

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

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

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

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

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

1 全局飛行流量協同優化模型

在飛行活動中，航空器一般沿著各自規劃的航線從起飛機場飛往目的機場，管制員以空域扇區為單元實施飛行管制，保證飛行活動安全、高效、有序運行。機場、扇區構成了空域運行的基本單元。由于機場運行能力和管制員工作負荷等原因，機場和扇區的容量是有限的?？罩薪煌髁烤W絡優化主要是對飛行活動中的起降時間和飛行路徑進行調控，以達到網絡運行經濟性和安全性的整體最優。

1.1 目標函數

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

1.1.1 空中交通擁堵

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

(1)

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

(2)

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

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

1.1.2 總體飛行延誤代價

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

(3)

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

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

1.2 約束條件

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

1.2.1 空域容量約束

空域扇區網絡中的各機場和扇區節點應全程滿足容量要求，即

(4)

1.2.2 起飛時間約束

(5)

1.2.3 軍航特殊任務約束

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

(6)

1.2.4 飛行距離約束

(7)

2 動態自適應多目標遺傳算法

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

2.1 算法框架

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

(8)

(9)

式中：|F|為飛行活動總數。

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

2.2 動態自適應算子

2.2.1 種群平均聚集距離

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

(10)

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

2.2.2 種群多樣性

種群多樣性為

(11)

2.3 交叉變異概率動態調整機制

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

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

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

(12)

(13)

(14)

(15)

3 實驗驗證

為了評價全局飛行流量協同優化模型和動態自適應多目標遺傳算法的有效性，本節利用中國扇區網絡的實際數據進行對比實驗。

3.1 實驗數據及參數設置

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

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

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

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

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

表1 算法主要參數取值

3.2 實驗結果與對比分析

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

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

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

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

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

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

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

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

表3 3種算法目標函數值對比

表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 結 論

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

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

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

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