姜 茂， 韓曉龍

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

?

姜 茂*， 韓曉龍

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

航班發(fā)生延誤時(shí)，需要采取有效恢復(fù)措施降低航空公司的經(jīng)濟(jì)和信譽(yù)損失.本文利用現(xiàn)有飛機(jī)資源，對(duì)飛機(jī)和乘客進(jìn)行合理的調(diào)度安排問(wèn)題建立了飛機(jī)和乘客恢復(fù)混合整數(shù)規(guī)劃模型.模型考慮了乘客的航班取消成本、航班延誤成本、座艙降級(jí)成本、飛機(jī)的非正常降落位置的懲罰成本及飛機(jī)飛行成本等，以使航班恢復(fù)成本最小化為目標(biāo).對(duì)航班恢復(fù)成本進(jìn)行細(xì)分，更接近航空公司在進(jìn)行航班恢復(fù)時(shí)的實(shí)際情況.使用法國(guó)某航空公司真實(shí)航班數(shù)據(jù)作為算例，以驗(yàn)證模型的有效性和實(shí)用性.算例顯示優(yōu)化模型相對(duì)于航班取消方案和航班順延方案分別使恢復(fù)成本降低了21.05%和21.46%.因此，模型能有效地解決航班航空公司飛機(jī)和乘客恢復(fù)問(wèn)題，提高航空公司競(jìng)爭(zhēng)力.

航空運(yùn)輸； 航班延誤； 混合整數(shù)規(guī)劃； 航班和乘客恢復(fù)

惡劣的天氣、飛機(jī)故障、機(jī)組成員自身的身體不適等原因都有可能導(dǎo)致航班的延誤，如果航班延誤沒(méi)有得到及時(shí)快速的處理，將會(huì)影響到整個(gè)航空公司的運(yùn)作、收益、決策效率和乘客的滿意度等.航班延誤發(fā)生時(shí)，航空公司必須調(diào)整航班計(jì)劃，比如延遲航班，取消航班，重設(shè)飛機(jī)路線，重新指派機(jī)組成員或召集新的機(jī)組，重新安排旅客等，如何以可行的、費(fèi)用最少的恢復(fù)方案使航班恢復(fù)到原來(lái)的運(yùn)行計(jì)劃是航空公司面臨的主要問(wèn)題.航班延誤的恢復(fù)問(wèn)題主要包括飛機(jī)、乘客、和機(jī)組的恢復(fù).

在航班發(fā)生延誤時(shí)對(duì)飛機(jī)恢復(fù)方面，Eggenberg N， Bierlaire M， Salani M[1]對(duì)時(shí)空網(wǎng)絡(luò)模型進(jìn)行了深度擴(kuò)展，解決以實(shí)現(xiàn)最小化總恢復(fù)時(shí)間和總恢復(fù)成本為目標(biāo)的多目標(biāo)整數(shù)規(guī)劃問(wèn)題，并引入了飛機(jī)維護(hù)約束，將列生成算法和網(wǎng)絡(luò)算法結(jié)合起來(lái)，尋求新的恢復(fù)計(jì)劃.樂(lè)美龍，馬彬[2]針對(duì)飛機(jī)路線受中斷情況，將飛機(jī)路線恢復(fù)問(wèn)題轉(zhuǎn)化為基于時(shí)間段的網(wǎng)絡(luò)模型，以最小化航班延誤成本和取消成本為目標(biāo)，結(jié)合飛機(jī)流平衡約束，較好地解決了飛機(jī)路線恢復(fù)問(wèn)題.唐小衛(wèi)，朱金福，高強(qiáng)[3]則放寬了飛機(jī)流平衡的約束，加入了合并航班的恢復(fù)策略，提出了貪婪隨機(jī)模擬退火算法以解決流不平衡條件下的大規(guī)模飛機(jī)恢復(fù)問(wèn)題.趙秀麗、朱金福等[4]構(gòu)建了以延誤時(shí)間最短或延誤成本最小為目標(biāo)函數(shù)的飛機(jī)恢復(fù)模型，在延誤成本構(gòu)成中提出了旅客失望溢出成本和失望溢出率的概念，并在實(shí)際調(diào)查的前提下對(duì)旅客失望溢出率函數(shù)進(jìn)行了擬合.

