羅 軍，江林林

（中國(guó)民用航空飛行學(xué)院空中交通管理學(xué)院，廣漢 618307）

0 引言

在當(dāng)代人的遠(yuǎn)距離旅行中，航空出行扮演著舉足輕重的地位，日益增長(zhǎng)的飛機(jī)數(shù)量造成航班正常率的不斷降低。天氣條件、機(jī)場(chǎng)保障等問(wèn)題都是導(dǎo)致飛機(jī)延誤或取消的主要原因，給出行者造成了不便利的同時(shí)，航空公司和機(jī)場(chǎng)也承擔(dān)著經(jīng)濟(jì)損失。但是由于航空的飛行安排已經(jīng)非常嚴(yán)密，一旦某飛機(jī)受到影響，延誤會(huì)在航班串上產(chǎn)生多米諾效應(yīng)，導(dǎo)致大量飛機(jī)晚點(diǎn)。及時(shí)合理地恢復(fù)延誤航班，確保恢復(fù)成本盡可能小，不能僅靠調(diào)度員，而采用最優(yōu)化算法則可以迅速達(dá)到目標(biāo)，在減少成本的同時(shí)還能將簽派員的工作效率提高，為后續(xù)飛機(jī)排班提供依據(jù)。

針對(duì)航班恢復(fù)問(wèn)題，國(guó)內(nèi)外已研究多年，也取得了相應(yīng)的成果，賴俊曉［1］基于我國(guó)機(jī)隊(duì)規(guī)模小，將限制信息融入資源指派模型，構(gòu)建了最小成本的航班恢復(fù)模型。為了提高航空公司效益，創(chuàng)造性地將改進(jìn)的貪婪隨機(jī)自適應(yīng)搜索算法運(yùn)用于航班恢復(fù)模型中。戴福青等［2］將機(jī)會(huì)成本應(yīng)用于航班恢復(fù)中，通過(guò)動(dòng)態(tài)規(guī)劃算法將延誤航班損失降為原來(lái)的44%，證明了動(dòng)態(tài)規(guī)劃算法在解決航班恢復(fù)問(wèn)題時(shí)的可行性。李琳丹等［3］在非正常航班成本分析與優(yōu)化方面，使用了三天內(nèi)可用及新開(kāi)航班結(jié)合的方法實(shí)施延誤航班恢復(fù)，利用LINGO 對(duì)延誤信息計(jì)算來(lái)減少恢復(fù)時(shí)間。姚韻［4］提出基于機(jī)號(hào)路徑置換算法，且用匈牙利法進(jìn)行邊界約束求解。白鳳等［5］在航線不足和空港封閉而導(dǎo)致客機(jī)非正常飛行的情形下，通過(guò)列生成算法來(lái)求解構(gòu)建的多商品網(wǎng)絡(luò)流模型。田倩南等［6］基于占優(yōu)準(zhǔn)則減少被恢復(fù)航線組合量，利用CPLEX 實(shí)現(xiàn)減小成本，提出了改進(jìn)的時(shí)空網(wǎng)絡(luò)法。Teodorovi?等［7］結(jié)合機(jī)組及飛機(jī)路線恢復(fù)，使用字典序優(yōu)化技術(shù)及分層優(yōu)化技術(shù)，對(duì)新的機(jī)組進(jìn)行排班重算。Vos 等［8］提出了一種新的動(dòng)態(tài)建模框架，該框架可以針對(duì)飛機(jī)短缺問(wèn)題解決已中斷的飛機(jī)時(shí)間表。Sinclair 等［9］在2016 年整合了航班和乘客恢復(fù)問(wèn)題，通過(guò)混合規(guī)劃整數(shù)模型，并運(yùn)用列生成算法來(lái)求解該模型。Petersen 等［10］將飛行計(jì)劃和線路、旅客等因素同時(shí)考慮，運(yùn)用列生成法與Benders 分解來(lái)求模型，最后得出航班調(diào)整的具體計(jì)劃。

1 不正常航班問(wèn)題描述

當(dāng)航空公司原因或機(jī)場(chǎng)因?yàn)槟承┩话l(fā)情況封閉，飛機(jī)原計(jì)劃飛行不能實(shí)施，這時(shí)要盡快調(diào)整航空公司飛行計(jì)劃，安排新飛行計(jì)劃。在航班計(jì)劃調(diào)整方面有三種調(diào)整策略，即飛機(jī)置換、航班延誤、取消航班［11］。由此可知，可以同時(shí)存在飛機(jī)的延誤成本和置換成本。

飛機(jī)置換是取消原執(zhí)行該航班的飛機(jī)，將原不正常航班安排給其他飛機(jī)去執(zhí)行，如圖1所示。

圖1 飛機(jī)置換圖

2 模型的建立

2.1 指派模型

航班恢復(fù)問(wèn)題是在短時(shí)間內(nèi)調(diào)整航班計(jì)劃而使延誤的成本最小化。所以，這類(lèi)問(wèn)題可看作指派問(wèn)題。指派問(wèn)題概念如下：

