中小型航空公司多機型機組復(fù)原問題研究

樂美龍，張 旭

（上海海事大學(xué)科學(xué)研究院，上海 201306）

飛機機械故障、惡劣天氣、航空管制、機組人員生病、機場宵禁和飛機維護等原因都可能造成航空公司的航班延誤甚至取消。在實際運營中，一個突發(fā)事件的發(fā)生，如某架飛機、某個機組周轉(zhuǎn)出現(xiàn)問題，或者由于某種原因機場封閉，都將會影響航班計劃的實施甚至中斷。因此航空公司需要采取相應(yīng)的措施，使航班能夠盡快恢復(fù)正常。筆者主要討論機組復(fù)原的恢復(fù)措施。

CLARKE［1］為航空公司開發(fā)了一個實時決策支持系統(tǒng)，該系統(tǒng)涵蓋了航空公司機組復(fù)原的模塊，GANG［2］介紹了美國大陸航空公司開發(fā)的“機組恢復(fù)解決方案”。然而，我國航空公司機組復(fù)原仍停留在手工復(fù)原階段，因此建立適合我國航空公司機組復(fù)原實際需要的模型和算法顯得尤為重要。WEI等［3］為機組復(fù)原問題構(gòu)建了多商品網(wǎng)絡(luò)流模型，但該模型沒有將加機組和調(diào)用后備機組的策略方案表示出來，并且對機組成本的計算方法過于籠統(tǒng)。GUO［4］則將機組復(fù)原問題視為集合分割問題，盡管將機組不執(zhí)行原排班任務(wù)的懲罰值列入了目標(biāo)函數(shù)，但還是沒能清晰地描述機組復(fù)原的目標(biāo)函數(shù)計算方法，同時模型求解時間較長，難以滿足航空公司實時有效性的需求。MEDARD［5］使用基于航班網(wǎng)絡(luò)的深度優(yōu)先搜索算法以及基于任務(wù)周期的列生成算法來求解機組復(fù)原問題，測試結(jié)果表明，這兩種算法都能較快地求解機組調(diào)配問題，且運行時間只有幾分鐘。CYNTHIA等［6］是機組復(fù)原問題較早的研究者，其描述了單個機組延誤無法正常連接后續(xù)航班任務(wù)執(zhí)行的問題，并給出了單機組復(fù)原問題的數(shù)學(xué)模型和解決方案。LETTOVSKY等［7］則在此基礎(chǔ)上提出了一種使機組復(fù)原成本最小化的方法。詹晨旭等［8］利用原時刻表，綜合考慮航班時間約束、飛機維護約束、機場容量約束和飛機容量約束，并結(jié)合航空公司運行實際，建立了適合中小型航空公司復(fù)原的飛機恢復(fù)模型。樂美龍等［9］在機組復(fù)原問題上結(jié)合了一種深度優(yōu)先搜索的啟發(fā)式算法，考慮了原來的時間表、時間地點約束以及排班規(guī)則，并調(diào)用Gurobi 4.6.1求解，但目標(biāo)函數(shù)中由于未涉及乘客復(fù)原問題，機組免費乘機的復(fù)原方案的可用性不強，且在后續(xù)算例分析中也未能體現(xiàn)該項措施；在模型構(gòu)建方面，未涉及到多機型的資源分配問題，且文獻中沒有考慮機場宵禁因素以及對可調(diào)用后備機組的容量限制。筆者則在這些方面進行了彌補與加強。

1 機組復(fù)原問題

1.1 問題描述

機組復(fù)原問題是指當(dāng)發(fā)生了影響機組原始排班的突發(fā)狀況以后，通過采取某種具體措施改變原始排班中一些航班的起飛與降落的時間，使得該突發(fā)狀況產(chǎn)生的影響最?。?0］。多機型機組復(fù)原問題通過將航班與機組進行配對得以實現(xiàn)。為此，筆者構(gòu)建了航班與機型配對和機型與機組配對兩個矩陣進行描述。

1.2 模型構(gòu)建

（1）集合定義。K為機組集，k∈K；F為航班集，f，g∈F；A 為機型集，a∈A。

