陶 蕾 彭 怡

(南京航空航天大學(xué)民航學(xué)院 南京 211106)

考慮期望恢復(fù)成本的魯棒性飛機(jī)排班模型

陶 蕾 彭 怡

(南京航空航天大學(xué)民航學(xué)院 南京 211106)

為了減少不正常航班給航空公司生產(chǎn)計劃的實(shí)際運(yùn)行帶來的影響，在經(jīng)典飛機(jī)排班模型的基礎(chǔ)上，考慮航班的期望恢復(fù)成本和航班計劃的魯棒性2個因素，對飛機(jī)排班模型作了改進(jìn).從延誤、取消、飛機(jī)交換和調(diào)機(jī)4種恢復(fù)措施討論了航班期望恢復(fù)成本的構(gòu)成，以總運(yùn)行成本最小和總魯棒性最大建立了雙目標(biāo)的魯棒性飛機(jī)排班模型.在AIMMS軟件中實(shí)現(xiàn)了該模型的求解，算例結(jié)果表明，在總運(yùn)行成本增加不多的情況下，該模型能有效提高飛機(jī)排班計劃的魯棒性.

飛機(jī)排班；魯棒性；恢復(fù)成本；AIMMS

0 引 言

航空公司通常以效益最大或運(yùn)行成本最小來制定生產(chǎn)計劃，但在實(shí)際運(yùn)行的時候，這些生產(chǎn)計劃往往不是最優(yōu)的，因?yàn)楹桨嘤媱澋膱?zhí)行會受到天氣、流量控制、飛機(jī)故障、機(jī)場關(guān)閉等不確定因素帶來的擾動.這些因素導(dǎo)致的航班延誤或取消會造成航班運(yùn)行混亂、旅客不滿意度增加,以及航空公司巨大的經(jīng)濟(jì)和聲譽(yù)損失.

學(xué)術(shù)界對航班計劃的優(yōu)化與管理研究分為2方面，一是“事前研究”，即從航班制定的角度，通過增加航班過站時間或飛機(jī)交換機(jī)會，提高航班計劃的魯棒性.Smith等[1]提出機(jī)場純度的概念，通過限制各機(jī)場的機(jī)型數(shù)量以增加飛機(jī)交換的機(jī)會，從而增加了航班計劃的靈活性.朱星輝等[2]在此基礎(chǔ)上提出航班純度的概念，建立了基于航班純度的魯棒性機(jī)型指派模型. 二是“事后研究”，即從航班恢復(fù)的角度，考慮航班發(fā)生不正常情況后的補(bǔ)救措施，在一定的恢復(fù)期內(nèi)使航班運(yùn)行恢復(fù)到正常狀態(tài).Rosenberger等[3]建立了飛機(jī)路線的恢復(fù)模型，在目標(biāo)函數(shù)中同時考慮路線分配成本和航班取消成本，并運(yùn)用啟發(fā)式搜索算法求解.樂美龍等[4]建立了飛機(jī)流和旅客流一體化恢復(fù)模型，讓旅客、飛機(jī)、機(jī)組這3種資源的總成本最小.Peterson等[5]則建立了飛機(jī)、旅客和機(jī)組路線的一體化恢復(fù)模型.雖然相關(guān)研究較多，但并未將“事前研究”與“事后研究”聯(lián)系起來.

1 飛機(jī)排班問題

1.1 時空網(wǎng)絡(luò)圖

在研究航空運(yùn)輸規(guī)劃問題時，為了直觀的表達(dá)飛機(jī)在時間和空間上的移動，方便構(gòu)建相應(yīng)的數(shù)學(xué)模型[6]，研究人員往往借助于時空網(wǎng)絡(luò)圖,見圖1.

圖1 時空網(wǎng)絡(luò)圖

