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

陶 蕾 彭 怡

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

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

陶 蕾 彭 怡

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

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

飛機排班；魯棒性；恢復成本；AIMMS

0 引 言

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

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

1 飛機排班問題

1.1 時空網絡圖

在研究航空運輸規劃問題時，為了直觀的表達飛機在時間和空間上的移動，方便構建相應的數學模型[6]，研究人員往往借助于時空網絡圖,見圖1.

圖1 時空網絡圖

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

1.2 經典的飛機排班模型

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

min ∑s∈SCSxS

(1)

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

(2)

xs={0,1}

(3)

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

2 航班的恢復成本

2.1 延誤成本

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

圖2 航空公司延誤成本結構圖

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

Cdelay=UnitCostdelay×N×T

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

2.2 取消成本

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

2.3 飛機交換成本

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

圖3 原飛機任務串

圖4 飛機交換后飛機任務串

2.4 調機成本

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

2.5 飛機路線的期望恢復成本

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

ERecoveryCost=[CdelayCcancellationCswapCferrying]·

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

3.1 飛機排班計劃的魯棒性

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

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

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

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

?i∈F,s∈S

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

?s∈S

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

3.3 模型提出

在經典的飛機排班模型基礎上，考慮航班的恢復成本因素，以及飛機排班計劃的魯棒性，可以建立起雙目標的飛機排班魯棒性優化模型.

(4)

(5)

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

(6)

xs={0,1}

(7)

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

3.4 模型求解

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

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

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

∑s∈Saisxs=1,?i∈F

xs={0,1}

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

4.1 數據

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

表1 航班時刻表

根據表1中的航班時刻表，可以構造出所有可行的飛機路線，見表2.

表2 飛機路線集合

4.2 使用AIMMS建模并求解

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

圖5 模型聲明

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

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

4.3 結果分析

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

5 結 束 語

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

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

[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].預測,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].工業工程,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]朱金福.航空運輸規劃[M].西安:西北工業大學出版社,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].交通運輸工程與信息學報,2011,9(1):5-9.

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

[11]何敏.航班計劃的魯棒性設計[D].南京:南京航空航天大學,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—)：女，碩士生，主要研究領域為航空運輸系統優化