樂美龍，王婷婷，吳聰聰

(上海海事大學(xué)科學(xué)研究院，上海201206)

中國民航局的民航行業(yè)發(fā)展統(tǒng)計公報中披露，2011年，我國各航空公司計劃航班235.3萬班，正常執(zhí)行181.5萬班，航班正常率為77.2%.其中，主要航空公司計劃航班201.8萬班，正常執(zhí)行157.2萬班，航班正常率為77.9%;中小航空公司計劃航班33.5萬班，正常執(zhí)行24.4萬班，航班正常率為72.7%.航班的不正常帶來的損失十分巨大，據(jù)美國航空協(xié)會統(tǒng)計，不正常航班每年給美國航空業(yè)造成約100億美元損失.

文獻(xiàn)［1］對近30年航空恢復(fù)優(yōu)化的文獻(xiàn)進(jìn)行了整理，指出航空恢復(fù)問題共分為4大類:飛機、機組、乘客、綜合恢復(fù)，并分別進(jìn)行了概述.文獻(xiàn)［2］中依據(jù)優(yōu)先配對原則，進(jìn)行了航班與機組的同時優(yōu)化.文獻(xiàn)［3］中提出了同時考慮飛機和乘客的模型，用“航班環(huán)”的概念代替“航班”來建立該模型，通過優(yōu)化器求解，給出不同類型的解決方案.文獻(xiàn)［4］中提出了一種結(jié)合時間窗的優(yōu)化模型，來重新規(guī)劃受到地面等待和延遲情況下的飛機航線.文獻(xiàn)［5］中運用了一種決策支持工具(decision support tool for airlines schdule ercovery，DSTAR)來解決航空公司遇到突發(fā)事件時的恢復(fù)問題.文獻(xiàn)［6］中提出了關(guān)于航班重新排班和調(diào)整飛機航線的模型，采用一種選擇啟發(fā)式算法來選出需要調(diào)整航線的飛機.文獻(xiàn)［7］中提出了一種大規(guī)模鄰域搜索的啟發(fā)式算法來解決飛機和乘客的恢復(fù)問題.文獻(xiàn)［8］中結(jié)合了各種資源的平衡來建立模型，運用循環(huán)啟發(fā)式算法來求解，另外針對不同措施進(jìn)行了偏好研究，給出了不同的計算結(jié)果.文獻(xiàn)［9］中運用了一種貪婪隨機適值搜索過程(greedy randomized adaptive search procedure，GRASP)來重新規(guī)劃受到地面等待和延誤的航線，但該算法尚存在一些不足之處，文中將在以下章節(jié)進(jìn)行詳細(xì)說明.

1 飛機恢復(fù)問題描述

飛機故障、機組人員病假、極端天氣、流量控制等突發(fā)事件，都會造成航班不正常執(zhí)行，此時，必須盡快恢復(fù)航班計劃，以減少航空公司的損失.一般來說，航空恢復(fù)問題主要包括飛機恢復(fù)、機組恢復(fù)及乘客恢復(fù).其中飛機是航空公司日常運行中成本最高的部分.因此，當(dāng)原航班計劃被擾動時，首先考慮飛機的恢復(fù)［10］.進(jìn)行飛機恢復(fù)時，可以采取的措施包括運用備用飛機、飛機調(diào)用、飛機互換、飛機超時限飛行等。一般用航班取消和延遲的成本衡量飛機航線安排的成本［11］.

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

以下是飛機恢復(fù)數(shù)學(xué)模型，該模型考慮了航班的取消和延遲，從而對可用飛機可進(jìn)行指派，目標(biāo)是使取消和延遲航班的總成本最小.

參數(shù):Sf為航班f的計劃起飛時間;trf為航班f的航行時間;tc為航班間的連接時間;Cf為航班f的取消成本;Df為航班f延遲1 min的成本.

變量:xkf={0，1}，當(dāng)航班f用飛機k飛時為1，否則為0;zf={0，1}，航班f取消時為1，否則為0;tdf為航班f的實際起飛時間;taf為航班f的實際到達(dá)時間.

目標(biāo)函數(shù):

約束條件:

模型中，目標(biāo)函數(shù)(1)中的第1部分為取消航班成本，第2部分為航班延遲成本;約束條件(2)表示對于每條航線，均指派不多于一架飛機;約束條件(3)保證對于每架飛機，只指派到不多于一條航線;約束條件(4)表示對于每個航班，要么取消，要么由一架飛機飛;約束條件(5)表示每個航班若不取消，其到達(dá)時間為起飛時間與飛行時間之和;約束條件(6)表示每條航線的后一個航班起飛時間為上一個航班到達(dá)時間與連接時間之和;約束條件(7)保證航班實際出發(fā)時間不早于計劃起飛時間.

3 算法

3.1 傳統(tǒng)的GRASP算法

傳統(tǒng)的GRASP的步驟為:① 構(gòu)造初始方案;②隨機選擇兩條航線組成航線對，進(jìn)行一系列的航班互換等操作，共7種方式，依次為航班環(huán)尾接、航班環(huán)續(xù)前、航班環(huán)插入中間、航班串的尾接、首尾機場相同的航班串互換、出發(fā)機場相同的航線尾航班串互換、航班環(huán)的取消，按照這幾種方式構(gòu)造鄰域解，并把成本減小的鄰域放到候選表中;③在候選表中隨機選擇一個鄰域解構(gòu)造可行解［9］.該方法被證明可以有效進(jìn)行初始解的鄰域搜索，最終可以得到接近最優(yōu)的解.

航班串代表有2個或2個以上的航班組成的一條航線(圖1).

“奉獻(xiàn)清潔能源，打造綠色企業(yè)”，這是中國石化一直以來的倡導(dǎo)。在每年的公眾開放日，年輕的講解員們借助智能機器人、小視頻，讓大家能深刻地了解油氣及石化產(chǎn)品從生產(chǎn)、加工到使用的一整套環(huán)節(jié)，也深刻地了解到了中國石化為老百姓平時的節(jié)能減排，環(huán)境保護方面做出的突出貢獻(xiàn)。這種近距離的接觸，不僅展示了企業(yè)的社會責(zé)任、技術(shù)革新，而且感染了前去參觀的老百姓，讓他們更深地體會到應(yīng)該節(jié)約能源、綠色生活。

圖1 航班串Fig.1 Flight route

航班環(huán)代表首尾為同一機場的航班串(圖2).

圖2 航班環(huán)Fig.2 Flight circle

算法不足之處在于:①將任意兩條航線作為航線對產(chǎn)生鄰域解，這其中包括了兩條均未受擾的航線，既不符合航空公司盡量不脫離原航班計劃的實際情況，又增加了算法運行時間;②選擇航線對時，將兩條所經(jīng)機場毫不相關(guān)的航線組對，也增加了算法運行時間;③鄰域產(chǎn)生后，算法將明顯不符合實際不情況的鄰域也進(jìn)行評價，如違反宵禁政策、原航班順序顛倒等，降低了算法效率;④ 只將成本降低的鄰域放入備選池，會容易陷入局部最優(yōu).

3.2 改進(jìn)的GRASP算法

3.2.1 鄰域解的構(gòu)造

文中的模型與算法研究是以航班串的形式展開，因此算法的初始解由一系列的航班串組成.對比傳統(tǒng)的GRASP算法的不足之處①，在實際情況中，航空公司傾向于選擇脫離原航班計劃較小的恢復(fù)方案.因此在構(gòu)造鄰域前，設(shè)計的算法是選擇一條受擾航線作為航線對中的第1條航線，后續(xù)展開的航班操作也是圍繞受擾航線展開的.

選擇航線對中的第2條航線時，若某條航線所經(jīng)過的機場不包括第1條航線的任意航班，則該航線不被選擇為第2條航線.兩條航線產(chǎn)生后組成航線對，對該航線對進(jìn)行GRASP算法的航班操作.按照這樣的方式產(chǎn)生初始解的鄰域.

3.2.2 鄰域驗證機制

由GRASP算法的航班操作方法產(chǎn)生一系列的航線對，這些航線對中有些不符合實際情況，可以提前排除，不對其進(jìn)行評價.這里違反的情況包括兩種:宵禁和原航班順序顛倒.

