基于決策樹的航空器離港滑出時間預測方法和模型

陳 禎 唐小衛(wèi)* 林有超 任思豫

(南京航空航天大學民航學院1) 南京 211106) (中航空管系統(tǒng)裝備有限公司2) 上海 200241)

0 引 言

當前我國大型繁忙機場采用的協(xié)同決策(collaborative decision making，CDM)系統(tǒng)通過集成空管、航空公司、機場三個獨立的子系統(tǒng)搭建出一個信息交互、數(shù)據(jù)共享的航空運輸一體化平臺，實踐表明：CDM系統(tǒng)在減少航班總體延誤、擴大機場容量等方面起到了積極作用.對于每一個離港航班，目前CDM系統(tǒng)是用每個航班在跑道上的計算起飛時刻減去平均滑行時間得到其在機位上的推出時刻，但航班離港滑行的過程具有較大的不確定性，僅憑經(jīng)驗預測滑行時間的傳統(tǒng)管理模式已不能滿足CDM系統(tǒng)的要求.因此，研究影響離港滑行時間的關(guān)鍵因素并設(shè)計合適的算法來提高離港滑行時間預測的準確性對優(yōu)化離場順序、提高CDM機制下起飛時刻的執(zhí)行率具有重要意義[1].

國內(nèi)外對航空器離港滑行時間預測的研究主要涵蓋特征選取和模型方法兩個方面.在特征選取方面，Kistler等[2-3]考慮了滑行距離、進離港交通量、跑滑結(jié)構(gòu)等影響滑行時間的因素，一定程度上豐富了特征變量集；Jordan等[4]進一步引入航空公司、滑行方向等虛擬變量并構(gòu)建交互特征，有效提升了模型的預測精度；Ravizza等[5-6]利用歐洲機場滑行道的專有特點構(gòu)建滑行轉(zhuǎn)彎角度與距離特征，在歐洲機場的樣本集上取得了良好的預測結(jié)果；馮霞等[7]將滑出時間預測分為兩個階段，先利用已知特征預測滑出期間使用同跑道起降的航班數(shù)量，再將其作為輸入變量構(gòu)建滑行時間預測模型，發(fā)現(xiàn)該方法的預測效果優(yōu)于直接預測；劉繼新等[8]對航空器滑出時間的影響因素進行分析，驗證了場面流量的影響最為顯著.在模型方法方面，Balakrishna等[9]在隨機動態(tài)規(guī)劃的概率框架中采用強化學習的方法進行滑行時間預測；Zhang等[10]建立計量經(jīng)濟學回歸模型預測無阻滑行時間，在計算排隊長度時考慮了飛機超越等因素，同時將跑道構(gòu)型、地面延誤程序和天氣作為解釋變量，使得模型可以廣泛應用于歐美機場滑行延誤對比；Herrema等[11]研究了機器學習在滑行時間預測上的運用，將神經(jīng)網(wǎng)絡(luò)、回歸樹分析、強化學習和多層感知方法四種機器學習方法運用于戴高樂機場實際運行數(shù)據(jù)，得出回歸樹模型預測效果最好.

以上研究主要聚焦于每個特征單獨對滑行時間的影響以及特征構(gòu)建后的模型選擇，少有研究考慮特征間相互作用會對滑行時間預測產(chǎn)生的效果.因此，文中基于滑出時間的影響因素構(gòu)建一次特征變量，運用特征工程構(gòu)建交互特征，與一次特征共同構(gòu)成初始變量集.考慮到初始變量集可能存在冗余特征對預測產(chǎn)生一定的影響，因此基于決策樹算法從所構(gòu)建的大量特征中篩選出一部分最重要的特征作為最優(yōu)特征變量集構(gòu)建離港滑行時間模型，并將該模型與僅使用一次特征構(gòu)建的模型對比驗證.

1 滑出模型的特征構(gòu)建

數(shù)據(jù)來源于首都機場2019年10月—2020年1月的航班運行數(shù)據(jù)，考慮到36R跑道為首都機場主離港跑道，因此選取36R跑道的航班運行數(shù)據(jù)進行研究分析.

1.1 一次特征構(gòu)建

1) 滑行距離 一般而言離港滑行時間隨著滑行距離的增加而增加，因此首先考慮建立離港滑行時間和滑行距離的一元線性回歸模型.現(xiàn)有數(shù)據(jù)無法獲得每個航班的具體離港滑行路徑，通過機場地面管制部門提供的場面運行規(guī)則，依據(jù)機場CAD底圖量取各機位至跑道口的滑行距離，將數(shù)據(jù)進行歸一化處理后得到

Tout=0.081D+0.184

(1)

