機場航班調度動態優化算法

田琛晟 張楚嫣 王煒祥 田啟川

關鍵詞： 機場航班; 調度方案; 沖突事件; 動態優化算法; 跑道入侵; 等待時間

中圖分類號： TN964?34; TP391.9 ? ? ? ? ? ? ? 文獻標識碼： A ? ? ? ? ? ? ? ? ? ?文章編號： 1004?373X（2019）02?0033?08

A dynamic optimization algorithm for airport flight scheduling

TIAN Chensheng1， ZHANG Chuyan1， WANG Weixiang1， TIAN Qichuan2

（1. Honors College， Northwestern Polytechnical University， Xian 710072， China;

2. School of Electrical and Information Engineering， Beijing University of Civil Engineering and Architecture， Beijing 102616， China）

Abstract： In allusion to the problems that the airport runways are limited as the aircrafts that need to take off and land increase and how to shorten the waiting time of passengers， a dynamic optimization algorithm for airport flight scheduling is proposed. The aircraft state parameter matrix model is defined. The sliding parameters of different types of aircrafts are calculated. The sequence scheduling schemes for a limited number of take?offs and landings are traversed according to the real?time flight information and time order of arranged taking?off and landing aircrafts in each airport terminal per hour. The time consumptions of scheduling schemes are compared. The dynamic scheduling optimization scheme is given on the premise of meeting the security target and taking the reduction of passengers′ waiting time as the optimization target. The runways and airport terminals are assigned to the corresponding aircrafts for take?offs and landings according to the optimization scheme， so as to increase the take?off and landing times of airport flights， improve the utilization rate of runways， and shorten the waiting time of passengers. The simulation results show that the dynamic optimization algorithm for airport flight scheduling is effective.

Keywords： airport flight; scheduling scheme; conflict event; dynamic optimization algorithm; runway incursion; waiting time

0 ?引 ?言 ? ??

近年來隨著經濟的高速發展，人們的生活水平大幅提高，飛機已經成為人們出行交通方式的第一選擇。因此，航空市場需求有了持續的高速增長，航班流量日益增加，這給機場安全起降造成了很大的壓力。受起降跑道等有限條件的限制造成飛機相撞、飛機延誤情況經常出現，飛機調度問題迫切需要解決。防止飛機相撞已成為空管日常工作中的一項重要內容，每起飛機相撞事故的發生，都會造成難以估計的損失[1?2]。

許多大型機場，飛機起降次數猛增，年吞吐量達到400萬人次以上。這么繁忙的機場受調度效率的影響，航班延誤率在不斷上升，機場使用效率降低。由于機場調度影響因素復雜，使得由此引起的諸多經濟社會問題備受關注。這些問題給人們的出行帶來影響，對航空公司、機場運營方造成了利益損失。

國際民用航空組織定義的“跑道入侵”指的是“在機場中發生的任何涉及錯誤的出現在用于飛機起飛和降落的保護區表面的飛機、車輛以及行人的事件”。據中國民用航空局網站消息，2016年10月11日，東航A320/B?2337號機執行MU5643航班任務，飛機于北京時間11：54滑出，北京時間12：03塔臺指揮飛機進跑道36L，機組在執行完起飛前檢查單之后進入跑道，12：04塔臺指揮：跑道36L，可以起飛。機組在確認跑道無障礙的情況下，執行起飛動作，在飛機速度達到110 kn左右，機長發現一架A330準備橫穿36L跑道，但此時飛機速度已經達到130 kn，機長短暫判斷后決定馬上起飛，幸運的是飛機正好飛越A330且后續飛行正常。該事件雖未造成事故，但是也是一起嚴重的A類穿越事件，一旦發生碰撞后果將不可想象。中國民航局公布的調查結果顯示，通過對事發相關人員進行調查問詢，調取通話錄音、雷達錄像，以及對涉事飛機的飛行數據記錄器、駕駛艙語音記錄器進行了譯碼，判斷該事件是一起因塔臺管制員指揮失誤造成跑道入侵事件。

造成飛行沖突的原因是多方面的，既有主觀方面的，也有客觀方面的;既有飛機本身原因，也有天氣、環境等外在原因。為避免大型高密度機場起降飛機發生沖突，必須制定高效的引導方案[3]，因此，機場航班調度非常重要，除去天氣等客觀原因，調度過程需要根據飛機的起降要求和位置，進行合理規劃，才能提高機場起降效率，讓飛機安全起降。

1 ? 問題描述和分析 ? ??

1.1 ?問題描述

1.1.1 ?機場描述

