戴福青，張舜堯

（中國(guó)民航大學(xué)空中交通管理學(xué)院，天津 300300）

不正常航班是指由于天氣、流量控制、機(jī)務(wù)維修、旅客等因素導(dǎo)致航班計(jì)劃無(wú)法正常執(zhí)行。不正常航班不僅使航空公司遭受經(jīng)濟(jì)損失，還會(huì)打亂旅客出行安排，進(jìn)而對(duì)航空公司產(chǎn)生負(fù)面影響。因此，在出現(xiàn)不正常航班時(shí)，盡快恢復(fù)航班計(jì)劃是航空公司決策者的首要任務(wù)。航班計(jì)劃的恢復(fù)分為3 個(gè)步驟：飛機(jī)計(jì)劃恢復(fù)、機(jī)組恢復(fù)及旅客恢復(fù)。由于飛機(jī)是航空公司時(shí)間價(jià)值最高的資源，航班恢復(fù)時(shí)優(yōu)先恢復(fù)飛機(jī)計(jì)劃。以下探討的是飛機(jī)計(jì)劃的恢復(fù)。

國(guó)內(nèi)外對(duì)于航班恢復(fù)的研究已有很多成果。賽秋玥等[1]構(gòu)造了離散時(shí)空網(wǎng)絡(luò)，采用可行路徑生成算法對(duì)不正常航班生成飛機(jī)的可行路徑。上官棟棟等[2]綜合考慮航班延誤、飛機(jī)置換和航班取消成本，建立了航班恢復(fù)模型，并用遺傳算法求解。吳剛等[3]構(gòu)建了多商品流網(wǎng)絡(luò)模型，運(yùn)用一種列生成算法求解模型。Teodorovic 等[4]采用分支定界方法求解了以總的旅客延誤時(shí)間達(dá)到最小為目標(biāo)函數(shù)的模型。唐小衛(wèi)等[5]提出一種貪婪模擬退火算法，提高了貪婪算法的收斂性，降低了問(wèn)題陷入局部最優(yōu)解的概率。趙秀麗等[6-7]構(gòu)建了以延誤成本最小或延誤時(shí)間最短為目標(biāo)函數(shù)的模型，并提出了旅客失望溢出成本的概念，采用啟發(fā)式方法并調(diào)用匈牙利法對(duì)模型求解，此外，還通過(guò)跟蹤航班延誤的前進(jìn)方向，設(shè)計(jì)了一種逐延誤指派算法，隨著航班串被重新指派而動(dòng)態(tài)生成飛機(jī)路徑。萬(wàn)俊強(qiáng)等[8]在協(xié)同決策環(huán)境下對(duì)不正常航班恢復(fù)策略的可行性進(jìn)行有效評(píng)估，采用可拓關(guān)聯(lián)函數(shù)及可拓評(píng)價(jià)方法確定模型中的指標(biāo)權(quán)重，并以定量結(jié)果來(lái)確定恢復(fù)策略的可行性。Argüello等[9]將貪婪隨機(jī)自適應(yīng)搜索（GRASP,greedy randomized adaptive search procedures）算法應(yīng)用于求解飛機(jī)路徑恢復(fù)問(wèn)題。劉艷紅等[10]分析了航班延誤的恢復(fù)調(diào)度問(wèn)題，提出了一種機(jī)場(chǎng)大面積航班延誤恢復(fù)模型，并構(gòu)造了基于免疫機(jī)制的免疫遺傳算法來(lái)求解模型。

現(xiàn)有的研究成果較多，但仍存在以下問(wèn)題：①在計(jì)算航空公司不正常航班損失時(shí)考慮因素過(guò)少，影響決策的合理性；②在航班恢復(fù)過(guò)程中沒(méi)有優(yōu)先考慮對(duì)時(shí)間敏感度更高、能為航空公司帶來(lái)更大利潤(rùn)的商務(wù)艙旅客，可能會(huì)導(dǎo)致商務(wù)艙旅客因延誤時(shí)間過(guò)長(zhǎng)而流失，對(duì)航空公司造成巨大損失；③已有的算法無(wú)法形象地描繪航班恢復(fù)路徑，且易出現(xiàn)陷入局部最優(yōu)解的情況。因此，將航空公司不正常航班損失細(xì)分為6 種，在文獻(xiàn)[6]提出的由于航班延誤導(dǎo)致的旅客流失基礎(chǔ)上，進(jìn)一步劃分了商務(wù)艙旅客和經(jīng)濟(jì)艙旅客的流失。將經(jīng)濟(jì)學(xué)中機(jī)會(huì)成本的概念應(yīng)用于航班恢復(fù)中，使損失的計(jì)算更加精細(xì)化。最終建立了以航空公司經(jīng)濟(jì)損失最小為目標(biāo)函數(shù)的航班恢復(fù)模型，并設(shè)計(jì)了一種動(dòng)態(tài)決策算法進(jìn)行求解。

