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

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

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

隨著世界各國(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 軌跡集，引入了一種新的光傳播算法。RUIZ 等[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]使用3 次樣條逼近方法，將四維航跡規(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)題。TIAN 等[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(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 模型中符號(hào)定義Table 1 Symbol definition in the model

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

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

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

1.5 模型求解

相較于基本遺傳算法，多目標(biāo)遺傳算法更適用于解決多個(gè)目標(biāo)函數(shù)在給定解空間上的優(yōu)化問(wèn)題?；诒疚奶岢龅碾p目標(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所示。

表2 部分飛行計(jì)劃數(shù)據(jù)Table 2 Partial flight plan data sheet

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

圖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)解集在11 682～12 783 之間。根據(jù)式(1)和式(2)，進(jìn)扇區(qū)延誤時(shí)間越長(zhǎng)，規(guī)劃后進(jìn)扇區(qū)時(shí)間越晚，即t′aa的值越大，則(t′da-t′aa)的值越小，即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ì)2個(gè)目標(biāo)函數(shù)值進(jìn)行比重加權(quán)，選擇較為適當(dāng)?shù)暮桔E規(guī)劃方案。表3列出了從帕累托最優(yōu)解集中選取的9種優(yōu)化方案。

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

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所示。

表4 對(duì)比算法參數(shù)設(shè)置Table 4 Compare algorithm parameter settings

從表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)了空域資源合理分配及充分利用。

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

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í)際管制需求。