時空網(wǎng)絡(luò)圖由節(jié)點(diǎn)與有向邊組成.每個節(jié)點(diǎn)代表1架飛機(jī)在某個時刻從某機(jī)場起飛或到達(dá)某機(jī)場，有向邊包括航班邊、停場邊和過夜邊.航班邊從出發(fā)機(jī)場節(jié)點(diǎn)指向到達(dá)機(jī)場節(jié)點(diǎn)；停場邊在同一機(jī)場由上一個節(jié)點(diǎn)指向下一個節(jié)點(diǎn)；過夜邊在同一機(jī)場的最后一個節(jié)點(diǎn)指向第一個節(jié)點(diǎn)，表示飛機(jī)在該機(jī)場過夜.在時空網(wǎng)絡(luò)圖中可以清楚地看出飛機(jī)路徑(即航班銜接)，所以它在飛機(jī)排班問題中應(yīng)用較廣.

1.2 經(jīng)典的飛機(jī)排班模型

飛機(jī)排班是根據(jù)由市場需求確定的航班時刻表(包括時刻、起降機(jī)場、班次、機(jī)型等)、飛機(jī)維修計劃，以及飛機(jī)的技術(shù)狀況，為每一架飛機(jī)安排一連串需執(zhí)行的航班，即飛機(jī)路徑.該問題可構(gòu)造成一個集合分割問題，具體描述如下：S為飛機(jī)路線集合；F為航班集合；參數(shù)Cs為飛機(jī)路線S的運(yùn)行成本；參數(shù)ais是0-1類型，航班i在飛機(jī)路線s中時值為1，否則為0；決策變量xS是一個0-1變量，當(dāng)飛機(jī)路線s被選中時值為1，否則為0.假設(shè)飛機(jī)均滿足維修計劃的要求，則可建立如下的飛機(jī)排班模型.

min ∑s∈SCSxS

(1)

s.t. ∑s∈Saisxs=1,?i∈F

(2)

xs={0,1}

(3)

式(1)為目標(biāo)函數(shù)，為計劃運(yùn)行成本最??；式(2)航班覆蓋約束，為每一個航班都僅在一個飛機(jī)路線中；式(3)為決策變量是一個0-1變量.該問題的變量數(shù)遠(yuǎn)遠(yuǎn)超過約束條件數(shù)，列生成算法已經(jīng)可以很好地求解.值得注意的是，航班恢復(fù)模型與飛機(jī)排班模型非常相似，只需要增加一個航班取消的決策變量，并在目標(biāo)函數(shù)中相應(yīng)地增加航班取消的成本即可[7].

2 航班的恢復(fù)成本

2.1 延誤成本

一般來說，航空公司的延誤成本可以從P，A，C 3個方面計算，即旅客延誤成本、飛機(jī)延誤成本、機(jī)組延誤成本.航空公司的延誤成本結(jié)構(gòu)見圖2.

圖2 航空公司延誤成本結(jié)構(gòu)圖

由于航班延誤成本是一項(xiàng)長期變動成本，航空公司通過歷史財務(wù)數(shù)據(jù)的統(tǒng)計，將延誤成本分?jǐn)傇诿總€旅客上，得到單位時間內(nèi)平均每旅客延誤成本Unit Costdelay，則航班的延誤成本可表示為

Cdelay=UnitCostdelay×N×T

式中：N為平均旅客數(shù)；T為平均延誤時間.

2.2 取消成本

航班取消會對航空公司帶來極大的經(jīng)濟(jì)損失，而且在實(shí)際運(yùn)行中航班通常是成對取消的(即同時取消往返程)，以保證飛機(jī)路線中其他航班的可恢復(fù)性.在計算取消成本時引入機(jī)會成本的概念，即取消成本相當(dāng)于航班不取消時航空公司可獲得的收益，則取消成本可表示為：Ccancellation=N×P.式中：N為平均旅客數(shù)；P為平均票價.

2.3 飛機(jī)交換成本

