基于混合模擬退火算法的機場進場程序優化

陳 昇，周 雋，2*，胡小兵，馬 霽，2

（1.中國民航大學中歐航空工程師學院，天津 300300；2.中國民航大學中法聯合空管應用數學研究中心，天津 300300；3.中國民航大學電子信息與自動化學院，天津 300300）

0 引言

機場終端區作為空中交通運輸的起點和終點，是最為復雜的空域類型之一，同時也是保證航班高效有序運行的關鍵環節。目前，由于終端區空域容量飽和，國內外許多大型機場都面臨航班延誤的問題，只有突破機場終端區空域的容量瓶頸，才能保障民航運輸的穩健發展。傳統的終端區擴容方式以新建機場和跑道為主，需要投入大量的人力物力且工期較長。此外，也可以通過合理設計機場進離場程序來從戰略層面提升空域資源利用率，進而達到提升終端區容量的目的。相比之下，后者具有成本較低、易實施的優勢。區域導航RNAV（Rules for implementation of area NAVigation）是一種新興的導航規范［1］，與傳統導航方式相比具有導航精度高、航路規劃較靈活等優勢，尤其適用于機場終端區空域的程序設計。

當前絕大部分機場進離場程序是根據機場地理位置和周邊環境，以國際民航組織文件DOC8168-POS/611 為標準，通過人工設計并借助計算機輔助軟件繪制完成的［2-3］，設計過程比較耗時，且方案的有效性大多取決于人員經驗，缺乏對于路徑長度等指標的定量分析。特別是對于吞吐量較大的機場，進場程序通過逐步匯聚的方式將交通流由終端區邊界的多個進場點逐步引導至最終進近點（Final Approach Fix，FAF）。進場程序的匯聚構型與航路匯聚順序、組合方式及匯聚點位置緊密相關。鑒于其拓撲結構的復雜性，單純基于經驗進行人工設計很難充分發揮終端區的空域資源優勢，因此，借助優化算法進行自動化的程序設計可以為程序設計人員提供必要的決策支持，提高設計效率，并且有利于從戰略層面優化終端區空域資源配置。

進場程序的優化屬于路徑規劃問題的范疇［4-5］。按照空間維度可以將相關研究劃分為二維和三維，按照路徑數量又可以劃分為單一路徑和多條路徑。二維層面的研究成果比較豐富［6-9］，研究關鍵點在于對障礙物的建模方式以及規避障礙物的路徑搜索算法。例如，文獻［6］將障礙物建模成二維凸包，通過順時針或逆時針轉彎的方式規避障礙物，并應用遺傳算法搜索最短航路。二維層面的路徑規劃不符合終端區內航空器的實際運行特點，因此需要對模型和算法進行三維的拓展［10-12］。文獻［11］對航路及障礙物進行了三維建模，提出了順時針轉彎、逆時針轉彎、保持飛行高度三種障礙物規避方式，并應用了分支定界法對一條進離場程序進行優化。文獻［12］應用改進的遺傳算法對一條三維的無人機路徑進行規劃，并采用三次B 樣條曲線對規劃出的路徑進行平滑，算法具有較好的環境適應性。三維空間的多條路徑規劃問題復雜度較高，相關研究還比較有限［13-14］。文獻［13］提出了基于A*算法的多條進離場程序優化，考慮了包括最大最小爬升及下降角度、平滑轉彎等航空器的運行約束。文獻［14］在文獻［11］的基礎上增加了多條程序間最小安全間隔的約束，并應用改進的分支定界法設計多條進離場程序。

進場程序匯聚結構的優化對于大型機場有重要意義。當前國內對于航路匯聚的研究側重于點匯聚進近程序的設計和風險評估［15-16］，以及交匯航路的交通流特征研究［17］，國外的相關研究也比較有限［18-20］。文獻［18］通過改變航路匯聚方式及匯聚點位置構造不同的匯聚結構，并測試其對空域容量的影響。文獻［19］將二維空域進行網格化劃分，在考慮規避障礙物、最大航向角改變量等約束下，建立整數規劃模型進而生成具有匯聚結構的多條二維進場程序。文獻［20］對進離場程序進行三維建模，每條程序由一條水平面的折線和豎直平面的扇形區域構成，考慮了障礙物規避和航路間安全間隔的約束，應用模擬退火算法優化進離場程序的匯聚和發散結構。