（2）參數(shù)定義。Cf，k為把航班f指派給機組k的費用；Rf為把航班f指派給后備機組的費用；df為航班f延遲1 min所花費的費用；OTf為航班f原來的起飛時間；UTf為航班f實際的起飛時間；UAf為航班f實際的到達時間；Tk為機組排班的時間限制；CFAf，a為航班f與機型a的配對系數(shù)；CACa，k為機型 a 與機組 k 的配對系數(shù)；bf，k為航班 f與機組k的配對系數(shù)；m為最大延遲時間；M為一個足夠大的數(shù)；N為機場宵禁時間；vf為航班f的飛行時間；ek為后備機組的最大容量；w為連續(xù)兩趟相繼航班之間的最小中轉(zhuǎn)時間；TSf為航班f的起飛機場；ASg為航班g的到達機場。

（3）變量定義。0－1協(xié)變量:

1.3 模型優(yōu)化

模型中，以成本最小化為總的目標(biāo)函數(shù)，即最小化機組原始排班成本、航班延遲成本以及調(diào)用后備機組排班成本最小化。在約束條件中，式（1）是對航班排班方式的約束，即對于任何一趟航班都需要安排一種排班方式［11］；式（2）是對航班與機組配對的定義，即通過分別對航班與機型的配對以及機型與機組的分配得以實現(xiàn)；式（3）是對多機型資源分配的限制；式（4）是對機組工作狀態(tài)的約束，即任意機組都可以存在排班或者休息兩種狀態(tài)；式（5）是對航班實際起飛時間的約束，即對于任意航班實際起飛時間不得早于航空公司所規(guī)定的起飛時間；式（6）是對任意機組所執(zhí)行的任意航班的實際到達時間的約束，即每一個機組排班下的每一趟航班的到達時間都不得超過航空公司所規(guī)定的機組排班時間；式（7）是對航班實際到達時間與實際起飛時間邏輯關(guān)系的定義，即任意航班的實際到達時間為該航班的實際起飛時間與飛行持續(xù)時間之和；式（8）是對航班延遲時間的約束，即任意航班的延遲時間都不得超過航空公司所規(guī)定的最大延遲時間；式（9）和式（12）是對同一機組連續(xù)兩趟航班的中轉(zhuǎn)時間約束，即確保同一機組任意兩趟連續(xù)航班之間必須在航空公司所規(guī)定的最小中轉(zhuǎn)時間之內(nèi)；式（10）和式（11）是對同一機組連續(xù)兩趟航班的地點約束，即確保同一機組任意兩趟連續(xù)航班之間必須滿足前一個航班的到達機場恰好是后一個航班的起飛機場；式（13）是機場宵禁約束，即需要在航班排班時間表中剔除超出機場宵禁時間的排班；式（14）是后備機組容量約束，即當(dāng)航班發(fā)生中斷后能夠調(diào)用的后備機組數(shù)量不得超過航空公司所規(guī)定的最大后備機組供給量。

2 算例

2.1 算例介紹

筆者采用國內(nèi)一家航空公司的實際數(shù)據(jù)來測試模型的有效性。該航空公司主要運營國內(nèi)航班，數(shù)據(jù)中所采用的飛機機型有4種，分別為波音737－800、767－300、757－200和 CRJ－200，以SHA為中心機場。假設(shè)連續(xù)兩趟相繼航班之間的最小中轉(zhuǎn)時間為40 min，航班最大延遲時間為2 h。表1所示的是8個機組的原始航班時間與原始排班費用，其中每個機組負(fù)責(zé)6趟航班，一共涉及10個機場，并以7:00為起始時間點對航班的起飛時間與到達時間進行數(shù)據(jù)預(yù)處理。

表1 航班運作時間和原始排班費用

原始機組排班費用總計為74191.25美元。

模型中費用分為3個部分:機組原始排班費用和、調(diào)用后備機組費用和航班延遲費用。費用和系數(shù)如表2所示。

表2 費用和系數(shù)

2.2 算例分析

2.2.1 測試場景1

受大范圍冰雪天氣影響，航班FM9533到達中心機場SHA的時間延誤為13:40，航班FM9354到達長春機場CGO的時間延誤為16:00，航班FM9350到達廈門機場XMN的時間延誤為19:30。上述航班到達時間的延誤，對其后續(xù)航班FM9353和FM9349造成影響。優(yōu)化結(jié)果如表3所示。

表3 測試場景1的優(yōu)化結(jié)果

