機場終端區(qū)空域的多條進離場程序優(yōu)化

周 雋，谷升豪

(1.中國民航大學 中歐航空工程師學院，天津 300300；2.中國民航大學 中法聯(lián)合空管應用數(shù)學研究中心，天津 300300)

0 引 言

機場終端區(qū)是最為復雜的空域之一，航班擁堵的情況在這一空域屢見不鮮。合理設計機場進離場程序能夠有效提高終端區(qū)空域利用率。所需導航性能(required navigation performance，RNP)是一種新興的導航規(guī)范，尤其適用于機場終端區(qū)這類對導航精度要求較高的空域[1]。當前絕大部分的進離場程序是根據(jù)機場地理位置和環(huán)境借助計算機輔助軟件設計的[2-4]。設計方案的有效性大多取決于人員經驗，在充分利用空域的層面仍有可提升空間。

路徑規(guī)劃類的算法可用于進離場程序優(yōu)化設計[5,6]。根據(jù)不同的空間維度可將相關研究分為二維[7-9]與三維[10,11]。二維優(yōu)化一般假設航空器處于最優(yōu)的運行高度。Pierre等應用遺傳算法計算最短航路，通過順時針或逆時針轉彎的方式規(guī)避由凸包所表示的障礙物區(qū)域[7]。馮國強等綜合運用A*算法與蟻群算法對航路進行智能規(guī)劃，以A*算法的導向性加快蟻群算法的收斂速度[8]。三維優(yōu)化更符合實際應用的需求，但相關研究比較有限。Granberg等基于網格圖對多條進場程序進行了整數(shù)規(guī)劃建模，考慮了爬升及下降角度、平滑轉彎等約束，并通過改變航向角來規(guī)避障礙物[10]。根據(jù)進離場程序數(shù)目又可分為單一程序優(yōu)化[7-9]與多條程序優(yōu)化[10,11]。多條程序優(yōu)化的難點主要在于需要滿足航路間最小安全間隔。比較常見的方法是依序逐條生成程序，將已經生成的程序作為后序程序的障礙物加以規(guī)避。Polishchuk基于RNP導航規(guī)范依序生成逐漸匯聚的進場程序[11]。綜合來看，單一的二維航路優(yōu)化復雜度較低，但是不夠貼近實際情況；而多條的三維航路優(yōu)化現(xiàn)有的研究成果較少，且在航路建模及障礙物與飛行沖突的規(guī)避方式上有待補充和改進。

綜上，本文提出一種基于改進的分支定界法的多條三維進離場程序優(yōu)化算法。在模型層面考慮了轉彎半徑、爬升角和下降角等航路實際特點；在沖突規(guī)避方式層面，除改變航向外，還提出了保持飛行高度這一方式，不但符合實際運行習慣，同時拓展了問題的解空間。最終生成的進離場程序滿足RNP導航規(guī)范，可以為程序設計人員提供有效的決策支持。

1 數(shù)學模型及單一進離場程序的優(yōu)化算法

1.1 障礙物與進離場程序建模

將機場終端區(qū)的障礙物(例如山區(qū)、禁飛區(qū)等)及其相應保護區(qū)建模為底面與水平面平行的三維圓柱體。令M∈N表示圓柱體總個數(shù)，每個圓柱體Ωj,j=1,…,M定義為(Cj(xj,yj),rj,zjinf,zjsup)，其中Cj(xj,yj)與rj分別表示Ωj兩底面的圓心與半徑，zjinf與zjsup分別表示下底面與上底面的高度。

令N∈N表示需要構建的進離場程序總個數(shù)。每個程序γi,i=1,…,N由兩部分構成：水平平面內由一系列首尾相連且彼此相切的線段和圓弧構成的光滑曲線γiH，以及豎直平面內囊括此程序上航跡剖面的近似扇形區(qū)域γiV。在水平平面，曲線γiH連接起點Ai(xAi,yAi)與終點Bi(xBi,yBi)，定義為函數(shù)：γiV

γiH:[0,1]→R2