1 不正常航班損失種類(lèi)

將不正常航班損失分為以下6 種。

1）飛機(jī)折舊

由于執(zhí)行航班的飛機(jī)在航班預(yù)計(jì)起飛前就已做好起飛準(zhǔn)備，在地面等待時(shí)會(huì)產(chǎn)生折舊費(fèi)用，即其中：ai為飛機(jī)i每分鐘的折舊費(fèi)用；為飛機(jī)i在地面等待執(zhí)行航班f的停場(chǎng)時(shí)間（航班f的計(jì)劃出發(fā)時(shí)間減飛機(jī)i的就緒時(shí)間）。

2）飛機(jī)停場(chǎng)費(fèi)用

根據(jù)中國(guó)民用航空局（簡(jiǎn)稱(chēng)民航局）規(guī)定，飛機(jī)停場(chǎng)2 h 以?xún)?nèi)免收停場(chǎng)費(fèi)用；超過(guò)2 h，每停場(chǎng)24 h 按照起降費(fèi)的15%計(jì)收。不足24 h 按24 h 計(jì)收。飛機(jī)停場(chǎng)費(fèi)用表示為

式中：pi為飛機(jī)起降費(fèi)用；符號(hào)[]表示向上取整。根據(jù)機(jī)場(chǎng)類(lèi)別的不同，飛機(jī)起飛重量不同，其起降費(fèi)用也不同，如表1所示，其中Ti為飛機(jī)i的最大起飛重量。

表1 飛機(jī)起降費(fèi)用Tab.1 Cost of aircraft takeoff and landing

3）機(jī)會(huì)成本

機(jī)會(huì)成本的定義[12]為：企業(yè)為從事某項(xiàng)經(jīng)營(yíng)活動(dòng)而放棄另一項(xiàng)經(jīng)營(yíng)活動(dòng)的機(jī)會(huì)，或利用一定資源獲得某種收入時(shí)所放棄的另一種收入。假設(shè)某航空公司在某機(jī)場(chǎng)擁有1 架飛機(jī)i，其就緒時(shí)間為t，此時(shí)該機(jī)場(chǎng)有兩個(gè)航班f1、f2待指派，預(yù)計(jì)起飛時(shí)間分別為t1、t2，t1＜t＜t2，若該航空公司決定將飛機(jī)指派給航班f2，由于航班起飛時(shí)間只能推后不能提前，該飛機(jī)需要在地面等待的時(shí)間為t2-t。而該時(shí)間內(nèi)由于無(wú)法執(zhí)行航班f1會(huì)造成經(jīng)濟(jì)損失。該損失即為航空公司為了執(zhí)行航班f2放棄執(zhí)行航班f1的機(jī)會(huì)成本。

在航班恢復(fù)問(wèn)題中，重新定義機(jī)會(huì)成本為：飛機(jī)的就緒時(shí)間早于航班的預(yù)計(jì)起飛時(shí)間，在地面等待起飛的時(shí)間里不能執(zhí)行其他飛行任務(wù)造成的潛在損失，即，其中g(shù)為可由航空公司單位飛行時(shí)間凈利潤(rùn)。

在航班恢復(fù)問(wèn)題中考慮機(jī)會(huì)成本的優(yōu)勢(shì)有：①更加精細(xì)化地進(jìn)行成本管理；②當(dāng)決策者對(duì)航班進(jìn)行分配時(shí)，可避免出現(xiàn)飛機(jī)在地面等待時(shí)間過(guò)長(zhǎng)的不合理指派；③使航班恢復(fù)模型更貼近實(shí)際，得出更好的優(yōu)化結(jié)果。

4）旅客失望溢出成本

參見(jiàn)文獻(xiàn)[6]中提出的旅客失望溢出成本概念，給出旅客失望溢出系數(shù)，即

旅客失望溢出成本

D=p×q×u

式中：p是該航班的旅客人數(shù)；q是該航班的平均票價(jià)。

該結(jié)論具有一定價(jià)值，但由于商務(wù)艙旅客和經(jīng)濟(jì)艙旅客對(duì)于時(shí)間的敏感度完全不同，而航空公司商務(wù)艙的銷(xiāo)售收入又占據(jù)重要位置，因此，商務(wù)艙和經(jīng)濟(jì)艙的旅客失望溢出系數(shù)應(yīng)取不同值。令經(jīng)濟(jì)艙的旅客失望溢出系數(shù)u1=u，商務(wù)艙的旅客失望溢出系數(shù)u2=w×u，其中w為商務(wù)艙旅客時(shí)間敏感系數(shù)，航空公司決策者可視實(shí)際情況給w賦值。