飛機(jī)交換是指當(dāng)航班發(fā)生延誤時，由暫時閑置的飛機(jī)代替延誤的飛機(jī)執(zhí)行后續(xù)飛行任務(wù)，從而減少延誤的波及，交換過程見圖3～4.原計劃中航班f1與f3銜接，f2與f4銜接.當(dāng)f1發(fā)生延誤，其到達(dá)時間晚于f2，那么可以將先到達(dá)的f2與f3銜接，后到達(dá)的f1與f4銜接，即2個任務(wù)串交換了執(zhí)飛的飛機(jī).這樣可以相應(yīng)地減少航班延誤的時間.飛機(jī)交換成本與機(jī)型有關(guān)，同種機(jī)型的交換對航班計劃影響較小.在在單機(jī)型飛機(jī)交換的情況下，假設(shè)發(fā)生一次飛機(jī)交換的成本為Cswap.

圖3 原飛機(jī)任務(wù)串

圖4 飛機(jī)交換后飛機(jī)任務(wù)串

2.4 調(diào)機(jī)成本

調(diào)機(jī)是指從某機(jī)場調(diào)運(yùn)一架閑置飛機(jī)到其他機(jī)場執(zhí)行飛行任務(wù).當(dāng)飛機(jī)出現(xiàn)機(jī)械故障，短時間內(nèi)無法修復(fù)，則調(diào)運(yùn)飛機(jī)可以幫助航班恢復(fù)運(yùn)行[10].調(diào)機(jī)成本與2個機(jī)場之間的航程以及飛機(jī)的機(jī)型有關(guān)，用Cferrying表示平均調(diào)機(jī)成本.

2.5 飛機(jī)路線的期望恢復(fù)成本

在飛機(jī)排班過程中，在對每個航班指派機(jī)型之后，可生成所有可行的飛機(jī)路線集合，通過歷史數(shù)據(jù)的統(tǒng)計與分析，可以計算出每個航班發(fā)生不正常情況后分別運(yùn)用延誤、取消、飛機(jī)交換、調(diào)機(jī)這4種恢復(fù)策略的概率pdelay，pcancellation，pswap，pferrying，從而該航班的期望恢復(fù)成本可以表示為

ERecoveryCost=[CdelayCcancellationCswapCferrying]·

3 考慮期望恢復(fù)成本的魯棒性飛機(jī)排班模型

3.1 飛機(jī)排班計劃的魯棒性

在飛機(jī)排班計劃的制定階段就考慮航班延誤的影響，使飛機(jī)排班計劃具有一定的抗干擾能力，這就是飛機(jī)排班計劃的魯棒性.具有魯棒性的飛機(jī)排班計劃有以下4個特點(diǎn)：減少航班延誤發(fā)生的概率，提高航班銜接的正常率；出現(xiàn)航班延誤等不正常現(xiàn)象時能夠快速恢復(fù)；能夠有效吸收不正?，F(xiàn)象的波及；一定程度上降低航空公司的運(yùn)行成本[11].提高飛機(jī)排班計劃的魯棒性的方法包括增加航班過站時間裕度、增加飛機(jī)交換機(jī)會和采用小循環(huán)的飛機(jī)路線等.

3.2 飛機(jī)排班計劃魯棒性的定量計算

通常，航班延誤分為固有延誤(inherent delays)和波及延誤(propagated delays).固有延誤是在理想狀態(tài)下航班計劃本身就有的獨(dú)立延誤，而波及延誤是由于前序航班的延誤而導(dǎo)致的，與飛機(jī)路線有關(guān).實(shí)際延誤(actual delays)是航班計劃在實(shí)際運(yùn)行中產(chǎn)生的延誤，包括固有延誤和波及延誤.航班計劃的魯棒性，即航班計劃的可靠性，可以用固有延誤和實(shí)際延誤的比值表示[12].

對飛機(jī)路線s上航班I來說，魯棒性可以定量表示為

?i∈F,s∈S

對一條飛機(jī)路線s來說，魯棒性可以定量表示為

?s∈S

對整個飛機(jī)排班計劃來說，魯棒性可以定量表示為

3.3 模型提出

在經(jīng)典的飛機(jī)排班模型基礎(chǔ)上，考慮航班的恢復(fù)成本因素，以及飛機(jī)排班計劃的魯棒性，可以建立起雙目標(biāo)的飛機(jī)排班魯棒性優(yōu)化模型.

