基于點融合系統的多目標進場排序與調度

張軍峰，游錄寶，周銘，楊春葦，康博

(1. 南京航空航天大學 民航學院，南京 210016； 2. 中國民用航空中南地區空中交通管理局，廣州 510403)

終端空域資源受限，且進離場交通交織，隨著終端空域進離場交通需求的激增，導致終端空域交通流量增長，從而造成管制工作負荷增加。為提高進場運行效率、緩解管制工作負荷，點融合系統（point merge system，PMS）[1]應運而生。該系統是一種新型儀表進場程序結構，通過融合到達交通流的新方法，相對于傳統的雷達引導，能夠標準化進場管制運行、增強飛行員情境意識。從實際運行來看，PMS 主要解決管制指揮標準化的問題，而進場運行效率提升的根本依舊需要借助進場排序與調度領域的研究及進場管理系統的應用。

Liang 等[2-3]研究了基于PMS 的進場調度問題，利用滑動時間窗機制、采用模擬退火算法動態優化進場運行。Hong 等[4]將PMS 引入進場調度，同時采用混合整數線性規劃（mixed integer linear programming,MILP）建模，通過最小化PMS 中所有航空器的總運行時間來優化著陸時間。在后續研究中，Hong 等[5]考慮了連續下降期間的不確定性，并依據不確定性規劃[6]提出了帶有魯棒特性的解決方案。You 等[7]考慮了PMS 并聯形式，并通過帶精英策略的遺傳算法實現并聯PMS 的進場排序與調度優化。

空中交通領域中空管、航司、機場和民眾等各利益相關方往往秉持不同的訴求，于是，進場排序與調度也需要綜合考慮安全、效率、容量、準點運行、環境等多個方面目標，因此，多目標進場排序與調度近年來逐漸引起重視。Hong 等[8]在PMS 運行情況下，以運行時間和序列改變次數為目標進行進場排序優化。Zhang 等[9-10]通過等效進場調度問題與機器調度問題，利用已有研究成果，梳理并精簡了進場排序與調度問題的優化目標，以總延誤時間、總飛行時間和最大飛行時間構建多目標進場排序與調度模型。

因此，本文面向多目標進場排序與調度問題，構建基于PMS 的多目標優化模型，設計多目標優化算法，借助蒙特卡羅模擬[11]驗證算法可行性。為了實現管制決策支持，引入四維航跡預測[12]協助解決進場調度問題。最后以長沙黃花國際機場的PMS運行為場景，考察融合四維航跡預測和PMS 的多目標進場排序與調度效果。

1 點融合系統與四維航跡預測

1.1 點融合系統

PMS 的結構示意圖如圖1 所示。航空器進入系統后在排序支路上勻速平飛，直到管制員發布轉彎指令，然后從排序支路到合并點執行連續下降進近。

圖1 PMS 結構示意圖Fig. 1 Schematic diagram of PMS

內外排序支路平行但不等高，用來實現必要延誤。為使內外支路上的航空器不發生沖突，支路的水平和垂直方向都配備間隔。航空器在排序支路上勻速平飛時，可以在任意點經由管制員引導轉向融合點。航空器進入PMS 之前，為確保與同一定序航段中的前序航空器安全分開，可以通過等待程序或速度調整加以實現。

在PMS 中，除了必要轉向指令，不再使用開環雷達引導，從而有助于節約燃油消耗、減少污染排放、降低噪音影響。因此，PMS 一方面可以確保飛行管理系統充分使用水平導航模式，發揮基于性能導航的優勢；另一方面能夠幫助飛行管理系統優化垂直剖面，實現連續下降進近。

1.2 四維航跡預測

引入PMS 后的進場排序與調度，進場航空器的四維航跡預測是前提和基礎。一方面，通過四維航跡預測獲得預計到達時間；另一方面，經過排序與調度獲得優化到達時間的同時，也可通過四維航跡預測反推航空器在排序支路上的飛行時間，給出航空器在排序支路上轉彎的決策建議。如圖2 所示各部分之間的邏輯關系。

圖2 航跡預測與排序調度的關系Fig. 2 Relation between trajectory prediction and arrival sequencing