指派問(wèn)題的簡(jiǎn)單定義是：有n個(gè)人做n件事，如果已知第i個(gè)人做第j件事的總成本為cij（i,j=1,2,…,n），需要指定人和事之間一一對(duì)應(yīng)的指派方案，使做這n件事的總成本最小。

設(shè)有n2個(gè)0-1變量，

數(shù)學(xué)模型為

2.2 航班恢復(fù)最小延誤成本模型

將不正常航班損失分為三種：航班取消成本、航班延誤成本、飛機(jī)置換成本。其中成本指標(biāo)包括：

（1）飛機(jī)折舊費(fèi)：飛機(jī)起飛前在地面等待時(shí)存在折舊費(fèi)用，即ai。ai為一小時(shí)飛機(jī)的折舊費(fèi)；為當(dāng)飛機(jī)i執(zhí)行航班f時(shí)停場(chǎng)時(shí)間。

（2）飛機(jī)停場(chǎng)費(fèi)用：根據(jù)民航局規(guī)定，飛機(jī)停場(chǎng)2 h 以內(nèi)免收停場(chǎng)費(fèi)用；超過(guò)2 h，每停場(chǎng)24 h 按照起降費(fèi)的15%計(jì)收。不足24 h 按24 h計(jì)收。當(dāng)0≤≤2 時(shí)，bi=0。當(dāng)＞2 時(shí)，bi=[/24]×pi× 15%，bi為飛機(jī)停場(chǎng)費(fèi)用，pi為起降費(fèi)用，如表1 所示，Gi為飛機(jī)i的最大起飛重量。

表1 起降費(fèi)用

（3）旅客賠償

民航局規(guī)定：延誤時(shí)間4～8 h，賠償標(biāo)準(zhǔn)不低于200元；延誤時(shí)間大于8 h，賠償不低400元。

（4）航班取消成本

航班取消成本按照該航班延誤大于8 h 計(jì)算。

基于指派模型，又建立了航班恢復(fù)目標(biāo)函數(shù)如下：

約束條件如下：

注釋：飛機(jī)i執(zhí)行航班f時(shí)，令=1，否則為0。飛機(jī)i執(zhí)行航班f需置換時(shí)，令=1，否則為0。航班f需要取消時(shí)，令zf=1，否則為0。代表飛機(jī)i執(zhí)行航班f時(shí)的旅客賠償費(fèi)。pf為航班取消成本。pf1和pf2分別表示航班f上的經(jīng)濟(jì)艙和商務(wù)艙旅客訂座數(shù)。qf1和qf2分別表示航班f上經(jīng)濟(jì)艙和商務(wù)艙的機(jī)票價(jià)格。vi,wi表示飛機(jī)i上經(jīng)濟(jì)艙和商務(wù)艙座位數(shù)。表示飛機(jī)i執(zhí)行的前序航班的到達(dá)機(jī)場(chǎng)；表示飛機(jī)i執(zhí)行的后序航班的出發(fā)機(jī)場(chǎng)。

2.3 改進(jìn)的匈牙利算法

（1）確定飛機(jī)的到達(dá)和起飛機(jī)場(chǎng)，篩選出從該機(jī)場(chǎng)起飛的航班與飛機(jī)進(jìn)行匹配，判斷是否滿足模型約束，直至所有航班滿足條件。

（2）重新搜集飛機(jī)的到達(dá)和起飛機(jī)場(chǎng)。

（3）采集航班延誤旅客人數(shù)、飛機(jī)折舊費(fèi)、飛機(jī)停場(chǎng)費(fèi)、起降費(fèi)、旅客賠償費(fèi)相關(guān)成本數(shù)據(jù)等。

（4）計(jì)算所有航班串的調(diào)整成本，建立目標(biāo)函數(shù)。

（5）根據(jù)約束條件，將成本矩陣輸入Matlab軟件編程求解模型并繪制時(shí)空網(wǎng)絡(luò)圖。

（6）得到新航班調(diào)整策略與各航班串延誤成本，直至結(jié)果滿足實(shí)際要求。

3 算例分析

表2 是成都某航空公司一天內(nèi)成都、北京、杭州三個(gè)機(jī)場(chǎng)的航班計(jì)劃，共包括14個(gè)航班、6架飛機(jī)、3個(gè)機(jī)場(chǎng)。因天氣條件低于機(jī)場(chǎng)最低飛行標(biāo)準(zhǔn)，管理部門(mén)決定在當(dāng)天的6：00—9：00關(guān)閉成都機(jī)場(chǎng)，在此時(shí)段內(nèi)機(jī)場(chǎng)不允許任何航空器起降，而此時(shí)段前的所有航班都可以正常起飛降落，此時(shí)段后機(jī)場(chǎng)立即允許飛機(jī)正常起飛降落。航班f8 因大霧低能見(jiàn)度，航班備降后機(jī)組超時(shí)而取消。

表2 原航班恢復(fù)計(jì)劃表

