基于有效中轉(zhuǎn)時間預(yù)測的不正常航班恢復(fù)技術(shù)

何堅，果紅艷，，姚遠，卞磊，*，唐紅武，王殿勝

（1.北京工業(yè)大學(xué) 信息學(xué)部，北京 100124； 2.中航信移動科技有限公司，北京 100029）

航班計劃表是航空公司提前幾個月制定好的航班計劃，包括每個航班的出發(fā)地、目的地、離港時間、到港時間及指定的執(zhí)行飛機等信息。航班計劃表的制定需考慮旅客的季節(jié)性、機組人員的排班、飛機的定期維護等多方面因素。在航空公司的日常運營中，飛機故障和惡劣天氣造成的機場關(guān)閉、機場容量限制、空中交通管制等，都會導(dǎo)致航班不能按計劃執(zhí)行［1］。同時，飛機價格昂貴及其日常巨大的維護成本，使得航空公司盡可能地減少飛機閑置時間，以獲得更大的利潤。由于一個航班任務(wù)受到干擾后，會對其后續(xù)航班造成一系列的影響，為了減少航班計劃受干擾帶來的損失，航空公司需要及時修改航班計劃表，重新安排飛機、機組等資源，不正常航班恢復(fù)問題由此提出。

航班恢復(fù)問題涉及8個必要因素：開始恢復(fù)時間、結(jié)束恢復(fù)時間、飛機、機場、航班、航線、干擾、航班中轉(zhuǎn)時間。開始恢復(fù)時間是用戶指定的開始進行航班恢復(fù)的時間，結(jié)束恢復(fù)時間一般是當(dāng)日的24：00。在航班恢復(fù)過程中，飛機是執(zhí)行航班任務(wù)的主體，飛機具有初始可用時間、初始可用機場、結(jié)束可用時間、結(jié)束可用機場、注冊號等屬性。惡劣天氣可能會造成機場關(guān)閉的情況，機場關(guān)閉時禁止飛機到港、離港，只有在機場開啟時進出該機場的航班才能正常執(zhí)行。航班包括離港時間、到港時間、離港機場、到港機場、執(zhí)行的飛機等多種屬性。飛機執(zhí)行的航班任務(wù)組成了該飛機的航線。航班恢復(fù)過程中包含多種干擾因素，如飛機故障、空中交通管制等。航班的中轉(zhuǎn)時間是當(dāng)前航班的離港時間減去前序航班的到港時間，在大多數(shù)航班恢復(fù)模型中，航班中轉(zhuǎn)時間被設(shè)置成一個固定的常數(shù)。梁哲等［2］將30 min的固定中轉(zhuǎn)時間應(yīng)用到基于列向量生成算法的飛機恢復(fù)研究中。Yu等［3］將40 min的固定中轉(zhuǎn)時間應(yīng)用于時空網(wǎng)絡(luò)模型中求解航班恢復(fù)問題。樂美龍等［4］將60 min的固定中轉(zhuǎn)時間應(yīng)用到基于貪婪隨機自適應(yīng)搜索過程的飛機優(yōu)化恢復(fù)方案研究中。

固定的航班中轉(zhuǎn)時間往往會影響實際恢復(fù)效果。本文的主要貢獻在于引入了有效中轉(zhuǎn)時間的概念。有效中轉(zhuǎn)時間為特定的飛機在特定的時間、特定的機場、特定的天氣狀況下所需要的最短中轉(zhuǎn)時間。在航班恢復(fù)過程中，根據(jù)航班的離港機場、到港機場、離港時間、天氣及分配飛機的機型，使用LightGBM［5］方法預(yù)測該時間，替代原本的固定中轉(zhuǎn)時間。在保證航班中轉(zhuǎn)時間充足的前提下，減少航班中轉(zhuǎn)任務(wù)中無意義的等待時間，提升飛機利用率。實際實驗數(shù)據(jù)驗證了有效中轉(zhuǎn)時間在航班恢復(fù)問題中的有效性，降低了航班恢復(fù)的成本。將列向量生成算法與時空網(wǎng)絡(luò)模型進行橫向比較，驗證了飛機數(shù)量較多的恢復(fù)問題中，列向量生成算法可以在更短的時間內(nèi)，達到與時空網(wǎng)絡(luò)模型近似的恢復(fù)效果。

1 研究現(xiàn)狀