以上海虹橋機場為例，上海虹橋機場示意圖見圖1。為了便于說明問題，將T2航站樓登機口按照登機樓所占區域劃分為T2?①，T2?②，T2?③和T2?④四個登機區。T2?①登機區為T2?1～T2?21登機口;T2?②登機區為T2?22～T2?33登機口;T2?③登機區為T2?34～T2?62登機口;T2?④登機區為T2?63～T2?75登機口。假設機場的風向為由北向南，風速為20 km/h，飛機逆風起飛，逆風降落，滑行速度假設為10 kn/h，這樣飛機無論是起飛還是著陸，滑跑方向都為從南向北。

1.1.2 ?起降航班情況描述

全天24 h的航班調度問題都可以看作每小時的航班調度問題，而且航班受許多客觀因素影響，起降時刻有不確定性，因此，針對1 h內的航班情況來調度和規劃路徑更有實際意義。

根據虹橋機場1 h之內要起降航班的情況：有27對航班起降，并對這些航班進行了編號，如表1、表2所示。

為了便于篩選與識別，對4：15PM—5：15PM時間段進行分段標號，如表3所示。這樣每5 min分一個時間段，共有13個標號，以此來研究這1 h內航班的調度問題。

1.2 ?問題分析

1.2.1 ?沖突分析

根據圖1的虹橋機場示意圖可知，機場分起飛跑道和降落跑道，T1航站樓在降落跑道一側，T2航站樓在起飛跑道一側，所以當發生飛機降落要到T2航站樓同時飛機要從T1航站樓起飛時，起降的飛機必然需要橫穿跑道，就有可能發生沖撞，這類事件就是“沖突事件”。而T1航站樓降落和T2航站樓起飛沒有沖突，可以同時發生，稱為“安全事件”。要求同一個時刻每個跑道不能有兩架飛機。也就是說，如果當前時刻有飛機在跑道上進行起降，那么其他要起飛的飛機只能在登機區等待，要降落的飛機也只能等待降落跑到無飛機時才能降落;因此，合理調度航班并規劃一條路徑才能節約時間提高機場效率。

根據對起飛降落航班信息進行分析可知，不同時間段的飛機起降分配或疏或密，增加了“沖突事件”發生的概率。在不改變航班次序的前提下，為了提高航班效率和安全性，就需要為起降飛機合理分配不同時間段和航站樓。這一過程可以通過遍歷算法來實現優化。

1.2.2 ?航班狀態矩陣模型

用[T1]，[T1*]分別表示T1航站樓的起降飛機數，用[T21]，[T21*]，[T22]，[T22*]，[T23]，[T23*]，[T24]，[T24*]分別表示T2航站樓的不同登機區域T2?①，T2?②，T2?③，T2?④的航班起飛和降落的數目。構造一個矩陣[M]，每行代表一個時間段，每行的數據元素分別為5個登機口的起飛航班數和降落航班數。其中：

[Mi=T1，T21，T22，T23，T24，T*1，T*21，T*22，T*23，T*24，i∈1，13]

[M=M1，M2，…，Mi，…，M13T] ?（1）

以矩陣[M]的形式，分別建立3個矩陣：[A13×10]表示13個時間段不同航站樓的起降航班數;[B13×10]表示13個時間段不同航站樓的沖突航班數;[C13×10]表示13個時間段不同航站樓的安全航班數，見式（2）～式（4）。用這3個矩陣對一個小時內的航班信息進行表示，建立分析模型，便于進一步分析和調度。

通過矩陣模型的方法簡化了航班信息，得到一組易于進行分析判斷的數據。因為從T2航站樓起飛的航班和著陸到T1航站樓的航班之間不存在“沖突事件”發生的可能性，即T2航站樓的起飛航班和著陸到T1航站樓的航班兩個事件為相互獨立事件，可以同時進行。對于可能造成“沖突事件”發生的航班，即矩陣[B13×10]中所列舉的航班。

因此，航班調度問題轉化為對航班狀態矩陣數據的分析問題，此外還需要考慮飛機穿越跑道的時間，需要進行分析并規劃設計出航班滑行的路線。

2 機場航班調度算法

2.1 ?模型簡化

為了便于說明問題，對上海虹橋機場進行了幾何簡化，如圖2所示，對T1，T2對應航班的滑跑路線給出圖示的幾條路線。假設每架飛機的滑跑距離、滑跑時間相同且起降滑跑時間都等于飛機橫穿跑道的時間，假定時間為90 s。

