基于點融合的多跑道進場航班排序*

王 寧 翟文鵬

（中國民航大學空中交通管理學院 天津 300300）

0 引 言

點融合系統(tǒng)（point merge system，PMS）是基于性能導航技術與雷達管制相結合在空域和飛行程序方面的集成應用，主要用于解決進場交通流匯聚問題并優(yōu)化間隔管理。相較于標準儀表進場程序的雷達引導過程，PMS的引入主要簡化了管制員指揮調度的指令，然而進場效率的提升從根本上依然需要進場排序和調度的研究為管制員提供有效的航班序列作為支持，所以針對在PMS運行的基礎上的航班進場排序與調度開展相關研究對于終端區(qū)空域效率有重要意義。

Liang等[1-3]率先針對PMS的進場航班排序展開相關研究，設計新的點融合程序，通過模擬退火算法和滑動時間窗對點融合進場過程進行排序以及4D航跡的優(yōu)化。Hong等[4-5]提出了1種基于混合整數(shù)線性規(guī)劃（MILP）的點融合排序算法以最小化飛行時間為目標優(yōu)化著陸時間；后續(xù)針對航班下降期間的不確定性因素，提出帶有魯棒性解決不確定性規(guī)劃的方法。You等[6]針對并行結構的PMS根據(jù)帶有精英策略的遺傳算法解決排序和調度問題。后續(xù)的關于PMS下的進場航班排序研究主要針對多個目標的動態(tài)求解問題，Hong[7-8]等針對PMS以最小延誤和最小管制員負荷為目標利用蒙特卡洛分析和混合整數(shù)規(guī)劃進行優(yōu)化。Zhang等[9]以最小化總延誤時間、最大總飛行時間和單航班的最大飛行時間為目標構建多目標模型進行航班進場的排序調度優(yōu)化。張軍峰等[9-10]針對進場多目標優(yōu)化問題利用帝國競爭算法進行排序與調度優(yōu)化。夏正洪等[11]利用雷達管制模擬機對點融合程序進行排序驗證點融合程序相較于傳統(tǒng)程序的有效性。關于進場航班排序的算法方面，包括模擬退火算法[12-13]、蟻群算法[14]、貪心算法[15-16]等。

標準進場程序的航班優(yōu)化一方面從約束條件和目標入手，選擇更先進的優(yōu)化算法；另一方面對進場的航跡進行優(yōu)化選擇更為有效的下降航跡。PMS的應用適應于終端區(qū)空域范圍廣、容量大的大型國際機場，而且針對國空域劃分的特殊性，點融合程序是與標準儀表進場程序混合同時運行導致航班的進場程序更為復雜。航班在進場時首先要考慮的是從哪條程序下降進近，其次才能確定排隊序列和進場下降的航跡。而對于混合程序運行的終端區(qū)來說，還要同時考慮是否選擇點融合程序，選擇程序后才能考慮排隊序列。針對結合PMS具有復雜進場程序的終端區(qū)，考慮通過將進場程序和跑道分配給進場航班并結合點融合程序優(yōu)化進場排序來達到提高終端區(qū)進場運行效率的目的。

選取上海浦東機場進場程序，通過0-1整數(shù)規(guī)劃將不同進場程序分配給航班，以最小總延誤時間和最小總飛行時間為目標函數(shù)，建立多目標進場航班優(yōu)化排序模型，并結合非支配排序遺傳算法對模型進行求解，確定航班的落地序列和進場程序，并與實際運行結果對比分析，實現(xiàn)通過利用點融合程序縮小飛行時間和延誤的目的。

1 點融合系統(tǒng)

點融合系統(tǒng)[17]的運行流程可概括為3個步驟：準備排序、建立排序、按序下降。如圖1所示，準備排序：在航班進入排序邊之前，管制員先檢查確定航班序列、進入條件（高度/速度/間隔）并發(fā)布指令。可以通過自動化系統(tǒng)中圖形工具（測距）或基于進場管理系統(tǒng)給出著陸次序。建立排序：航班沿排序邊水平勻速飛行，管制員監(jiān)控已排序航班之間的間隔。一旦排序邊上的航班與前機達到間隔配備，發(fā)布“直飛”指令。排序下降：管制員在考慮平行于排序邊上的下降航班之間的間隔配備后，下達下降指令，然后通過改變速度優(yōu)化間隔并考慮退出系統(tǒng)。

圖1 點融合進場程序圖Fig.1 Procedure of point fusion approach

