□ 田倩南,張成勇,李 杰,冷凱君

(1.湖北經(jīng)濟學院 湖北物流發(fā)展研究中心，湖北 武漢 430205；2.華中科技大學 管理學院,湖北 武漢 430074)

據(jù)國際航空運輸協(xié)會(International Air Transport Association,IATA)的數(shù)據(jù)，2019年全球航空業(yè)的旅客總量為45.8億人次，比2018年增長6%。其中，2019年中國民航旅客運輸量6.6億人次，同比增長7.9%。民航進一步與綜合交通深度融合，其旅客周轉量在綜合交通運輸體系中占比達32.8%，同比提升1.5%，與其他運輸行業(yè)相比，航空運輸具有速度快、效率高、覆蓋范圍廣等多種優(yōu)勢，與此同時，也容易因天氣(大規(guī)模臺風和雨雪霧等)、航空公司(機組人員空勤或航班計劃調(diào)整等)、空管(流量控制等)及其他因素(旅客等)(如表1所示)而產(chǎn)生延誤。比如，2018年我國主要航空公司(全年航班量排名前十的航司)平均航班正常率只有75.62%。據(jù)估算，我國民航業(yè)由于各種因素導致的延誤帶來的總經(jīng)濟損失每年不少于500億元人民幣。

表1 2020年航班不正常原因分類統(tǒng)計

受擾航班恢復問題是指當原來的航班計劃遇到干擾(如飛機故障等因素)使得部分航班延誤甚至取消，出現(xiàn)原航班計劃不可行的情況，這就需要對原來的航班計劃進行重新排列以快速恢復飛機航線(航線是由航班組成的)，降低航空公司的損失。當航班發(fā)生延誤時，航空公司運行調(diào)度人員需要對航班計劃進行實時調(diào)整，使航班在最短時間內(nèi)恢復正常，同時還要確保公司為此支付的成本最小。其中，航班計劃是航空公司在整個航線網(wǎng)絡上對所有航班進行設計和優(yōu)化的過程，完整的航班計劃包含航線、航班(航班號、起降時刻、起降機場等信息)、班期(某航班在周期內(nèi)的哪幾天被執(zhí)行)、班次(每個航線上有多少航班)、機型(飛機型號)等信息，它是航空公司運營活動的基礎，也是航空公司整個運營計劃的核心，飛機排班、機組人員排班等都是在此基礎上展開的。因此，研究受擾航班恢復問題有著重要的現(xiàn)實意義，不僅能夠提高航空公司的運營效率，還可增強調(diào)度方案的靈活性，也為接下來機組排班計劃的研究提供科學依據(jù)。

從上個世紀六十年代開始就有關于航空公司受擾航班恢復問題的論述。Jedlinsky[1]提出了一個最小費用流模型來對該問題進行建模，建立實時信息系統(tǒng)，采用網(wǎng)絡流理論中的out-of-kilter算法對問題進行求解。Gershkoff[2]采用時空網(wǎng)絡方法求解受擾航班恢復問題，但在該研究中沒有考慮實際生活中出現(xiàn)的情況，如允許航班延誤、允許航班交換等，從而缺乏可行性。Teodorovic和Stojkovic[3]對已有的模型進行改進，將目標函數(shù)分為兩階段：在第一階段中要求最小化航班取消的總數(shù)量，在第二階段中要求最小化旅客的總延誤時間。該文是第一個提出同時考慮恢復航班時刻和飛機路線的，并且還考慮了機場宵禁約束的要求，遺憾的是文中并沒有給出具體算例的測試。Bierlaire等[4]以最小恢復成本為目標函數(shù)，采用列生成算法對該問題進行求解，但是在子問題的求解過程中，只考慮了取消航班和延誤航班，這樣就會導致大量的航班被取消或者航班延誤時間過長，因此給旅客帶來極大的不便。白鳳等[5]研究了因飛機資源短缺和機場關閉造成的航班不正常情況，不足的是該文獻沒有考慮飛機維修的情況。Bisaillon等[6]將航班恢復與乘客重新安排一起考慮，采用寬領域搜索算法，其枚舉式的搜索效率比較低，解決問題規(guī)模小。Hu等[7]是以飛機延誤成本和旅客退票重新分配成本之間費用的平衡為目標，在算法GRASP基礎上進行求解的。樂美龍等[8]以最小化乘客總延遲時間為目標，用計算機軟件進行求解。楊歡等[9]研究了基于動態(tài)環(huán)境的機場航班實時調(diào)度優(yōu)化的初級階段，采用遺傳算法求解優(yōu)化模型。陳茂林等[10]對民航調(diào)度系統(tǒng)中的空管、機場和航空公司之間復雜的協(xié)同調(diào)度問題進行研究。Sinclair等[11]對航班恢復和旅客恢復進行了綜合研究，采用啟發(fā)式算法進行求解，增加了問題的求解規(guī)模，但是在恢復措施中，航班推遲采取的是分段推遲，而不是連續(xù)推遲。Liang等[12]考慮了有維修情況的航班恢復問題。Lan等[13]和田文等[14]分別對航班延誤時間序列特性和航班延誤傳播的分析方法進行了研究，構建航班延誤時間序列并構建了基于航空演化網(wǎng)絡的延誤傳播模型。劉盼等[15]研究了航班延誤及儲備員工分配的機組分配問題。