3.2.3 鄰域解的備選池

每種恢復(fù)方案對應(yīng)算法的一個執(zhí)行解，對執(zhí)行解驗證通過后，將航線對應(yīng)到飛機，即得到新的執(zhí)行解，并再度驗證評價，以此類推.每組航線對對應(yīng)的鄰域解有很多，算法將所有鄰域解進(jìn)行評價，如果這個鄰域解比原航線對的總成本(包括取消與延誤成本)小，則將其放入備選池中.在這種方式的基礎(chǔ)上，將總成本增大的放入附加備選池.將這兩種備選池統(tǒng)稱為鄰域解的備選池.這種篩選可以控制鄰域解的數(shù)量，并提高算法的收斂性.

3.2.4 執(zhí)行解的選取

得到鄰域解的備選池后，需要從中選取執(zhí)行解，本算法采用隨機選取的方式，并基于以下原則:①若基礎(chǔ)備選池不為空，則在其中隨機選取鄰域解作為執(zhí)行解;②若基礎(chǔ)備選池為空，即當(dāng)前解不存在目標(biāo)成本降低的鄰域解，則轉(zhuǎn)向附加備選池，允許執(zhí)行解暫時變壞，因此在附加備選池中隨機選取一個解.但由于執(zhí)行解的目標(biāo)成本增加的情況總是存在，且鄰域解數(shù)量較多.因此，設(shè)定了模擬退火方法的判定方式，即判斷附加備選池中滿足式(8)的鄰域解的數(shù)量與備選池中鄰域解的比例，若大于5%，則從中隨機選取一個解;反之算法結(jié)束.

式中:Δ表示增加的成本;Kt表示當(dāng)前溫度;random(0，1)指0 至1 的一個均勻隨機數(shù)［12］.

選取出執(zhí)行解后即可進(jìn)行改造，所得到的執(zhí)行解作為下一次迭代的初始解.為了滿足航班恢復(fù)的時效性，算法設(shè)置了時間限制.算法流程如圖3.

圖3 改進(jìn)的GRASP算法步驟Fig.3 Procedure of the improved GRASP

4 算例分析

文中對所提出的模型，運用小規(guī)模的算例進(jìn)行計算，將計算結(jié)果與簡單順延方式進(jìn)行比較.這里指出，簡單的順延方式即飛機在原航班出發(fā)時間的基礎(chǔ)上加上被延誤的時間作為該航班的出發(fā)時間.當(dāng)航班違反宵禁時即取消該航班及其后續(xù)航班.計算中其中涉及的假設(shè)包括:①允許飛機的調(diào)換;②航班延遲成本為每分鐘100元;③ 航班間平均連接時間為60分鐘;④ 航班取消成本按照特定公式(取消成本=乘客數(shù)×機票均值)來計算.

以某航空公司某天737-800機隊的部分?jǐn)?shù)據(jù)進(jìn)行計算，數(shù)據(jù)涉及到20架飛機，109個航班，8126個乘客.其中時間表示方式按照6:00為0，以后的時間按分鐘數(shù)依次累加，例如130指8:10.突發(fā)事件以及相關(guān)數(shù)據(jù)如表1，其中直接或間接受到飛機故障影響的航班有9個，受到機場關(guān)閉影響的航班有9個，受到影響的航班共占8.26%.

表1 突發(fā)事件Table 1 The disruptions

采用 C#語言對原 GRASP算法、改進(jìn)后的GRASP算法及Gurobi求解器分別進(jìn)行程序設(shè)計，在個人筆記本電腦(Duo CPU@2 GHz，1 GB RAM)上運行，分別對該問題進(jìn)行求解，所得結(jié)果與簡單的順延結(jié)果的比較情況如表2.

表2 計算結(jié)果對比Table 2 Comparison of different results

