基于航班延誤的飛機和乘客恢復模型

姜 茂， 韓曉龍

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

?

姜 茂*， 韓曉龍

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

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

航空運輸； 航班延誤； 混合整數規劃； 航班和乘客恢復

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

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

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

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

根據航空運輸的實際情況，飛機上設置了不同的座艙等級，如頭等艙、商務艙和經濟艙.座艙等級不同的乘客機票成本也不相同，導致在航班恢復過程中乘客行程的取消成本，座艙降級成本，航班延誤成本都不同.此外，國際航空公司必須考慮航班延誤對出入境乘客的不同影響.上述文獻在旅客行程恢復或綜合恢復中只是將每架飛機上的乘客視為一個整體，在恢復過程中沒有考慮不同航班類型上各座艙等級的位置數量約束和座艙降級成本，也沒有考慮國際航班恢復過程中出入境乘客恢復成本的異同.只有對這些成本進行細分，才能更好的選擇恢復方案，踐行為旅客服務的宗旨，從而讓航空公司又好又快的發展.

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

1 問題描述

航班延誤對飛機和乘客的影響可由圖1表示，圖中展示了一個由7個航班和3架飛機組成的航線網絡，橫軸代表時間，縱軸代表飛機.每一個航班用一條粗線代替，開始與結束的粗線分別代表航班的出發和到站時間以及機場.線下方括號里的字母代表乘客的行程.如圖1所示，航班f1從機場G出發，到達機場H.航班f1結束后飛機A執飛航班f2，行程P1的旅客銜接至下一個航班f4.

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

當航班f1和航班f3延誤時，要用到航班f1和航班f3執飛飛機的下一個航班以及相關的乘客都將受到影響.行程為P1的乘客有兩個航班，f1和f4，當航班f1發生延誤，乘客到達航班f4的始發機場H時，航班f4已出發，他們的行程被擾動了.因為飛機A發生了延誤，而航班f2必須滿足飛機的最小過站時間限制才能出發，所以航班f2會被延誤.又因為行程為P2的旅客需要足夠的登機時間銜接到航班f7，所以航班f7會受到擾動.航班f3發生延誤時，若不改變航班計劃，行程為P3的乘客會錯過接下來的航班f6和f7，行程P3被擾動.

這個例子表明航班延誤對乘客和飛機的連鎖反應，也表明同時恢復飛機和旅客的必要性.本文研究的問題是同時解決航空公司最貴的飛機資源和為航空公司帶來收益的旅客資源.

2 模型構建

2.1 集合

2.2 參數

2.3 決策變量

2.4 目標函數

(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)表示各航班弧最多由一架飛機執飛，xijf表示由飛機f執飛航班弧ij；式(3)是飛機定期檢查維修約束；式(4)和式(5)表明在規定時間段內，起飛和降落飛機數量不得超過機場所允許的起飛和降落數量；約束(6)表明在整個恢復期結束后，為不影響航空公司的后續運營，各機場對不同機型數量需求的要求；式(7)表明各飛機所執飛的航班飛行距離均不能超過其最大航程；式(8)表示受干擾航班的實際降落時間等于航班實際起飛時間與實際飛行時間之和；式(9)表示受干擾航班的實際起飛時間等于計劃起飛時間與航班延誤時間之和；約束(10)確保恢復過程中被調配給某飛機的各類座艙的乘客數與原來該飛機上所有的各類座艙乘客數之和小于該飛機的乘客容量；約束(11)確保受干擾乘客不被分配給一個中間有取消航班的行程；約束(12)、(13)確保行程p之間的航班有足夠的過站時間；式(14)是決策變量取值范圍約束.

3 算例

該算例是來自法國一家航空公司的真實數據，包括15個航班，其中國內航班2個，洲內航班9個，洲際航班4個；包括6個機場，3個國內機場，3個國外機場；旅客行程2 729個，其中需要轉機的乘客行程200個，航班與旅客行程時段網絡圖如圖2所示.

圖2 航班與旅客行程時段網絡圖Fig.2 Time-band network of flights and itineraries

機場間的距離及不同機場間的航班類別如表1所示，其中I表示跨洲際航班，C表示洲內航班，D表示國內航班.

表1 機場間的距離及航班類別

部分旅客行程信息如表2所示，其中A表示入境乘客，R表示出境乘客，F、B與E分別表示頭等艙、商務艙與經濟艙.

表2 部分旅客行程信息

續表2

由于特殊原因，航班3延誤了1 h，導致該由該飛機執飛的航班8和航班9無法按原定計劃執行，并且導致部分乘坐航班3的旅客無法按時銜接到航班5.

通過CPLEX優化軟件進行求解，運行時間為3.5 min，經過調整后的具體航班恢復方案如表3所示.

表3 航班延誤的恢復方案1

即將原本由飛機A320#1執飛的航班8和航班9改由飛機A320#2準點執飛，而飛機A320#1則準點執飛原本由飛機A320#2執飛的航班10，航班5則順延1 h.恢復成本如表4所示.

表4 方案1航班恢復成本

經過模型優化后的恢復成本為33 156歐元，其中航班5順延1 h，等待來自航班3的銜接乘客，順延成本為30 156歐元，飛機在不影響航空公司恢復期結束后的正常運營條件下，非正常降落位置的懲罰成本為3 000歐元.

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

圖3 恢復方案成本對比Fig.3 Cost Comparison between Different Recovery Schemes

綜上所述，本文所建立的優化模型同時解決了航班發生延誤時乘客與飛機的恢復問題，并取得了良好的經濟效果.

4 結語

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

[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] 樂美龍， 馬 彬. 基于時間段網絡模型的飛機路線恢復研究[J]. 武漢理工大學學報， 2012， 34(11): 63-68．

[3] 唐小衛， 朱金福， 高 強. 流不平衡條件下飛機恢復的優化模型與算法研究[J]. 小型微型計算機系統，2010， 31(04):793-796．

[4] 趙秀麗， 朱金福， 郭 梅. 不正常航班延誤調度模型及算法[J]. 系統工程理論與實踐， 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] 白 鳳， 朱金福， 高 強. 基于列生成算法的不正常航班調度[J]. 系統工程理論與實踐， 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算法的不正常航班旅客流恢復問題[J]. 武漢理工大學學報(信息與管理工程版)， 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] 樂美龍， 王婷婷， 吳聰聰. 多機型不正常航班恢復的時空網絡模型[J]. 四川大學學報(自然科學版)， 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] 趙秀麗. 航空公司不正常航班恢復模型及算法研究[D]. 南京：南京航空航天大學， 2010．

[15] 樂美龍， 李曉嵐. 飛機和旅客流一體化恢復模型[J]. 工業工程， 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.

上海市科委項目(11510501900)．

1000-1190(2015)06-0876-07

F560.1

A

*E-mail:jiangmao8880@163.com．