雖然針對航空器的路徑規劃問題已經進行了諸多研究，但仍然存在以下兩點不足：

1）進場程序的模型沒有充分考慮同一航路上各航空器下降角度不同的特點；

2）多條進場程序的優化，尤其是針對其三維匯聚結構的優化研究仍有待拓展。

本文針對上述問題，首先結合RNAV 的導航規范及航空器在豎直平面內下降角度的特點，建立單一的進場程序三維模型；在此基礎上以最小化進場程序總長度為目標，以障礙物規避、進離場程序間安全間隔、航向角改變量為主要限制條件，建立完整的數學模型。其次，開發了一種基于模擬退火算法與改進A*算法的混合啟發式算法，其中模擬退火算法用于控制解空間的搜索過程，即確定與進場程序匯聚構型相關的決策變量取值；改進A*算法用于搜索鄰域最優解，即求解與決策變量相應的總長度最短的匯聚構型。最終仿真實驗驗證了本文模型和算法的有效性。

1 進場程序匯聚結構模型

首先建立單一的進場程序三維模型，在此基礎上提出關于多條進場程序匯聚結構的決策變量；其次給出所需考慮的約束條件及相應的數學表達式；最后明確優化問題的目標函數。

1.1 單一進場程序三維模型

單一進場程序的三維模型由水平平面分量與豎直平面分量組成。在水平平面，程序的投影為一條連接一系列散點的折線，起點為一個進場航路點，終點為FAF，中間散點為航路匯聚點或導航點。連接兩個相鄰散點的直線段在實際運行中對應一個點對點的直飛航路段，滿足RNAV 的導航規范。在豎直平面，由于航空器的性能差異和外界環境的影響（風向、風速等），同一航路上的不同航空器有不同的下降角度。因此將進場程序在豎直平面建模成由最大下降角αmax，LD和最小下降角αmin，LD所包圍的類似扇形區域，如圖1（a）中的陰影部分所示。程序水平分量上的任意一點p對應豎直分量上的一個高度區間[hp，inf，hp，sup]（如式（1）、（2）所示）：

其中：hFAF表示FAF 點的高度；d(p，FAF)表示點p到FAF 的水平面飛行距離。圖1（b）為一條進場程序的三維示意圖，其水平分量是依次連接p1、p2、p3和FAF 的一條折線，折線上任意點在豎直平面對應的高度區間構成了程序在豎直平面的分量，如圖中陰影區域所示。

圖1 進場程序建模示意圖Fig.1 Schematic diagrams of arrival procedure modeling

多條進場程序通過彼此匯聚最終收斂到FAF。圖2 所示的匯聚結構包含五條進場程序。以加粗線段所表示的進場程序為例，其水平面分量是由8 個散點{pi∪FAF|i=1，2，…，7}依序相連所組成的折線，其中p1為進場點，p3、p5、p7為匯聚點，其余為普通導航點。為便于后文表述，給出“航路段”的定義：航路水平分量上的以相鄰進場點、匯聚點或FAF 點為端點的部分折線段。令點p、q表示一個航路段的兩個端點，則將該航路段記作。

圖2 進場程序匯聚結構示意圖Fig.2 Schematic diagram of merging structure of arrival procedures

1.2 匯聚結構決策變量

多條進場程序匯聚結構的布局主要與兩方面因素相關：一方面是進場程序匯聚方式的決策，即參與匯聚的程序的組合方式和匯聚的先后順序；另一方面是由匯聚所形成的匯聚點的具體位置。為避免多條進場程序同時匯聚于一處而造成過大的管制負荷，人為地規定每次匯聚只有兩條程序參與。為了便于表示匯聚結構，以下首先介紹對進場點與匯聚點的排序標號方法，隨后提出模型的決策變量。

