基于航跡運行模式的航空器航跡優化模型

　　摘要：針對密集航空器流量與有限空域資源間的矛盾，為應對空域扇區內的容流沖突，研究航空器四維航跡規劃問題。以基于航跡運行模式為背景，以航跡規劃為核心，以總延誤時長最小和總燃油消耗量最少為目標，在滿足容流限制、安全間隔等約束條件的基礎上，構建基于航跡運行模式下巡航階段的航空器四維航跡的雙目標規劃模型。為求解模型，使用更加符合二倍體生物特性的雙鏈染色體結構和指導種群進化的先驗知識來改進標準快速非支配遺傳算法。以華北地區 05 扇區為基礎，結合航空器飛行計劃數據進行實例驗證與算法對比。研究結果表明：在優化效果方面，總延誤時長與燃油消耗較對比算法分別減少了 54.79%和 23.65%;在計算效率方面，較對比算法提升了 56.58%。模型可在有限的時間內提供兼顧時效性與經濟性并滿足管制規則的航跡規劃策略，具有明顯優勢。通過航跡規劃，優化了航空器流的過關鍵航路點的時間，在保障運行的同時提高了效益，減少了擁堵及沖突的概率，提高了空域資源的利用率。

　　關鍵詞：四維航跡;航跡規劃;雙目標優化;雙染色體;快速非支配遺傳算法

　　李萌; 初建宇; 李印鳳; 苗亞; 傅航; 傅子濤 鐵道科學與工程學報 2022-01-10

　　隨著世界各國對航空運輸需求的與日俱增，現行的空中交通管理模式和有限的空域資源已經不能滿足航空業高速發展的要求。航班延誤及空域擁堵等問題時有發生，威脅空中交通運行安全。為突破當前空管系統所處的瓶頸，在新一代空管系統中提出了基于四維航跡運行(Trajectory Based Operation，TBO)這一核心理念。TBO 是以安全、精準的管控航空器的運行為目的，參考并在空管系統內共享航空器的四維航跡(4 Dimensional Trajectory，4DT)，實現各參與方間的協同決策。四維航跡是指在航空器整個起降過程中經歷的所有點的四維坐標(時間和空間)的集合[1]。TBO 是國際民航組織最新發布的全球航行計劃中航行系統組塊升級的總目標，也符合我國民航局空管局下發的中國民航空中交通管理現代化戰略和四強空管行動方案，滿足民航業提升空管運行保障能力的需求。國內外學者針對 TBO 模式下的四維航跡規劃,從不同角度出發展開了積極地探索。DOUGUI 等[2]為了生成無沖突的 4D 軌跡集，引入了一種新的光傳播算法。CASTELLI 等[3]提出了運用關系空間數據結構和時空數據結構的概念，進行軌跡與路徑之間的戰略沖突檢測。SOLER 等[4]研究了軌跡轉換敏感環境中的 4D 軌跡規劃問題，建立了四維航跡的混合整數最優控制模型。YAN 等[5]以安全有效分配 4D 軌跡為目的，研究了全網范圍的 4D 飛行軌跡規劃問題。 GUAN 等[6]以減少總延誤和航空器的沖突數量為雙目標，建立航跡優化模型，并采用進化算法求解。 QIAN 等[7]在減少燃油成本和延誤成本的基礎上，考慮安全距離的約束，建立航空器無沖突的四維航跡優化模型，并設計最大改進分布式算法求解。DAL 等[8]以最短延誤和最小費用為目標，結合空域用戶的偏好，建立了多目標二進制整數編碼的四維航跡優化模型。SAITO 等[9]從分散航班軌跡來實現噪聲公平分配的角度，提出了兩階段航跡規劃方法。DAL 等[10]考慮利益相關者的偏好和延誤航班重新排序的優先級等約束，建立了多目標四維航跡規劃模型，并用模擬退火算法求出帕累托解。AHMED 等[11]使用三次樣條逼近方法，將四維航跡規劃模型的目標函數和約束條件表示為時間節點的狀態和控制值的函數。 SEENIVASAN 等[12]通過設置風暴空域的飛行約束，并結合運行限制，建立了航空器航跡規劃模型，并采用混合最優控制解決問題。YONG 等[13]從綠色空管的角度出發，以常規成本和溫室氣體及有害氣體等環保因素成本為目標，設計了四維航跡的綠色規劃模型，并采用 A*搜索算法和梯形并置方法來優化四維航跡。韓云祥[14]對單航空器和多航空器的航跡進行了系統規劃。公言會[15]通過柵格法和元細胞自動機建立了航路網絡優化模型并求解。周娟[16]從啟用臨時航線的角度出發得到最優航線。張陽等[17]通過改變過關鍵點的時間和高度，對預戰術階段的多空域航跡進行規劃。楊德暘[18]建立了基于飛行計劃集中處理的預戰術階段航空器航跡規劃理論。陳雨童等[19]以航路運行為對象，開展了面向受限空域的自主航跡規劃與沖突管理技術研究。在航跡規劃方面，現有研究成果主要從航路分配及微觀沖突探測等方面展開研究。為滿足空域扇區內的飛行需求，本文以達到扇區內的整體容流平衡為目的，以時效性和經濟性為優化目標，構建基于四維航跡運行的航空器航跡規劃模型，并設計帶先驗種群的雙染色體 NSGA-Ⅱ遺傳算法求解。