其中，γiH(0)=(xAi,yAi)，γiH(1)=(xBi,yBi)。在豎直平面，起點Ai對應的高度為HAi，近似扇形區(qū)域γiV定義為函數(shù)

1.2 數(shù)學模型

對于給定的進離場程序γi，每個障礙物對應的三維圓柱體Ωj與兩個決策變量相關聯(lián)：sij和tij。當γi與Ωj相接觸并且用以下方式之一對Ωj進行規(guī)避：順時針轉彎、逆時針轉彎、保持當前飛行高度，則此時Ωj對γi來說是“激活的”，以決策變量sij來表示

而tij則表示了γi對Ωj的規(guī)避方式

當所有決策變量(sij,tij)j=1,…M的取值確定，與之相對應的進離場程序γi的構型隨之確定：按照圓心到該程序起始點連線的水平投影長度遞增的順序對障礙物進行排序，而后根據(jù)選取的障礙物規(guī)避方式構造航路。

航空器在機場終端區(qū)運行需要滿足諸多約束條件，包括障礙物規(guī)避、對正跑道、最大最小轉彎半徑等約束，還需額外考慮航路之間的最小安全間隔約束(水平方向3海里，豎直方向1000英尺)，這對于保證航空器安全運行至關重要。具體實現(xiàn)方法見2.2，2.3。

于是，我和同行的詩友輪流駕駛，開始聊一些家長里短，之后又轉移到工作的話題，直到太陽西沉，夜色吞沒了大地和山巒的某個瞬間，車內才突然陷入了沉默。

單一進離場程序γi對應的加權長度Lγi定義為

(1)

(2)

1.3 單一進離場程序的優(yōu)化算法

