非正常航班管理中的飛機恢復(fù)問題研究

詹晨旭，樂美龍

（上海海事大學(xué)物流研究中心，上海 200135）

中國民航局發(fā)布的民航行業(yè)發(fā)展統(tǒng)計公報披露，2010年，中國國內(nèi)大型航空公司計劃航班188.8萬次。其中，正常航班143.1萬次，不正常航班45.7萬次，航班不正常率為24.2%。2010年，中國中小航空公司計劃航班26.0萬次。其中，正常航班17.9萬次，不正常航班8.1萬次，航班不正常率31.2%。根據(jù)民航局披露的數(shù)據(jù)，2010年，在導(dǎo)致主要航空公司航班不正常的原因中，航空公司自身原因占到41.1%；流量控制占27.6%；天氣占19.5%，其他占到11.8%。在對中小航空公司航班不正常原因進行的統(tǒng)計中，航空公司自身原因高達(dá)47.9%。

無論是由于飛機故障、機組人員病假等航空公司的原因，還是天氣、流量控制等其他原因，航班不正常難以避免。在發(fā)生航班不正常時，采用科學(xué)的方法，盡快恢復(fù)航班尤其重要。

目前的航空恢復(fù)研究主要關(guān)注飛機資源，這是因為飛機資源是航空公司最為重要的資源（Kohl et al.2007）[1]。

Teodorovic 和 Guberinic（1984）[2]是最早研究飛機恢復(fù)問題的學(xué)者之一。他們從運營的角度研究這一問題，考慮當(dāng)出現(xiàn)某一架飛機無法執(zhí)行任務(wù)的情況時，通過交換航段和延誤航班達(dá)到最小化乘客延誤的目的。他們構(gòu)建了一個數(shù)學(xué)模型，并通過分支定界法求解該模型。但是許多實際運營中的約束條件，例如機場宵禁、飛機維護約束和飛機平衡約束等在他們的模型中并未體現(xiàn)。此外，航班取消這一選項也未被考慮。而 Clarke（1998）[3]，F(xiàn)ilar et al.（2001）[4]，Andersson 和Varbrand（2004）[5]，Kohl et al.（2007）[1]，Yu and Qi（2005）[6]以及 Clausen et al.（2010）[7]等對飛機恢復(fù)問題的概念與模型均提出了綜合性的回顧。Yan S.and Yang D.（1996）[8]提出了一個包含航班取消、航班延誤和調(diào)用飛機等選項的模型，以解決飛機恢復(fù)問題。他們的模型基于若干假設(shè)：單一機隊；所有的航班都是不經(jīng)停航班；僅有1架飛機出現(xiàn)無法執(zhí)行航班狀況。同時，他們還提出了一個時空網(wǎng)絡(luò)用以表述飛機恢復(fù)問題，該網(wǎng)絡(luò)滿足前述的3個選項。該模型的目標(biāo)函數(shù)是最小化航班時刻表受干擾時間。通過利用中華航空的實際數(shù)據(jù)，運用拉格朗日松弛方法，對模型進行了檢驗。

Jay M.Rosenberger，Ellis L.Johnson，George L.Nemhauser（2003）[9]將飛機恢復(fù)問題轉(zhuǎn)化為一個帶時間窗約束和時間槽約束的集覆蓋（setpacking）問題。在他們的模型中，目標(biāo)函數(shù)是最小化總成本，包含飛機重新指派路徑成本和航班取消成本。Teodorovic和Sto jkovic（1990）[10]提出了一個啟發(fā)式算法用來解決飛機恢復(fù)問題。在他們的文章中，最小化取消航班數(shù)量與乘客延誤總數(shù)是目標(biāo)函數(shù)，但是沒有考慮航班延誤成本以及取消成本。Michael F.Arguello，Jonathan F.Bard，Gang Yu（1997）[11]提出了一個基于隨機臨近搜索的啟發(fā)式算法用以解決飛機恢復(fù)問題。在文章中，他們創(chuàng)造了一個貪婪隨機適應(yīng)搜索程序（GRSAP），用這一程序重建飛機路徑以應(yīng)對干擾。目標(biāo)函數(shù)是最小化飛機路徑指派成本和航班取消成本。但是在他們的程序與模型中并沒有考慮飛機維護要求和機組限制。Jonathan F.Bard，Gang Yu和 Michael F.Arguello（2001）[12]也對飛機恢復(fù)問題提出了一個時間帶優(yōu)化模型。通過將飛機路徑問題轉(zhuǎn)化為一個基于時間的網(wǎng)絡(luò)，他們構(gòu)建了時間帶模型，并將飛機恢復(fù)問題視作一個最小成本流問題。Thengvall B.，Bard J.，Yu G.（2000）[13]對 Michael F.Arguello，Jonathan F.Bard，Gang Yu（1997）[11]的網(wǎng)絡(luò)模型進行了拓展。他們所提出的模型中，目標(biāo)函數(shù)中使用了偏離原時刻表罰值，并以其最小化為目標(biāo)。同時，其允許人工計劃員指定與恢復(fù)操作相關(guān)的參數(shù)。測試數(shù)據(jù)包括2個機隊的27架飛機。Eggenberg N.，Bierlaire M.，Salani M.（2007）[14]提出了一個擴展的時空網(wǎng)絡(luò)模型，目標(biāo)函數(shù)是最小化包括航班延誤、取消成本，飛機航段交換成本以及完成成本（makespan cost）在內(nèi)的總成本。