1.2.1 進場點與匯聚點編號

令Ne∈N+表示進場點個數，則進場點的編號由1 遞增至Ne，將進場點及其相應水平面坐標的集合記作{ei(xei，yei)，i=1，2，…，Ne}，具體的排序方式為：構造以跑道中心點P(xP，yP)為起點、以FAF 點為終點的基準向量PF，同時構造以P(xP，yP)為起點、以各進場點為終點的向量集合V={Pei|i=1，2，…，Ne}。選取V中與PF沿順時針方向夾角最小的進場點，并將其標記為1 號點，其他進場點按順時針方向夾角遞增的順序進行標號。圖2 的匯聚結構中共有5 個進場點，其編號如圖3 所示。

令Nm∈N+表示匯聚點個數，則匯聚點的編號由Ne+1遞增至Ne+Nm，將匯聚點及其相應水平面坐標的集合記作{mj(xmj，ymj)|j=1，2，…，Nm}。由于人為地規定每次匯聚只有兩條程序參與，通過簡單計算可知，匯聚點數量比進場點數量少一個，即Nm=Ne-1。在對匯聚點進行排序編號前，需要確定匯聚點所在“層數”：將進場點定義為第1 層匯聚點，將由兩個以進場點為起點的航路段匯聚所形成的匯聚點定義為第2 層匯聚點，當k≥3 時，將由以第k-1 層和第l層（l≤k-1）的兩個匯聚點為起點的航路段匯聚所形成的匯聚點定義為第k層匯聚點。匯聚點的排序首先取決于該匯聚點所在的匯聚層數，層數越小的排序越靠前；對于同層匯聚點，需要比較該匯聚點所在航路段的起始端點的標號，起始端點標號較小的匯聚點的排序靠前。圖2 的匯聚結構中共有4 個匯聚點，其標號如圖3 所示。為簡化表述，將生成第k層匯聚點所對應的匯聚過程稱為“第k層匯聚”。

圖3 進場點、匯聚點編號示意圖Fig.3 Schematic diagram of arrival points and merging points numbering

1.2.2 匯聚方式的決策

引入大小為Nr×Ne的矩陣M1以表征進場程序的匯聚過程，其中Nr為匯聚結構的層數（按1.2.1 節定義），Ne為進場點個數。矩陣M1中元素取值的集合為{0，1，…，Ne+Nm}，除0 外每個數值代表一個進場點或匯聚點的編號（按1.2.1節定義）。

同時引入含有Nr-1 個行向量的集合M2={V1，V2，…，}以表示參與匯聚航路段組合方式的決策。行向量Vi表示矩陣M1第i行中元素值所對應的進場點或匯聚點在第i+1 層匯聚中的組合方式。每個行向量中元素的取值為0 或1，分別表示以相應的進場點或匯聚點為起點的航路段不參與或參與下一層匯聚。

確定矩陣M1和集合M2中元素取值的過程實際上即是確定匯聚方式決策的過程，具體步驟如下：

1）根據進場點編號生成矩陣M1中的第一行元素，即[1，2，…，Ne]；

2）根據矩陣M1第i行中元素的取值，選擇集合M2中行向量Vi的取值；

3）根據集合M2中的行向量Vi的取值，確定矩陣M1中第i+1 行中元素的取值；

4）重復第2）～3）步直至所有進場程序全部匯聚，此時矩陣M1和集合M2中所有元素的取值確定。