傳統(tǒng)進場程序運行過程中，管制員是通過改變航班的航向和飛行速度來調整航班的安全間隔，也就導致了航班的飛行間隔主要依靠管制員的經驗來調控。尤其在進場航班數(shù)量較多時，管制員很難判斷如何調度航班來提高整體運行效率，調度的主要目標是使航班滿足安全間隔安全著陸，也就導致航空航班的實際運行間隔要遠遠大于安全間隔，這也是產生航班延誤的重要原因。引入PMS后，融合點代替了傳統(tǒng)的起始進近點，排序邊和下降到融合點的過程代替了進場過程。排序邊上個點到航班的距離相同，所有管制員可以通過調整多架航班在排序邊上的飛行時間來調整航班之間的間隔，航班在排序邊排序下降的時刻差值就是航班之間的時間間隔。因為航班可以嚴格按照程序飛行，所以航班之間的時間間隔可以很大程度上的逼近最小安全間隔，達到減少航班延誤的目的。

2 基于PMS的多跑道進場航班排序模型

考慮到進場程序在加入PMS后，航班的進場過程變得更為復雜。即是否選擇PMS進場、是否在排序邊上排序后進場。不同進場過程的飛行時間范圍不同，航班選擇不同的進場過程會導致不同的落地時間窗。所以考慮航班可選擇的進場程序，根據(jù)選擇不同的進場程序確定落地時間窗對航班進行優(yōu)化排序，還可以通過PMS可以優(yōu)化安全間隔的優(yōu)點對航班的飛行時間進行優(yōu)化。

2.1 PMS下多跑道進場航班排序方法

2.1.1 PMS下多跑道進場航班排序規(guī)則

航班在實際運行過1個進場程序過程依次要經過進場點、進場路徑、起始進近點、中間進近點、最后進近點、接地點和跑道，而PMS的融合點一般設計在在標準儀表程序的起始進近點。由于航班在融合點的高度確定，航班在融合點匯聚，所以將融合點的序列作為航班著陸次序，即假設在起始進近點以前將航班的的次序和間隔調度好。

假設有2條獨立平行進近跑道，每個航班的進場時刻，預計到達時刻，最早、最晚到達時刻和機型已知（見圖2），先將進場航班根據(jù)進場時刻安排在1條跑道上，將其中時刻緊密的的航班分配到另1條跑道上，這樣做的好處是能夠在隨機排序的過程中盡可能的將其中1條跑道的時隙資源充分利用將航班排的更加緊密以達到目標更優(yōu)。再根據(jù)將進場程序隨機分配給航班，根據(jù)進場程序、航班性能等確定航班的著陸時間窗，對各個航班進行排序確定著陸次序。

圖2 PMS下多跑道進場航班排序規(guī)則Fig.2 Sequence rules of multi-runway approach flights under PMS

2.1.2 進場航班排序方法

假設機場有r條獨立平行進近跑道，每個航班的進場時刻，預計到達時刻，最早、最晚到達時刻和機型已知。根據(jù)航班的進場點和進場時刻，考慮目標函數(shù)的要求下，將合適的進場程序的不同航路分配給航班，再將航班安排到第1條跑道上，根據(jù)航班在航路上的飛行時間，計算航班的落地時刻，若不滿足安全間隔要求，將不滿足的安排在第2條跑道上，若第2條跑道上的航班也不滿足要求，則重新分配航路。

通過對實際運行的大量數(shù)據(jù)可以統(tǒng)計從不同航路進場的航班選擇不同排序邊即不同進場程序的飛行時間范圍，據(jù)此為飛行時間約束，分析航班之間的最大調整量和最大調整飛行時間。也就是說航班選擇何種進場程序進場影響整個終端區(qū)的運行情況。可以通過0-1整數(shù)規(guī)劃來將某1個時間段的航班能夠選擇的進場程序進行合理分配，在滿足約束的條件下將延誤降到最低。也就是說，在實際運行過程中，通過即將到達終端區(qū)的航班的進場時刻，通過系統(tǒng)的計算可以提前分析出最佳的著陸次序并為管制員提供有效的管制指令建議。

2.2 點融合程序下多跑道進場航班排序模型建立

2.2.1 目標函數(shù)

1）總延誤時間最小。航班的進場延誤時間是綜合機場、航空公司雙方的效益訴求，即所有航班與預計到達時間的總和最小，即

2）總飛行時間最小。由于航班選擇不同進場程序的預計到達時間不同，在滿足最小延誤的基礎上還要考慮到管制員管制時間和飛行員飛行時間的工作負荷需求，選擇所有航班的飛行時間最小為另一個目標函數(shù)，即

2.2.2 約束條件

