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

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

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

　　李萌; 初建宇; 李印鳳; 苗亞; 傅航; 傅子濤 鐵道科學(xué)與工程學(xué)報(bào) 2022-01-10

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

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

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

　　1.2 基本假設(shè)

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

　　1.3 模型參數(shù)

　　模型中的符號(hào)及其定義如表 1 所示：

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

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

　　1.5 模型求解

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

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

　　2) 遺傳算子本問(wèn)題為多染色體的多目標(biāo)優(yōu)化問(wèn)題，因此選用錦標(biāo)賽選擇算子、模擬二進(jìn)制交叉算子和多項(xiàng)式變異算子來(lái)進(jìn)行遺傳操作。

　　2 實(shí)例分析 2.1 算法運(yùn)行結(jié)果

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

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

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

　　2.2 算法比較

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

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

　　3 結(jié)論

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