李萌，初建宇，李印鳳,2，苗亞，傅航，傅子濤

(1. 華北理工大學 建筑工程學院，河北 唐山 063210；2. 中國電子科技集團第二十八研究所 空中交通管理系統(tǒng)與技術國家重點實驗室，江蘇 南京 210007；3. 中國民用航空局空中交通管理局 運行管理中心，北京 100022；4. 中國民用航空華北地區(qū)空中交通管理局 通信網絡中心，北京 100621)

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

1 巡航階段航跡規(guī)劃模型

1.1 建模思路

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

1.2 基本假設

基于扇區(qū)復雜的空域結構及運行情況，為簡明、全面的描述問題，建立以下假設：

1) 將航空器看作一個質點，處于巡航狀態(tài)；

2) 各航空器按原定計劃時間進扇；

3) 上游、下游扇區(qū)均處于容流平衡狀態(tài)；

4) 不考慮航空器在一個扇區(qū)內的速度改變；

5) 不考慮扇區(qū)內已有航空器。

1.3 模型參數

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

表1 模型中符號定義Table 1 Symbol definition in the model

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

模型的目標函數及約束條件如式(1)～(7)所示：

目標函數式(1)為時間成本目標f1，表示進扇區(qū)總延誤時長最短；目標函數式(2)為經濟成本目標f2，表示總燃油消耗量最小，以保證不同機型的航空器在飛行過程中的油耗成本；式(3)表示扇區(qū)內容量與流量平衡約束，即在時間段Ti內，扇區(qū)S內的流量需小于等于容量，且大于等于容量的μ倍(μ為常數，μ＜1)，方可在不浪費空域資源的同時保障航空器飛行安全；式(4)和式(5)分別表示進、出扇時間間隔約束，即對于進、出扇航路點相同的航空器，進、出扇區(qū)時間需滿足最小時間間隔，以減少航空器間沖突，fm+1是與fm進、出扇航路點相同的相鄰航班；式(6)表示不提前進扇約束，即航空器fa規(guī)劃后的進扇區(qū)時間不能早于計劃進扇區(qū)時間；式(7)表示扇區(qū)內飛行時長約束，航空器fa在扇區(qū)正常飛行時有tda=taa+la/va，而規(guī)劃后因采取調整措施，形成扇區(qū)內消耗時長Δt，即t′da=t′aa+la/va+Δt，則扇區(qū)內飛行時長Δt′=la/va+Δt，故為保障運行安全及效率，需約束航空器在扇區(qū)內的飛行時長。

1.5 模型求解

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

為了更好地抑制早熟，提高算法的運行速度及搜索精度，本文使用更加符合生物特性的二倍體雙鏈染色體結構并添加先驗種群，算法中的遺傳操作如下。

1) 編碼方式

因問題搜索空間大且約束條件復雜，本文選用實值編碼方案。研究中把各個航空器的進扇、出扇時間換算成相較于當天00:00:00的時間差，并計算為分鐘，以此實值表示一個基因。另外，因問題決策變量個數較多，故以雙鏈染色體表示一個個體，其中，一條染色體表示進扇區(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 算法運行結果

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

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

表2 部分飛行計劃數據Table 2 Partial flight plan data sheet

遺傳算法中設置最大進化代數為500，種群規(guī)模為60。算法進化的帕累托解集如圖5所示。

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

表3 進、出扇區(qū)時間優(yōu)化方案Table 3 Optimization scheme of inbound and outbound sector time

2.2 算法比較

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

表4 對比算法參數設置Table 4 Compare algorithm parameter settings

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

表5 本文算法與無先驗種群的雙染色體NSGA-Ⅱ算法運行速度對比Table 5 Running speed of the proposed algorithm is compared with that of the two-chromosome NSGA-Ⅱalgorithm without prior population

3 結論

1) 改進的快速非支配遺傳算法在優(yōu)化程度和計算效率方面得到明顯的提升，目標優(yōu)化效果方面，改進的快速非支配遺傳算法較差分遺傳算法、基本遺傳算法和單目標雙染色體基本遺傳算法平均提升了39.22%，且改進算法收斂穩(wěn)定，不易陷入局部最優(yōu)解；計算效率方面，改進的快速非支配遺傳算法較無先驗種群的雙染色體NSGA-Ⅱ算法提升了56.58%。

2) 提出的模型可以在較短的時間內給出較優(yōu)的策略，使航空器進扇區(qū)延誤總時長和扇區(qū)飛行的燃油消耗總量均達到了較優(yōu)的水平，給決策者提供滿足其不同偏好的調整方案，符合空中交通管理過程中的實際管制需求。