航空器四維航跡預測是指根據當前航空器的位置、環境狀態和航空器性能參數，基于航空器動力學與運動學模型，（見式（1）），以及航空器意圖，預測航空器未來四維航跡的過程[12]。

式中：(?，η，h)為空間位置；VTAS為真空速；γ、ψ和φ分別為航徑角、航向角和轉彎坡度；mg、T和D分別為航空器飛行時受到的重力、推力和阻力；w1和w2分別為飛行時受到風的正東向分量和正北向分量。本文中各種機型性能參數均來自航空器基礎性能資料數據庫(base of aircraft data，BADA)，計算過程詳見文獻[12]。

在PMS 中，航空器在排序支路平飛，管制員發布轉彎指令后，航空器向融合點執行連續下降運行指令。因此，整個過程中航空器意圖明確，能夠保障四維航跡預測的準確性。

2 多目標進場排序與調度模型

2.1 多目標選擇

在航空器進場著陸的過程中，有諸如機場、航司、管制、民眾等利益相關方，通過對其訴求進行類比，得出表1 中5 個具有代表性的目標。

表1 排序目標匯總Table 1 Multi-objective arrival sequencing and scheduling

文獻[9，13]研究結果表明，表1 中的5 個目標可以用3 個目標函數涵蓋，分別為：最小化總延誤、最小化總飛行時間、最小化最大飛行時間；對于PMS 來說，航空器在排序支路上的飛行時間即代表其延誤時間。故當連續下降時間接近時，最小化總延誤與最小化總飛行時間可縮減為一個目標，即本文的多目標為最小化總飛行時間和最小化最大飛行時間為

2.2 約束條件

1) 進入點時間窗。航空器在進入點的時間窗約束：

規定了排序支路上航空器的飛行時間約束，也限制了到達融合點時航空器的飛行時間范圍。

3) 安全間隔。

不管在進入點還是融合點,在保證安全距離間隔的情況下一次只允許一架航空器通過。

5) 位置轉換約束。

位置轉換約束通過限定航空器在先到先服務序列的基礎上移動位置不超過z位次，從而確保了公平，以及限制了管制工作負荷。

6) 專機約束。

當航空器為專機時，要保證航空器要在預定的時間內落地，即著陸時間限定為預計到達時間。

3 多目標進場排序與調度算法

3.1 帝國競爭算法

作為一種新型的社會仿生進化算法，帝國競爭算法(imperialist competitive algorithm, ICA)[14]包含帝國(Emp.)、殖民國家(Imp.)和殖民地(Col.)等元素，是將初始解分組成若干個帝國，每個帝國中包含一個殖民國家（帝國內最優解）和多個殖民地，通過對帝國內殖民地和殖民國家不斷更新迭代達到產生最優解的目的。該算法的優點在于：通過帝國內競爭和帝國間競爭，加強深度搜索和廣度搜索，從而提升鄰域搜索和全局優化的能力[13]。

3.2 多目標帝國競爭算法

在PMS 進場排序與調度中，設計多目標帝國競爭算法，其特點在于引入非支配排序。多目標帝國競爭算法流程如圖3 所示。圖3 中算法的參數imax為最大迭代次數。

圖3 多目標帝國競爭算法流程Fig. 3 Flowchart of multi-objective ICA

步驟 3 革命。為防止陷入局部最優，本文主要采用子段逆序、單點變異和2 點交換3 種算子進行革命。子段逆序：隨機選擇部分連續航空器進行逆序操作，獲得相反序列。單點變異：隨機選擇某架航空器，分配新的優化時間；2 點交換：滿足最大位置轉換約束限制下，隨機交換2 航空器優化時間；為確保新解均為可行解，需要考慮連續落地航空器之間的尾流間隔。

步驟 4 帝國內競爭。更新帝國內殖民國家與殖民地的成本值，成本值最小成為新殖民國家。

步驟 5 帝國間競爭。帝國間競爭實現了帝國間殖民地的再分配，勢力強大的帝國逐步吞并勢力弱小的帝國。帝國勢力值計算過程如下：

4 案例仿真與驗證

4.1 四維航跡預測驗證

為驗證四維航跡預測模型與方法，將預測航跡與真實數據作對比。選用某航班的快速存取數據（quick access recorder, QAR），該航班機型為B737，與預測數據對比得出結果如圖4 和圖5 所示，其中圖4為三維航跡對比，圖5 中表示的是過點時間對比，其中，橫坐標為航路點。