綜上所述，現(xiàn)有研究成果為進一步研究受擾航班恢復計劃問題提供了借鑒和思路。在關于受擾航班恢復計劃問題研究方面，可以看出較少研究同時考慮了飛機資源短缺、機場關閉、計劃外的飛機維修、旅客等多因素的情況，更少有研究同時采用航班延誤(維修不允許延誤)、航班取消、航班交換等多種恢復措施。本文以航空公司原航班計劃受干擾后需要快速恢復為研究背景，基于航空公司遇到的實際情況，對飛機航線恢復問題進行分析，建立數(shù)學優(yōu)化模型，設計適用于該模型的算法，并結合實際案例進行測試，對算法求得的結果進行對比分析，為航空公司的運行決策提供有力的支持。

1 問題描述及數(shù)學建模

1.1 問題描述

每個機場有固定的開始時間和關閉時間，在機場的可利用時間段內(nèi)安排航班任務和維修任務，航空公司根據(jù)機場、飛機以及航班需求等信息制定正常的航班計劃。但是在航空公司的運營中，導致航班延誤甚至取消的原因有很多，比如飛機機械故障、機場關閉、機組人員缺乏、惡劣天氣影響等。

文中只考慮造成航班受擾的兩個主要因素：機場關閉、飛機維修(計劃外機械故障引起)，機場關閉意味著在一段時間內(nèi)，飛機不允許離開或者達到關閉的機場，然而已經(jīng)達到該機場的飛機可以在機場內(nèi)完成維修任務(如果有維修需求)，在這里我們把航班和維修都當成是飛機的任務(飛行任務和維修任務),如圖1所示。

圖1 計劃的航班或維修

在實際情況中，如果一架飛機出現(xiàn)計劃外的故障，就需要對飛機進行維修(計劃外的)。飛機維修需要在固定的機場和固定的時間段內(nèi)完成維修任務，這樣的情況本文稱為非計劃的維修任務。因為維修不是計劃內(nèi)的，飛機一旦選擇維修，就有可能出現(xiàn)原航班計劃中的飛行時間與維修時間重疊的情況，因此該架飛機在維修時間內(nèi)不能執(zhí)行任何航班任務。本文中飛機維修任務的時間窗是開集，意味著飛機一旦降落到指定的機場就可以馬上進行維修，同理維修任務一旦完成，飛機可以及時起飛離開機場。因此，如果出現(xiàn)機場關閉或者維修任務，原有的航班計劃就會出現(xiàn)沖突，比如航班原有的降落機場不能降落，飛機維修不能執(zhí)行接下來的航班任務等，造成原航班計劃不可行的情況，為了恢復航班計劃的可行性，同時降低損失，則有推遲航班、交換航班、取消航班以及取消維修四個選項。其中，推遲航班：航班實際的“起飛和到達時間”與“原航班計劃中航班的起飛時間和到達時間”不一樣。例如，圖2列出了飛機尾號為Tali 1的一個航班任務信息，即航班5183的原航班計劃的信息。在實際情況中，這個航班可能會因為上述一些原因延誤一段時間，比如，延誤30分鐘，那么航班的起飛時間就變成同一天的上午8∶05和10∶25，其他信息保持不變。全球規(guī)定的航班推遲時間閾值為180分鐘，意思就是航班5183可以在0-180分鐘內(nèi)選擇任意時間段的推遲，但是航班推遲是有懲罰的，要求推遲時間越短越好。交換航班：在原航班計劃中每個航班都有指定的飛機去執(zhí)行，即飛機尾號，如果一個航班最后被執(zhí)行的飛機尾號與原計劃航班的飛機尾號不一樣，我們就稱該航班為交換航班。航班交換是有懲罰的，要求航班交換的數(shù)目越少越好。取消航班：如果一個航班不能指派給任何一架飛機去執(zhí)行，那么就取消；取消維修：如果維修任務無法指定給原計劃的飛機，那么只能取消，這里要注意的是維修任務是不能指派給別的飛機的。取消航班或者取消維修的懲罰相對于上面其他恢復措施懲罰更嚴重，要求取消的個數(shù)越少越好。