設定飛機起降工作為優先考慮事件，飛機穿行跑道為次要考慮事件。工作模式為優先進行“不沖突事件”航班的起降，“沖突事件”的航班按照一定的次序在起降跑道與等候跑道的交點（稱之為節點）處等待。當聚集在同一條跑道上不同節點的飛機總數目大于2時，該跑道立刻停止起降工作，容許等待穿行的飛機穿過跑道。其中從降落跑道穿行起飛跑道到T2航站樓共有兩個節點，從T1航站樓穿行降落跑道到起飛跑道共有三個節點。

2.2 ?以安全性為目標的航班調度算法

以安全性為單一目標的航班調度算法如下：

1） 按照航班信息表選取1 h內的所有航班[A13×10]，將起飛航班和降落航班分別按照時間進行排隊;

2） 依據航班次序，計算[B13×10]，分析起飛航班、降落航班是否存在沖突可能，如果不存在沖突可能，那么[C13×10]的安全航班可正常安排起降，否則需要等待;

3） 發生沖突的等待航班，當聚集在同一條跑道上不同節點的飛機總數目大于2時，該跑道立刻停止起降工作，容許等待穿行的飛機穿過跑道。

按照該調度算法，對航班表1、表2所列航班進行調度，給出的調度策略如表4所示。

表4給出各個航班起降及停靠位置，是一個完整的路徑規劃方案。將飛機航班表中的初始時間4：15PM設為0時刻，Time1表示飛機起降任務的起始時間，Time2表示飛機起降任務的完成時間，兩者的差Δt為旅客等待時間。

由表4可以看出，完成所有任務用時為3 420 s，小于要求的1 h起降時間。該調度策略能夠完成這1 h內的起降任務，保證起降不發生沖突現象。但是，從調度表也發現了一些問題，那就是有的航班從準備起降到完成起降任務中間有較長的時間，旅客在飛機機艙中等待飛機起飛或降落的時間有些長，如Planedown 26和Planeup 3的等待時間分別為1 080 s和2 070 s，這容易引起旅客產生不滿情緒或心里不安，降低了航班準點率及機場使用率。考慮到旅客對航班等待的忍耐程度和機場地面調控的安全，需要在保證安全性的前提下，調度時應能夠給出一個旅客等待時間短的調度方案。

3 ?機場航班調度動態優化算法

3.1 ?參數修正

在前面的調度中，未進行精確的建模，統一采用固定的90 s時間進行航班調度，未考慮從各個航站樓登機區到起飛跑道的距離、不同機型需要不同的起降滑行時間和距離，因此第2節中調度算法還需要改進。

不同的飛機型號具有不同的起飛和降落滑行距離和時間，對不同的飛機型號，只有得到較準確的飛機滑行距離和時間，才能對飛機在跑道上的停留時間做出較準確的預測，才能避免沖突事件發生。

為了使規劃更加準確合理，對飛機滑行時間和滑跑距離進行修正[4?5]。計算可知降落至滑行時間約為47 s，起飛滑跑時間約為38 s，準確計算了現行7種飛機起降時滑跑距離，得到如表5所示的不同機型起降距離。

在數據修正的基礎上，依據中國民航局地面滑行最小安全間隔的規定，飛機在滑行道上滑行時必須滿足最低尾流間隔標準，其間隔標準取決于飛機的機型。鑒于1 h內航班機型情況，考慮到優化滑行路徑時是以時間為基礎的，所以有必要把滑行飛機的間隔距離轉換為時間間隔來控制，也可參照文獻進行滑跑路徑優化[6?10]。依據中國民航總局的相關規定，設定機場地面飛機滑行時間間隔為30 s，再加上修正后的起飛滑跑時間38 s，平均一架飛機從滑行、等待到升空所需時間為68 s。同理，降落跑道使用時間間隔為77 s。

3.2 ?等待時間

在飛機安全的基礎上考慮準點率和起降率，將時間忍耐度作為一個優化的目標變量，根據動態規劃對調度方案進行動態優化，使方案更加優化。文中設500 s最大旅客等待時間作為旅客最大能夠忍耐的時間。

這樣，飛機調度的策略就是以安全作為第一考慮要素，按照航班的排列順序，以跑道上起飛降落的飛機作為第一安全考慮，當跑道上有飛機起降，需穿行的飛機必須等待起降飛機的起降工作。如果按照航班時刻表去調度是沒辦法實現航班次序優化減少等待時間的，要想縮短旅客的等待時間，需要調度調整起降順序。

3.3 ?航班順序遍歷