旅客作為航空公司的主要服務(wù)對(duì)象，在恢復(fù)過(guò)程中必須予以考慮.L. Lettovsky[5]考慮了航班恢復(fù)過(guò)程中旅客的航班取消成本、餐飲及住宿成本，并估計(jì)了航班延誤對(duì)航空公司帶來(lái)的信譽(yù)損失成本.Eggenberg等[6]提出了旅客流恢復(fù)網(wǎng)絡(luò)模型，減少旅客行程取消的數(shù)量.白鳳，朱金福，高強(qiáng)[7]為每一架可用的飛機(jī)構(gòu)建時(shí)空恢復(fù)網(wǎng)絡(luò)，把旅客恢復(fù)問(wèn)題簡(jiǎn)化為多商品最小費(fèi)用流問(wèn)題，在求解模型時(shí)用到了列生成算法和分支定界法.D. Clarke[8]建立了一個(gè)乘客流模型，其目標(biāo)函數(shù)是最大化乘客收益，但作者認(rèn)為應(yīng)先考慮航班恢復(fù)，然后在此基礎(chǔ)上考慮乘客恢復(fù).王瑩，朱金福[9]在已獲得航班恢復(fù)方案和航班容量為剩余座位數(shù)的限制等假設(shè)前提下，通過(guò)構(gòu)建時(shí)空網(wǎng)絡(luò)，建立了不正常航班旅客流恢復(fù)模型，并設(shè)計(jì)了Danzig-Wolfe分解算法進(jìn)行求解，給出了旅客恢復(fù)方案.

在飛機(jī)、旅客和機(jī)組綜合恢復(fù)方面，Niloofar Jafari[10]在其定義的恢復(fù)范圍內(nèi)，研究了飛機(jī)和乘客的同時(shí)恢復(fù)模型.Karine Sinclair等[11]針對(duì)軸輻式航線網(wǎng)絡(luò)中的航班恢復(fù)提出了一種改進(jìn)的大規(guī)模鄰域搜索算法，包括航班重設(shè)，航班修正和航班改進(jìn)三個(gè)過(guò)程.樂(lè)美龍，王婷婷等[12]建立了基于時(shí)空網(wǎng)絡(luò)的多機(jī)型航班恢復(fù)模型，在不正常航班發(fā)生時(shí)，利用機(jī)場(chǎng)的多機(jī)型資源，進(jìn)行調(diào)機(jī)，以達(dá)到使航空公司損失最小的目的.Bratu等[13]在綜合恢復(fù)中考慮了備用機(jī)組，文章對(duì)乘客成本和航班成本做了一個(gè)權(quán)衡，模型描述了乘客的行程和航段之間的關(guān)系，目標(biāo)函數(shù)是獲得最大利潤(rùn)和提高客戶滿意度.趙秀麗[14]建立了航班、飛機(jī)、機(jī)組和旅客恢復(fù)的一體化模型，將航班恢復(fù)問(wèn)題定義為主問(wèn)題，將飛機(jī)、機(jī)組和旅客恢復(fù)定義為子問(wèn)題.樂(lè)美龍，李曉嵐[15]在飛機(jī)和旅客流恢復(fù)的基礎(chǔ)上加入了機(jī)組指派和時(shí)間約束，并考慮了備用機(jī)組，目標(biāo)函數(shù)是最小化飛機(jī)和機(jī)組恢復(fù)成本、最小化旅客總延誤成本.