圖2 航班信息

本文研究的受擾航班恢復問題，目標是盡快恢復受擾航班和盡量減小航班延誤時間、航班取消個數(shù)、維修取消個數(shù)以及航班交換個數(shù)，這些恢復措施有不同的懲罰系數(shù)。除了上述提到的情況，在研究飛機路線恢復問題時還要遵守以下的約束：(i)任何時候，最多只能有一個任務(航班或者維修)安排給一架飛機；(ii)每一架飛機剛開始都有一個指定的可獲得機場，那么該架飛機開始執(zhí)行任務(航班或者維修)時必須和任務的開始機場相匹配；(iii)指派給同一架飛機的任何兩個連續(xù)的任務(航班或者維修)應該“首尾”相連，也就是說，前面任務完成時的機場和后面一個相連任務開始時的機場是一樣的；(iv)對于每一個機場盡量保持機場飛機數(shù)目的平衡，例如，圖1中在最后的降落機場“DEF”上有兩架飛機，那么在接下來的飛機航線恢復問題的可行解中，當恢復問題完成時盡量保持有兩架飛機降落在機場“DEF”上，然而此約束為軟約束，如果有機場最后沒有保持這個平衡，我們會在目標函數(shù)中添加懲罰；(v)每架飛機的第一個任務(航班或者維修)的開始時間不能早于該飛機可飛行的開始時間，同理，最后一個任務(航班或者維修)的結束時間也不能晚于該飛機的結束時間；(vi)對于每架飛機所執(zhí)行的連續(xù)的兩個航班任務之間都必須滿足一個周轉時間(30分鐘)，這個周轉時間是飛機為執(zhí)行接下來的航班任務做準備，包括旅客下機、食物補給、清潔等。

1.2 數(shù)學建模

在這里我們基于飛機的航線建立一個整數(shù)規(guī)劃模型以更準確地描述問題，首先，給出模型的參數(shù)定義。

集合

P-飛機集合;R-飛機飛行路線集合;F-航班集合;A-機場集合;MT-維修任務集合

參數(shù)(下面的參數(shù)都屬于整數(shù))

機場方面的(原計劃中)：

飛機方面的(原計劃中)：

航班方面的(原計劃中)：

維修方面的：

決策變量

xpf：如果航班任務f最后指派給了飛機p去執(zhí)行則為1，否則為0，f∈F,p∈P;

ymt：如果維修任務mt在給定的機場被完成則為1，否則為0，mt∈MT;

zf：如果航班任務f屬于交換航班則為1，否則為0，f∈F;

πf：如果航班任務f被取消了則為1，否則為0，f∈F。

目標函數(shù)：

(1)

約束條件：

(2)

ymt≤1,?mt∈MT

(3)

(4)

(5)

(6)

(7)

(8)

(9)

xpf∈{0,1},?p∈P,f∈F

(10)

ymt∈{0,1},?mt∈MT

(11)

zf∈{0,1},?f∈F

(12)

該模型中，目標函數(shù)(1)最小化航班取消成本、航班交換成本、航班延誤成本、維修取消成本以及機場飛機數(shù)目不平衡成本的懲罰的總和；約束(2)要求每一個航班要么被安排到某一架飛機，要么被取消；約束(3)維修任務也是，要么被完成，要么被取消，這里要注意，維修任務不能交換也不能推遲；約束(4)要求任何一個航班的延誤時間不能大于規(guī)定的最大延誤時間；約束(5)要求任意兩個連續(xù)航班之間的周轉時間不能小于TT；約束(6)保證每架飛機所飛行航線中的第一個航班的起飛機場與該飛機的可飛行開始機場一致；約束(7)表示每架飛機所飛行航線中任意兩個連續(xù)的航班要滿足前航班的結束機場與后面一個航班的開始機場相一致；約束(8)表示原航班計劃中每個機場最后降落的飛機數(shù)目；約束(9)表示恢復航班計劃之后每個機場最后降落的飛機數(shù)目；約束(10)～(12)表示決策變量是0-1變量。

