樂美龍，張 旭

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

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

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

1 機(jī)組復(fù)原問題

1.1 問題描述

機(jī)組復(fù)原問題是指當(dāng)發(fā)生了影響機(jī)組原始排班的突發(fā)狀況以后，通過采取某種具體措施改變?cè)寂虐嘀幸恍┖桨嗟钠痫w與降落的時(shí)間，使得該突發(fā)狀況產(chǎn)生的影響最?。?0］。多機(jī)型機(jī)組復(fù)原問題通過將航班與機(jī)組進(jìn)行配對(duì)得以實(shí)現(xiàn)。為此，筆者構(gòu)建了航班與機(jī)型配對(duì)和機(jī)型與機(jī)組配對(duì)兩個(gè)矩陣進(jìn)行描述。

1.2 模型構(gòu)建

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

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

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

1.3 模型優(yōu)化

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

2 算例

2.1 算例介紹

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

表1 航班運(yùn)作時(shí)間和原始排班費(fèi)用

原始機(jī)組排班費(fèi)用總計(jì)為74191.25美元。

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

表2 費(fèi)用和系數(shù)

2.2 算例分析

2.2.1 測(cè)試場(chǎng)景1

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

表3 測(cè)試場(chǎng)景1的優(yōu)化結(jié)果

經(jīng)過 CPLEX優(yōu)化后，復(fù)原后的費(fèi)用為101223.8美元。如果不采取相應(yīng)的優(yōu)化措施，由于連續(xù)兩趟航班之間的最小中轉(zhuǎn)時(shí)間為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。已知機(jī)組原始排班費(fèi)用為74191.25美元，根據(jù)公式順延費(fèi)用=機(jī)組原始排班費(fèi)用+額外延誤費(fèi)用，可得順延費(fèi)用為106191.3美元。因此，經(jīng)優(yōu)化后的復(fù)原成本可以降低4967.5美元。

2.2.2 測(cè)試場(chǎng)景2

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

表4 測(cè)試場(chǎng)景2優(yōu)化結(jié)果

經(jīng)過 CPLEX優(yōu)化后，復(fù)原后的費(fèi)用為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。由上述公式可得，順延費(fèi)用為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)的運(yùn)行環(huán)境下的求解時(shí)間為8.82 s，通過有效地調(diào)用后備機(jī)組，使得航班在發(fā)生干擾后快速進(jìn)行復(fù)原，不僅能夠減少航班順延的時(shí)間，而且能夠?yàn)楹娇展緶p少航班延誤成本，將突發(fā)事件對(duì)航空公司正常運(yùn)營的干擾降低至最小。

4 結(jié)論

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

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

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

（3）模型能夠較快地產(chǎn)生一個(gè)最優(yōu)解，當(dāng)實(shí)際航班發(fā)生干擾時(shí)能夠較快地找到復(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］詹晨旭，樂美龍.非正常航班管理中的飛機(jī)恢復(fù)問題研究［J］.中國民航大學(xué)學(xué)報(bào)，2012，30（2）:45 －48.

［9］樂美龍，李貞.基于深度優(yōu)先搜索算法的機(jī)組復(fù)原研究［J］.武漢理工大學(xué)學(xué)報(bào)，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ī)排班研究［J］.武漢理工大學(xué)學(xué)報(bào):信息與管理工程版，2013，35（1）:86－90.