1）尾流間隔約束。關于連續(xù)的前后2架航班，由于航班在飛行時的機翼上下表面會產生由于壓力差產生的渦流，航班向前運動則形成航班尾流，對后續(xù)的航班正常飛行造成影響。尾流的大小與前機的機型大小和重量有關，一般來說是成正相關。所以，航班的進場排序必須滿足尾流間隔的約束。

式中：Dqhr為前機機型為q后機機型為h且進場程序為r前后機的尾流安全間隔。由于PMS的進場過程，管制員可以在進入點融合程序之前可以調配安全間隔，然后根據(jù)優(yōu)化后的序列通過點融合程序再進行排序調度，所以假設所有航班的落地次序與間隔為航班通過融合點的次序與間隔。

2）著陸時間窗約束。航班的著陸存在最晚和最早著陸時間[18]，最晚著陸時間主要根據(jù)航班的燃油消耗和燃油儲備；最早著陸時間主要根據(jù)航班的飛行性能和選擇的進場程序，即下降速度越快，航程越短，著陸越早。

3）進場程序約束。航班從進場到著陸的整個過程只能選擇1條進場程序（包括PMS）和跑道，不存在在運行過程中臨時修改進場程序和跑道；由于實際運行中有些進場程序不存在交集，即從某一進場點g進場的航班只能選擇所能可以經過的程序r，r的個數(shù)根據(jù)終端區(qū)實際進場飛行程序確定。設進場點為g的航班的可選進場程序集合為Rg。

2.2.3 基于0-1規(guī)劃的PMS進場航班排序模型

假設航班在終端區(qū)的進場點為g。各個進場點在經過一段非等距的進場航路后會匯聚到多個匯聚點，也就是各個航班可能發(fā)生沖突的點，管制員需要提前對各個不同進場點進場的航班進行調度，可以通過安排到不同高度的高度層，或者到達匯聚點的時間不同來避免航班在匯聚點發(fā)生沖突。假設在確定進場時間的情況下對各個剛進場的航班1個最優(yōu)化的著陸序列，管制員可以通過利用到達匯聚點的早晚來決定著陸次序。但是當航班進場較為密集的情況下，航班數(shù)量較多，管制員無法及時對各個航班進行到達前后時間的調度，還要通過不同高度層的分配。這就會導致實際排序與優(yōu)化序列不同。引入點融合程序后，管制員可以僅通過發(fā)布航向指令就可以調度航班序列，省掉了高度層分配和調速指令。

在點融合程序的基礎上，將點融合程序的排序弧分為λ個階段，第λ階段的起止時間為[(λ-1)θ,λθ]，θ為將點融合均分λ階段的每一階段的飛行時間。通過這種方式，可以確定從各個進場點進入的航班可選擇的進場程序。圖3表示從進場程序r進場的航班i可選擇的進場程序與其他航班的機場程序進行優(yōu)化排序，根據(jù)選擇的程序、進場時刻在滿足約束調價下得到航班的著陸次序。

圖3 航班排序流程Fig.3 Flight sequencing process

設多個進場航路點共計m個進場程序，以0-1規(guī)劃為基礎，假設決策變量為Xikr，xikr=1為i分配程序r進場程序給k進場點進場的航班i。

約束式（7）～（8）表示1個航班僅且只能分配1個進場程序進場且所有航班不能在中途改變進場程序。

設某時間段進場航班有n架，以進場航班為行向量，進場程序為列向量，則航班i的其他程序為，航班i選擇進場程序r的決策變量為=(0,…,1,…,0)（Xigr為1×r矩陣，1位于第r列），所經程序r的飛行時間為Fkr，據(jù)此可以得到進場航班和航班選擇進場程序的0-1變量矩陣。

則所有航班的選擇進場程序r的優(yōu)化落地時間為

結合式（1）～（10），基于0-1規(guī)劃的點融合多跑道進場航班排序模型的目標式為（1）和（2），約束條件式為（3）～（9）。

3 基于0-1規(guī)劃的NSGA-II算法

進場航班的優(yōu)化排序具有多目標多約束的特點，所以選取帶有精英策略的快速非支配遺傳算法（NSGA-Ⅱ）對模型進行求解。

考慮到模型的優(yōu)化排序首先是對進場航班的進場程序進行隨機分配，隨機生成初始解的范圍根據(jù)進場程序的個數(shù)隨機生成，另外還要考慮到初始解生成后轉化為0-1矩陣模型進行求解。其次在交叉變異的過程中，由于不同進場點的可選擇的進場程序不同會產生不滿足約束或者改變程序范圍的情況，需要對交叉變異過程進行修改。所以針對以上考慮的情況，對NSGA-Ⅱ的算子重新定義，對交叉變異過程根據(jù)約束條件不同進行范圍修訂。