通過改變航班次序來比較不同的調度方案最終得到優化的航班調度方案，采用數值模擬的方法進行方案比對[11]。調度方案遍歷尋優一方面是為飛機確定無沖突的滑行路徑，最優路徑是從可行路徑中選擇，另一方面要通過航班到達其路徑上節點的時間進行優化，因此，方案的優化采用前面的計算模型，來模擬航班按照不同的順序起降，計算該方案所需要的最短時間。為了得到所用時間最短的航班調度方案，需要盡可能多地遍歷不同的航班組合，以給出較優的調度方案，否則機場利用率會很低[12]。

在可以改變航班次序的情況下，該問題可以視為非線性問題的動態規劃。但是，由于可能性過多，求得全局最優方案不太實際，所以選擇建立有限的隨機方案，求取這些隨機方案的最優解，在隨機方案數量有限的約束條件下，用這些隨機方案的最優解代替全局最優的方案作為調度方案，基于遺傳算法的調度優化也只能是較優解，而不是最優解[13]。

3.4 ?以安全性和等待時間為目標的航班調度算法

如表1、表2所示，當前的1 h內有27架次的起飛航班和27架次的降落航班，那么這種排列組合是一個很大的數，遍歷各種可能的情況是不切合實際的，所以必須通過一定的方式來簡化計算過程，盡可能地得到較優調度方案。航班信息每時每刻都在更新，航班調度屬于非線性動態規劃[14]。

機場航班調度動態優化算法步驟如下：

1） 按照航班信息表選取1 h內的所有航班[A13×10]，分別將起飛航班和降落航班分別按照時間進行排隊;

2） 對航班順序進行編號，并選出多組隨機排列組合，作為多種航班調度方案;

3） 依據航班次序，計算[B13×10]，分析起飛航班、降落航班是否存在沖突可能，如果不存在沖突可能，那么[C13×10]的安全航班可正常安排起降，否則需要等待;

4） 發生沖突的等待航班，當聚集在同一條跑道上不同節點的飛機總數目大于2時，該跑道立刻停止起降工作，容許等待穿行的飛機穿過跑道;

5） 與已有的調度方案比較，記錄不同調度方案的用時最少的多個方案和該方案的旅客等待時間;

6） 如果選出的全部航班調度方案遍歷已經結束，那么轉到步驟7），否則，轉到步驟3）進行下一組調度方案分析;

7） 從最后得到的多個調度方案中選出等待時間最短的方案（其他方案也可以作為備選方案）。

為了獲得接近最優的調度方案，用來分析的隨機調度方案數量應該盡可能多一些，遍歷這些不同方案就可得到接近于最優的方案，但是這樣會帶來計算量的增大，因此具體選擇多少組隨機方案可根據算法的實時性要求確定。

4 ?實驗仿真

虹橋機場1 h之內要起降航班的情況見表1、表2。為了尋求好的調度方案，編寫了產生不同排列隨機調度方案的程序，實驗中隨機調度方案的數量限定為5 000個。經過比對，從中選取時間最短的解作為最優解和最終的航班調度表，如表6所示。

可以看出，采用文中航班動態調度算法，僅用2 495 s就完成了計劃內所有航班的起飛和降落任務。同時，在54次起降任務中，該調度方案有35次航班無需等待，可以直接進行起飛或降落，最長的等待時間都在500 s之內，限制在旅客能夠承受的時間范圍內。

通過比較，參數優化后增加了最大忍耐時間后的調度優化策略明顯更合理、更科學，提高了機場起降效率。該機場航班動態調度算法可以針對1～2 h內的航班進行調度優化，由于航班起降也受其他因素影響，航班調度沒有必要一次進行24 h內航班的起降進行規劃，這樣根據實時的航班信息對1～2 h進行調度優化，更新航班數據后再對下一個時間段進行調度優化，實現機場起降登機的統籌安排，確保不會影響旅客的出行計劃。

5 ?結 ?語 ?

針對日益增多的依靠航班出行、旅游人員來說，很看重飛機的安全性和航班的準點率，面對機場起降飛機增多的情況，航班的調度決定著機場的起降效率：求取不同機型飛機滑行時間和滑行距離，有助于提高調度的精細化;簡化機場模型，以時間進行動態規劃，保證飛機起降安全;在限定隨機方案數量的情況下，借助矩陣模型進行沖突分析，對影響調度結果的參數進行精確優化，最終的調度方案極大縮短旅客等待時間。實驗結果表明，本文提出并實現了基于安全性和最大忍耐時間的航班調度優化算法，實時性好，可實現機場高效服務。