根據(jù)航空運(yùn)輸?shù)膶?shí)際情況，飛機(jī)上設(shè)置了不同的座艙等級(jí)，如頭等艙、商務(wù)艙和經(jīng)濟(jì)艙.座艙等級(jí)不同的乘客機(jī)票成本也不相同，導(dǎo)致在航班恢復(fù)過(guò)程中乘客行程的取消成本，座艙降級(jí)成本，航班延誤成本都不同.此外，國(guó)際航空公司必須考慮航班延誤對(duì)出入境乘客的不同影響.上述文獻(xiàn)在旅客行程恢復(fù)或綜合恢復(fù)中只是將每架飛機(jī)上的乘客視為一個(gè)整體，在恢復(fù)過(guò)程中沒(méi)有考慮不同航班類型上各座艙等級(jí)的位置數(shù)量約束和座艙降級(jí)成本，也沒(méi)有考慮國(guó)際航班恢復(fù)過(guò)程中出入境乘客恢復(fù)成本的異同.只有對(duì)這些成本進(jìn)行細(xì)分，才能更好的選擇恢復(fù)方案，踐行為旅客服務(wù)的宗旨，從而讓航空公司又好又快的發(fā)展.

本文綜合考慮了基于航班延誤的飛機(jī)和乘客恢復(fù)模型，主要貢獻(xiàn)包括兩方面：1)在乘客恢復(fù)方面，進(jìn)行了細(xì)致的成本劃分，針對(duì)3種不同的航班：洲際航班，洲內(nèi)國(guó)際航班和國(guó)內(nèi)航班，兩種不同的乘客：入境乘客和出境乘客，3種不同的座艙級(jí)別：頭等艙、商務(wù)艙和經(jīng)濟(jì)艙，進(jìn)行了細(xì)致的恢復(fù)成本劃分.包括航班取消成本，航班延誤成本，航班座艙降級(jí)成本； 2)在飛機(jī)恢復(fù)方面，除了考慮恢復(fù)期內(nèi)對(duì)飛機(jī)的各種條件限制，如飛機(jī)定期檢查維修限制、飛機(jī)里程限制等之外，為了避免恢復(fù)期內(nèi)的飛機(jī)調(diào)度對(duì)恢復(fù)期結(jié)束后航空公司正常運(yùn)營(yíng)的影響，還考慮了恢復(fù)期結(jié)束后受影響的各機(jī)場(chǎng)對(duì)不同機(jī)型的飛機(jī)數(shù)量需求約束，可以避免航班延誤恢復(fù)期結(jié)束后對(duì)多航空公司后續(xù)運(yùn)作的影響.

1 問(wèn)題描述

航班延誤對(duì)飛機(jī)和乘客的影響可由圖1表示，圖中展示了一個(gè)由7個(gè)航班和3架飛機(jī)組成的航線網(wǎng)絡(luò)，橫軸代表時(shí)間，縱軸代表飛機(jī).每一個(gè)航班用一條粗線代替，開(kāi)始與結(jié)束的粗線分別代表航班的出發(fā)和到站時(shí)間以及機(jī)場(chǎng).線下方括號(hào)里的字母代表乘客的行程.如圖1所示，航班f1從機(jī)場(chǎng)G出發(fā)，到達(dá)機(jī)場(chǎng)H.航班f1結(jié)束后飛機(jī)A執(zhí)飛航班f2，行程P1的旅客銜接至下一個(gè)航班f4.

圖1 航班延誤對(duì)乘客和飛機(jī)的影響Fig.1 Flights delay effects on passengers and aircrafts

當(dāng)航班f1和航班f3延誤時(shí)，要用到航班f1和航班f3執(zhí)飛飛機(jī)的下一個(gè)航班以及相關(guān)的乘客都將受到影響.行程為P1的乘客有兩個(gè)航班，f1和f4，當(dāng)航班f1發(fā)生延誤，乘客到達(dá)航班f4的始發(fā)機(jī)場(chǎng)H時(shí)，航班f4已出發(fā)，他們的行程被擾動(dòng)了.因?yàn)轱w機(jī)A發(fā)生了延誤，而航班f2必須滿足飛機(jī)的最小過(guò)站時(shí)間限制才能出發(fā)，所以航班f2會(huì)被延誤.又因?yàn)樾谐虨镻2的旅客需要足夠的登機(jī)時(shí)間銜接到航班f7，所以航班f7會(huì)受到擾動(dòng).航班f3發(fā)生延誤時(shí)，若不改變航班計(jì)劃，行程為P3的乘客會(huì)錯(cuò)過(guò)接下來(lái)的航班f6和f7，行程P3被擾動(dòng).

