基于大數(shù)據(jù)的航班調(diào)度優(yōu)化模型與算法初探

石磊 陳偉

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

關(guān)鍵詞：大數(shù)據(jù)；航班調(diào)度；航線實時規(guī)劃；到達(dá)時間預(yù)測；機(jī)器學(xué)習(xí)

中圖分類號：V247.4文獻(xiàn)標(biāo)識號：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 引言

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

1問題描述

研究中，航班調(diào)度通常包括兩個方面：

問題A，飛機(jī)航線的優(yōu)化，即（根據(jù)大數(shù)據(jù)）實時調(diào)整飛機(jī)的時空位置；

問題B，根據(jù)航線的安排，準(zhǔn)確預(yù)測航班的達(dá)到時間。

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

1）航空管制區(qū)是無論如何不能進(jìn)入的；

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

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

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

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

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

對于相關(guān)的研究工作，由于目前還未有專用模擬器問世可用來對如此復(fù)雜問題進(jìn)行建模，因此目前仍然少見關(guān)于航班調(diào)度的研究。

2航班調(diào)度問題模型

在本節(jié)中，針對航班調(diào)度模型的各個要素進(jìn)行研究抽象，從而分別建立起問題A和問題B的數(shù)學(xué)模型。

2.1 各要素的量化分析處理

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

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

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

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

2.2 模型構(gòu)建研究

3航班調(diào)度最優(yōu)化解決方案

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

3.1 問題A的解決方案

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

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

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

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

3.2 問題B的解決方案

對于問題B，研究采用人工智能和機(jī)器學(xué)習(xí)的方法來進(jìn)行大數(shù)據(jù)時代航班到達(dá)時刻的準(zhǔn)確預(yù)測。該方法分為兩個部分：其一是從歷史數(shù)據(jù)中提煉可能會對航班到達(dá)時刻有關(guān)系的特征表達(dá)；其二是對第一部分所提取特征表達(dá)進(jìn)行需求分類或者預(yù)測。

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

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

4 結(jié)束語

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

參考文獻(xiàn)：

[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.