基于航跡運行模式的航空器航跡優(yōu)化模型

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

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

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

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

　　1 巡航階段航跡規(guī)劃模型 1.1 建模思路

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

　　1.2 基本假設

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

　　1.3 模型參數(shù)

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

　　1.4 雙目標優(yōu)化模型

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

　　1.5 模型求解

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

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

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

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

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

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

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

　　2.2 算法比較

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

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

　　3 結論

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