Teodorovic＇和Guberinic＇在 不 考 慮 航 班 取 消 的情況下建立模型，以減少乘客總延時為目標，采用分支定界法求解模型［6］，但示例只有3架飛機，缺少在大規(guī)模數(shù)據(jù)下的測試驗證。Jarrah等［7］在只考慮航班延誤或取消的情況下，以成本最小化為目標，加入了備用飛機及轉(zhuǎn)移飛機的策略，提出由延遲模型、取消模型構(gòu)成的時空網(wǎng)絡(luò)模型，但該模型無法同時解決航班延誤和取消的問題。Yan和Lin［8］以時空網(wǎng)絡(luò)模型為基礎(chǔ)，在機場關(guān)閉的情況下，提出將航班延誤、航班取消及轉(zhuǎn)移飛機等調(diào)度方法添加到一個框架中的調(diào)度模型。Cao和Kanafani［9-10］在Jarrah等［7］建 立 的 延 遲 模 型 基 礎(chǔ) 上提出了0-1二次規(guī)劃模型，能夠同時包含航班延遲和航班取消。Thengvall等［11-12］針對機場關(guān)閉后的多機隊飛機恢復(fù)問題，提出了基于多商品網(wǎng)絡(luò)的3種模型。梁哲等［2］進一步改進了Thengvall等［11-12］的工作，提出了同時具有機場容量約束及維護靈活性的列向量生成算法。

雖然現(xiàn)有航班恢復(fù)模型已考慮了多方面的約束條件與恢復(fù)策略，但都沒有考慮航班中轉(zhuǎn)時間對航班恢復(fù)的影響［13-17］。航班中轉(zhuǎn)時間是前一個航班到港后，下一個航班離港前飛機在機場停留的時間?，F(xiàn)有不正常航班恢復(fù)模型中，通常將中轉(zhuǎn)時間看作一個固定的常數(shù)［18-19］，而在實際中，由于天氣、機場流量等因素影響，航班中轉(zhuǎn)時間也是時刻變化的，固定的中轉(zhuǎn)時間會造成部分航班在執(zhí)行完中轉(zhuǎn)任務(wù)后，需要等待一段時間才能離港，降低了飛機的利用率。對此，根據(jù)航班相關(guān)特征，對每個航班的有效中轉(zhuǎn)時間進行預(yù)測。梯度提升樹（gradient boosting decision tree，GBDT）模型［20］是常用的預(yù)測算法，但在大數(shù)據(jù)的情況下，GBDT模型訓(xùn)練速度相對較慢。LightGBM模型是GBDT模型的一種［21］，用于解決GBDT模型在海量數(shù)據(jù)處理上遇到的問題，其具有訓(xùn)練速度快、模型精度高的優(yōu)點。Ke等［21］在多種數(shù)據(jù)集下實驗證明，當(dāng)模型的準確率相同時，LightGBM模型的訓(xùn)練速度是GBDT模型的20倍以上。因此，LightGBM模型被廣泛應(yīng)用于交通預(yù)測［22］、價 格 評 估［23］等 方 面。航 班 歷 史 信 息 數(shù) 據(jù)量較大，選擇使用LightGBM模型對航班的中轉(zhuǎn)時間進行預(yù)測，將預(yù)測結(jié)果應(yīng)用于不正常航班恢復(fù)模型中，通過列向量生成算法求解，生成新的航班計劃。

2 基于LightGBM的航班有效中轉(zhuǎn)時間預(yù)測模型

在分析影響航班中轉(zhuǎn)時間主要因素基礎(chǔ)上，建立基于LightGBM的航班有效中轉(zhuǎn)時間預(yù)測模型及評估技術(shù)。

2.1 影響航班中轉(zhuǎn)時間因素分析

航班的預(yù)計中轉(zhuǎn)時間為當(dāng)前航班的預(yù)計離港時間（estimated time of departure）與前序航班的預(yù)計到港時間（estimated time of arrival）之間的差值。為了有效預(yù)測航班的中轉(zhuǎn)時間，選取了2018年5月至2019年10月某航空公司的實際航班數(shù)據(jù)進行特征分析。該數(shù)據(jù)集包含了不同機型、時間、位置及多種天氣條件下的航班中轉(zhuǎn)時間記錄，具體特征如表1所示。影響航班中轉(zhuǎn)時間的因素主要包括：

表1 數(shù)據(jù)結(jié)構(gòu)特征Table 1 Data structure characteristics