其中第2）步是生成不同匯聚組合方式的關鍵步驟，具體來說：將矩陣M1的第i行中連續兩個及以上取值相同的元素歸為一組。在對Vi的第j個元素進行賦值時，假設該元素前面的j-1 個元素中有k1個“1”和k2個“0”，則當第j個元素取“0”時，表示以矩陣M1第i行中的第2k1+k2+1 個元素組對應的進場點或匯聚點為起點的航路段不參與下一層匯聚；取“1”則表示以矩陣M1第i行中的第2k1+k2+1 和2k1+k2+2 個元素組對應的進場點或匯聚點為起點的航路段在下一層匯聚。第3）步的具體實現過程為：令aij表示矩陣M1中第i行第j列元素的值，當以max({akj|k=1，2，…，i-1})為起點的航路段不參與第i層匯聚時，取aij=0；當以max({akj|k=1，2，…，i-1})為起點的航路段參與第i層匯聚時，取aij∈{Ne+1，Ne+2，…，Ne+Nm}，具體取值按1.2.1 節定義。以圖3 中的匯聚結構為例，相應的匯聚方式決策對應的矩陣，集合。

1.2.3 匯聚點位置的決策

進場程序通過匯聚結構逐漸向FAF 點收斂。根據這一特點，基于匯聚的層數及參與匯聚兩航路段起始點的位置，人為地設定每個匯聚點位置的選擇范圍，其原則是令位于較高匯聚層的點比位于較低匯聚層的點更靠近跑道。設以點A(xA，yA)、點B(xB，yB)為起點的航路段匯聚到點C(xC，yC)，且點C位于第k層匯聚，則點C水平面坐標(xC，yC)的選擇范圍為扇環?C，如圖4 所示。其中表示連接點p和點q的直線段。具體計算方法如下：

圖4 匯聚點位置的取值范圍示意圖Fig.4 Schematic diagram of value range for locations of merging points

1）計算所有進場點到FAF 的最短直線距離，記作R1=，其中表示連接FAF 點與進場點ei的直線段的長度。

2）令K1表示矩陣M1的行數，構造以FAF 為圓心的K1個同心圓，其中第j個同心圓Πj的半徑為Rj=。

3）以FAF 為圓心、RC為半徑作圓ΠC，其中RC=分別表示連接FAF 與點A、點B的線段的長度。

1.3 約束條件

機場終端區進場程序規劃需要考慮的主要限制條件包括：障礙物的規避、進離場程序間的安全間隔以及航向角的最大改變量。

1.3.1 障礙物的規避

機場終端區的障礙物包括禁飛區、山區、城市等。對于一個障礙物（包括其保護區），令Γobst表示包裹該障礙物水平面投影的最緊凸集，令hobst，inf和hobst，sup分別表示該障礙物在豎直平面高度的下確界與上確界，則該障礙物的三維模型記作Ωobst={(x，y，z)|(x，y)∈Γobst，z∈[hobst，inf，hobst，sup]}。令表示連接導航點p、q的直線段，判斷與Ωobst是否存在沖突的方法為：當時，二者不存在沖突；否則需要進一步在豎直平面檢測，若式（3）或（4）成立，則與Ωobst不存在沖突。

1.3.2 進離場程序間的安全間隔

為從戰略層面減少進離場航班流之間的潛在沖突，進離場程序間需要滿足最小安全距離，其中最小水平和豎直安全距離分別記作δH、δV。令p、q表示某進場程序上的兩個相鄰散點，令p′、q′表示某離場程序上的兩個相鄰散點，則當線段的最小距離大于δH時，二者不存在沖突；否則需要進一步驗證二者在豎直平面的相對位置關系，當式（5）或（6）成立時可以判定二者不存在沖突。

1.3.3 航向角的最大改變量

過大地改變航向角量會使航空器發生大幅度滾轉，不利于正常飛行。因此，進場程序水平分量上的任意兩個相鄰直線段對應的向量夾角應滿足式（7）：

其中：θmax為最大航向角改變量。

1.4 目標函數

考慮到匯聚后的航路段實際上由多個進場程序共同使用，因此本文的優化目標為各個航路段長度的加權和，即加權航路長，如式（8）所示：

其中：Nt表示航路段總數量；Li(i∈[1，Nt])表示第i個航路段的長度；αi表示經過第i個航路段的進場程序個數。以圖3中的匯聚結構為例，連接匯聚點6 和9 的航路段是由連接進場點1 和匯聚點6 的航路段及連接進場點2 和匯聚點6 的航路段匯聚而成的，因此該航路段對應的權值為2。