經(jīng)過 CPLEX優(yōu)化后，復(fù)原后的費用為101223.8美元。如果不采取相應(yīng)的優(yōu)化措施，由于連續(xù)兩趟航班之間的最小中轉(zhuǎn)時間為40 min，則FM9354相應(yīng)地延誤1.55 h，F(xiàn)M9353相應(yīng)地延誤2.50 h，F(xiàn)M9349相應(yīng)地延誤35 min。已知機組原始排班費用為74191.25美元，根據(jù)公式順延費用=機組原始排班費用+額外延誤費用，可得順延費用為106191.3美元。因此，經(jīng)優(yōu)化后的復(fù)原成本可以降低4967.5美元。

2.2.2 測試場景2

受軍事演習(xí)機場管制的影響，中心機場SHA于13:35～14:05之間不能起飛或者降落任何航班，因此航班 FM9354、FM9333、FM9257、FM94531和FM9348均受到了影響，其實際起飛時間都不得早于13:35。優(yōu)化結(jié)果如表4所示。

表4 測試場景2優(yōu)化結(jié)果

經(jīng)過 CPLEX優(yōu)化后，復(fù)原后的費用為115986.3美元。如果不采取相應(yīng)的優(yōu)化措施，則FM9354、FM9353 均延誤65 min，F(xiàn)M9257、FM9258均延 誤 45min，F(xiàn)M94531、FM94532 均 延 誤105 min，F(xiàn)M9348、FM9347 均延誤 25 min。由上述公式可得，順延費用為122191.3美元。因此經(jīng)優(yōu)化后的復(fù)原成本可以降低6204.95美元。

3 結(jié)果分析

CPLEX在Intel（R）Core（TM）i3－2370 M CPU@2.40 GHz處理器、2.00 GB 內(nèi)存和32 位操作系統(tǒng)的運行環(huán)境下的求解時間為8.82 s，通過有效地調(diào)用后備機組，使得航班在發(fā)生干擾后快速進行復(fù)原，不僅能夠減少航班順延的時間，而且能夠為航空公司減少航班延誤成本，將突發(fā)事件對航空公司正常運營的干擾降低至最小。

4 結(jié)論

筆者對多機型機組復(fù)原問題進行了深入的研究，創(chuàng)新點集中在以下幾個方面:

（1）在多機型機組復(fù)原的問題上，通過構(gòu)建航班與機型的配對矩陣、機型與機組的配對矩陣來實現(xiàn)航班與機組的配對；

（2）模型中對同一機組的相繼航班所需滿足的時間和地點作出了進一步的約束，確保了航班之間的連續(xù)。同時，模型考慮了機組的排班時間限制，并對機場進行了宵禁約束，限制了航空公司可提供的后備機組容量；

（3）模型能夠較快地產(chǎn)生一個最優(yōu)解，當(dāng)實際航班發(fā)生干擾時能夠較快地找到復(fù)原方案。

［1］CLARKE D M.Irregular airline operations:a review of the state of the practice in airline operations control centers［J］.Journal of Air Transport Management，1998（4）:67－76.

［2］GANG Y，ARGUELLO M.A new era for crew recovery at continental airlines［J］.Interfaces，2003，33（1）:5 －22.

［3］WEI G，GANG Y.Optimization model and algorithm for crew management during airline irregular operations［J］.Journal of Combinatorial Optimization，1997（1）:305－321.

［4］GUO Y F，LEENA S，MARKUS P T.Solving the airline crew recovery problem by a genetic algorithm with local improvement［J］.Operational Research，2005，5（2）:241－259.

［5］MEDARD S.Airline crew scheduling from planning to operations［J］.European Journal of Operational Research，2007，183（3）:1013 －1027.

［6］CYNTHIA B，ELLIS L J，GEORGE L N，et al.Branch and price:columngeneration for solving huge integer programs［J］.Operations Research，1998，46（3）:316－329.

［7］LETTOVSKY L，JOHNSON E L，NEMHAUSER G L.Airline crew recovery［J］.Transportation Science，2000，34（4）:337 －348.

［8］詹晨旭，樂美龍.非正常航班管理中的飛機恢復(fù)問題研究［J］.中國民航大學(xué)學(xué)報，2012，30（2）:45 －48.

［9］樂美龍，李貞.基于深度優(yōu)先搜索算法的機組復(fù)原研究［J］.武漢理工大學(xué)學(xué)報，2012，34（9）:63 －68.

［10］NIKLAS K.Airline disruption management perspect，experience and outlook［J］.Journal of Air Transpose Management，2007，13（3）:149 －162.

［11］魏星，朱金福.航空公司一體化飛機排班研究［J］.武漢理工大學(xué)學(xué)報:信息與管理工程版，2013，35（1）:86－90.