注：本文通訊作者為田啟川。

參考文獻

[1] 孫金峰，張咫千，姚東賓.從上海虹橋機場跑道入侵事件談飛行沖突的處理[J].科技創新與應用，2016（34）：292.

SUN Jinfeng， ZHANG Zhiqian，YAO Dongbin. Discussion on the handling of flight conflict from the runway intrusion event at Shanghai Hongqiao Airport [J]. Scientific and technological innovation and application， 2016（34）： 292.

[2] ANDERSON J D. Introduction to flight [M]. New York： McGraw?Hill Education， 2015.

[3] 湯新民，安宏鋒，王翀.面向沖突避免的航空器場面滑行引導方法[J].西南交通大學學報，2011，46（6）：1032?1039.

TANG Xinmin， AN Hongfeng， WANG Chong. Conflict avoidance oriented airport surface aircraft taxiing guidance method [J]. Journal of Southwest Jiaotong University， 2011， 46（6）： 1032?1039.

[4] 黃奇，李宜峰，林可心，等.飛機起飛和著陸所需滑跑距離計算方法中參數值的試驗分析[J].路基工程，2013（5）：87?89.

HUANG Qi， LI Yifeng， LIN Kexin， et al. Experimental analysis on parameters required in calculation of taxiing distance for airplane′s taking?off and landing [J]. Subgrade engineering， 2013（5）： 87?89.

[5] 董瑩，安然.機場航空器地面滑行時間優化研究[J].交通運輸系統工程與信息，2011，11（5）：141?146.

DONG Ying， AN Ran. Optimization of aircraft taxiing time [J]. Journal of transportation systems engineering and information technology， 2011， 11（5）： 141?146.

[6] 尤杰，韓松臣.基于多Agent的機場場面最優滑行路徑算法[J].交通運輸工程學報，2009，9（1）：109?112.

YOU Jie， HAN Songchen. Taxi route optimization algorithm of airport surface based on multi?Agent [J]. Journal of traffic and transportation engineering， 2009， 9（1）： 109?112.

[7] 李鋆，王春雷.機場場面飛機滑行路徑優化模型[J].黑龍江科技信息，2012（1）：20?21.

LI Jun， WANG Chunlei. Optimization model of aerodrome plane gliding path [J]. Heilongjiang science and technology information， 2012（1）： 20?21.

[8] 黃邦菊，李婷.航空器場面滑行路徑優化研究[J].海峽科技與產業，2016（6）：96?98.

HUANG Bangju， LI Ting. Study on the optimization of the gliding path of aircraft [J]. Technology and industry across the straits， 2016（6）： 96?98.

[9] 高國政.基于蟻群算法的航空器地面滑行研究[J].山東交通科技，2011（1）：24?27.

GAO Guozheng. Research of airport surface taxing for aircraft based on ant colony algorithm [J]. Traffic science and technology in Shandong， 2011（1）： 24?27.

[10] 李鋆.機場場面飛機滑行調度優化問題的MILP模型及算法[J].價值工程，2012，31（3）：144?146.

LI Yun. An optimization MILP model for aircrafts taxi scheduling in the airport surface and algorithm [J]. Value engineering， 2012， 31（3）： 144?146.

[11] 宋花玉，蔡良才，鄭汝海.飛機起飛滑跑距離數值積分改進算法[J].交通運輸工程學報，2007（2）：24?28.

SONG Huayu， CAI Liangcai， ZHENG Ruhai. Numerical value integral improvement algorithm of aircraft take?off running distance [J]. Journal of traffic and transportation engineering， 2007（2）： 24?28.

[12] 楊雪，胡玉清.機場調度算法的性能分析與研究[J].軟件導刊，2009，8（6）：51?53.

YANG Xue， HU Yuqing. Analysis and research on the performance of airport schedule algorithm [J]. Software guide， 2009， 8（6）： 51?53.

[13] 劉兆明，葛宏偉，錢鋒.基于遺傳算法的機場調度優化算法[J].華東理工大學學報（自然科學版），2008（3）：392?398.

LIU Zhaoming， GE Hongwei， QIAN Feng. Airport scheduling optimization algorithm based on genetic algorithm [J]. Journal of East China University of Science and Technology （Natural science edition）， 2008（3）： 392?398.

[14] 吳受章.離散時間最優控制：評論動態規劃[J].控制理論與應用，2013，30（9）：1165?1169.

WU Shouzhang. Discrete?time optimal control： comments on dynamic programming [J]. Control theory & applications， 2013， 30（9）： 1165?1169.