綜上所述，本問題的輸入參數為：

1）機場跑道中心點坐標P(xP，yP)；

2）FAF 點坐標及高度hFAF；

3）進場點坐標集合{ei(xei，yei)，i=1，2，…，Ne}；

4）進場程序最大、最小下降角度：αmax，LD、αmin，LD；

5）離場程序構型；

6）機場終端區內障礙物信息；

7）進離場程序間最小水平、豎直間隔：δH、δV；

8）最大航向角改變量θmax。

進場程序匯聚結構模型可表示為：

對本問題的求解可分解為兩個關鍵子問題：第一個子問題是求解合理的匯聚方式決策和匯聚點位置決策，這是一個典型的組合優化問題。其中，匯聚點位置決策的組合數量隨進場程序數量呈指數增長。第二個子問題是在已知匯聚方式和匯聚點決策后，求解滿足約束條件的最優路徑，這是一個典型的路徑規劃問題，其求解難度在于如何在三維空間處理路徑規劃的多個約束條件。

2 算法實現

根據對數學模型的分析，規劃進場程序的匯聚結構首先需要搜索合理的決策變量組合，其次要針對給定的決策變量構造滿足約束條件的最短航路。對于決策變量的求解，確定性算法（例如分支定界法）能夠收斂到全局最優解，但在類似問題的應用中，其計算效率較低。例如，文獻［19］建立了進場程序匯聚結構的二維整數規劃模型，并應用分支定界法求解。當進場程序數量為4 時，根據不同的目標函數，其最短和最長計算耗時分別為993 s 和9 447 s。隨著數學模型擴展到三維空間、進場程序數量和匯聚點備選位置數量的進一步增加，分支定界法的計算耗時將顯著增長。與確定性算法相比，啟發式算法具有一定隨機性，但是能夠在合理的計算時間內提供比較優質的解。因此，為了在提升計算效率的同時得到比較滿意的解，本文提出了基于模擬退火算法與改進A*算法的混合優化方法。其中，模擬退火算法用于控制對決策變量組合解空間的搜索；對于每一個模擬退火算法的鄰域解，改進A*算法用于逐段計算滿足限制條件的最優航路段，進而獲得與決策變量相對應的進場程序匯聚結構。

2.1 模擬退火算法

模擬退火算法借鑒了對固體物質進行退火處理的過程。以控制參數T模擬固體溫度，每一個溫度階梯需進行K次迭代，將初始溫度、終止溫度和溫度衰減系數分別記作T0、Tf、β。在求解過程中，每個解X相應的成本函數記作F(X)。每次迭代基于當前解Xcur生成新的鄰域解Xnew，并比較F(Xcur)與F(Xnew)。若F(Xnew)

本文提出的模擬退火算法中的每一個當前解Xcur包含著一組匯聚方式決策和匯聚點位置決策的組合。在生成Xcur的過程中：第一步應生成匯聚方式的決策，并在此基礎上確定匯聚結構中匯聚點的數量及每一條進場程序由進場點起按序所經過的每一個匯聚點（見1.2.2 節）；第二步再生成相應的匯聚點位置決策，即確定每一個匯聚點的坐標（見1.2.3 節）。隨后，應用改進A*算法（見2.2 節）逐段計算每條進場程序上連接相鄰進場點、匯聚點、FAF 的航路段最優構型，并根據式（8）計算相應的加權航路長，記作F(Xcur)。

基于當前解Xcur生成鄰域解Xnew是模擬退火算法的核心內容，也是算法遍歷決策變量組合解空間的關鍵。解Xcur的品質主要取決于兩方面：一方面是航路匯聚方式是否合理；另一方面是匯聚決策不變時，匯聚點位置選擇是否仍能改進。因此，在本文提出的模擬退火算法中，為了避免上述不合理的決策變量組合，構造了“匯聚方式修正算子”和“匯聚點位置修正算子”，分別用來檢測相應決策變量的合理性并予以必要的修正。每次迭代以概率P0執行匯聚方式修正算子，以概率(1-P0)執行匯聚點位置修正算子，進而基于當前解Xcur生成鄰域解Xnew。兩個算子的具體運算過程如下。