根據(jù)動(dòng)態(tài)規(guī)劃算法，構(gòu)造航班成本矩陣，計(jì)算出每個(gè)可行航班的成本，通過(guò)Matlab 軟件計(jì)算得到航班調(diào)整方案，為了避免太多無(wú)效航班串致使Matlab 求解速度太慢，規(guī)定前序航班與緊后航班之間不得超過(guò)8 h，所有航班間隔8 h以上的匹配均無(wú)效。將各機(jī)場(chǎng)成本矩陣輸入Matlab 進(jìn)行編程來(lái)求得使各個(gè)機(jī)場(chǎng)成本最小的最優(yōu)解矩陣，最后將三個(gè)機(jī)場(chǎng)的最優(yōu)解矩陣進(jìn)行整合，得出新航班調(diào)整計(jì)劃的航班串，并根據(jù)飛機(jī)起飛和到達(dá)機(jī)場(chǎng)、執(zhí)行航班飛機(jī)的起飛機(jī)場(chǎng)來(lái)整合出已有的各架飛機(jī)所執(zhí)行的新航班。Matlab 求解得到成都機(jī)場(chǎng)、北京機(jī)場(chǎng)和杭州機(jī)場(chǎng)的最優(yōu)解矩陣依次見(jiàn)圖2、見(jiàn)圖3和圖4。

圖2 成都機(jī)場(chǎng)最優(yōu)解矩陣

圖3 北京機(jī)場(chǎng)最優(yōu)解矩陣

圖4 杭州機(jī)場(chǎng)最優(yōu)解矩陣

根據(jù)成都、北京、杭州機(jī)場(chǎng)的最優(yōu)解矩陣，得到新的航班恢復(fù)計(jì)劃表，見(jiàn)表3。

表3 新航班恢復(fù)計(jì)劃表

利用時(shí)空網(wǎng)絡(luò)圖對(duì)新航班計(jì)劃表進(jìn)行描述，繪制出調(diào)整之后的各航班串，見(jiàn)圖5。實(shí)驗(yàn)結(jié)果分析：原航班恢復(fù)計(jì)劃表表1 中，航班串為f1—f5—f9—f12，恢復(fù)成本10.11萬(wàn)元，f2—f10—f13恢復(fù)成本20.14萬(wàn)元，f3—f6恢復(fù)成本3.05，f4—f7 恢復(fù)成本3.5，f8 航班取消，成本58 萬(wàn)元，f11—f14 恢復(fù)成本4.1 萬(wàn)元，總最小成本目標(biāo)函數(shù)值為95.4 萬(wàn)元。新航班恢復(fù)計(jì)劃表表2 中，航班串為f1—f7，恢復(fù)成本3.7 萬(wàn)元，f2—f9—f12，恢 復(fù) 成 本18.18 萬(wàn) 元，f3—f6—f10—f14—f8，恢復(fù)成本32.63 萬(wàn)元，f4—f5，恢復(fù)成本3.8 萬(wàn)元，f11—f13，恢復(fù)成本2.3 萬(wàn)元，總最小成本目標(biāo)函數(shù)值為60.61 萬(wàn)元?？梢?jiàn)新航班恢復(fù)計(jì)劃成本比原航班恢復(fù)計(jì)劃成本降低36.5%。

圖5 恢復(fù)后航班時(shí)空網(wǎng)絡(luò)圖

4 結(jié)語(yǔ)

本文通過(guò)充分考慮航班恢復(fù)的實(shí)際背景，從不正常航班延誤成本最小化的角度出發(fā)，將可用航班的次序進(jìn)行調(diào)整等方式，在指派模型的基礎(chǔ)上建立使不正常航班調(diào)整的成本最小化的目標(biāo)函數(shù)，運(yùn)用Matlab 軟件求解航班最優(yōu)排班，盡可能使航空公司的經(jīng)濟(jì)損失降到最低。本文建立的成本最小化模型及算法適應(yīng)面廣，在短時(shí)間內(nèi)能計(jì)算出使延誤成本最低的航班調(diào)整計(jì)劃，模型合理，算法較為準(zhǔn)確，能提高簽派員工作效率，具有一定的研究?jī)r(jià)值和發(fā)展?jié)摿Α１疚拇嬖谝欢ǖ目筛倪M(jìn)空間，也是下一步需要繼續(xù)研究的地方。比如：①航班調(diào)整方面僅考慮延誤成本，未考慮到旅客滿意度和公平性等問(wèn)題。②沒(méi)有將成本指標(biāo)和非成本指標(biāo)賦權(quán)結(jié)合考慮，須在實(shí)踐中繼續(xù)研究，充分考慮實(shí)際，將非成本指標(biāo)建立模糊綜合評(píng)價(jià)體系。③模型進(jìn)行成本最小化求解時(shí)，是將三個(gè)機(jī)場(chǎng)分開(kāi)，分別將每個(gè)機(jī)場(chǎng)同時(shí)作為前序航班的到達(dá)機(jī)場(chǎng)和后續(xù)航班的出發(fā)機(jī)場(chǎng)進(jìn)行各最小調(diào)整成本求解，最后將三機(jī)場(chǎng)最小成本求和得到最小總成本，下一步可考慮直接求解所有機(jī)場(chǎng)的最小調(diào)整成本。