周 雋，谷升豪

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

0 引 言

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

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

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

1 數(shù)學(xué)模型及單一進(jìn)離場(chǎng)程序的優(yōu)化算法

1.1 障礙物與進(jìn)離場(chǎng)程序建模

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

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

γiH:[0,1]→R2

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

1.2 數(shù)學(xué)模型

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

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

當(dāng)所有決策變量(sij,tij)j=1,…M的取值確定，與之相對(duì)應(yīng)的進(jìn)離場(chǎng)程序γi的構(gòu)型隨之確定：按照?qǐng)A心到該程序起始點(diǎn)連線的水平投影長(zhǎng)度遞增的順序?qū)φ系K物進(jìn)行排序，而后根據(jù)選取的障礙物規(guī)避方式構(gòu)造航路。

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

于是，我和同行的詩(shī)友輪流駕駛，開(kāi)始聊一些家長(zhǎng)里短，之后又轉(zhuǎn)移到工作的話題，直到太陽(yáng)西沉，夜色吞沒(méi)了大地和山巒的某個(gè)瞬間，車(chē)內(nèi)才突然陷入了沉默。

單一進(jìn)離場(chǎng)程序γi對(duì)應(yīng)的加權(quán)長(zhǎng)度Lγi定義為

(1)

(2)

1.3 單一進(jìn)離場(chǎng)程序的優(yōu)化算法

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

2 多條進(jìn)離場(chǎng)程序的優(yōu)化算法

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

2.1 方法概述

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

2.2 航路沖突檢測(cè)算法

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

2.2.1 水平平面沖突檢測(cè)

圖1 水平平面沖突檢測(cè)示例

2.2.2 豎直平面沖突檢測(cè)

當(dāng)兩個(gè)航路段同時(shí)發(fā)生水平?jīng)_突和豎直沖突，則定義二者之間存在沖突。

2.2.3 虛擬障礙物的生成方法

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

2.3 航路沖突解決算法

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

2.3.1 通過(guò)轉(zhuǎn)彎實(shí)現(xiàn)的局部擾動(dòng)

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

2.3.2 通過(guò)保持飛行高度實(shí)現(xiàn)的局部擾動(dòng)

圖4 通過(guò)轉(zhuǎn)彎方式局部擾動(dòng)航路

圖5 通過(guò)保持飛行高度方式局部擾動(dòng)航路

2.3.3 航路后處理方法

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

3 算例仿真

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

3.1 算例1

本算例考慮的是1條進(jìn)場(chǎng)程序、1條離場(chǎng)程序及6個(gè)障礙物。應(yīng)用分支定界法單獨(dú)生成進(jìn)離場(chǎng)程序，并應(yīng)用2.2中算法進(jìn)行沖突檢測(cè)，航路構(gòu)型及沖突區(qū)域如圖6所示。圖6(a)中深灰色陰影圓盤(pán)表示為使進(jìn)離場(chǎng)程序?qū)φ艿蓝藶樵O(shè)置的輔助障礙物，黑色圓圈表示實(shí)際障礙物；圖6(a)、圖6(b)中的淺灰色區(qū)域表示進(jìn)離場(chǎng)程序的初始沖突區(qū)域。應(yīng)用2.3中算法解決航路沖突，進(jìn)行兩次測(cè)試，測(cè)試1優(yōu)先生成離場(chǎng)程序(仿真結(jié)果如圖7(a)、圖7(c)、圖7(e)，測(cè)試2優(yōu)先生成進(jìn)場(chǎng)程序(仿真結(jié)果如圖7(b)、圖7(d)、圖7(f)。數(shù)值結(jié)果見(jiàn)表1。每個(gè)測(cè)試耗時(shí)約為0.5 s。兩個(gè)測(cè)試均可以解決航路間的沖突。

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

圖6 算例1原始進(jìn)離場(chǎng)程序及沖突區(qū)域

圖7 算例1仿真結(jié)果

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

3.2 算例2

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

圖8 算例2原始進(jìn)離場(chǎng)程序及沖突區(qū)域

圖9 算例2仿真結(jié)果

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

4 結(jié)束語(yǔ)

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