由表2可以看出，兩種GRASP搜索算法與Gurobi求解器均可以在較短時間內(nèi)得出航班恢復(fù)方案.其中原GRASP算法搜索出的可行解取消航班數(shù)為4個，而改進(jìn)后的算法為2個，且改進(jìn)后的算法延遲航班數(shù)也較少.其中，原GRASP算法所得方案1h以內(nèi)延遲航班數(shù)占總延遲航班數(shù)的64.71%，而改進(jìn)后的算法這一數(shù)據(jù)為71.43%，因此優(yōu)化方案的結(jié)構(gòu)更好.同時，改進(jìn)后算法比原算法總成本減少了8.99%，計算時間少了36%，因此更適合解決較大規(guī)模的問題.另外，運用改進(jìn)的GRASP算法與求解器得出的方案相同，但明顯的是，算法的計算時間較求解器節(jié)省70%以上，雖然計算時間均在1 min之內(nèi)，但計算更大規(guī)模數(shù)據(jù)時，算法的優(yōu)勢將體現(xiàn)出來.

5 結(jié)論

文中針對航空公司飛機恢復(fù)要求，建立了數(shù)學(xué)模型.之后，運用Gurobi優(yōu)化軟件與改進(jìn)前后的GRASP算法進(jìn)行算例求解，得到了恢復(fù)方案.運用改進(jìn)后的GRASP算法，明顯減少了求解時間，提高了運算效率.文中采用的數(shù)據(jù)來自于上海某航空公司.實例計算表明:采用優(yōu)化軟件進(jìn)行模型求解可以得出比順延更好的簡單實時恢復(fù)方案，GRASP算法的運用可以減少求解時間，而運用改進(jìn)后的GRASP算法還可以將求解效率進(jìn)一步提高.

但是，文中算法尚存在一些不足之處.對于模型，文中只考慮了飛機的恢復(fù)，未考慮機組人員和乘客的恢復(fù).對于算法，文中雖然在運行時間上將GRASP進(jìn)行了改進(jìn)，提高了求解效率，但沒有考慮機型交換方式.另外，文中只解決當(dāng)日飛機的恢復(fù)，沒有處理多日內(nèi)的恢復(fù)問題.以上均為以后進(jìn)一步的研究方向.

References)

［1］ Le Meilong，Wu Congcong，Zhan Chenxu，et al.30 years′march of mathematical programming:a classification and literature review［C］∥International Conference on Transportation and Mechanical，and Electrical Engineering.Changchun China:［s.n.］，2011:36-41.

［2］Le Meilong，Sun Lihong.Optimal airline crew recovery considering flight time constraint and paring rule［C］∥2011 International Conference on Transportation and Mechanical＆ Electrical Engineering.Changchun China:［s.n.］，2011:78-84.

［3］Jafari N，Zegordi H.Simultaneous recovery model for aircraft and passengers［J］.Journal of the Franklin Institute，2011，348(7):1638-1655.

［4］Bard J F，Yu G，Arguello M F.Optimizing aircraft routings in response to groundings and delays［J］.IIE Transactions，2001，33:931-947.

［5］Abdelghny K F，Abdelghany A F，Ekollu G.An integrated decision support tool for airlines schedule recovery during irregular operations［J］.European Journal of Operational Research，2008，185(2):825-848.

［6］Rossenberger J M，Johnson E L，Nemhauser G L.Rerouting aircraft for airline recovery ［J］.Transportation Science，2003，37(4):408-421.

［7］ Bisaillon S，Cordeau J F，Laporte G，et al.A large neighborhood search heuristic for the aircraft and passenger recovery problem［J］.Operation Research，2011，9:139-157.

［8］Thengvall B G，Bard J F，Yu G.Balancing user preferences for aircraft schedule recovery during irregular operations［J］.IIE Transactions，2000，32:181-193.

［9］Arguello M F，Bard J F，Yu G.A GRASP for aircraft routing in response to groundings and delays［J］.Journal of Combinatorial Optimization，1997，5:211-228.

［10］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.

［11］Kohl N，Larsen A，Larsen J，et al.Airline disruption management:perspectives，experiences and outlook［J］.Journal of Air Transport Management，2007，13(3):149-162.

［12］唐小衛(wèi)，高強，朱金福.不正常航班恢復(fù)模型的貪婪模擬退火算法研究［J］.預(yù)測，2010(1):66-70.Tang Xiaowei，Gao Qiang，Zhu Jinfu.Research on greedy simulated annealing algorithm of irregular flight schedule recovery model［J］.Forecasting，2010(1):66-70.(in Chinese)