5）旅客賠償

民航局規(guī)定：延誤時(shí)間超過(guò)4 h 不足8 h，賠償標(biāo)準(zhǔn)不低于200 元；延誤時(shí)間超過(guò)8 h，賠償標(biāo)準(zhǔn)不低于400 元。

6）航班取消成本

航班取消成本按照該航班延誤8 h 計(jì)算。

2 航班恢復(fù)模型

模型以第1 節(jié)提到的6 種不正常航班損失之和最小為目標(biāo)函數(shù)，同時(shí)考慮航班覆蓋約束、飛機(jī)流平衡約束等約束條件。假定F為航班集合，航班f∈F；A為系統(tǒng)內(nèi)可用飛機(jī)集合，飛機(jī)i∈A；S為機(jī)場(chǎng)集合，機(jī)場(chǎng)s∈S，建立航班恢復(fù)目標(biāo)函數(shù)如下

約束條件如下

3 動(dòng)態(tài)決策算法

動(dòng)態(tài)決策算法相較于已有的一些算法有以下優(yōu)點(diǎn)：①能夠快速求解；②不易于陷入局部最優(yōu)；③求解過(guò)程較直觀。

航班恢復(fù)問(wèn)題本質(zhì)上就是將飛機(jī)動(dòng)態(tài)地指派到符合約束條件的航班上，最后使得指派之后的航班計(jì)劃成本最小，即所有飛機(jī)飛行路徑的集合成本最小。因此，只需要確定所有飛機(jī)可能的飛行路徑，并找出飛行路徑總成本最小的方案即可。算法思路如下。

步驟1確定飛機(jī)的就緒時(shí)間及出發(fā)機(jī)場(chǎng)，搜索所有從該機(jī)場(chǎng)出發(fā)的航班，將飛機(jī)與航班進(jìn)行匹配，判斷是否滿(mǎn)足模型中的式（4）和式（5），若滿(mǎn)足，則引出1 條航班邊，若不滿(mǎn)足，則檢查下個(gè)航班。直到完成所有匹配。

步驟2更新飛機(jī)的就緒時(shí)間及出發(fā)機(jī)場(chǎng)。就緒時(shí)間=前序航班的實(shí)際出發(fā)時(shí)間+飛行時(shí)間+過(guò)站時(shí)間，出發(fā)機(jī)場(chǎng)為前序航班的到達(dá)機(jī)場(chǎng)。

步驟3重復(fù)上述過(guò)程，直至飛機(jī)執(zhí)飛的第n個(gè)航班的降落時(shí)間小于24：00，而第n+1 個(gè)航班的降落時(shí)間超過(guò)24：00。

步驟4利用步驟1、2、3 繪制飛機(jī)飛行路徑圖，如圖1所示（方塊代表飛機(jī)的到達(dá)機(jī)場(chǎng)及出發(fā)機(jī)場(chǎng)，方塊之間的連線代表飛機(jī)能夠執(zhí)飛的航班）。

圖1 可行飛行路徑圖Fig.1 Feasible flight path

步驟5由飛機(jī)所經(jīng)機(jī)場(chǎng)的就緒時(shí)間及從該機(jī)場(chǎng)出發(fā)的可匹配航班的預(yù)計(jì)起飛時(shí)間計(jì)算飛機(jī)執(zhí)行這些航班的成本。以所有飛機(jī)飛行路徑總成本最小建立目標(biāo)函數(shù)。

步驟6由飛行路徑圖寫(xiě)出約束條件。由于飛行路徑圖的繪制過(guò)程中已滿(mǎn)足式（4）和式（5），同時(shí)通過(guò)飛行路徑圖可直觀看到：①每架飛機(jī)在每輪指派時(shí)最多安排1 個(gè)航班任務(wù)，即在航班任務(wù)f1、f2、f3中最多執(zhí)行1 個(gè)，包含式（3）；②飛機(jī)前序航班的到達(dá)機(jī)場(chǎng)為后續(xù)航班的出發(fā)機(jī)場(chǎng)，即想要執(zhí)行航班f5，就必須先執(zhí)行航班f1，包含式（6）。式（1）、式（2）和（7）可直接寫(xiě)出。

步驟7根據(jù)目標(biāo)函數(shù)及約束條件編程求解模型。

