基于大數據的航班調度優化模型與算法初探

石磊 陳偉

摘 要：為了提高服務質量和降低運營成本，所有的航空公司都在不斷尋找各種方法來合理安排航線，降低航班延誤。本文主要討論如何利用大數據來更準確的預測飛機時空位置和航班到達（跑道、登機口）時間，從而來更有效的實時優化航班，使得總的延誤時間與消耗燃油最小。在此過程中，我們細化航班調度涉及的目的與問題，在此基礎上建立數學模型，最終通過機器學習技術求解此模型，提出合理的調度方法。

關鍵詞：大數據；航班調度；航線實時規劃；到達時間預測；機器學習

中圖分類號：V247.4文獻標識號：A文章編號：2095-2163（2016）02-

Exploration of big data based flight schedule optimization

SHI Lei1 ， CHEN Wei1

（1 China Travelsky Holding Company， Beijing， 100105， China）

Abstract：In order to improve the service quality and reduce the operating costs， all airlines are constantly looking for ways to optimize the routes， reducing flight delays. This article discusses the methods to use big data to more accurately predict the location of aircraft and the arrival time， and thereby to more effectively do real-time flight optimization. In this process， the paper refines the flight scheduling purposes and the issues involved， and based on the aboved， the mathematical model is built. The paper tries to solve the model by using machine learning technique to arrive in reasonable scheduling method.

Keywords： Big data； flight schedule； real-time route planning； arrival time prediction； machine learning

0 引言

隨著人們生活水平的提高，選擇飛機出行方式的人越來越多，使得航空運輸的重要性日趨顯著，從而必然導致航班數量的急劇增加。目前，不斷增長的航班數量在面對有限的登機口數目，以及各類突發變化的內、外界（包括天氣原因、流量控制、機械故障或公司周轉）的綜合作用都可能實時導致航班的延誤，不僅給乘客出行帶來困擾，更會使得航空公司成本直線提升。例如經常出現的由于目的地的臺風天氣，導致航班被迫取消，旅客滯留，從而需要賠償并安排食宿。統計數據顯示，對于一個中等規模的航空公司，如果能夠使得每次航班的平均延誤時間減少一分鐘，則每年將可節省數億元的成本[1-2]，航空公司成本具體表現為：燃油、賠償以及人員費用。綜上所述可知，航空公司的航班調度計劃對于航空公司的基礎良性運行則始終發揮著至關重要的智能支撐作用。調度計劃上微小優化都可為航空公司節省大筆費用。因此各國的航空公司及研究學界都在不斷探尋各種方法來優化航班調度，減少航班延誤，提高服務質量。本文即針對這一課題內容展開探索論述，具體如下。

1問題描述

研究中，航班調度通常包括兩個方面：

問題A，飛機航線的優化，即（根據大數據）實時調整飛機的時空位置；

問題B，根據航線的安排，準確預測航班的達到時間。

一般來說問題A，即飛機航線的優化涉及到通過給定當前位置、目的地位置、天氣以及其他相關因素來制定飛行計劃，從而使得所有航班的平均成本降至最低。將其進行數學抽象后可知，該問題順于成本函數已知的一個約束極小化問題。問題A的輸出，也就是通過優化技術制定的飛行計劃常規狀況下多是表現為一個四元組序列：（經度，緯度，高度，速度）。航線的制定不僅要考慮物理定律，同時還需要實際考慮到航空管制區以及高度授權。其中：

1）航空管制區是無論如何不能進入的；

2）很多航班只能在特定高度飛行。

問題A的最優解答，即最佳飛行計劃必須含括3點：首先是出發地到目的地的路徑最短；其次是最優的巡航高度，以及最優的起飛和降落計劃；最后是綜合考慮飛行時間與燃油，從而得到最佳飛行計劃。

對于問題B，輸入上和問題A基本相同，但比問題A多出的一項則是目前時刻所得到的飛行歷史，輸出即是預測的航班到達時間。問題B的最優解答，也就是最優預測當然是和實際的飛機到達時間最大限度地接近才可稱為理想。機場得到飛機的到達時間越發準確，才能更趨現實合理地調控資源安排，包括跑道、登機口和人員。