2.1.1 匯聚方式修正算子

不合理的匯聚方式會導致不同進場程序的航路段間發生交叉，如圖5（a）中虛線圓圈標識的區域所示；或導致某段航路為規避沖突而大幅度繞彎，如圖5（b）中連接2 號進場點和6 號匯聚點的航路段所示。上述情況均不利于飛行員操作及空管員管理，應盡量避免。因此，對于每個當前解Xcur，首先執行航路交叉的檢測和標記：對于當前解Xcur的進場航路段進行逐對逐段檢測，若發生航路段交叉，則將這兩條航路段的兩個端點分別標記1 次。若不存在航路交叉，則執行航路段弧弦比的檢測和標記，其中弧弦比是指某航路段的實際長度與連接其兩個端點的直線段的長度的比值。逐段計算當前解Xcur中每條進場程序上各航路段的弧弦比，當比值大于閾值ε1時，對相關的航路段的兩個端點標記1 次。檢測完成后，選取被標記次數最多的進場點或匯聚點，在Xnew的決策向量集合M2，new中修改與該點相關的決策方式。若兩種情況均不存在，則隨機選擇Xcur的決策向量集合M2，cur中的一個向量，從該向量起進行微調，生成新的M2，new。最后，根據M2，new中元素取值的改變重新生成相應的匯聚點位置決策。

圖5 不合理的匯聚方式的示意圖Fig.5 Schematic diagram of unreasonable merging modes

2.1.2 匯聚點位置修正算子

當匯聚點位置不合理時，相關航路段會出現為滿足最大航向角改變量的約束而繞彎的情況。對于當前解Xcur中的每條進場程序，逐段計算各航路段上的航向角改變量的絕對值之和。若大于閾值ε2則對該航路段的兩個端點標記1 次。檢測完成后，選擇被標記次數最多的匯聚點，并在1.2.3 節中定義的相應扇環內隨機選取新的位置坐標。若未檢測出上述情況，則隨機選取一個匯聚點并改變其位置坐標。

2.2 改進A*算法

在每次模擬退火算法生成一個新的鄰域解后，相應匯聚結構中每條進場程序由進場點起到FAF 點為止按序所經過的每一個匯聚點也隨之確定。則對于每條進場程序上的每一個航路段，其兩個端點坐標已知，因此可以應用A*算法構造連接兩個端點且滿足約束條件的最優航路段。A*算法是解決最短路徑問題最常用的算法之一，一般應用于網格圖或加權圖中。為了對搜索空間進行離散化，采用二維網格覆蓋終端區在水平平面的投影，其中每一個單元格邊長記作δ。進場點、匯聚點、FAF 點及定義障礙物邊界的散點均取在二維網格的節點處。結合本問題模型的特點與求解難點，與傳統的A*算法相比，本文算法做了如下三方面改進：

1）傳統的A*算法在每次迭代中只擴展與當前最優節點直接相鄰的8 個節點，這種方法可能會導致最優路徑的航向改變過于頻繁，路徑不夠平滑且總長度較長。因此，在改進A*算法中將展點數量擴大為48 個。設當前點p的坐標為(xp，yp)，改進后的備選展點集合為，為避免在同一方向重復展點，將展點方向重復的外層點剔除。

2）傳統的A*算法主要在二維平面進行路徑規劃，改進A*算法拓展到三維空間，每個節點對應一個高度區間。以備選節點qi為例，它所對應的高度區間為，根據式（10）～（11）計算：

其中：(hp，inf，hp，sup)表示當前節點的高度區間；(αmin，LD，αmax，LD)表示進場程序的最小、最大下降角。