1）機型因素。不同機型的飛機在執(zhí)行航班中轉(zhuǎn)任務(wù)時，需要完成的工作量不同。例如，座位數(shù)少的飛機在執(zhí)行乘客登機、離機、裝卸行李等任務(wù)時工作量較小，需要的時間較短。

2）離港機場因素。不同規(guī)模的機場每天航班起降架次有很大差異。2017年北京首都國際機場航班日高峰達到1 863架次，而長沙黃花國際機場僅有548架次。機場的繁忙程度會體現(xiàn)在航班起降架次上，機場繁忙時，可能會出現(xiàn)跑道被占用等資源不足的情況，航班只能在地面等待，中轉(zhuǎn)時間隨之增加。

3）到港機場因素。航班到港機場與離港機場之間的距離可能影響航班執(zhí)行中轉(zhuǎn)任務(wù)的工作量，對中轉(zhuǎn)時間造成影響。

4）天氣因素。當(dāng)天氣條件不佳時，為了保證飛行安全，可能會導(dǎo)致航班延誤，造成航班的中轉(zhuǎn)時間增加。

5）時間因素。圖1表示了數(shù)據(jù)集中2018年5月至2019年5月每個月的離港航班總數(shù)。不同月份離港航班數(shù)有明顯的波動。將2018年5月2日的航班數(shù)據(jù)以1 h為時間間隔分成24個時間段，每個時間段的離港航班個數(shù)如圖2所示，10：00—21：00之間，離港航班數(shù)量明顯多于其他時段。航班的時間因素與機場的起降架次相關(guān)，會對航班的中轉(zhuǎn)時間造成影響。此外，初始航班計劃會對航班的中轉(zhuǎn)時間造成影響。例如，某架飛機計劃到港時間為09：00，該飛機執(zhí)行的下一趟航班將于17：00離港，該航班的中轉(zhuǎn)時間為480 min，這種數(shù)據(jù)會影響航班中轉(zhuǎn)時間的預(yù)測。因此，對所有的航班數(shù)據(jù)進行預(yù)處理，將航班中轉(zhuǎn)時間偏大的數(shù)據(jù)剔除，只保留中轉(zhuǎn)時間在30～75 min之間的樣本。篩選后的數(shù)據(jù)集包含12萬條航班信息。

如圖1和圖2所示，航班的中轉(zhuǎn)時間與離港時機場的流量緊密相關(guān)。在不同的月份或同一天的不同時間段內(nèi)，航班的離港數(shù)量存在較大差異。因此，對原始數(shù)據(jù)集進行處理，提取到航班離港的月份、時間段數(shù)據(jù)。依據(jù)上述航班中轉(zhuǎn)時間影響因素，選取航班的離港機場、到港機場、機型、離港時間段、離港月份、天氣信息作為影響航班中轉(zhuǎn)時間預(yù)測模型的特征。

圖1 離港航班個數(shù)與月份關(guān)系Fig.1 Relationship between the number of departure flights and the months

圖2 2018年5月2日離港航班個數(shù)與時間關(guān)系Fig.2 Relationship between the number of departure flights and the time on May 2，2018

此外，針對原始數(shù)據(jù)集中存在數(shù)據(jù)缺失、數(shù)據(jù)重復(fù)問題，對原始數(shù)據(jù)進行缺失值填充、去重操作，對出發(fā)機場及到達機場通過mapping方式將類別信息映射成數(shù)值，再將機型、雪雨等天氣信息使用獨熱編碼（one-hot encoding）轉(zhuǎn)換成數(shù)值信息。

2.2 基于LightGBM的航班有效中轉(zhuǎn)時間預(yù)測

采用LightGBM模型對航班的中轉(zhuǎn)時間進行預(yù)測，LightGBM采用具有深度限制的按葉子生長（leaf-wise）策略，能夠提升模型的精確度，降低過擬合的風(fēng)險；同時，該模型使用直方圖算法，大幅度減少了內(nèi)存占用、執(zhí)行時間。

將2018年5月至2019年7月的9萬條數(shù)據(jù)作為訓(xùn)練集，將2019年8月至10月的3萬條航班數(shù)據(jù)作為測試集。提取的特征如2.1節(jié)所述，預(yù)測目標為航班的中轉(zhuǎn)時間，屬于連續(xù)值的預(yù)測問題，這類問題屬于機器學(xué)習(xí)中的回歸問題。模型的性能使用均方根誤差（root mean square error，RMSE）及平均絕對誤差（mean absolute error，MAE）來衡量，計算公式如下：