問題A和問題B并非相互獨立，而是相互影響，相互制約的。顯然，航班的時空位置會影響飛機抵達跑道和登機口的時間；而飛機的到達時間則會關系到機場資源的使用，例如跑道以及登機口的使用沖突等，從而導致機場的擁堵，間接影響其他航線的調度計劃。

本文提出了國內航班調度的優化模型，討論如何利用大數據，包括飛行歷史、天氣、航空管制以及其他數據來更好地實時調整航班的飛行路線，并準確預測飛機的到達時間，從而更為有效地實施航班的安排管理，使得航空公司的總體成本（包括延誤時間和燃油費用）最低。

對于相關的研究工作，由于目前還未有專用模擬器問世可用來對如此復雜問題進行建模，因此目前仍然少見關于航班調度的研究。

2航班調度問題模型

在本節中，針對航班調度模型的各個要素進行研究抽象，從而分別建立起問題A和問題B的數學模型。

2.1 各要素的量化分析處理

2）歷史與當前的飛行數據FD（Flight Data），包括航班出發與到達的地點和時間、計劃的航班路線與實際的航班路線等，可見細節需要提供到燃油、航空公司、飛機型號、航班號、出發機場位置、到達機場位置、預計出發時間、實際出發時間、預計到達時間、實際到達時間、到達的航站樓位置、到達的登機口位置、若干航班計劃路線（一個航班由于在飛行過程中通常都會調整飛行路線，每次調整都作為一次計劃的航班路線，因此多會對應若干航班計劃路線）、航班飛行過程中實際的地理位置（經緯度，通常每分鐘更新一次）。

3）航空管制數據CD（air traffic Control Data），包括航空管制的時間、區域等，這些數據對航班的到達時間具有重大影響。一般來說管制區是需要進行交通管制服務的區域。國內將管制區域分為A、B、C、D四類。其中，A類空域為高空管制區，高度為6600米以上高空。高空管制區由高空區域管制室負責。在高空管制區只允許IFR飛行（儀表飛行規則，Instrument flight rules）；B類為中低空管制區，高度為6600米以下的空域。B類空域接受IFR和VFR飛行（目視飛行規則，Visual Flight Rules）。但VFR飛行須經航空器駕駛員申請并經中低空區域管制室批準方可進入現實發生；C類空域為進近管制空域，通常設置在一個或幾個機場附近的航路匯合處，也是中低空管制區與塔臺管制區的連接部分。其高度為6000米以下、最低高度層以上，水平范圍通常以機場基準點為中心半徑50公里或走廊進出口以內的除機場塔臺管制范圍之外的空間；D類為塔臺管制區，通常包括起飛航線、第一等待高度層及其以下、地球表面以上的空間和機場機動區。為了簡化問題，一般在研究中假設所有管制區的形狀均為凸多邊形，坐標給定，且位置保持不變。航班是絕對不允許進入航空管制區的。在本文的模型中提出如下假定：一旦航班進入航空管制區，成本函數將設定為無窮大，從而強迫其繞過航空管制區。文中模型假設所有的航空管制區都為多邊形且位置已知，雖然實際情形是航空管制區會按時間變化，但在模型中則假設其恒定不變。

4）湍流區位置數據TD（Turbulent zones Data）每時每刻均處于變化之中，因此必須將數據做好提前監測與儲備，包括區域的坐標位置，高度的上下界。為了簡化問題模型以及算法求解的復雜度，假設湍流區的數目有限，同時與航空管制區類似，一般也是假設湍流區都為凸多面體。如果飛機進入湍流區，將會導致飛機的損耗，以及燃油的消耗，此時即需對成本函數添加合適的懲罰項。和航空管制區略顯差別的一點就是，湍流區會一直變化。

5）天氣數據WD（Weather Data），包括歷史與實際的天氣數據，細節到需要遍及全國范圍的若干個氣象站的實時數據。對民航影響較大的天氣數據主要是能見度、風速、溫度等，一般來說，民航機場都裝備了功能齊全的氣象站，因此可以直接利用站點提供的數據。其中，風速數據是2D數據，包含實際風速和預測風速，地面風、速溫、能見度等。

2.2 模型構建研究

3航班調度最優化解決方案