式中：Tout為離港滑行時間，min;D為離港滑行距離，km；表1中的各項評價指標分別為該預測模型的±3 min準確度、±5 min準確度、擬合優(yōu)度和相關(guān)系數(shù)，可見滑行距離與離港滑行時間的相關(guān)性很低，滑行時間不會受到滑行距離的顯著影響.

表1 評價指標

2) 擁堵變量 航空器的離港滑行會占用跑道、滑行道等場面資源，航空器間由于資源占用而發(fā)生沖突，當沖突發(fā)生時航空器需在原地等待直至沖突解除.場面擁堵加劇導致沖突發(fā)生的頻率變高、解除沖突的時間變長，進而滑行時間增加.因此構(gòu)建了兩個擁堵變量，即某個航班滑出期間內(nèi)使用同跑道離港的航班數(shù)量(Ntxot)和進離港瞬時流量(Nins).Ntxot指在航班撤輪擋推出時刻至計算起飛時刻的這段時間內(nèi)使用同跑道離港的航班數(shù)量；Nins指在航班撤輪擋推出時刻的場面進離港瞬時流量.

圖1分別給出了Ntxot，Nins與Tout的相關(guān)性分析，相關(guān)系數(shù)分別為0.88和0.47，可見Ntxot，Nins與Tout具有較強的相關(guān)性，但在流量相同的情況下，出港滑行時間相差可達30～40 min，說明除了上述2個擁堵變量，還存在其他影響離港滑行時間的因素.

圖1 Ntxot,Nins與Tout的相關(guān)性分析

3) 推出前15 min離港航班平均滑行時間tdep通過挖掘相鄰時間段內(nèi)使用同跑道離港的航空器的滑行時間之間的關(guān)系，以15 min為一個單位將滑行時間離散化處理，發(fā)現(xiàn)推出前15 min使用同跑道起飛的其他航班的平均滑行時間tdep與該航班的滑行時間具有一定的相關(guān)性.圖2為tdep與Tout的相關(guān)性分析，結(jié)果顯示相關(guān)系數(shù)為0.47.

圖2 tdep與Tout的相關(guān)性分析

4) 機型類別 不同機型的操縱性能不同，其本身滑行時的速度也有差異.航班樣本涉及C、D、E、F四種機型，在相同范圍的滑行距離下，各類機型的樣本數(shù)量、平均滑行時間、標準差見表2.

表2 各類機型樣本數(shù)量、滑行時間均值及標準差

由表2可知，C類和E類機型為樣本占比最大的兩種機型，E類機型的平均滑行時間比C類機型長約1 min，且標準差相差很小，說明數(shù)據(jù)的離散程度相似.總體而言大機型的滑行時間普遍高于小機型，可見機型對滑行時間具有一定的影響.

為了讓訓練集涵蓋更多的數(shù)據(jù)特征，使用one-hot編碼將非數(shù)值型數(shù)據(jù)轉(zhuǎn)化為數(shù)值型數(shù)據(jù)，機型變量就可以編碼為一個長度為4的特征向量.每個航班有且僅有一種機型執(zhí)飛，因此機型變量的約束條件為：

(2)

式中：FtypeC、FtypeD、FtypeE、FtypeF分別對應C、D、E、F四種機型；i為執(zhí)飛的航班號.

5) 航空公司類別 一般而言，基地航司比非基地航司更熟悉場面環(huán)境，滑行速度相對更快；國內(nèi)飛行員與管制對話時沒有語言障礙，可以比外籍飛行員更快地執(zhí)行指令，因此可以認為航空公司類型與滑出時間有一定的聯(lián)系.從樣本數(shù)、平均滑行時間和滑行時間標準差三個角度對國內(nèi)航司、國外航司分別進行統(tǒng)計，結(jié)果見表3.可以看出國外航司執(zhí)飛的航班占比近11%，在相同范圍的滑行距離內(nèi)，國外航司平均滑行時間比國內(nèi)航司高出近2 min，可見航空公司類別不同對離港滑行時間具有一定影響，因此可將航空公司類別A分為國內(nèi)和國外兩種類型并設(shè)置為二值型變量，即當A=1時表示航班由國內(nèi)航司執(zhí)飛，A=0時表示航班由國外航司執(zhí)飛.

表3 不同類別航空公司樣本數(shù)、滑行時間均值及標準差

6) 機位影響指數(shù) 航空器的推出和滑行會占用推出引入線、機位資源和滑行道資源，導致周圍其他機位上的航空器運行受限.受機坪構(gòu)型等因素的影響，不同機位的飛機在推出滑行過程中影響的機位數(shù)量不同.受限機位數(shù)量越多，表明這個機位受其他機位的影響程度越大，因此對這個機位上航班的滑行時間影響也越大，因此將機位影響指數(shù)I也考慮進來.