采用相同的特征，將LightGBM模型與GBDT模型進行實驗對比，實驗結(jié)果如表2所示。Light-GBM模型的RMSE及MAE這2個評估指標均優(yōu)于GBDT模型，并且LightGBM模型的訓(xùn)練時間小于GBDT模型。

表2 不同模型航班中轉(zhuǎn)時間性能對比Table 2 Performance comparison about different models’flight transit time

3 基于列向量生成算法的不正常航班恢復(fù)

基于第2節(jié)航班中轉(zhuǎn)時間預(yù)測模型，預(yù)測出恢復(fù)期內(nèi)所有航班被任意飛機在整點時刻執(zhí)行時的中轉(zhuǎn)時間。設(shè)計了基于列向量生成算法的不正常航班恢復(fù)算法，在每次使用航班中轉(zhuǎn)時間時，根據(jù)航班執(zhí)行的整點時刻、天氣、離港機場、到港機場、執(zhí)行任務(wù)的飛機等信息，從航班中轉(zhuǎn)模型的預(yù)測結(jié)果中讀取該航班的中轉(zhuǎn)時間，作為有效中轉(zhuǎn)時間。

3.1 基于列向量生成算法的不正常航班恢復(fù)算法

系統(tǒng)為每一航班設(shè)定最大許可延誤時間，據(jù)此可采用航班延誤、航班取消、航班交換3種策略實現(xiàn)不正常航班恢復(fù)。其中，當(dāng)航班的延誤時間小于該數(shù)值，航班允許延誤，可以使用航班延誤的策略來降低航班恢復(fù)方案的成本；當(dāng)航班的延誤時間超過該數(shù)值，航班通常會被取消，將飛機資源留給其他航班使用；在航班恢復(fù)過程中，可采用同類型飛機相互替代的方法（即航班交換策略）來設(shè)計恢復(fù)方案。此外，航班恢復(fù)過程受到可用飛機數(shù)量和機場運行、關(guān)閉狀態(tài)的影響。考慮飛機故障、機場關(guān)閉的情況，設(shè)計基于列向量生成算法的低成本航班恢復(fù)方案。

基于列向量生成算法的不正常航班恢復(fù)算法的流程如圖3所示。該流程主要分成4個階段：初始化過程、主問題的求解、子問題的求解及生成恢復(fù)方案。在初始化過程中，為每個飛機選擇執(zhí)行的航班序列，形成飛機的航線；在主問題中以恢復(fù)成本最小化作為目標，建立整數(shù)規(guī)劃模型，并計算其松弛模型，為每個飛機選擇執(zhí)行的航線；在子問題中，為飛機選擇恢復(fù)成本更低的航線加入主問題的航線選擇集合中，主問題與子問題迭代執(zhí)行，直到所有飛機的子問題都無法找到比當(dāng)前主問題選中航線更優(yōu)的航線，迭代過程結(jié)束；計算主問題的整數(shù)規(guī)劃模型，根據(jù)模型選中的航線，生成航班恢復(fù)方案。

圖3 列向量生成算法解決不正常航班恢復(fù)問題的流程Fig.3 Flowchart for solving irregular flight recovery problems by column vector generation algorithm

為了清晰描述航班恢復(fù)問題的過程，定義以下幾類符號：

1）集合?？捎蔑w機的集合P，航班的集合F，航線的集合L，機場的集合A。

2）參數(shù)。航班f取消的成本cf，飛機p執(zhí)行航線l的成本cp，l，航班f屬于航線l時bf，l值為1，否則bf，l值為0，航線l終止于機場a時bl，a值為1，否則bl，a為0，航班f原計劃由飛機p執(zhí)行時sp，f值為0，否則sp，f為1，恢復(fù)期結(jié)束時機場a需要的飛機數(shù)量ha，換飛機個數(shù)上限sp，恢復(fù)期結(jié)束后任何機場中每個飛機不平衡的成本cub；恢復(fù)期結(jié)束后所有機場不平衡的飛機個數(shù)numub（參數(shù)cf、cp，l、ha、sp、cub、numub均大于0）。

3）決策變量。如果飛機p執(zhí)行了航線l時xp，l值為1，否則xp，l值為0，如果航班f被取消時yf值為1，否則yf值為0。

