詹晨旭，樂美龍

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

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

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

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

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

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

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

1 飛機(jī)恢復(fù)模型

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

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

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

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

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

2 解決方法

本文設(shè)計(jì)了一種基于改進(jìn)的隨機(jī)搜索策略的啟發(fā)式算法，該算法主要參考GA算法思路。通過迭代計(jì)算，得到每次迭代結(jié)果較優(yōu)的可行解，并在迭代中對解搜索方向加以引導(dǎo)，逐次逼近最優(yōu)解，提高搜索精度，加快搜索速度。參考GA求解思路，首先定義可行解空間容量為M，該空間里的可行解是迭代的對象；然后對每次迭代得到的可行解按照成本最?。繕?biāo)函數(shù)要求）排序，并保留前Mα個可行解，將其直接作為下次迭代的結(jié)果；再對可行解進(jìn)行迭代，直至迭代次數(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*。隨機(jī)挑選一個剩余RS0g，調(diào)整其解結(jié)構(gòu)（即調(diào)整其航班屬性——到達(dá)時間或離開時間，以及執(zhí)行飛機(jī)），得到一個新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í)際數(shù)據(jù)來測試模型與算法的有效性。該航空公司主要運(yùn)營國內(nèi)航班，以PVG與SZX為其運(yùn)營基地，在NKG、PVG、SZX、PEK、XIY等5個機(jī)場具備飛機(jī)維護(hù)資格。該航空公司一個周期內(nèi)的航班時刻表包含198個航班，由32架飛機(jī)執(zhí)行，飛機(jī)機(jī)型計(jì)有5種，包括B747、B777、A300、A310以及A320。本文所用數(shù)據(jù)節(jié)選自該航班時刻表，基本數(shù)據(jù)匯總?cè)绫?所示，飛機(jī)具體數(shù)據(jù)如表2所示。

表1 基本情況Tab.1 Basic information

表2 機(jī)型數(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)注機(jī)場某時段的容量變化，因而本文將干擾情況設(shè)定為：某日因天氣狀況，PVG 機(jī)場在 12：00關(guān)閉，直至 13：30，即在12∶00～13∶30內(nèi)，PVG 容量減為 0。

3.2 結(jié)果分析

使用C#語言實(shí)現(xiàn)啟發(fā)式算法，在CPU為CORE i3 2.13 GHz，內(nèi)存為2 GB的PC上運(yùn)行該算法，求解問題。針對前述的干擾情況，按照不同的迭代次數(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%，所花費(fèi)的求解時間為19 min，較精確解求解所花時間（42 min）減少54.76%。

4 結(jié)語

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

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

需要指出的是，本文所提出的模型屬于非線性，因此，其結(jié)果為局部最優(yōu)解。本文最大的約束在于不允許產(chǎn)生新的航班，但是在實(shí)際活動中產(chǎn)生的干擾情況是多種多樣的。因此，針對不同的情況，應(yīng)該建立一個適應(yīng)度更強(qiá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.