2 模型的求解算法

2.1 基于滿足不同中斷要求的啟發(fā)式序列延遲算法求解可行解

此算法的目的是針對原航班計劃遇到干擾時進行恢復，使恢復之后得到一個可行的飛機航班計劃表。在算法求解的過程中，首要目標是產(chǎn)生一個可行解，在此基礎上盡可能獲得較優(yōu)的解。啟發(fā)式序列延遲算法是基于滿足不同的中斷情況對航班進行推遲或者取消。首先，選擇一個原計劃航班中的航線，當飛機遇到維修任務或者機場關閉的情況時，篩選出受影響的航班；其次，調(diào)整這些航班使其不再受影響，對于滿足約束條件的航班給予指派，對于不滿足約束條件的航班進行取消，由于相連航班要求滿足“首尾相連”的特性，所以航班的取消會成對出現(xiàn)，當這個航線處理完之后轉入下一個航線。

2.2 構建啟發(fā)式算法的基本框架

飛機航線恢復問題是非常復雜的組合優(yōu)化問題，上面我們針對該問題建立整數(shù)規(guī)劃模型，考慮精確算法求解此問題時，需要對每一架飛機p∈P給出所有的可能路線，然而由于實際中的飛機航線恢復問題涉及的約束繁多、規(guī)模龐大，問題的搜索空間也非常大以及算法的求解過程非常耗時等，使得精確算法在實際問題求解過程中不切實際，達不到實時調(diào)整的要求。

構建啟發(fā)式算法，是兩種常用的啟發(fā)式算法之一。算法描述如下：

①根據(jù)輸入的航班信息，對同一航線的航班根據(jù)其起飛開始時間的大小做非減排序，同時，根據(jù)機場關閉信息和航班信息，找出一定被取消的航班(由于機場關閉這些航班延誤時間大于給定的最大延誤時間閾值，所以此時只能取消)；

②先選定一架飛機，然后開始選擇航班，在選擇航班中，飛機可能會遇到維修任務和機場關閉的情況，根據(jù)維修以及機場關閉的信息，航班做出相應的調(diào)整，否則取消航班，當這架飛機的航班都被安排完畢，則結束該架飛機的飛行路線，并轉向下一架飛機；

③當所有的飛機和航線都被安排完畢，則算法停止，輸出恢復后的可行航班計劃。

在實際情況中，由于飛機的維修對旅客的安全有著極其重要的影響，因此飛機的維修任務取消的懲罰成本在所有的懲罰成本中是最大的，所以本文選擇以維修任務優(yōu)先的構造啟發(fā)式算法，即當飛機起飛之后遇到維修任務的干擾且不能滿足延誤條件時，就優(yōu)先安排維修任務，刪除不能滿足延誤條件的航班。

3 實驗

3.1 案例背景以及案例數(shù)據(jù)

本文中的程序使用C++編碼，采用2GB內(nèi)存和2.8GHz英特爾雙核處理器進行測試運行。為了驗證本文所提出的構建啟發(fā)式優(yōu)化算法的有效性，本文結合S航空咨詢公司實際案例進行測試，即測試數(shù)據(jù)來源于S公司的真實數(shù)據(jù)。本文中測試了9個不同案例來反映實際中可能遇到的情景，其中，每個案例對應一種場景，每個場景的中斷情況有所不同，并且每個案例對應的恢復措施的懲罰成本也各不相同。雖然這些成本有所不同，但是在每個場景中，取消航班或者取消維修任務的懲罰成本都是最嚴重的。表2給出了每個場景中恢復措施的懲罰成本。其中，“F”與“P”分別表示航班數(shù)目與飛機數(shù)目，即“F24-P2”表示這個算例中有24個航班和2架飛機。表2中第一列是算例，后面的各列給出了不同飛機航線恢復措施的懲罰成本。另外，每個算例中航班的最大延誤時間是180分鐘(或者10800秒)、連續(xù)航班之間的最小周轉時間是30分鐘(或者1800秒)。為了清楚表示每個算例中遇到的擾亂情況，本節(jié)給出了每個算例的基本情況，如表3所示，在表3中算例 “F24-P2”遇到1個維修任務和1個機場關閉的情況、算例“F33-P10”遇到16個維修任務、算例“F43-P3”遇到1個機場關閉的情況、算例“F53-P4”遇到1個維修任務和1個機場關閉的情況、算例“F59-P16”遇到23個維修任務、算例“F95-P12”遇到1個機場關閉的情況、算例“F417-P85”遇到25個維修任務和1個機場關閉的情況、算例“F586-P44”遇到24個維修任務和1個機場關閉的情況、算例“F638-P44”遇到29個維修任務。每個算例的維修任務和機場關閉的具體情況也所不同，比如維修任務指定的飛機或者完成這個維修任務需要的時間各不相同。