基于上述符號，建立如下航線選擇整數(shù)規(guī)劃模型：

航班恢復(fù)過程以成本最小化為目標，如式（3）所示，恢復(fù)成本包含取消航班的成本及執(zhí)行航班的成本?；謴?fù)過程主要考慮如下約束：式（4）為航班覆蓋約束，表示每個航班只能執(zhí)行一次，或者取消該航班；式（5）為飛機任務(wù)約束，表示每個飛機最多只能執(zhí)行一條航線；式（6）為機場的飛機流平衡約束，恢復(fù)期結(jié)束時，各個機場?？康娘w機個數(shù)應(yīng)該等于恢復(fù)期結(jié)束后待執(zhí)行航班需要的飛機個數(shù)；式（7）表示在主問題的計算結(jié)果中，所有飛機選中的航班集合內(nèi)，換飛機的航班個數(shù)之和不能超出限制個數(shù)；式（8）和式（9）表示決策變量的取值約束。

3.2 航班恢復(fù)算法的初始化過程

航班恢復(fù)過程中，初始化過程的目的是為主問題中飛機航線提供初始的選擇方案。實驗分析發(fā)現(xiàn)，列向量生成算法的初始解會對算法的迭代次數(shù)產(chǎn)生很大影響。當(dāng)初始解足夠好時，列向量生成算法可經(jīng)過幾次迭代就得出最終恢復(fù)方案。對此，采用初始化原始航線的方法為每架飛機生成一條初始航線，步驟如下：

步驟1 以飛機注冊號、計劃離港時間對航班進行排序；根據(jù)航班的狀態(tài)（航班執(zhí)行中、航班未離港、航班已到港）、航班預(yù)計飛行時長、機場的狀態(tài)（機場開啟、機場關(guān)閉）及飛機的狀態(tài)（飛機正常、飛機故障）計算每架飛機在恢復(fù)期內(nèi)的初始可用時間、初始可用機場。

步驟2 從飛機集合中選出一架飛機，若飛機正常，執(zhí)行步驟3，若飛機故障，執(zhí)行步驟4。

步驟3 遍歷飛機的初始飛行計劃，根據(jù)飛機所在機場、可用時間、離港機場、到港機場的狀態(tài)信息選出飛機執(zhí)行的下一個航班任務(wù)，更新該飛機的可用時間及機場信息，遍歷完該飛機執(zhí)行的所有航班之后，將該飛機從飛機集合中刪除，并將航線加入到航線集合中。

步驟4 查看飛機的可用時間，若飛機在整個恢復(fù)期內(nèi)都不可用，則該飛機的航線為空；若飛機在恢復(fù)期內(nèi)一段時間內(nèi)不可用，只能在飛機的可用時間安排航班任務(wù)。

步驟5 繼續(xù)執(zhí)行步驟2，直到飛機集合為空，初始化過程結(jié)束，每個飛機都得到一條初始航線。

3.3 航班恢復(fù)算法的主問題

航班恢復(fù)主問題的求解過程就是飛機航線的選擇過程，屬于整數(shù)線性規(guī)劃問題。航班恢復(fù)主問題的整數(shù)規(guī)劃模型在3.1節(jié)中已經(jīng)說明。模型的目標函數(shù)如式（3）所示，模型以恢復(fù)成本最小化為目標。在主問題的計算中，需要考慮多種類型的約束，式（4）～式（6）均為主問題求解的物理約束。此外，提出航班恢復(fù)實際業(yè)務(wù)中對換飛機總個數(shù)的業(yè)務(wù)條件約束，如式（7）所示。梁哲［2］和Yu［3］等都沒有此類型的約束，但在航班實際運行中，這樣的約束是必要的，也是符合航空公司具體操作規(guī)范的。解決不正常航班恢復(fù)問題的流程如圖4所示，圖中展開說明了主問題的計算流程，在計算主問題的整數(shù)型性規(guī)劃時，需要構(gòu)建物理約束（式（4）～式（6））、業(yè)務(wù)條件約束（式（7））及決策變量約束（式（8）、式（9）），并根據(jù)可行航線集合生成恢復(fù)方案。

圖4 列向量生成算法主問題的流程Fig.4 Flowchart of main problem using column vector generation algorithm