(4)

(5)

s.t.∑s∈Saisxs=1,?i∈F

(6)

xs={0,1}

(7)

目標(biāo)函數(shù)(4)是最小化飛機(jī)排班計劃實(shí)際總運(yùn)行成本，包括計劃運(yùn)行成本和期望恢復(fù)成本；目標(biāo)函數(shù)(5)是最大化飛機(jī)排班計劃魯棒性；約束(6)表示每一個航班都僅在一個飛機(jī)路線中；式(7)表示決策變量是一個0-1變量.

3.4 模型求解

這是一個雙目標(biāo)規(guī)劃問題，求解難度較大，可將其轉(zhuǎn)化為單目標(biāo)規(guī)劃問題再求解.求解步驟如下.

步驟1 先求解問題式(4)，得到滿足約束條件的目標(biāo)函數(shù)的最小值Cmin.

步驟2 要求加入魯棒性因素后飛機(jī)排班計劃總體成本增加的比例不超過r，那么可將目標(biāo)函數(shù)式(4)化為約束條件，從而得到單目標(biāo)規(guī)劃模型.

∑s∈Saisxs=1,?i∈F

xs={0,1}

4 實(shí)例分析并運(yùn)用AIMMS軟件求解

4.1 數(shù)據(jù)

由于缺乏航空公司的真實(shí)數(shù)據(jù)，文中設(shè)計了一個算例，航班計劃見表1.

表1 航班時刻表

根據(jù)表1中的航班時刻表，可以構(gòu)造出所有可行的飛機(jī)路線，見表2.

表2 飛機(jī)路線集合

4.2 使用AIMMS建模并求解

AIMMS(advanced integrated multidimensional modeling software)是一款能夠快速完成建模與求解的軟件，它擁有集成的開發(fā)環(huán)境、求解器和圖形化用戶界面，為運(yùn)籌學(xué)領(lǐng)域的研究人員提供了有效的研究工具.運(yùn)用AIMMS完成算例的建模與求解過程，模型聲明與求解結(jié)果分別見圖5和表3.

圖5 模型聲明

飛機(jī)路線步驟1步驟2R1R21R31R4R5R6R7R81R9R10R111R12R13R141TotalCost22372323TotalRobustness6．28．0

模型中的各參數(shù)和變量的定義見圖5，F(xiàn)light和Route分別代表航班和飛機(jī)路線的集合；參數(shù)ais是0-1類型，航班i在飛機(jī)路線s中時值為1，否則為0；參數(shù)Robustness(s)表示飛機(jī)路線s的魯棒性；參數(shù)OperationCost(s)和EstimatedRecoveryCost(s)分別代表飛機(jī)路線的運(yùn)行成本和期望延誤成本；參數(shù)r表示加入魯棒性因素后成本增加的最大比例，一般由航空公司的計劃制定人員設(shè)定；參數(shù)Cmin表示步驟1計算出來的最小成本；變量xs是0-1變量，當(dāng)飛機(jī)路線s被選中時值為1，否則為0；變量TotalCost表示飛機(jī)排班計劃的總成本，包括運(yùn)行成本和期望延誤成本；變量TotalRobustness表式飛機(jī)排班計劃的總魯棒性值；約束FlightCoverage(i)是航班覆蓋約束，表示每一個航班i都要在一條飛機(jī)路線中；約束CminConstraint表示加入魯棒性因素后飛機(jī)排班計劃總體成本增加的比例不超過r；最后是兩個目標(biāo)函數(shù)，MinTotalCost和MaxTotalRobustness分別代表總運(yùn)行成本最小和總魯棒性最大.

4.3 結(jié)果分析

上述算例中，步驟1的最優(yōu)解為飛機(jī)路線R3，R11和R14，加入飛機(jī)路線的期望恢復(fù)成本之后的總運(yùn)行成本為2 237，總魯棒性為6.2；步驟2設(shè)定加入魯棒性因素后飛機(jī)排班計劃總成本增加的比例不超過5%， 最終求得最優(yōu)解為飛機(jī)路線R2和R8，總成本為2 323，總魯棒性為8.0.可以發(fā)現(xiàn)，加入魯棒性目標(biāo)后，雖然總成本上升了3.8%，但是飛機(jī)排班計劃的魯棒性增加了29.0%，從而使排班計劃更好地吸收不正常航班帶來的影響.