基于上述分析，初步構(gòu)建出了10個一次特征作為航空器離港滑行時間預測的初始特征集合，即X={D,Ntxot,Nins,tdep,FtypeC,FtypeD,FtypeE,FtypeF,A,I}，其中特征Ntxot，Nins,A,I以及機型變量為本文首次提出.

1.2 二次特征構(gòu)建

在特征工程中，運用兩個特征的乘積就可以組成一對簡單的交互特征，即二次特征.這種相乘關(guān)系可以用邏輯操作符AND來類比，表示由一對條件形成的結(jié)果，這種特征常見于決策樹模型和廣義線性模型中.除了采用離港飛機數(shù)量、機型等單獨的特征來預測滑行時間，還可以將離港飛機數(shù)量和機型相乘，即根據(jù)某種機型的離港飛機數(shù)量來進行預測，通過構(gòu)建此類二次變量捕獲特征之間的交互作用.與僅使用單一特征相比，引入交互特征在一定程度上可能會為模型準確率的提升帶來顯著效果.

基于3.1的10個一次特征，可將它們分別兩兩相乘構(gòu)建出一組二次特征.需要注意的是，在一次特征中機型類別為正交型特征，意味著它們之間兩兩相乘為0，因此需將這部分二次特征從候選集中剔除.此外，F(xiàn)typeC,FtypeD,FtypeE,FtypeF,A這五個特征為二值變量，它的平方等于自身，因此也需將其從候選集中刪除，所以一共可構(gòu)建出44個二次特征.

本文構(gòu)建二次特征基于以下兩點原因：①在上述構(gòu)建的10個一次特征中FtypeC,FtypeD,FtypeE,FtypeF,A分別為表征機型和航空公司類型的二值變量，這些二值特征和其他特征之間構(gòu)成的交互特征可能會對模型產(chǎn)生重要的影響.②構(gòu)建三次或更高次的特征會增加模型復雜度，容易導致模型過擬合，因此我們僅考慮構(gòu)建二次特征.綜上，候選特征集由一次特征、二次特征共同組成，共包含54個候選特征.

2 滑出模型設(shè)計

2.1 模型選擇

為了選出合適的預測模型，使用K-最近鄰(k-nearest neighbor，KNN)、支持向量回歸(support vactor regression，SVR，包括Linear SVR、Poly SVR、RBF SVR)、決策樹(decision tree)這幾種常見的回歸算法對54個候選特征進行初步試驗，選取±3 min準確度、±5 min準確度、可決系數(shù)(R2)、均方誤差(mean square error，MSE)、平均絕對誤差(mean absolute error，MAE)、算法運行時間這6個指標對模型進行評估，結(jié)果見表4，決策樹模型的預測效果在各項指標上的表現(xiàn)都更佳，此外決策樹模型具備特征選擇的功能可以去除冗余優(yōu)化模型，因此選擇決策樹模型作為航空器離港滑行時間的預測模型.

表4 模型預測結(jié)果對比

2.2 決策樹模型構(gòu)建

CART樹是決策樹算法中用于解決回歸問題的常見算法，CART樹的生成是遞歸構(gòu)建二叉決策樹的過程，即每次劃分都把當前樣本集劃分為兩個子集，用誤差平方和最小化準則進行特征選擇.CART樹回歸算法具體如下：

假設(shè)X與Y分別為輸入與輸出變量，給定訓練數(shù)據(jù)集

D={(x1,y1),(x1,y1),…,(xn,yn)}

(3)

選擇第j個特征xj及其取值s作為切分變量和切分點，并定義兩個區(qū)域R1和R2

(4)

步驟1遍歷每一個特征及其每個取值，計算每個特征和切分點的損失函數(shù)，選擇最小損失函數(shù)所對應的最優(yōu)切分變量xj與切分點s，損失函數(shù)為

(5)

式中：cm為區(qū)間Rm上的輸出平均值.

(6)

步驟2使用上步得到的切分點將當前的輸入空間劃分為R1和R2兩個部分.

步驟3分別對兩個子區(qū)域R1和R2遞歸調(diào)用步驟1～2，直到不能繼續(xù)劃分.

步驟4最終將輸入空間劃分為k個部分R1,R2,…,Rk，并且在每個部分Rk上有一個固定的輸出值ck，那么回歸樹模型為

(7)

式中：I(x∈RK)為指示函數(shù).

3 基于決策樹的特征篩選