在實際應(yīng)用中，式（6）的飛機流平衡約束可能造成模型無解。因此，可以去掉此約束并采用式（10）在目標函數(shù)中增加飛機不平衡成本因子來修正式（3）。

為了使用列向量生成算法計算航班恢復(fù)問題，對主問題的整數(shù)線性規(guī)劃模型進行線性規(guī)劃松弛，將約束條件式（8）和式（9）替換為式（11）和式（12）的非整數(shù)約束，建立松弛模型。

3.4 航班恢復(fù)算法的子問題

子問題的任務(wù)是計算每個飛機的所有可行航線的簡約成本，從而選擇出成本最優(yōu)的解。如圖5所示，圖中展開介紹了子問題的處理流程，在子問題的計算中，僅需要考慮主問題中物理約束帶來的影響。令αf表示式（4）中對于航班f的對偶變量，令βp表示式（5）中對于飛機p的對偶變量，令γa表示式（6）中對于機場a的對偶變量，飛機p執(zhí)行航線l的簡約成本ˉcp，l按照式（13）計算：

圖5 列向量生成算法子問題的流程Fig.5 Flowchart of subproblem using column vector generation algorithm

飛機p執(zhí)行航線l的成本cp，l根據(jù)式（14）計算：

飛機p執(zhí)行航線l時的平均航班簡約成本meanp，l按照式（15）計算：

為了篩選出飛機的最優(yōu)可行航線，應(yīng)計算出飛機p所有航線的簡約成本的最小值minc，p及整條航線上所有航班的平均簡約成本的最小值minmeanc，f，按照式（17）、式（18）計算：

若minc，p＜0，則飛機p選中的航線l優(yōu)于該飛機在主問題中選中的航線；若minc，p≥0且minmeanc，f＜0，則飛機p選中的航線l優(yōu)于該飛機在主問題中選中的航線；若minc，p≥0且minmeanc，f≥0，則飛機p的最優(yōu)航線就是主問題中選擇的航線。

使用列向量生成算法進行航班恢復(fù)的步驟如下：

步驟1 生成航班恢復(fù)初始解，將初始解加入主問題的航線集合R中。

步驟2 根據(jù)R計算主問題的線性模型，得出計算結(jié)果及對偶變量αf、βp、γa，并根據(jù)每個選中航線的總成本及選中航線上的總航班數(shù)，計算出每個選中航線上所有航班的平均航班成本ˉcp。

步驟3 根據(jù)航班計劃的預(yù)計離港時間、預(yù)計到港時間計算出所有航班的計劃執(zhí)行時間。根據(jù)飛機的可用時間、飛機的可用機場、機場的可用時間、航班的預(yù)計離港時間、航班的計劃執(zhí)行時間這些信息，并且將恢復(fù)期開始時間、恢復(fù)期結(jié)束時間作為航線的限制信息，控制航線的長度，使用枚舉法，為所有飛機生成全部可行航線集合S。

步驟5 若集合C中存在航線，將C中的所有航線加入集合R中，執(zhí)行步驟2；若C為空集合，則執(zhí)行步驟6。

步驟6 根據(jù)主問題的整數(shù)規(guī)劃模型，計算出整數(shù)解。

步驟7 根據(jù)步驟6中的整數(shù)解，生成新的航班計劃表。

4 實驗及結(jié)果分析

采用JetBrains PyCharm 2019對本文算法進行了編程實現(xiàn)。算法運行在Win10操作系統(tǒng)，運行內(nèi)存為32 GB，并使用大規(guī)模數(shù)學(xué)規(guī)劃優(yōu)化器Gurobi求解主問題的線性規(guī)劃及整數(shù)規(guī)劃模型。

實驗數(shù)據(jù)均來自于航旅縱橫APP官方平臺（http：//www.umetrip.com/），其計算及數(shù)據(jù)可為航班運控、航延服務(wù)、疫情防控［24］等提供精準服務(wù)。數(shù)據(jù)按航班規(guī)模分為5組，航班個數(shù)分別為50、100、200、400、800，飛機個數(shù)分別為19、37、71、144、305，算例中給出了離港、到港涉及機場的總和。算例中存在飛機故障及機場關(guān)閉的情況，恢復(fù)期內(nèi)涉及的航班個數(shù)及機場個數(shù)、飛機故障個數(shù)等信息如表3所示。表4為每個算例的成本參數(shù)。

表3 算例基本參數(shù)Table 3 Basic par ameters of calculation examples

