何堅(jiān)，果紅艷，，姚遠(yuǎn)，卞磊，*，唐紅武，王殿勝

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

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

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

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

1 研究現(xiàn)狀

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

為了清晰描述航班恢復(fù)問(wèn)題的過(guò)程，定義以下幾類符號(hào)：

1）集合。可用飛機(jī)的集合P，航班的集合F，航線的集合L，機(jī)場(chǎng)的集合A。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 實(shí)驗(yàn)及結(jié)果分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié) 論

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

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

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

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