5 結(jié) 束 語

航班受到外界因素的干擾發(fā)生延誤的現(xiàn)象是不可避免的，為了能夠在飛機(jī)排班計劃的制定階段就考慮可能會發(fā)生的航班不正?，F(xiàn)象，在模型的目標(biāo)函數(shù)中同時計算計劃運(yùn)行成本和期望恢復(fù)成本，以總運(yùn)行成本最小建立飛機(jī)排班模型.在此基礎(chǔ)上，為了提高計劃的魯棒性，加入了總魯棒性最大化的目標(biāo)函數(shù)，從而建立起雙目標(biāo)的魯棒性飛機(jī)排班模型，并運(yùn)用功能強(qiáng)大的AIMMS軟件進(jìn)行求解.

不足之處是模型中只考慮了航空公司的直接恢復(fù)成本，未考慮不正常航班帶來的旅客忠誠度降低等間接成本.不正常航班如何影響旅客以后的航班選擇行為是未來的研究方向.

[1]SMITH C, JOHNSON L. Robust airline fleet assignment: imposing station purity using station decomposition[J]. Transportation Science,2006,40(4):497-516.

[2]朱星輝,朱金福,高強(qiáng).基于航班純度的魯棒性機(jī)型指派問題研究[J].預(yù)測,2011,30(1):71-74.

[3]ROSENBERGER M, JOHNSON L, NEMHAUSER L. Rerouting aircraft for airline recovery[J]. Transportation Science,2003,37(4):408-421.

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

[5]PETERSEN D, S?LVELING G, CLARKE J P, et al. An optimization approach to airline integrated recovery[J]. Transportation Science,2016,46(4):482-500.

[6]朱金福.航空運(yùn)輸規(guī)劃[M].西安:西北工業(yè)大學(xué)出版社,2009.

[7]CLAUSEN J, LARSEN A, LARSEN J, et al. Disruption management in the airline industry-concepts, models and methods[J]. Computers & Operations Research,2010,37(5):809-821.

[8]ANDERSSON G T. The flight perturbation problem[J]. Transportation Planning & Technology,2004,27(2):91-117.

[9]趙文智,劉博.航班延誤成本測算方法研究[J].交通運(yùn)輸工程與信息學(xué)報,2011,9(1):5-9.

[10]王春林.基于灰色理論的非正常航班運(yùn)行研究[D].廣漢:中國民用航空飛行學(xué)院,2013.

[11]何敏.航班計劃的魯棒性設(shè)計[D].南京:南京航空航天大學(xué),2012.

[12]JASENKA P. Beyond airline disruptions[M]. America:Ashgate Publishing,2009.

Robust Modeling for Aircraft Scheduling Problem by Considering the Estimated Recovery Cost

TAO Lei PENG Yi

(CollegeofCivilAviation,NanjingUniversityofAeronauticsandAstronautics,Nanjing211106,China)

In order to reduce the impact of disrupted flights on the actual operations of airlines, the traditional aircraft scheduling model is improved by considering the estimated recovery cost of flights and robustness of the schedule. The constituents of the recovery cost are discussed based on four recovery strategies: delay, cancellation, swap and ferrying. A two-objective robust aircraft scheduling model is presented, which aims to minimize the total actual operation cost and maximize the total robustness of the scheduling model. AIMMS software is applied to solve the model. The results show that the model could effectively enhance the robustness of schedule without much increase on cost.

aircraft scheduling; robustness; recovery cost; AIMMS

2016-08-27

F560

10.3963/j.issn.2095-3844.2016.06.033

陶蕾(1992—)：女，碩士生，主要研究領(lǐng)域?yàn)楹娇者\(yùn)輸系統(tǒng)優(yōu)化