由于民航數據的敏感性，因此本文僅只對航班調度最優化進行了理論上技術方案的實現解析。目前也正在和各航空公司以及民航總局積極探討數據的共享和使用方式，預計在不久的將來可以驗證本文所提出的框架和方法的有效性。

3.1 問題A的解決方案

針對問題A，方案的總體思路是首先設計一個初始路線，其次將根據風速對航線做微觀調整，最后則根據燃油以及機場的資源情況來系統確定飛機起飛、降落、巡航的速度。下面即針對解決方案的3個步驟展開深入、全面論述。

首先，在作初始路線設計時，禁飛區是完全不能闖入的，因此必須避開。在避開禁飛區的前提下，通過確定地圖上兩點之間的最近距離，找到初始路徑。可以通過時下的眾多算法來確定最短的距離，包括著名的Dijkstra算法等[3]。

其次，要根據風向和風速來調整已經得到的初始路徑。一般來說，燃油消耗是和速度直接相關的。而飛機的實際速度是飛機本身的速度與風速的組合，因此合理利用風速可以在相當程度上有助于成本的降低。已有的動態規劃算法可以在一定范圍成功搜索到能夠最為有效利用風能的路線。

最后，基于起飛、巡航、降落的燃油消耗模式的不同，還需要進一步考慮飛機的高度和速度問題，其中最為核心的就是飛機開始降落的時間點。如果飛機離目的地仍然遙遠，就會爬升到最高，再開始巡航，最后降落。如果時間也較為充裕，可以適當減速，從而降低燃油消耗。因此巡航的速度以及飛機降落時間點是研究中的兩個關鍵因素。

3.2 問題B的解決方案

對于問題B，研究采用人工智能和機器學習的方法來進行大數據時代航班到達時刻的準確預測。該方法分為兩個部分：其一是從歷史數據中提煉可能會對航班到達時刻有關系的特征表達；其二是對第一部分所提取特征表達進行需求分類或者預測。

在第一部分，對航班到達時刻有作用影響的，也可說是前一節中提到的能做各種利用的特征表達有如下若干種，具體包括歷史的預測到達跑道（登機口）時間、真實的到達跑道（登機口）時間、預定起飛時間、實際起飛時間、平均延誤時間、平均出租車等候時間、目的地機場的平均風速、最近測量的風速＼溫度＼能見度值、以上數據一階差分、到達機場的代碼、目的地和始發地之間的距離、航班從出發地到目前位置的歷史平均速度、出發機場以及到達機場的經緯度等。

在提取了上述的特征以后，就可以采取多階段的方法來進行到達時刻的預測，包括利用回歸模型（regression models）[4]，梯度推進機（gradient boosting machines）[5]等方法。在不同的階段，也將使用不同的特征。例如首先可以使用線性模型對低維特征進行初始預測；為了挖掘數據中的非線性信息，還可以使用梯度推進機，或者隨機森林（random forest）[6]等方法；同時，實施方案中更需要考慮稀疏特征，以及對預測結果的微調等。

4 結束語

在本文中，重點圍繞大數據的航班調度問題進行了形式化的描述。而后針對這一此形式化描述，綜合考慮了對航班調度能夠產生影響的所有參數，從而建立了大數據時代的航班調度模型。最后則從理論上給出了該航班調度模型的最優化解決方案。

參考文獻：

[1] J. Leber. A data-crunching prize to cut flight delays. 2013， MIT Technology Review. [2013-04-03]. http：//www.technologyreview.com/news/513141/a-data-crunching-prize-to-cut-flight-delays.

[2] S. Altus. Effective flight plans can help airlines economize.[2009-03-09]. http：//www.boeing.com/commercial/aeromagazine/articles/qtr_03_09/article_08_1.html.

[3] DIJSTRA E. A note on two problems in connexion with graphs[J].Numerische Mathematik， 1959， 1（4）：269–271.

[4] BOUSSON K， MACHADO P. 4d flight trajectory optimization basedon pseudo spectral methods[J]. Engineering and Technology， 2010， 4（1）： 471–477.

[5] D Merle. Flight path optimization for an airplane [D].Trondheim： Norwegian University of Science and Technology， 2011.

[6] ATKINS EM. Flight plan management with George Jetson as pilot [C] //AAAI Spring Symposium 2004. Palo Alto： AAAI， 2004：1-6.