由圖4 和圖5 發現，預測航跡與真實航跡在水平軌跡與高度剖面高度吻合，且在過點時間上精度也較高，證明了四維航跡預測模型與方法的可用性。

圖4 預測軌跡與實際三維軌跡對比Fig. 4 Comparison between three dimensional predicted and actual trajectory

圖5 預測軌跡與實際軌跡過點時間對比Fig. 5 Comparison of flight time at each fix between predicted and actual trajectory

4.2 參數值確定

為研究序列改變對多個目標造成的影響，Hong等[5]采用序列偏差（order deviation，OD），Jung 等[15]使用斯皮爾曼秩，評價進場排序與調度模型和算法的優化結果。本文擬用序列變化來量化常規的先到先服務（first come first service, FCFS）序列和優化序列之間的差異。若航空器改變其與相鄰航空器的位置，則序列變化的數量增加1。例如，如果FCFS序列和優化序列分別為1-2-3 和3-2-1，那么序列差異為3。1-2-3 →1-3-2 →3-1-2 →3-2-1

考慮10 架進場航空器，PMS 期間的連續下降飛行時間設定為290 s，整個排序支路可供水平飛行時間為310 s（上述數值的確定考慮了實際運行的歷史數據分析）。

可以預期，所提算法的性能與交通密度存在較大關系。因此，考慮高、中、低3 種不同的交通密度。記2 架航空器之間的標準尾流間隔為Sijrr′A。在高交通密度下，2 個航班之間的初始相對距離在Sijrr′A和 1.5 倍 的Sijrr′A之 間 隨 機 產 生。對 于 中 和 低交 通 密 度，范 圍 在1.5 倍Sijrr′A和 2 倍Sijrr′A及2 倍Sijrr′A和 2.5 倍Sijrr′A之 間。對 于 每 種 交 通 密 度 采 用蒙特卡羅模擬各生成500 個初始位置序列，分配的每個航班初始位置用到達PMS 的初始點的時間來表示。

通過MATLAB2014b 編程實現模型及算法， 如圖6 所示交通密度情況下，Pareto 解位置轉換趨勢，圖6 中每個點為500 次模擬的平均結果。通過重復增加序列改變次數的上限，隨之優化總延誤、最大飛行時間的目標。

圖6 目標隨序列改變趨勢Fig. 6 Trend of objectives with different sequences

如圖6 所示，橫坐標為0 時表示FCFS 的序列，當序列次數從0 變化到1 時，2 個目標都可以觀察到最大的斜率。說明序列的改變相對于FCFS 來說各個目標都有優勢。從大趨勢來看，各個目標（縱坐標）隨著序列改變次數的增加而減少，在序列改變次數為6 時，最大飛行時間和總延誤達到最優。序列的最終決定權取決于空中交通管制員，其根據目前的態勢及整體情況從獲得的Pareto 最優解中選擇最合適的解來做決定。

盡管空中交通管制員通常根據FCFS 順序做出決定，但由分析表明，與FCFS 序列之間略有偏差，可以實現總延誤與最大飛行時間的顯著減少。因此，經多目標算法優化的解決方案更適合于空中交通管制員。

4.3 排序與調度優化算法驗證

本節采用真實數據對PMS 的排序與調度優化算法進行驗證。以長沙黃花國際機場進場運行為例，圖7 顯示了一天的進場航空器的綜合航跡，機場共有5 個進港點：DAPRO、OVTAN、LIG、LLC、BEMTA。

圖7 長沙終端航班進場軌跡Fig. 7 Arrival trajectories within Changsha terminal area

利用Qt 平臺構建長沙黃花國際機場的PMS 進場排序與調度仿真系統，通過處理實際雷達軌跡數據得到如表2（部分數據）所示的飛行計劃。將處理好的飛行計劃輸入到PMS 進場排序與調度仿真系統中進行仿真，仿真場景如圖8 所示。

圖8 系統仿真界面示意圖Fig. 8 Interface of simulation system

表2 基于實際進場數據的飛行計劃（部分）Table 2 Flight plan based on actual operation (part)