表4 算例成本參數(shù)Table 4 Cost parameter s of calculation examples

實驗選擇以時空網(wǎng)絡(luò)模型的恢復(fù)結(jié)果作為對照，將時空網(wǎng)絡(luò)模型的恢復(fù)結(jié)果與改進后的列向量生成模型恢復(fù)結(jié)果進行比較。其中，未使用有效中轉(zhuǎn)時間的時空網(wǎng)絡(luò)模型及未使用有效中轉(zhuǎn)時間的列向量生成模型分別記作模型A及模型B，2個模型的恢復(fù)結(jié)果如表5、表6所示。使用了有效中轉(zhuǎn)時間的時空網(wǎng)絡(luò)模型及使用了有效中轉(zhuǎn)時間的列向量生成模型分別記作模型C、模型D，2個模型的恢復(fù)結(jié)果如表7、表8所示。

表5 模型A的計算結(jié)果Table 5 Calculation r esults of Model A

表6 模型B的計算結(jié)果Table 6 Calculation results of Model B

表7 模型C的計算結(jié)果Table 7 Calculation results of Model C

表8 模型D的計算結(jié)果Table 8 Calculation results of Model D

將算例F800（航班數(shù)800）作為樣本，航班的中轉(zhuǎn)時間分布情況如表9所示，表中包含設(shè)置的固定中轉(zhuǎn)時間及在當(dāng)前中轉(zhuǎn)時間下能夠完成中轉(zhuǎn)任務(wù)的航班比例。當(dāng)固定中轉(zhuǎn)時間為30 min［2］時，沒有航班能夠完成中轉(zhuǎn)任務(wù)，當(dāng)固定中轉(zhuǎn)時間為40 min［3］與60 min［4］時，大多數(shù)航班不能完成中轉(zhuǎn)任務(wù)，當(dāng)固定中轉(zhuǎn)時間為75 min時，63.15%的航班能夠完成中轉(zhuǎn)任務(wù)。因此，選取75 min作為固定中轉(zhuǎn)時間，應(yīng)用到模型A、模型B中。所有算例的換飛機個數(shù)限制在30架內(nèi)，時空網(wǎng)絡(luò)模型采用30 min［3］的時間窗口。上述3個模型的恢復(fù)成本包括航班延誤成本、航班取消成本、換飛機成本及機場的飛機不平衡成本4部分。通過恢復(fù)結(jié)果的對比可以發(fā)現(xiàn)，應(yīng)用了有效中轉(zhuǎn)時間的列向量生成模型（模型D），能夠取得最小的恢復(fù)代價。同時，與時空網(wǎng)絡(luò)模型相比，列向量生成算法在運行時間上有很大的優(yōu)勢。模型A、模型B在不同航班規(guī)模下的運行時間如圖6所示。隨著算例規(guī)模的增加，列向量生成模型運行時間的增長速度遠小于時空網(wǎng)絡(luò)模型。

圖6 列向量生成算法與時空網(wǎng)絡(luò)模型運行時間對比Fig.6 Comparison of operation time between column vector generation algorithm and spatio-temporal network model

表9 算例F800的航班中轉(zhuǎn)時間分布Table 9 Flight transit time distribution of scenario F800

模型D使用Gurobi優(yōu)化器對主問題的求解結(jié)果如表10所示。其中，LP為迭代結(jié)束時主問題線性規(guī)劃模型的最終計算結(jié)果，IP為主問題整數(shù)規(guī)劃模型的最終計算結(jié)果，最優(yōu)間隔比例由式（19）計算得出。模型D的4個算例的最優(yōu)間隔比例均為0%，取得了最優(yōu)解，算例F400沒有取得最優(yōu)解，但是該算例的最優(yōu)間隔比例僅為0.059%，證明了列向量生成算法的有效性。

表10 基于模型D的優(yōu)化器實驗結(jié)果Table 10 Experimental results of optimizer based on Model D