本文以飛機恢復(fù)為主要研究內(nèi)容，提出一個飛機恢復(fù)的優(yōu)化模型，并給出一個解決飛機恢復(fù)問題的啟發(fā)式算法。第1章闡述恢復(fù)模型；第2章介紹啟發(fā)式算法；在第3章中，若干算例將被應(yīng)用，利用算例對模型和算法進行了驗證分析；最后，第4章對模型及算法進行了總結(jié)，并提出了后續(xù)研究改進的方向。

1 飛機恢復(fù)模型

依照航空公司的日常運營，考慮所關(guān)注的飛機資源，本文為某一時間周期內(nèi)的飛機恢復(fù)問題建立了模型。在建立模型時，考慮到飛機恢復(fù)的最終目標(biāo)是恢復(fù)航班時刻表，因而本文引入原始時刻表和修正時刻表兩個概念。原始時刻表是指在干擾情況發(fā)生之前，航空公司所計劃執(zhí)行的時刻表；修正時刻表是指產(chǎn)生干擾后，經(jīng)過恢復(fù)操作所得到的時刻表。本文將機場分為兩類，一類是可執(zhí)行飛機維護操作的機場，剩余的機場歸為一類。具體參數(shù)、變量如下：

T=[t，t]為時間周期；OS為原時刻表；RS為修正的時刻表；F為航班集合；A為機場集合；AC為飛機集合；H為需要在T內(nèi)維護的飛機集合；Amaint為可以執(zhí)行飛機的計劃維護的機場集合；TF為原時刻表中的航班總數(shù)（）為在時刻和時刻之間機場 a的到達(dá)容量（ta，ta）為在時刻和時刻之間機場a的離開容量（）為在和之間進入機場 a的航班集合；F-a（ta，ta）為在 ta和 ta之間離開機場 a 的航班集合為將航班f∈F指派給修正時刻表RS的成本為航班f∈F的取消成本為航班f∈F的每分鐘延誤成本為航班f∈F上乘客的每分鐘延誤成本為將飛機n∈AC指派給航班f∈F的成本為飛機n∈AC上每個座位空閑的成本；sea（tn）為飛機n∈AC上的座位數(shù)量；CAP（f）為航班f∈F要求的座位數(shù)；taf為航班f∈F的實際到達(dá)時間；Tf為航班f∈F的計劃到達(dá)時間；tdf為航班f∈F的實際離開時間；DTf為航班f∈F的飛行時間；TurnTime（n）為飛機 n∈AC 的轉(zhuǎn)向（turnaround）時間；xf為1，如果航班f∈F被指派給修正時刻表RS；lm，n為1，如果一個合格的維護機場m∈Amaint被飛機n∈AC 訪問；yn，f為 1，如果飛機 n∈AC 被指派給航班f∈F；zf′，f為 1，如果航班 f′是航班 f的后接航班。

式（*）是總成本目標(biāo)，即最小化航班成本與飛機成本。

式（1a）中，第1項是指派成本，即將航班f指派給修正時刻表RS，且由飛機n執(zhí)行航班f的成本；第2項是航班取消成本；第3項是航班延誤成本，與延誤時間有關(guān)。延誤成本既包括航班自身延誤產(chǎn)生的成本，也包括該航班上乘客的延誤成本。式（1b）是因座位空閑而造成的成本。

約束條件中，式（2）指在時段T內(nèi)，進入機場a的航班數(shù)量受機場到達(dá)容量的限制。式（3）指在時段T內(nèi)，離開機場a的航班數(shù)量受機場離開容量的限制。航班數(shù)量約束，即被指派的航班數(shù)量不超過總航班數(shù)，在式（4）中體現(xiàn)。式（5）約束航班指派，即航班指派給飛機時的0-1約束。飛機指派約束在式（6）中限制，每架飛機只能被指派1次。式（7）體現(xiàn)飛機維護約束，需維護的飛機要求訪問有維修資格的機場。航班容量約束在式（8）中體現(xiàn)，如果飛機n被指派給航班f，則飛機上的座位數(shù)應(yīng)不小于航班要求的座位數(shù)。式（9）～式（13）約束航班時間。式（9）約束離開時間，即航班f的實際離開時間應(yīng)不小于其計劃離開時間。式（10）約束到達(dá)時間，即航班f的實際到達(dá)時間等于其實際離開時間加上飛行時間。式（11）體現(xiàn)飛機轉(zhuǎn)向（turnaround）時間約束，即如果航班f′是航班f的緊接航班，若它們由1架飛機執(zhí)行，則這兩個航班間的到達(dá)和離開時間差應(yīng)大于該飛機的turnaround時間。式（12）、式（13）表明實際離開時間和實際到達(dá)時間應(yīng)在時間范圍T內(nèi)。式（14）～式（16）是0、1變量約束。