選取繁忙時段20 架航空器進行優化，由于航空器從不同進港點到PMS 進入點的飛行時間不同，因此需同時考慮總飛行時間和總延誤時間。尾流間隔分別取標準間隔的1.2 倍和1.5 倍，仿真優化結果如表3 所示。

表3 仿真結果Table 3 Simulation results

由表3 可知，利用PMS 結合多目標優化算法的方法可以有效提升航空器進場的運行效率和效益。初步引進新技術時，往往需要優先保證安全第一，因此容易采取更為保守的安全間隔，所以本文適當擴大尾流間隔限制。

1.2 倍標準尾流間隔時，多個目標的效益都有較大幅度提升，其中總延誤時間減少了70.8%，總飛行時間減少了13.2%，最大飛行時間減少了11.8%。1.5 倍標準尾流間隔時，在不增加其他指標的同時，總延誤仍能縮短23.4%，說明PMS 確實能提升效率和效益。

圖9 以時序圖的形式展示了實際著陸次序與1.2 倍標準間隔下優化著陸序列的對比。圖10 是實際和優化序列的航跡對比。表4 提供了基于PMS 的進場排序與調度的航空器在排序支路上總的飛行時間。圖9 中藍色菱形表示通過PMS 優化的著陸時間，紅色方框表示實際著陸時間，綠色三角表示航空器預計著陸時間。從圖9 可知，經PMS的航班序列與預計到達序列較相似，說明優化算法在保證優化目標的前提下優先考慮公平性。反觀實際運行到達序列，與預計到達序列有較大的差距，究其原因，在于常規進場管制員對于航班的引導沒有既定路線，航班密度較大情況下可能有較多的盤旋等待、側向偏離等調配策略，如圖10 真實軌跡所示，容易造成既定序列的改變，也會影響運行的效率和效益。

圖9 PMS 與實際數據時序對比Fig. 9 Comparison of scheduling results between PMS and actual operation

圖10 中在標準尾流間隔1.2 倍的情況下，PMS仍然不需要通過等待進行航班延誤。在長沙PMS進場程序中，最短的一條排序支路是西向進港（LLC/BEM）的部分，航班在支路上最長可飛行290 s，而由表4 可以看出，20 架航空器在排序支路上等待的最長時間為275 s，還未達到溢出的狀態，說明PMS不僅能在延誤及飛行時間等方面有效能的提升，還在容量方面有相應的利用價值。而常規情況下管制員引導航空器主要依賴經驗，兼之飛行員具體操控航空器時對管制員指令的依從度無法預知，最終導致無法充分利用終端空域及跑道的容量。

圖10 PMS 仿真軌跡與實際軌跡對比Fig. 10 Comparison of trajectories between PMS simulation and actual operation

表4 仿真案例航空器在排序支路飛行時間Table 4 Aircraft flight time on sequencing leg of simulation case

綜合4.3 節可以得出，將PMS 與進場排序與調度結合有諸多優點：①排序與調度的結果可達性，根據優化結果直接在PMS 程序上以轉彎時機的形式表現，為管制員提供決策建議；②結合優化算法，從空管、航司、機場、民眾等多方面進行了效能提升；③PMS 的特殊固定路線，增強了管制員與飛行員的態勢感知；④飛行軌跡更為規整有序，有效降低了終端空域進場運行的復雜性。

5 結 論

本文研究了PMS 的運行，從實際運行角度出發，基于四維航跡預測，結合以非支配排序的多目標帝國競爭算法，對航空器進場排序與調度做出優化。

1） 基于非支配排序的多目標帝國競爭算法可行性較好，解決方案能為空中交通管制員提供決策支持。

2） 結合四維航跡預測的多目標優化算法在模擬實驗中有良好的反饋，在較為保守的安全間隔限制下仍能獲得比實際運行更好的效果。

3） PMS 在航空器進場過程中發揮了顯著的優勢，從管制的角度來說降低了相關工作人員的工作負荷；從機場的角度PMS 合理利用了空域，對提升有限終端區內的進場容量有很大的發展潛力。

本文主要解決了單跑道航空器進場排序與調度問題，結合PMS 的優勢，未來在多跑道機場跑道分配和進離場協同運行等方面值得后續深入研究。