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

陶 蕾 彭 怡

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

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

陶 蕾 彭 怡

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

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

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

0 引 言

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

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

1 飛機排班問題

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

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

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

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

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

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

min ∑s∈SCSxS

(1)

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

(2)

xs={0,1}

(3)

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

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

2.1 延誤成本

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

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

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

Cdelay=UnitCostdelay×N×T

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

2.2 取消成本

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

2.3 飛機交換成本

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

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

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

2.4 調(diào)機成本

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

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

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

ERecoveryCost=[CdelayCcancellationCswapCferrying]·

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

3.1 飛機排班計劃的魯棒性

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

3.2 飛機排班計劃魯棒性的定量計算

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

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

?i∈F,s∈S

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

?s∈S

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

3.3 模型提出

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

(4)

(5)

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

(6)

xs={0,1}

(7)

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

3.4 模型求解

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

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

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

∑s∈Saisxs=1,?i∈F

xs={0,1}

4 實例分析并運用AIMMS軟件求解

4.1 數(shù)據(jù)

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

表1 航班時刻表

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

表2 飛機路線集合

4.2 使用AIMMS建模并求解

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

圖5 模型聲明

飛機路線步驟1步驟2R1R21R31R4R5R6R7R81R9R10R111R12R13R141TotalCost22372323TotalRobustness6．28．0

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

4.3 結(jié)果分析

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

5 結(jié) 束 語

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

不足之處是模型中只考慮了航空公司的直接恢復(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]朱星輝,朱金福,高強.基于航班純度的魯棒性機型指派問題研究[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]樂美龍,李曉嵐.飛機和旅客流一體化恢復(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]朱金福.航空運輸規(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].交通運輸工程與信息學(xué)報,2011,9(1):5-9.

[10]王春林.基于灰色理論的非正常航班運行研究[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)域為航空運輸系統(tǒng)優(yōu)化