由于數(shù)學模型中決策變量的取值為整數(shù)，進離場程序優(yōu)化問題實際被建模為整數(shù)規(guī)劃問題，應用分支定界法進行解算。其分支策略是基于障礙物規(guī)避方式提出的：對于程序γi,i=1,…,N，每一個障礙物Ωj,j=1,…,M可以分出4支，分別是：不激活(sij=0)、激活且以逆時針轉彎規(guī)避(sij=1,tij=0)、激活且以順時針轉彎規(guī)避(sij=1,tij=1)、激活且以保持飛行高度規(guī)避(sij=1,tij=2)。設SP為求解進離場程序γi的分支界定法中生成的一解空間子集，其中只有部分決策變量的值確定，記作{(sij,tij)j∈J,J?{1,…,M。則SP的目標下界通過以下方式計算：將未取值的決策變量設為未激活，即{sij=0j∈(1,…,M)/J；構造相應的進離場程序，記作γiSP；根據(jù)式(1)計算其值LγiSP即為SP的目標下界。若LγiSP大于當前最優(yōu)值，則對SP進行剪枝，進而逐步縮小搜索范圍以獲得最優(yōu)解。

2 多條進離場程序的優(yōu)化算法

對于每條新生成的航路，首先檢測它是否與已生成航路發(fā)生沖突。若沖突存在，則可以通過順時針轉彎、逆時針轉彎、保持飛行高度3種不同的方式在沖突區(qū)域附近對新生成的航路進行擾動，以改變其局部結構，進而規(guī)避沖突。

2.1 方法概述

應用依序策略逐條生成進離場程序，已經生成的程序成為新生成程序的障礙物。每條程序首先應用1.3中的分支定界法生成。隨后，檢測它是否與已生成航路發(fā)生沖突。若沖突存在，則對沖突區(qū)域進行聚類分組。將每組沖突按照1.1中的障礙物模型建模成三維圓柱體，稱作“虛擬障礙物”。航路沖突的檢測、聚類以及虛擬障礙物的生成方法見2.2。當不止一個虛擬障礙物存在，按照圓心到程序起始點連線的水平投影長度遞增的順序，對它們進行排序。為解決第一個虛擬障礙物所對應的航路沖突，在沖突區(qū)域附近對當前航路進行局部擾動。然后重新應用分支定界法構建剩余部分的航路，并再一次用相同方法對剩余部分航路進行沖突檢測和解決。最終，按上述方法逐段生成進離場程序，其中每段程序均在分支定界法計算的最優(yōu)解基礎上進行局部擾動，進而保證最終解的優(yōu)越性。航路沖突解決的算法見2.3。

2.2 航路沖突檢測算法

考慮一對航路γi和γi′(i≠i′)，首先，在水平平面檢測γiH和γi′H是否存在不滿足3海里水平間隔的航路段；若存在，則針對這樣的航路段繼續(xù)在豎直平面檢測是否滿足1000英尺的豎直間隔。將同時不滿足水平間隔和豎直間隔的航路段定義為沖突航路段。

2.2.1 水平平面沖突檢測

圖1 水平平面沖突檢測示例

2.2.2 豎直平面沖突檢測

當兩個航路段同時發(fā)生水平沖突和豎直沖突，則定義二者之間存在沖突。

2.2.3 虛擬障礙物的生成方法

將存在沖突航路段的單元格定義為沖突單元格。對于沖突單元格(Ix,Iy)定義其高度的下界和上界，分別記作Zinf(Ix,Iy)和Zsup(Ix,Iy)。令I?{1,…,N}表示已經生成的航路的編號集合，并且令{γik,k+1|k∈Ki,Ki?{0,…,Ni},i∈I}表示(Ix,Iy)單元格內，與當前航路存在沖突的航路段的集合，則

2.3 航路沖突解決算法

當生成了不止一個虛擬障礙物，則說明當前航路與已生成的航路存在多處沖突，此時在第一個虛擬障礙物Ωf(Cf(xf,yf),rf,zfinf,zfsup)對應的沖突區(qū)域附近對當前航路進行局部擾動。與2.2中類似地，設sij和tij是與Ωf相關的兩個決策變量，提出3種規(guī)避Ωf的航路局部擾動方法：沿Ωf逆時針轉彎(sij=1,tij=0)、沿Ωf順時針轉彎(sij=1,tij=1)、在Ωf底面處保持飛行高度zfinf(sij=1,tij=2)?？紤]到保持飛行高度會增加油耗和污染氣體的排放，因此優(yōu)先考慮通過轉彎的方式解決沖突：當順、逆時針轉彎均可以解決沖突時，取長度較短的作為新的解；當只有其中一種方式能夠解決沖突時，直接將其設為新的解；當轉彎無法有效解決沖突時，考慮保持飛行高度的方式；若3種方式均無法解決沖突，則選擇剩余沖突最少的為新解。具體航路局部擾動方式見2.3.1，2.3.2。

2.3.1 通過轉彎實現(xiàn)的局部擾動

圖3 虛擬障礙物和輔助障礙物

2.3.2 通過保持飛行高度實現(xiàn)的局部擾動

圖4 通過轉彎方式局部擾動航路

圖5 通過保持飛行高度方式局部擾動航路

2.3.3 航路后處理方法

通過轉彎方式進行局部擾動的航路在沖突區(qū)域附近的構型由3個連續(xù)且兩兩相切的圓弧段組成，這種構型方式符合RNP的運行規(guī)范[5]。但在實際運行中，飛行員在轉彎規(guī)避沖突后，往往直接飛向下一導航點。因此，對已經生成的航路進行后處理。對于進場程序(或離場程序)，每一次通過轉彎進行的局部擾動，將虛擬障礙物之前(或之后)的輔助障礙物設為未激活，重構航路。若重構的沒有與其它航路產生新的沖突，則接受此重構航路作為新的解。

3 算例仿真

為測試算法的解算能力及運算效率，給出兩種不同的人為生成的算例。取目標函數(shù)(式(1))中懲罰系數(shù)c1=1、c2=0；取進場程序最大、最小下降角度分別為2.4°和0.92°；離場程序最大、最小爬升角度分別為6.3°和4°。所有測試均在2.4 GHz處理器，8 GB安裝內存的Linux平臺上運行。由于篇幅限制，每個算例中進離場程序的起點終點坐標，以及障礙物的相關參數(shù)取值參見鏈接https://pan.baidu.com/s/1l-U_-ZrLzgXzBcvnweq2Ew(提取碼：b3za)。

3.1 算例1

本算例考慮的是1條進場程序、1條離場程序及6個障礙物。應用分支定界法單獨生成進離場程序，并應用2.2中算法進行沖突檢測，航路構型及沖突區(qū)域如圖6所示。圖6(a)中深灰色陰影圓盤表示為使進離場程序對正跑道而人為設置的輔助障礙物，黑色圓圈表示實際障礙物；圖6(a)、圖6(b)中的淺灰色區(qū)域表示進離場程序的初始沖突區(qū)域。應用2.3中算法解決航路沖突，進行兩次測試，測試1優(yōu)先生成離場程序(仿真結果如圖7(a)、圖7(c)、圖7(e)，測試2優(yōu)先生成進場程序(仿真結果如圖7(b)、圖7(d)、圖7(f)。數(shù)值結果見表1。每個測試耗時約為0.5 s。兩個測試均可以解決航路間的沖突。

測試1中通過生成包裹沖突區(qū)域的虛擬障礙物及相應輔助障礙物(圖7(c)中虛線圓圈)，并且令進場程序沿此虛擬障礙物逆時針轉彎，可以有效解決航路間沖突。隨后應用2.3.3中方法對獲得的進場程序進行后處理以減少不必要的轉彎(如圖7(c)所示)。另外，由圖7(e)可見，局部擾動后的進場程序此時在離場程序的下方通過，有效地規(guī)避了原有的沖突。類似地，測試2中對離場程序進行局部擾動，使得航路長度邊長，相應的豎直平面內飛行高度增加，因此進場程序可以從下方通過，規(guī)避了原有的沖突(如圖7(f)所示)。通過比較兩個測試的數(shù)值結果可見，測試2的航路總長度更短，這說明改變航路生成順序對解的質量有一定影響。

圖6 算例1原始進離場程序及沖突區(qū)域

圖7 算例1仿真結果

表1 算例1數(shù)值結果

3.2 算例2

本算例考慮的是2條離場程序(圖8(a)中的γ1，γ2)、3條進場程序(圖8(a)中的γ3，γ4，γ5)及9個障礙物。應用分支定界法單獨生成的進離場程序及原始沖突區(qū)域如圖8所示。圖中輔助障礙物、實際障礙物與初始沖突區(qū)域的表示方法與圖6相同。應用沖突解決算法的仿真結果如圖9所示。進離場程序按標號遞增的順序逐一生成。其中γ2以順時針轉彎的方式規(guī)避它與γ1的沖突；γ3與γ1、γ2均無沖突，因此無需調整；γ4以保持飛行高度的方式規(guī)避與γ1的沖突，保持飛行高度航段如圖9(a)虛線部分所示，航路構型的剖面圖如圖9(c)所示；γ5分別以順時針、逆時針轉彎的方式規(guī)避它與γ2、γ3的沖突。所有虛擬與輔助障礙物如圖9(b)所示。最終所有沖突得以解決。數(shù)值結果見表2。測試耗時約為1.1 s。

圖8 算例2原始進離場程序及沖突區(qū)域

圖9 算例2仿真結果

表2 算例2數(shù)值結果

4 結束語

本文結合機場周邊環(huán)境、空域限制因素，提出了機場終端區(qū)空域多條進離場程序的優(yōu)化設計算法。首先，對進離場程序及障礙物進行了三維建模，模型符合RNP導航規(guī)范。其次，開發(fā)了適用于三維模型的沖突檢測及沖突解決算法。對于存在沖突的程序給出順、逆時針轉彎、保持飛行高度3種不同的沖突解決策略，符合空管和飛行員的日常操作習慣。算法基于經典的分支定界法進行改進，以保證最終解的優(yōu)越性。仿真結果表明，在復雜障礙物布局下，算法能夠高效地解算出多條無沖突且符合RNP規(guī)范的進離場程序，可以為實際進離場程序設計提供有效的決策支持。