對比表5和表6，由于時空網(wǎng)絡(luò)模型是采用將所有的航線直接進行優(yōu)化計算的方式，航線個數(shù)隨著航班規(guī)模的增長迅速增加，使得模型在求解大規(guī)模問題時計算速度非常慢。列向量生成算法采用迭代的方式選擇航線，使得每次迭代過程的計算量都遠小于時空網(wǎng)絡(luò)模型，并且列向量生成算法可以通過控制迭代次數(shù)的方式在有限的時間中求得最低的恢復(fù)成本。時空網(wǎng)絡(luò)方法采用離散的航班延誤時間，在某個時間間隔內(nèi)，航班未能執(zhí)行，只能在下一個時間間隔才可能離港，離散的延誤時間可能會導(dǎo)致模型求出的最小成本高于最優(yōu)解的最小成本。而列向量生成算法采用連續(xù)的航班延誤時間，飛機可用時就可以分配飛機離港，解決了這一問題。同時，時空網(wǎng)絡(luò)模型需要將時間軸劃分成多個相同長度的時間窗，時間窗口的長短不易控制，如果時間窗口較長，時空網(wǎng)絡(luò)模型求得的恢復(fù)成本會偏高，而時間窗口較短，模型的恢復(fù)成本會降低，但是模型的求解時間會更久。列向量生成算法采用連續(xù)的延誤時間，不需要考慮這一問題。通過對比列向量生成算法及時空網(wǎng)絡(luò)模型的恢復(fù)結(jié)果，列向量生成算法存在恢復(fù)成本高于時空網(wǎng)絡(luò)模型的情況，若列向量生成算法在篩選滿足子問題約束的航線時沒有遺漏，則列向量生成算法可以取得與時空網(wǎng)絡(luò)模型相同或者更低的恢復(fù)成本。由此可知，列向量生成算法篩選滿足子問題約束的航線，并加入到主問題的優(yōu)化集合中，這一特點使得列向量生成算法在計算最優(yōu)解時，可能遺漏最優(yōu)解中包含的航線。列向量生成算法的這一特點及時空網(wǎng)絡(luò)模型的時間窗口較長都可能導(dǎo)致模型求得的恢復(fù)成本比最優(yōu)恢復(fù)成本高，因此時空網(wǎng)絡(luò)模型與列向量生成算法各有優(yōu)劣。但是在大規(guī)模航班恢復(fù)過程中，2個模型的恢復(fù)成本相似時，時空網(wǎng)絡(luò)模型的計算時間可以達到列向量生成算法的3倍以上，影響了恢復(fù)結(jié)果的實時性。因此，在計算大規(guī)模航班恢復(fù)問題時，列向量生成算法的優(yōu)勢明顯。表7、表8顯示了將航班有效中轉(zhuǎn)時間預(yù)測模型分別應(yīng)用到時空網(wǎng)絡(luò)模型和列向量生成算法中的航班恢復(fù)結(jié)果，與表5、表6相比，雖然模型的運行時間可能稍有增加，但是2個模型的恢復(fù)成本均有顯著的下降。

5 結(jié) 論

將航班中轉(zhuǎn)時間預(yù)測模型與改進后的列向量生成算法相結(jié)合，提出了一種基于有效中轉(zhuǎn)時間的不正常航班恢復(fù)模型。通過對比實驗，得出以下結(jié)論：

1）基于列向量生成算法的航班恢復(fù)模型與時空網(wǎng)絡(luò)模型相比，在恢復(fù)成本基本一致的情況下，計算時間更少。并且隨著航班規(guī)模的增加，在時間上的差異會進一步增大。當(dāng)航班規(guī)模是400架時，時空網(wǎng)絡(luò)模型的恢復(fù)時間是列向量生成算法的2.97倍；當(dāng)航班規(guī)模是800架時，時空網(wǎng)絡(luò)模型的恢復(fù)時間是列向量生成算法的3.67倍。

2）將有效中轉(zhuǎn)時間應(yīng)用于不正常航班恢復(fù)模型，雖然模型的計算時間有所增加，但航班的恢復(fù)成本明顯降低。在大規(guī)?；謴?fù)場景下，可以將航班恢復(fù)成本減少36.3%。

不正常航班恢復(fù)問題涉及到飛機恢復(fù)、機組恢復(fù)、乘客恢復(fù)3個階段，本文中只針對飛機恢復(fù)階段進行了研究，下一步可以針對后2個階段進行研究，逐漸完善所提出的不正常航班恢復(fù)模型。在飛機恢復(fù)問題中，只考慮了以恢復(fù)成本為目標的航班恢復(fù)問題，在未來的研究中，可以將航班恢復(fù)成本與航班正常率等多個目標同時添加到航班恢復(fù)模型中，實現(xiàn)多目標條件下的航班恢復(fù)模型。