2 解決方法

本文設(shè)計了一種基于改進的隨機搜索策略的啟發(fā)式算法，該算法主要參考GA算法思路。通過迭代計算，得到每次迭代結(jié)果較優(yōu)的可行解，并在迭代中對解搜索方向加以引導(dǎo)，逐次逼近最優(yōu)解，提高搜索精度，加快搜索速度。參考GA求解思路，首先定義可行解空間容量為M，該空間里的可行解是迭代的對象；然后對每次迭代得到的可行解按照成本最小（目標(biāo)函數(shù)要求）排序，并保留前Mα個可行解，將其直接作為下次迭代的結(jié)果；再對可行解進行迭代，直至迭代次數(shù)達(dá)到之前所設(shè)定的值。算法流程如圖1所示。具體算法步驟如下：

步驟1 按照FCFS（先來先服務(wù)）策略延誤或取消OS中受干擾航班，得到M個初始RS，若調(diào)整受干擾航班無法得到M個初始解，則復(fù)制任意一個初始解，填充剩余初始解空間，將所有初始解記為RS01，…，RS0m。

步驟2 對RS0*按成本升序排列，保留前Mα個RS0*，將其視作本次調(diào)整所得的結(jié)果，并調(diào)整剩余的M（1-α）個RS0*。隨機挑選一個剩余RS0g，調(diào)整其解結(jié)構(gòu)（即調(diào)整其航班屬性——到達(dá)時間或離開時間，以及執(zhí)行飛機），得到一個新RS，如果新RS的成本不比調(diào)整前的RS0*成本大，則將其保留，并記為RS1*。

步驟3 對RS1*重復(fù)步驟2，得到RS2*。

步驟4 重復(fù)步驟2與步驟3，直至完成之前設(shè)定的迭代次數(shù)，得到RSn*。

步驟5 按成本，升序排列RSn*，將RSn*中成本最小的解作為解決方案，并輸出。

圖1 算法流程Fig.1 Algorithm process

3 算例與結(jié)果分析

3.1 算例

本文使用國內(nèi)一家航空公司的實際數(shù)據(jù)來測試模型與算法的有效性。該航空公司主要運營國內(nèi)航班，以PVG與SZX為其運營基地，在NKG、PVG、SZX、PEK、XIY等5個機場具備飛機維護資格。該航空公司一個周期內(nèi)的航班時刻表包含198個航班，由32架飛機執(zhí)行，飛機機型計有5種，包括B747、B777、A300、A310以及A320。本文所用數(shù)據(jù)節(jié)選自該航班時刻表，基本數(shù)據(jù)匯總?cè)绫?所示，飛機具體數(shù)據(jù)如表2所示。

表1 基本情況Tab.1 Basic information

表2 機型數(shù)量Tab.2 Aircraft type and number

由于該航空公司以國內(nèi)航班為主，因而其航班基本上為短途航班，即飛行時間在3 h以下。將時間窗設(shè)定為 T=[t，t]=[07：00，24：00]，設(shè)=0元=25 000元=50 元/min=50 元/min如表2所示為每個航班上的座位票價。在求解時，設(shè)可行解空間容量M=50，解保留比率α=10%，迭代次數(shù)N=5 000。

對于干擾情況，由于在模型中較為關(guān)注機場某時段的容量變化，因而本文將干擾情況設(shè)定為：某日因天氣狀況，PVG 機場在 12：00關(guān)閉，直至 13：30，即在12∶00～13∶30內(nèi)，PVG 容量減為 0。

3.2 結(jié)果分析

使用C#語言實現(xiàn)啟發(fā)式算法，在CPU為CORE i3 2.13 GHz，內(nèi)存為2 GB的PC上運行該算法，求解問題。針對前述的干擾情況，按照不同的迭代次數(shù)，得到不同的解決方案?？梢园l(fā)現(xiàn)，隨著迭代次數(shù)的增加，成本越來越趨近于某一值。在迭代5 000次之后，發(fā)現(xiàn)成本值曲線接近平緩，得到的成本值為28 587.45元。迭代次數(shù)與成本值之間的關(guān)系如圖2所示。而使用LINGO 9.0求解該問題，最優(yōu)解為28 314.10元。使用啟發(fā)式算法得到的最終解，較最優(yōu)解高0.97%。因此，認(rèn)為該最終解可被接受，可被視作最終解決方案。