這個(gè)例子表明航班延誤對(duì)乘客和飛機(jī)的連鎖反應(yīng)，也表明同時(shí)恢復(fù)飛機(jī)和旅客的必要性.本文研究的問(wèn)題是同時(shí)解決航空公司最貴的飛機(jī)資源和為航空公司帶來(lái)收益的旅客資源.

2 模型構(gòu)建

2.1 集合

2.2 參數(shù)

2.3 決策變量

2.4 目標(biāo)函數(shù)

(1)

2.5 約束條件

(2)

(3)

(4)

(5)

(6)

(7)

taf=tdf+DTf，?f∈F,

(8)

(9)

(10)

(11)

(tdIT(p，n)-taIT(p，n-1)-u)*yp≤0，?p∈P,

(12)

(tdIT(p，n)-taIT(p，n-1)-u)*(1-yp)≥0，

?p∈P,

(13)

(14)

式(2)表示各航班弧最多由一架飛機(jī)執(zhí)飛，xijf表示由飛機(jī)f執(zhí)飛航班弧ij；式(3)是飛機(jī)定期檢查維修約束；式(4)和式(5)表明在規(guī)定時(shí)間段內(nèi)，起飛和降落飛機(jī)數(shù)量不得超過(guò)機(jī)場(chǎng)所允許的起飛和降落數(shù)量；約束(6)表明在整個(gè)恢復(fù)期結(jié)束后，為不影響航空公司的后續(xù)運(yùn)營(yíng)，各機(jī)場(chǎng)對(duì)不同機(jī)型數(shù)量需求的要求；式(7)表明各飛機(jī)所執(zhí)飛的航班飛行距離均不能超過(guò)其最大航程；式(8)表示受干擾航班的實(shí)際降落時(shí)間等于航班實(shí)際起飛時(shí)間與實(shí)際飛行時(shí)間之和；式(9)表示受干擾航班的實(shí)際起飛時(shí)間等于計(jì)劃起飛時(shí)間與航班延誤時(shí)間之和；約束(10)確?；謴?fù)過(guò)程中被調(diào)配給某飛機(jī)的各類座艙的乘客數(shù)與原來(lái)該飛機(jī)上所有的各類座艙乘客數(shù)之和小于該飛機(jī)的乘客容量；約束(11)確保受干擾乘客不被分配給一個(gè)中間有取消航班的行程；約束(12)、(13)確保行程p之間的航班有足夠的過(guò)站時(shí)間；式(14)是決策變量取值范圍約束.

3 算例

該算例是來(lái)自法國(guó)一家航空公司的真實(shí)數(shù)據(jù)，包括15個(gè)航班，其中國(guó)內(nèi)航班2個(gè)，洲內(nèi)航班9個(gè)，洲際航班4個(gè)；包括6個(gè)機(jī)場(chǎng)，3個(gè)國(guó)內(nèi)機(jī)場(chǎng)，3個(gè)國(guó)外機(jī)場(chǎng)；旅客行程2 729個(gè)，其中需要轉(zhuǎn)機(jī)的乘客行程200個(gè)，航班與旅客行程時(shí)段網(wǎng)絡(luò)圖如圖2所示.

圖2 航班與旅客行程時(shí)段網(wǎng)絡(luò)圖Fig.2 Time-band network of flights and itineraries

機(jī)場(chǎng)間的距離及不同機(jī)場(chǎng)間的航班類別如表1所示，其中I表示跨洲際航班，C表示洲內(nèi)航班，D表示國(guó)內(nèi)航班.

表1 機(jī)場(chǎng)間的距離及航班類別

部分旅客行程信息如表2所示，其中A表示入境乘客，R表示出境乘客，F(xiàn)、B與E分別表示頭等艙、商務(wù)艙與經(jīng)濟(jì)艙.

表2 部分旅客行程信息

續(xù)表2

由于特殊原因，航班3延誤了1 h，導(dǎo)致該由該飛機(jī)執(zhí)飛的航班8和航班9無(wú)法按原定計(jì)劃執(zhí)行，并且導(dǎo)致部分乘坐航班3的旅客無(wú)法按時(shí)銜接到航班5.