　　1 巡航階段航跡規劃模型 1.1 建模思路

　　空域或機場容量是指空域和機場在特定時間內可接收的最大飛機數量[20]。扇區內的航路點、航路及其容量構成了帶權重的空中交通網絡有向圖，綜合反映交通流的組成及空域限制信息。空中交通網絡如圖 1 所示，其中，p 為航路點，R 為航路，f 為流量，c 為容量。繁忙空域扇區內的流量與容量失衡問題不僅造成了空中交通網絡的擁堵，還威脅著扇區內航空器的飛行安全。針對扇區內流量過大造成的空域擁堵，本文從平衡扇區容流的角度出發，兼顧時效性與經濟性，以各個航空器的進、出扇時間作為決策變量，以總延誤時長最小及總油耗量最少為優化目標，構建宏觀層面的航空器四維航跡雙目標規劃模型，為航空器規劃進、出扇區時間，減少各航空器之間的沖突，保障扇區容流平衡。

　　1.2 基本假設

　　基于扇區復雜的空域結構及運行情況，為簡明、全面的描述問題，建立以下假設：(1)將航空器看作一個質點，處于巡航狀態;(2)各航空器按原定計劃時間進扇;(3)上游、下游扇區均處于容流平衡狀態;(4)不考慮航空器在一個扇區內的速度改變;(5)不考慮扇區內已有航空器。

　　1.3 模型參數

　　模型中的符號及其定義如表 1 所示：

　　1.4 雙目標優化模型

　　模型的目標函數及約束條件如式(1)~式(7)所示：(1)(2)(3)(4)(5)(6)(7)目標函數式(1)為時間成本目標 ，表示進扇區總延誤時長最短;目標函數式(2)為經濟成本目標 ，表示總燃油消耗量最小，以保證不同機型的航空器在飛行過程中的油耗成本;式(3)表示扇區內容量與流量平衡約束，即在時間段 內，扇區 S 內的流量需小于等于容量，且大于等于容量的 倍(為常數， )，方可在不浪費空域資源的同時保障航空器飛行安全;式(4)、式(5)分別表示進、出扇時間間隔約束，即對于進、出扇航路點相同的航空器，進、出扇區時間需滿足最小時間間隔，以減少航空器間沖突， 是與 進、出扇航路點相同的相鄰航班;式(6)表示不提前進扇約束，即航空器 規劃后的進扇區時間不能早于計劃進扇區時間;式(7)表示扇區內飛行時長約束，航空器 在扇區 正 常 飛 行 時 有 ， 而 規 劃 后 因 采 取 調 整 措 施 ， 形 成 扇 區 內 消 耗 時 長 ， 即，則扇區內飛行時長 ，故為保障運行安全及效率，需約束航空器在扇區內的飛行時長。

　　1.5 模型求解

　　相較于基本遺傳算法，多目標遺傳算法更適用于解決多個目標函數在給定解空間上的優化問題。基于本文提出的雙目標航跡規劃模型，選用快速非支配遺傳算法(NSGA-Ⅱ)進行求解。圖 2 為遺傳算法求解流程。

　　為了更好的抑制早熟，提高算法的運行速度及搜索精度，本文使用更加符合生物特性的二倍體雙鏈染色體結構并添加先驗種群，算法中的遺傳操作如下。 1) 編碼方式因問題搜索空間大且約束條件復雜，本文選用實值編碼方案。研究中把各個航空器的進扇、出扇時間換算成相較于當天 00:00:00 的時間差，并計算為分鐘，以此實值表示一個基因。另外，因問題決策變量個數較多，故以雙鏈染色體表示一個個體，其中，一條染色體表示進扇區時間，另一條則表示出扇區時間。例如，若問題中有 5 架航班，他們的進扇區時間分別為 08:00:00、08:06:00、08:10:00、08:15:00、 08:04:00，出扇區時間分別為 08:10:00、08:16:00、08:20:00、08:25:00、08:14:00，則采用實值編碼的二倍體雙鏈染色體基因型如圖 3 所示。