3.1 算法修改

3.1.1 基于0-1規(guī)劃初始算子的生成

3.1.2 基于進場程序啟發(fā)式交叉變異

為了避免某一進場點航班在交叉過程中產生的解導致該航班運行到另一進場點的進場程序中去，首先將各個進場航路點歸類，對同一進場點的航班的染色體進行交叉變異操作，這樣產生的新的解不會改變原來某一進場點航班運行的進場程序范圍。

3.1.3 對不滿足約束的解篩選修復

重新利用0-1規(guī)劃模型對新的種群的每個個體（解）進行計算，求得各個解相應的優(yōu)化落地時間集合。對每個個體依據(jù)落地時間進行由小到大排序，依次對各個航班的的落地時間相減，得到各個相鄰航班的時間間隔。在求差過程中若某2架相鄰航班的時間間隔不滿足間隔約束條件，則計算后1架航班的最晚落地時間與與前1架航班的落地時間的間隔是否滿足間隔約束。若滿足，則后1架航班的優(yōu)化落地時間改為前1架航班的落地時間加上時間間隔；若不滿足，則認定此個體為殘次品，重新對該個體進行交叉變異。

3.2 算法流程

基于上述修改，算法步驟如下。

步驟1。獲得本場進場航班的進場時刻。

步驟2。根據(jù)各航班的進場點分配進場程序，并根據(jù)選擇的進場程序得到預計到達時刻并分配跑道。循環(huán)N次得到N組數(shù)據(jù)。

步驟3。根據(jù)航班的進場程序生成第一代種群，個體數(shù)為N。

步驟4。對整群所有個體進行非支配排序，得到1組非支配解。對這1組解進行交叉變異生成新的子代，將上1組非支配解和子代合并，再進行1次非支配排序，根據(jù)擁擠度計算規(guī)則計算個體擁擠度，將優(yōu)良個體作為新的父代。

步驟5。對新的父代交叉變異產生新的子代返回步驟4循環(huán)，直至循環(huán)至最大迭代次數(shù)。最后輸出結果。

算法流程圖見圖4。

圖4 算法流程Fig.4 Algorithm flow

4 實例分析

4.1 仿真場景構建

選取上海浦東機場進場向南運行為例，根據(jù)17R和16L2條獨立平行進近跑道的運行情況，對某天高峰時段01：35—02：35（方便計算，時間換算為秒，以00：00為0計算）的38個進場航班進行優(yōu)化排序。浦東機場的進場程序見圖5。SANAN進場點的航班有2條進場程序的航跡；BK進場點的航班可以左轉通過BK-83A標準儀表進場程序進場著陸或通過BK-81A、BK-82A點融合程序進場；AND進場點的航班進場過程與經過BK的相同；DUMET進場點的航班有2條點融合進場程序航跡和1條連續(xù)下降運行（continuous descent operations）的進場程序航跡；MATUN進場點的航班有2條進場程序航跡。在這里將程序依次從1～13編號，點融合程序總數(shù)共計6條，程序編號分別為6、7、8、9、10、12、13，4個進場點中有3個進場點可以選擇通過PMS進行優(yōu)化排序。由于PMS上航班飛行高度層和飛行速度不變，航班的飛行軌跡一定，可以精確讓實際間隔逼近安全間隔，所以通過PMS排序的航班的安全間隔設為最小安全間隔，最小安全間隔以文獻[19]為標準，并做簡單化處理，即前機機型為輕型機，與后機的時間間隔為90 s，前機為中型機，與后機間隔100 s，前機為重型機，與后機間隔為115 s。不通過PMS的間隔設為最小安全間隔的1.2倍。

圖5 浦東進場程序圖Fig.5 Standard approach procedure of PudongAirport

統(tǒng)計浦東機場1 d的航班進場時刻、進場程序以及到達時刻，得到不同進場程序航班飛行時間的四分位數(shù)。如表1所示，航空的最早、預計、最晚著陸時間分別為代表不同航班選擇不同進場程序對應的百分比進場飛行時間。

表1 各程序進場飛行時間Tab.1 Approach flight time of each procedure

4.2 優(yōu)化結果分析

基于軟件Matlab2017b，設置種群規(guī)模設為50，交叉、變異概率設為0.8和0.03，迭代次數(shù)200次。