表2 恢復措施的懲罰成本

表3 每個算例的基本情況

3.2 優(yōu)化方法測試結果以及與啟發(fā)式序列延遲算法的對比

本文選取的案例數(shù)據(jù)具有代表性，案例的規(guī)模大小不同，每個案例所涉及的不同受擾中斷情況也更加貼近現(xiàn)實。通過啟發(fā)式序列延遲算法和構建啟發(fā)式算法去求解這些算例，由于飛機的維修任務懲罰成本最大，航空公司實際運營中也是以維修為主，所以本文在算法構造上采用了以優(yōu)先考慮維修任務為主的策略。

關于程序運行方面，程序使用C++編碼，采用2GB內(nèi)存和2.8GHz英特爾雙核處理器進行測試運行。每個案例的測試時間都不超過5分鐘，最短的只需要0.17分鐘，因此，從時間上看，該算法完全滿足公司在時間方面時效性的要求。首先，表4給出了構建啟發(fā)式算法求解算例的結果，其中，第二列給出了目標函數(shù)值，其余各列給出了飛機航線恢復中恢復措施的采取情況。由表4第四列“取消維修數(shù)”可知，所有算例中的維修都被優(yōu)先考慮。以算例“F53-P4”為例，原航班計劃中包含53個航班、4架飛機，所有的航班和飛機信息中包含有6個不同的機場，分別用“1、2、3、4、5、6”表示六個機場，但是在原航班計劃實施前遇到了維修任務和機場關閉的情況，其中，維修任務要求第四架飛機在第2個機場進行維修，維修時間為425分鐘；機場關閉要求第2個機場在第“1336086000秒至1336100400秒”的時間段內(nèi)關閉。維修任務的時間和第四架飛機航線內(nèi)航班任務的時間有沖突，機場的關閉對這個時間段內(nèi)航班(航班起飛機場或者降落機場是關閉機場的)有影響，比如航班編號為“2457074”的航班的起飛機場是機場“2”，起飛的時間正好在機場“2”的關閉時間段內(nèi)，這就需要對原航班計劃進行航班恢復，結果顯示飛機航線恢復之后的可行計劃中取消了4個航班，有兩個機場的飛機數(shù)目沒有保持平衡，有2架飛機與原計劃飛機的位置不一樣，有20個航班進行了交換，所有的航班總共延誤了145分鐘。

表4 航班恢復情況

表5 算法分析對比

4 總結

本文研究了基于多因素不確定環(huán)境下受擾航班計劃的恢復問題，其主要任務是在考慮干擾因素的情況下盡量完成航班任務，形成可行的飛機航線，即以最小化航班取消、航班交換、航班延誤、維修取消以及機場飛機數(shù)目不平衡懲罰成本的總和為目標。結合S航空公司實際操作的案例，針對該問題建立符合航空公司實際調(diào)整規(guī)則及制度的數(shù)學模型，根據(jù)不同的策略，通過對比分析，設計有效的構建啟發(fā)式求解算法，并通過S公司實際的案例進行測試分析，分析結果顯示，構建啟發(fā)式算法比“算法1”的結果平均提高了32.47%，在求解規(guī)模上完全達到航空公司實際應用規(guī)模的受擾航班恢復問題，并且在時間上完全符合實際操作的實時性要求，本文提出了適用性較高的算法，為航空公司的運行決策提供有力的支持。

本文研究的內(nèi)容只是航空公司運營計劃中的一部分，它與機組人員排班、機型分配以及乘客安排等其他環(huán)節(jié)緊密相關，因此對于航班恢復問題還需要更加深入的研究。同時，本文研究的內(nèi)容具有一定的局限性，后期還可以進一步研究，設計出綜合的優(yōu)化方案，提升解的質(zhì)量。