在最終解決方案中，取消航班數(shù)為0，延誤航班數(shù)為13班次，占總航班的21.67%，產(chǎn)生的總成本為28 587.45元。而按照迭代次數(shù)的不同，產(chǎn)生不同的解決方案，各方案航班信息如表3所示。

表3 各方案航班信息Tab.3 Flight information of each solution

啟發(fā)式算法得到的最終解決方案產(chǎn)生28 587.45元的總成本，較按FCFS策略延誤航班產(chǎn)生的成本（35 569.95元）減少19.63%，所花費的求解時間為19 min，較精確解求解所花時間（42 min）減少54.76%。

4 結(jié)語

本文所提出的模型主要針對于航空公司非正常航班管理中的飛機恢復(fù)問題。當(dāng)受到干擾時，可以輔助管制員實施調(diào)度。在盡量恢復(fù)原計劃的同時，其延誤率也大大降低。由于該模型所涉及到的數(shù)據(jù)量較多，因此該模型適用于中小型航空公司。

對于所設(shè)計的啟發(fā)式算法，使用了不同規(guī)模的數(shù)據(jù)進行了測試。在較小規(guī)模數(shù)據(jù)（3架飛機、18個航班、12個機場）情況下，算法表現(xiàn)良好，迭代5 000次，花費8 min得到結(jié)果；中型數(shù)據(jù)（13架飛機、60個航班、25個機場）情況下，迭代5 000次，花費19 min得到結(jié)果；而對于大規(guī)模數(shù)據(jù)（25架飛機、154個航班、46個機場）情況下，迭代5 000次，花費51 min?？梢钥闯?，隨著數(shù)據(jù)規(guī)模的擴大，本文所設(shè)計的啟發(fā)式算法的搜索效率則大為下降，因而可考慮使用其他效率較高的啟發(fā)式算法。

需要指出的是，本文所提出的模型屬于非線性，因此，其結(jié)果為局部最優(yōu)解。本文最大的約束在于不允許產(chǎn)生新的航班，但是在實際活動中產(chǎn)生的干擾情況是多種多樣的。因此，針對不同的情況，應(yīng)該建立一個適應(yīng)度更強的模型。針對本文所提出的方案也可有多方面的拓展。

[1]KOHL N，LARSEN A，LARSEN J，et al.Airline disruption management perspectives，experiences and outlook[J].Journal of Air Transport Management，2007，13：149-162.

[2]TEODORVIC D，GUBERNIC S.Optimal dispatching strategy on and airline network after a schedule perturbation[J].European Journal of Operations Research，1984，15：178-182.

[3]CLARKE M D D.Irregular airline operations：a review of the state-ofthe-practice in airline operations control centers[J].Journal of Air Transport Management，1998，4：67-76.

[4]FILAR J A，MANYEM P，WHITE K.How airlines and airports recover from schedule perturbations：a survey[J].Annals of Operations Research，2001，108：315-333.

[5]ANDERSSON T，VARBRAND P.The flight perturbation problem[J].Transportation Planning and Technology，2004，27：91-117.

[6]YU G，QI X.Disruption Mmanagement：Frameworks，Models and Applications[M].Singapore：World Scientific Publishing，2004.

[7]JENS CLAUSEN，ALLAN LARSEN，JESPER LARSENA，et al.Disruption management in the airline industry——concepts，models and methods[J].Computers & Operations Research，2010，37：809-821.

[8]YAN S，YANG D.A decision support framework for handling schedule perturbations[J].Transportation Research，1996，30（6）：405-419.

[9]JAY M ROSENBERGER，ELLIS L JOHNSON，GEORGE L NEMHAUSER.Rerouting aircraft for airline recovery[J].Transportation Science，2003，37（4）：408-421.

[10]TEODOROVIC D，STOJKOVIC G.Model for operational daily airline scheduling[J].Transportation Planning and Technology，1990，14：273-285.

[11]MICHAEL F ARGUELLO，JONATHAN F BARD，GANG YU.A GRASP for aircraft routing in response to groundings and delays[J].Journal of Combinatorial Optimization，1997，5：211-228.

[12]JONATHAN F BARD，YU GANG，MICHAEL F ARGUELLO.Optimizing aircraft routings in response to groundings and delays[J].IIE Transactions，2001，33：931-947.

[13]THENGVALL B，BARD J，Yu G.Balancing user preferences for aircraft schedule recovery during irregular operations[J].IIE Transactions，2000，32：181-193.

[14]EGGENBERG N，BIERLAIRE M，SALANI M.A Column Generation Algorithm for Disrupted Airline Schedules[R].2007.