　　2) 遺傳算子本問題為多染色體的多目標優化問題，因此選用錦標賽選擇算子、模擬二進制交叉算子和多項式變異算子來進行遺傳操作。

　　2 實例分析 2.1 算法運行結果

　　根據華北區域 2018 年 10 月歷史飛行計劃數據，統計分析了各扇區流量，最終以 2018 年 10 月 28 日 ACC05 扇區的繁忙時段 16:00:00-16:29:59 的飛行計劃數據為基礎進行預處理，預處理步驟包括：1)在飛行計劃數據中，篩選出計劃進入 ACC05 扇區的航班信息;2)清洗掉進扇和出扇時間相同的航班信息;3)統計扇區日流量，選擇繁忙、有容流沖突的時段;4)確定航班機型、進扇區點等模型所需要的數據。

　　利用 python 進行編程，實現帶先驗種群的雙染色體 NSGA-Ⅱ算法。扇區半小時內的容量設定為 23 架次。ACC05 扇區結構如圖 4 所示，其中主要航路有 7 條，主要進扇區航路點有 3 個，分別為 ISGOD、 LARAD-B458-UBTAB、ENGIL。部分飛行計劃數據如表 2 所示。

　　圖 5 中，F1 為航空器流進扇區延誤時長，F2 為航空器流在扇區內飛行時的燃油消耗量，F1 進扇區延誤總時長的最優解集在 94-121 之間;F2 總燃油消耗量的最優解集在 11682-12783 之間。根據 1.4 節中式(1)和式(2)，進扇區延誤時間越長，規劃后進扇區時間越晚，即 的值越大，則 的值越小，即 F1 與 F2 之間具有相互抑制作用，F1 值得到優化的同時 F2 值的優化程度會減小。帕累托最優解是使 F1 和 F2 盡可能達到最優的解的集合。模型最終得出多種兼顧時效性與經濟性且符合約束條件的航跡優化策略，使決策者可結合實際情況對兩個目標函數值進行比重加權，選擇較為適當的航跡規劃方案。表 3 列出了從帕累托最優解集中選取的 9 種優化方案。

　　2.2 算法比較

　　為了驗證本算法的運行速度及優化效果，分別與差分進化算法、基本遺傳算法、單目標雙染色體基本遺傳算法和不加先驗種群的雙染色體 NSGA-Ⅱ算法進行了對比，其中，差分進化算法、基本遺傳算法和單目標雙染色體基本遺傳算法的參數設置如表 4 所示。本文算法與對比算法的進化結果如表 5 和圖 6 所示。

　　從表 5 和圖 6 可以看出，在優化效果上，本文算法的進扇區延誤時長較差分遺傳算法、基本遺傳算法和單目標雙染色體基本遺傳算法分別平均降低了 45.47%、57.77%和 61.13%，燃油消耗較差分遺傳算法、基本遺傳算法和單目標雙染色體基本遺傳算法分別平均降低了 37.19%、31.27%和 2.49%，且差分遺傳算法與基本遺傳算法因自身局限性，均產生局部收斂過快的現象。在計算速度上，本文算法較無先驗種群的雙染色體 NSGA-Ⅱ算法提升了 56.58%。綜上所述，本文采用的帶先驗種群的雙染色體 NSGA-Ⅱ算法在優化效果及運算速度方面都優于其他算法，可在較短的時間內提供多種較優的扇區內航空器航跡規劃策略，具有靈活性和適用性，降低了扇區內的航空器沖突風險，實現了空域資源合理分配及充分利用。

　　3 結論

　　1)改進的快速非支配遺傳算法在優化程度和計算效率方面得到明顯的提升，目標優化效果方面，改進的快速非支配遺傳算法較差分遺傳算法、基本遺傳算法和單目標雙染色體基本遺傳算法平均提升了 39.22%，且改進算法收斂穩定，不易陷入局部最優解;計算效率方面，改進的快速非支配遺傳算法較無先驗種群的雙染色體 NSGA-Ⅱ算法提升了 56.58%。 2)提出的模型可以在較短的時間內給出較優的策略，使航空器進扇區延誤總時長和扇區飛行的燃油消耗總量均達到了較優的水平，給決策者提供滿足其不同偏好的調整方案，符合空中交通管理過程中的實際管制需求。