3）傳統的A*算法通常只考慮障礙物規避這一單一約束，改進A*算法考慮1.3 節中所有約束條件。首先是航向角改變量約束，令節點u(xu，yu)表示節點p的父節點，則向量up和pqi應滿足式（7）；其次是根據1.3.1 節的方法判斷線段是否滿足障礙物規避的約束；最后，對已知的離場程序構型進行離散化，再將離場程序上離散后的線段按照1.3.2 節的方法逐個與進行沖突檢測，以判斷是否滿足航路間隔約束。只有滿足所有約束才能對該節點進行展點。

3 仿真結果

為測試算法的有效性和運算效率，并與現有相關研究的仿真結果［19-20］進行對比，選取瑞典阿蘭達（Arlanda）機場和上海浦東機場的終端區空域布局進行仿真實驗，將機場跑道位置、進場點數量及坐標、離場程序構型作為已知參數。離場程序的模型與1.1 節中定義的進場程序模型相似。測試中，根據實際進離場航班航跡剖面圖選取進場程序最小、最大下降角分別為1°和3°，離場程序最小、最大爬升角分別為4.5°和7.5°。與模擬退火算法相關的參數如表1 所示，其他用戶設置的參數如表2 所示。在圖6～8 中，實線表示優化的進場程序，虛線和點劃線分別表示該機場實際的離場程序和進場程序，與進場點、匯聚點相鄰的數字表示其編號（按1.2.1 節定義）。所有仿真測試均在3.0 GHz 處理器，16 GB 運行內存的Windows 10 平臺運行。

表1 模擬退火算法的相關參數Tab.1 Related parameters of simulated annealing algorithm

表2 其他用戶設置參數Tab.2 Other user-defined parameters

3.1 瑞典阿蘭達機場仿真實驗

在笛卡兒坐標系中，以經緯度（58.87°N，16.73°E）為坐標原點，跑道中心點P和FAF 所對應的坐標點分別為（54，66）和（54，72）、(54，72)，FAF 高度為0。在圖6（a）和圖7（a）中，網格的單元格邊長為δ=3 n mile。

1）算例1：4 個進場點且不考慮離場程序的仿真實驗。

首先對4 個進場點且不考慮離場程序的情況進行10 次仿真實驗，仿真結果的統計數據見表3。其中第2 次實驗最終解的目標函數值最小且計算耗時最短，加權航路長度為277.02 n mile，計算耗時為127 s，相應的進場程序匯聚構型如圖6（a）所示。在相同進場點布局且不考慮離場程序的情況下，文獻［19］中的最優解如圖6（b）所示，其中網格單元的邊長為6.64 n mile，相應匯聚結構的加權航路長度為286 n mile，計算耗時為993 s。經對比，本文提出的混合模擬退火算法在航路長度上縮短了約3%，計算耗時減少了約87%。雖然文獻［19］應用了確定性算法求解，但其網格單元邊長是本文算法中的2.2 倍。因此，在相同終端區范圍內，本文算法的網格節點數量較多，為匯聚點位置的決策和A*算法的展點提文供了更多可能性，最終求得的路徑更加平滑且長度更短。文獻［20］也針對相同算例進行測試，最優解如圖6（c）所示，相應匯聚結構的加權航路長度為339 n mile，計算耗時約為3 s，雖然運算效率較高但航路長度較本文結果增加了22%。通過對比可見，本文提出的混合模擬退火算法所規劃的路徑長度最短，計算耗時比較合理，更適合以最小化路徑長度為目標的戰略層面的進場程序設計。

表3 算例1的10次仿真結果統計Tab.3 Result statistics of 10 simulations of example 1

圖6 算例1仿真結果的示意圖Fig.6 Schematic diagrams of simulation results of example 1

2）算例2：4 個進場點且考慮離場程序的仿真實驗。