由表2可知，通過優(yōu)化后得到的結果明顯好于實際的結果。經計算，優(yōu)化后總飛行時間為49 582 s，相較于實際的總飛行時間52 149 s降低了5%，；優(yōu)化后總延誤時間1 774 s，比實際延誤時間2 872 s降低了38.2%?？梢钥闯?，總飛行時間的降低也就是終端區(qū)的運行效率和容量提高了2.1%，延誤時間降低了38.2%是由于優(yōu)化后的進場航班通過點融合程序排序邊調整安全間隔來逼近最小時間安全間隔，然后最大化的使航班進場飛行的時間最短，來達到延誤的最小化。

表2 優(yōu)化排序結果Tab.2 Optimized sorting results

統(tǒng)計基于0-1整數(shù)規(guī)劃的NSGA-II優(yōu)化和實際過程中的所有航班的著陸時間結果見圖6，優(yōu)化后大部分航班整體的著陸時間都要早于實際式著陸的航班。實際運行過程中，管制員對航班的前后間隔主要考慮安全性，且不考慮根據(jù)排序序列優(yōu)化進場航班來減少不必要的延誤。而優(yōu)化過程通過0-1整數(shù)規(guī)劃模型，在確定落地序列之后通過程序分配和PMS優(yōu)化了前后航班的安全間隔，使得航班的著陸時間分配更加均勻、合理，從而達到減少航班延誤、提高終端區(qū)運行效率的目的。

圖6 優(yōu)化結果圖Fig.6 Optimized results

圖7～8是各條跑道的優(yōu)化結果和實際結果對比，結果得出優(yōu)化后跑道1著陸的航班提高到25架，相較于實際航班的基礎上提高了7架，證明延誤時間和飛行時間的目標都得到了優(yōu)化，跑道時隙資源被充分利用，跑道容量大大增加。因為研究對象是靜態(tài)進場航班，選取的基礎數(shù)據(jù)是1 h內實際的進場航班，跑道2的航班數(shù)相應減少了7架，使得跑道的流量壓力大大減少，為跑道容量的提高提供了支持。

圖7 跑道1著陸結果圖Fig.7 Landing results of runway 1

圖8 跑道2著陸結果圖Fig.8 Landing result of runway 2

與其他的進場排序方式相比，由于點融合程序下的進場程序為航班的進場下降提供了多種程序引導，通過0-1整數(shù)規(guī)劃利用分配進場程序對航班進行排序的方式主要依靠將進場航班分配到不同進場程序，可以使航班的進場航跡不同來避免航班之間的沖突，來達到充分利用有限的空域和時隙資源提高運行效率的目的。通過分配不同的進場程序對航班進行排序，一方面解決了進場程序在引入點融合程序的情況下，航班應該通過何種程序進場下降來提高進場效率的問題；另一方面可以為管制員提供各個航班的既定進場程序和序列的決策建議。

5 結束語

論文針對最新引入的PMS，通過分析PMS優(yōu)化飛行時間和安全間隔的特點以及、PMS下復雜的終端區(qū)進場程序中航班進場后能夠選擇的進場程序（各個標準程序或點融合程序），為航班選擇有效的進場程序，再通過優(yōu)化排序提高航班的進場效率。

1）分析點融合程序下，管制員發(fā)布指令調度航班排序著陸的運行過程，考慮航班準點率和終端區(qū)運行效率確定最小延誤時間和最小飛行時間的目標函數(shù)?？紤]到所選進場程序不同引起的飛行時間不同，并結合PMS優(yōu)化安全間隔的特點，將不同進場程序和跑道分配不同航班確定航班落地時間。以此建立基于0-1整數(shù)規(guī)劃的雙跑道進場航班排序模型。

2）根據(jù)多個目標函數(shù)的線性規(guī)劃模型，選取非支配遺傳算法進行迭代求解，并將0-1整數(shù)規(guī)劃的0、1變量解轉換成適合優(yōu)化算法迭代的常數(shù)變量解，設計基于0-1整數(shù)規(guī)劃的排序算法。

3）選取上海浦東機場進行實例仿真計算，與實際排序結果對比，證明了優(yōu)化后的排序結果能夠有效減少進場航班的飛行時間和延誤時間，且優(yōu)化后的著陸航班的著陸時間間隔更合理、均勻，對提高機場的延誤率和運行效率有重要作用。

由于論文是針對點融合程序和標準進場程序混合運行的具有復雜進場結構的終端區(qū)的進場航班，對進場程序和航班序列優(yōu)化，只與先到先服務的實際結果進行對比分析，且未考慮航班在點融合程序中詳細的四維航跡。未來在結合四維航跡、其他排序模型和優(yōu)化算法等情況值得更深入的研究。