通過(guò)CPLEX優(yōu)化軟件進(jìn)行求解，運(yùn)行時(shí)間為3.5 min，經(jīng)過(guò)調(diào)整后的具體航班恢復(fù)方案如表3所示.

表3 航班延誤的恢復(fù)方案1

即將原本由飛機(jī)A320#1執(zhí)飛的航班8和航班9改由飛機(jī)A320#2準(zhǔn)點(diǎn)執(zhí)飛，而飛機(jī)A320#1則準(zhǔn)點(diǎn)執(zhí)飛原本由飛機(jī)A320#2執(zhí)飛的航班10，航班5則順延1 h.恢復(fù)成本如表4所示.

表4 方案1航班恢復(fù)成本

經(jīng)過(guò)模型優(yōu)化后的恢復(fù)成本為33 156歐元，其中航班5順延1 h，等待來(lái)自航班3的銜接乘客，順延成本為30 156歐元，飛機(jī)在不影響航空公司恢復(fù)期結(jié)束后的正常運(yùn)營(yíng)條件下，非正常降落位置的懲罰成本為3 000歐元.

相比兩種手動(dòng)恢復(fù)方案，一、取消方案：若直接取消來(lái)自航班3的行程銜接乘客，航班8、9和航班10交換執(zhí)飛飛機(jī)后準(zhǔn)點(diǎn)執(zhí)行，則取消成本為39 000歐元，恢復(fù)總成本為42 000歐元；二、順延方案：若直接采取航班順延的方法，即由飛機(jī)A320#1執(zhí)飛的航班8和航班9順延，航班10仍由飛機(jī)A320#2準(zhǔn)點(diǎn)執(zhí)飛，則總延誤成本為42 216歐元，優(yōu)化模型分別使恢復(fù)成本降低了21.05%和21.46%，如圖3所示.

圖3 恢復(fù)方案成本對(duì)比Fig.3 Cost Comparison between Different Recovery Schemes

綜上所述，本文所建立的優(yōu)化模型同時(shí)解決了航班發(fā)生延誤時(shí)乘客與飛機(jī)的恢復(fù)問(wèn)題，并取得了良好的經(jīng)濟(jì)效果.

4 結(jié)語(yǔ)

在航班發(fā)生延誤時(shí)，以恢復(fù)成本最小為目標(biāo)函數(shù)，綜合考慮了飛機(jī)和乘客的恢復(fù).在考慮飛機(jī)恢復(fù)的過(guò)程中，不僅考慮了如何調(diào)度現(xiàn)有飛機(jī)資源，進(jìn)行合理的乘客與飛機(jī)的一體化調(diào)度，還考慮了在恢復(fù)期結(jié)束時(shí)，航空公司對(duì)飛機(jī)位置的要求，即恢復(fù)期結(jié)束后，后續(xù)航班上的乘客行程不至于受航班恢復(fù)過(guò)程的影響.在考慮乘客恢復(fù)的過(guò)程中，充分考慮了乘客的延誤成本，座位降級(jí)成本.此外，對(duì)不同的航班，如國(guó)內(nèi)航班，洲內(nèi)國(guó)際航班和跨洲際航班上的乘客恢復(fù)成本進(jìn)行細(xì)分，與實(shí)際情況相符，并取得了良好的恢復(fù)效果.此外，本文只考慮了航班延誤恢復(fù)一種情況，未考慮機(jī)場(chǎng)關(guān)閉，飛機(jī)故障等其它條件下的航班、乘客恢復(fù)，且尚未考慮機(jī)組的約束條件及恢復(fù)成本，這些將是我們進(jìn)一步的研究方向.

[1] EGGENBERG N， BIERLAIRE M， SALANI M. A colume generation algorithm for disrupted airline schedules [R]. Lausanne: Ecole Polytechnique Fédérale de Lausanne， 2007．

[2] 樂(lè)美龍， 馬 彬. 基于時(shí)間段網(wǎng)絡(luò)模型的飛機(jī)路線恢復(fù)研究[J]. 武漢理工大學(xué)學(xué)報(bào)， 2012， 34(11): 63-68．