隨著航班量和機(jī)場(chǎng)數(shù)目的增加，飛機(jī)的可行路徑數(shù)目會(huì)呈指數(shù)級(jí)上升，為了避免解空間過(guò)大導(dǎo)致求解速度達(dá)不到實(shí)際要求，規(guī)定飛機(jī)與航班之間銜接時(shí)間不得超過(guò)300 min，所有超過(guò)該時(shí)間的匹配均視為無(wú)效匹配。剪去無(wú)效匹配的航班邊，重新構(gòu)造所有飛機(jī)的飛行路徑，將不確定的、動(dòng)態(tài)指派問(wèn)題轉(zhuǎn)化為確定的、靜態(tài)的指派問(wèn)題，大大降低了求解難度。

4 算例分析

表2 是某航空公司一天內(nèi)的部分航班計(jì)劃，涉及10 個(gè)航班、5 架飛機(jī)、3 個(gè)機(jī)場(chǎng)。尾號(hào)為3982 的飛機(jī)由于機(jī)械故障當(dāng)天無(wú)法執(zhí)行航班任務(wù)，航班f7、f8被取消。已知B737 的折舊成本為100 元/min，最大起飛重量為78 t，A310 的折舊成本為130 元/min，最大起飛重量為138 t；商務(wù)艙旅客時(shí)間敏感系數(shù)取1.2；根據(jù)該航空公司年報(bào)計(jì)算可得機(jī)會(huì)成本為87 元/min。

表2 待恢復(fù)的航班計(jì)劃表Tab.2 Flight schedule to be recovered

根據(jù)算法思路，以尾號(hào)3912 為例構(gòu)建出飛機(jī)的可行飛行路徑圖，如圖2所示。

圖2 尾號(hào)3912 的飛機(jī)可行飛行路徑圖Fig.2 Feasible flight path diagram for aircraft with tail No.3912

圖2 中：該飛機(jī)在上海機(jī)場(chǎng)的就緒時(shí)間為08：00，可執(zhí)行的航班為f1，到達(dá)廣州機(jī)場(chǎng)；在廣州機(jī)場(chǎng)的就緒時(shí)間為11：00，可執(zhí)行的航班有f2、f3、f5、f10，分別到達(dá)上海機(jī)場(chǎng)、北京機(jī)場(chǎng)、上海機(jī)場(chǎng)和上海機(jī)場(chǎng)，就緒時(shí)間分別為14：00，16：00，14：00，15：20?？尚新窂侥┪驳臋C(jī)場(chǎng)表示該飛機(jī)的過(guò)夜機(jī)場(chǎng)。

式中：xijk表示飛機(jī)i指派給第j個(gè)路徑航班號(hào)為k的航班為1 時(shí)，否則為0；Cijk為飛機(jī)執(zhí)飛航班的成本矩陣。由于篇幅所限，約束條件不再列出，優(yōu)化結(jié)果如表3所示。

表3 恢復(fù)后的航班計(jì)劃表Tab.3 Recovered flight schedule

恢復(fù)前目標(biāo)函數(shù)值為254 560 元，恢復(fù)后目標(biāo)函數(shù)值為112 420 元，僅為恢復(fù)前的44%，大幅降低了延誤帶來(lái)的損失。

5 結(jié)語(yǔ)

根據(jù)航班恢復(fù)問(wèn)題的研究現(xiàn)狀及目前研究成果的部分不足，提出了以下創(chuàng)新：①在航班恢復(fù)模型中將減少商務(wù)艙旅客的延誤時(shí)間放在更重要的位置，避免因航班延誤時(shí)間過(guò)長(zhǎng)導(dǎo)致商務(wù)艙旅客流失；②將經(jīng)濟(jì)學(xué)中機(jī)會(huì)成本的概念應(yīng)用于航班恢復(fù)模型中，避免了飛機(jī)在地面等待時(shí)間過(guò)長(zhǎng)的情況；③基于構(gòu)建飛機(jī)的可行路徑設(shè)計(jì)了一種動(dòng)態(tài)決策算法，該算法可將動(dòng)態(tài)指派問(wèn)題簡(jiǎn)化為靜態(tài)指派問(wèn)題，在合理地減小解空間之后可快速地求解問(wèn)題，且不易陷入局部最優(yōu)。通過(guò)給出一個(gè)航班不正常實(shí)例，建立了航空公司經(jīng)濟(jì)損失最小模型，并用動(dòng)態(tài)指派算法求解該模型，結(jié)果表明，航班恢復(fù)后的經(jīng)濟(jì)損失僅為恢復(fù)前的44%，證明了模型及算法的可行性。