在機器學習的實際應用中，特征數(shù)量多、維度高容易引發(fā)“維度災難”.本文構(gòu)建的候選特征變量集中含有大量二維交互特征，增加了模型的訓練時間和計算成本，因此特征選擇具有十分重要的意義.具體而言，特征選擇的目的是在不降低預測準確性或者在對預測準確性影響很小的情況下，從候選特征集中去除冗余和不相關(guān)特征，選擇出能夠構(gòu)建一個簡約模型的關(guān)鍵特征子集.通過精簡無用的特征，可以降低模型的復雜程度、增強模型的泛化能力、提高計算效率.本文采用的決策樹算法能夠?qū)⑻卣鬟x擇作為模型訓練的一部分，即在模型訓練的同時自動進行特征選擇.

3.1 最優(yōu)特征集構(gòu)建

以首都國際機場2019年10月10日—2020年1月2日36R跑道離港航班的實際運行數(shù)據(jù)作為樣本數(shù)據(jù)集，采取隨機抽樣法進行劃分，其中70%的數(shù)據(jù)作為訓練集，其余30%作為測試集，訓練集樣本數(shù)為28 896，測試集樣本數(shù)為12 384.

決策樹的構(gòu)建會針對每個特征計算出一個劃分標準值，特征重要度為劃分標準減少量的歸一化值.CART回歸樹的特征重要度是誤差平方和減少量的歸一化值，公式為

(8)

式中：N為樣本的總數(shù)；Nt為當前節(jié)點的樣本數(shù)目；NtL為結(jié)點左子樹的樣本數(shù)目；NtR為結(jié)點右子樹的樣本數(shù)目；impurity為不純度，這里指的是誤差平方和；right_impurity為結(jié)點右子樹的不純度；left_impurity為結(jié)點左子樹的不純度.特征越重要，不純度就越?。徊患兌葴p小得越多，意味著該結(jié)點分裂的收益越大，該節(jié)點對應特征的重要度越高.

特征重要度反映了各個特征在模型構(gòu)建中對目標變量預測的貢獻能力，特征重要度越大說明對目標變量預測的貢獻能力越強.將重要度由大到小排序，表5為重要度排名前10位的特征，采用序列前向選擇算法進行特征篩選，即從空集開始依據(jù)重要度排名由高到低依次將特征加入特征子集，接著重新訓練模型，然后依據(jù)預測準確率最高的原則選擇最優(yōu)的特征子集.圖3為不同特征子集訓練出的模型所對應的平均絕對誤差(mean absolute error，MAE)，橫軸為每次用于模型訓練的特征個數(shù).

表5 特征重要度(前10位)

圖3 特征篩選迭代過程

由圖3迭代的結(jié)果可以看出，當添加5個特征變量時，平均絕對誤差最小，當繼續(xù)添加特征變量時，預測誤差在不斷變大.由此可以認為這5個特征變量構(gòu)成的特征子集是決策樹模型的關(guān)鍵特征子集，不僅可以提升模型的準確度，同時大大降低了模型的復雜程度，提高了計算效率.因此，本文構(gòu)建的最優(yōu)特征變量集為

最優(yōu)特征變量集由4個二次特征和1個一次特征組成，可以看出通過決策樹算法對特征變量進行篩選后，從10個候選一次特征中選出了4個一次特征，即Ntxot、Nins、A和FtypeC，這4個二次特征均與Ntxot有關(guān)，說明擁堵變量對滑行時間特征選擇具有十分重要的影響.

圖4 最優(yōu)二次特征和滑出時間的相關(guān)性分析

3.2 結(jié)果分析

對篩選出的五個交互特征的各項指標進行交叉驗證，對比使用篩選出的五個交互特征構(gòu)建的模型和單獨使用一次特征構(gòu)建的模型的性能指標見表6，與單獨采用一次特征相比，引入交互特征預測離港滑行時間可使準確率有較大的提升.圖5為滑行時間預測值與實際值的對比圖，橫軸為測試集樣本，縱軸為離港滑行時間的預測值和真實值，可見預測值能較好得擬合真實值的變化情況，再次驗證本文采用的方法具有較好的預測效果.

表6 預測結(jié)果對比

圖5 預測結(jié)果對比圖

4 結(jié) 論

1) 提出進離港瞬時流量、機型、航空公司等因素對離港滑行時間的影響，并將這些影響因素構(gòu)建成一次特征作為預測模型的輸入，取得了良好的效果.

2) 運用特征工程構(gòu)建交互特征，驗證了二值特征和其他特征之間的交互作用對預測模型產(chǎn)生的重要影響.

3) 采用決策樹模型進行特征篩選構(gòu)建最優(yōu)特征子集，在降低模型復雜度的同時提升了預測的準確度.

4) 與直接采用單獨的一次特征構(gòu)建預測模型的傳統(tǒng)做法相比，本文引入交互特征的方法使模型具有更好的預測準確率、R2和MAE.