[3] 唐小衛(wèi)， 朱金福， 高 強(qiáng). 流不平衡條件下飛機(jī)恢復(fù)的優(yōu)化模型與算法研究[J]. 小型微型計(jì)算機(jī)系統(tǒng)，2010， 31(04):793-796．

[4] 趙秀麗， 朱金福， 郭 梅. 不正常航班延誤調(diào)度模型及算法[J]. 系統(tǒng)工程理論與實(shí)踐， 2008， 28(4): 129-134．

[5] LETTOVSKY L. Airline operations recovery: An optimization approach[D]. Atlanta: Georgia Institute of Technology， 1997．

[6] EGGENBERG N， SALANI M， BIERLAIRE M. Constraint-specific recovery network for solving airline recovery problems [J]. Computers & Operations Research， 2010， 37(6): 1014-1026．

[7] 白 鳳， 朱金福， 高 強(qiáng). 基于列生成算法的不正常航班調(diào)度[J]. 系統(tǒng)工程理論與實(shí)踐， 2010， 30(11): 2036-2045．

[8] CLARKE M D. Development of heuristic procedures for flight researching in the aftermath of irregular airline operation[D]. Massachusetts:Massachusetts Institute of Technology，1998．

[9] 王 瑩， 朱金福. 基于Danzig-Wolfe算法的不正常航班旅客流恢復(fù)問(wèn)題[J]. 武漢理工大學(xué)學(xué)報(bào)(信息與管理工程版)， 2013， 35(4):551-554+579．

[10] JAFARI N， ZEGORDI S H. Simultaneous recovery model for aircraft and passengers [J]. Journal of the Franklin Institute， 2011， 348 (07): 1638-1655．

[11] SINCLAIR K， CORDEAU J-F， LAPORTE G. Improvements to a large neighborhood search heuristic for an integrated aircraft and passenger recovery problem [J]. European Journal of Operational Research， 2014， 233(1): 234-245．

[12] 樂(lè)美龍， 王婷婷， 吳聰聰. 多機(jī)型不正常航班恢復(fù)的時(shí)空網(wǎng)絡(luò)模型[J]. 四川大學(xué)學(xué)報(bào)(自然科學(xué)版)， 2013， 50(3): 477-483．

[13] BRATU S， BARNHART C. Flight operations recovery: new approach considering passenger recovery [J]. Journal of Scheduling， 2006， 9(3) : 279-298．

[14] 趙秀麗. 航空公司不正常航班恢復(fù)模型及算法研究[D]. 南京：南京航空航天大學(xué)， 2010．

[15] 樂(lè)美龍， 李曉嵐. 飛機(jī)和旅客流一體化恢復(fù)模型[J]. 工業(yè)工程， 2013， 16(5): 113-119.

The recovery model of aircrafts and passengers based on flight delay

JIANG Mao， HAN Xiaolong

(Scientific Research Academy， Shanghai Maritime University， Shanghai 201306)

When flight delay occurred, it will bring huge economic and reputation losses to airlines if effective measures are not performed by managers to deal with it. The mathematical model established in this article mainly aims at making full use of the existing aircraft resources and performing reasonable scheduling of aircrafts and passengers when flight delay occurred. The objective function focuses on minimizing recovery cost which included cost of flights cancellation, flights delay, Seat degradation of passengers, penalty for wrong locations and aircrafts. The recovery cost was subdivided to make it closer to the real situation. Real flight data of a French airline as an example was used to verify the validity and practicability of the model. The example shows that the optimization model with respect to the cancellation scheme of flights and postponement scheme of flights costs were reduced by 21.05% and 21.46% respectively. Therefore, the model is able to effectively solve aircraft and passengers recovery problem and improve the competitiveness of airlines.

air transport; flight delay; mixed integer programming; flight and passenger recovery

2015-03-15.

上海市科委項(xiàng)目(11510501900)．

1000-1190(2015)06-0876-07

F560.1

A

*E-mail:jiangmao8880@163.com．