將阿蘭達機場實際離場程序作為已知參數，構造進場程序匯聚結構，此時需要考慮進離場程序間的最小安全距離的約束。進行10 次仿真實驗，仿真結果的統計數據見表4。其中，最短的加權航路長度為280.26 n mile，相應的進場程序匯聚構型如圖7（a）所示。通過與圖6（a）的進場程序結構對比發現，由于考慮航路安全間隔約束，連接3 號進場點和5 號匯聚點的航路段為規避終端區東部的離場程序而發生轉彎繞飛，使得3 號進場程序長度增加。此時3 號進場程序與東部的離場程序不存在三維沖突，如圖7（b）所示。類似地，4 號進場程序與終端區北部的離場程序在水平面相交，但二者在豎直平面滿足最小安全間隔，如圖7（c）所示。與算例1仿真結果對比，在考慮離場程序時，由于問題復雜度增加，算法運行時間明顯增加。

表4 算例2的10次仿真結果統計Tab.4 Result statistics of 10 simulations of example 2

圖7 算例2仿真結果的示意圖Fig.7 Schematic diagrams of simulation results of example 2

3.2 上海浦東機場仿真實驗

在笛卡兒坐標系中，以經緯度（29.87°N，120.27°E）為坐標原點，跑道中心點P和FAF 所對應的坐標點分別為（80，81.2）和（84，72）。在圖8（a）中，網格的單元格邊長為δ=3n mile。

將浦東機場實際離場程序作為已知參數，構造進場程序匯聚結構。進行10 次仿真實驗，仿真結果的統計數據見表5。其中第4 次實驗最終解的目標函數值最小，為392.35 n mile，相應的進場程序匯聚構型如圖8（a）所示。以7 號匯聚點和9 號進場點對應的航路段的三維結構為例，它們與終端區東南部的離場程序不存在三維沖突，如圖8（b）所示。

表5 上海浦東機場的10次仿真結果統計Tab.5 Result statistics of 10 simulations of Shanghai Pudong Airport

上海浦東機場實際的進場程序如圖8（a）中灰色點劃線所示，其加權航路長為420.25 n mile；則優化后的進場程序總長度縮短了約6.6%，平均每條進場程序的長度縮短了5.6 n mile。上海浦東機場的日起降約為1 450 架次/天，則其中進場航班數量約為725 架次/天。假設每架航班完全遵循一條進場程序進行進場并著陸，則全部進場航班的總飛行長度減少了4 046 n mile/d。從經濟角度分析，這將在燃油消耗費上減少大量開支。以空客A320 機型為例，其在進場過程中的平均油耗為6 kg/km，則總的油耗減少量為4 4954 kg。以2021 年1 月發布的航油價格2.8 元/千克來計算，則優化后的進場程序相較于真實的進場程序要減少約12.6 萬元/天的燃油開銷，每年的燃油費用可節省約4 600 萬元。除了節約燃油成本外，更短的飛行距離有利于減少航空器的尾氣排放和噪聲污染。在不考慮空中交通擁堵的情況下，應用優化的進場程序，每架航空器對空域的平均占用時間降低，因此有利于提高空中交通運行效率，減輕管制員的工作負荷。

圖8 上海浦東機場的仿真結果示意圖Fig.8 Schematic diagrams of simulation results of Shanghai Pudong Airport

4 結語

本文針對機場終端區進場程序規劃的模型和算法存在的不足，首先建立了符合區域導航規范的進場程序三維模型，在豎直剖面考慮了處于同一航路的航空器在下降過程中下降角度的差異；其次，給出了表征進場程序匯聚構型的決策變量；最后，提出了基于模擬退火算法與改進A*算法的混合算法，前者主導對匯聚方式決策和匯聚點位置決策的組合優化過程，后者在前者的基礎上逐段計算符合約束的最短航路段。基于瑞典阿蘭達機場和上海浦東機場的仿真測試表明，算法針對不同的空域布局均能夠有效規劃多條具有匯聚結構的進場程序，仿真結果在航路總長度和計算耗時兩方面較現有相關研究有一定優越性。應用優化的進場程序一方面有利于在戰略層面提升終端區空域資源利用效率，另一方面有利于機場和航空公司的節能減排。在后續研究中，將進一步擴展模型和算法，實現對離場程序發散構型的規劃，提出一套完整的機場進離場程序優化方法。