航班擾動情形下的飛機路線恢復研究

魏依凝， 吳永強， 曾 實

(中國民用航空飛行學院 機場工程與運輸管理學院， 機場管理與工程研究中心， 四川 廣漢 618307)

隨著中國經濟總量持續增長，居民收入穩步增加，越來越多的旅客選擇航空方式出行。然而面對有限的資源、惡劣天氣、空中交通流量管制以及飛機停場等情況，導致無法執行原航班計劃，造成航班計劃的擾動(perturbation)。

航班計劃受擾后，若延誤航班未及時恢復，則會將延誤傳播到與其有關的所有下游航班，產生“延誤波及”現象。2016年，民航大數據研究院曾對航班延誤波及問題做了相關研究[1]，對于一天內有4次航班任務的飛機而言，當飛機執行第一航班時，起飛延誤率僅為26.06%；可到了第四航班起飛時，延誤率已達49.14%。若是國際航班產生延誤波及，甚至可能會嚴重影響中國在整個航空業的聲譽。2015—2019年，中國主要航空公司平均每年執行航班300.2萬班次，其中正常航班227.86萬班次，平均每年航班正常率為75.9%，與“十三五”時期民航發展預期的“80%航班正常率”[2]有一定距離。當航班計劃發生擾動時，以中國一架延誤的空客333飛機為例，其延誤費用可達到10萬以上。因此快速獲取有效的航班計劃恢復方案，減少航空公司損失十分重要，并且飛機是航空公司的寶貴資源，飛機路線的恢復尤為關鍵。

國內外學者針對恢復飛機路線的問題進行了相關研究。Yan等[3]提出了一個基本調度擾動模型(basic schedule perturbation model，BSPM)，使用拉格朗日松弛法和次梯度法求解；Yan等[4]拓展其研究，將BSPM模型擴展為基本的多機型調度擾動模型，以同樣的算法求解，運用案例驗證了模型的可行性。Bard等[5]利用節點和弧為每架飛機構建了時空網絡，并在此基礎上提出了以航班延遲和航班取消成本之和最小為目標函數的數學模型，解決了單機型的飛機恢復問題；Thengvall等[6]提出了3個多商品網絡流模型解決飛機恢復問題，并分別比較3種模型解的質量和計算時間，得出第一種模型給出的飛機恢復方案較為出色；Nickkar等[7]針對航班擾動恢復，提出了一種基于非線性規劃的多目標優化模型，采用了Dantzig-Wolfe分解算法求解，模型可解決大規模航班恢復問題；Zhang[8]提出了用兩階段啟發式算法來降低航班恢復問題的規模，設計了飛機恢復模型；趙秀麗等[9]建立了以延遲成本或延遲時間最小為目標函數的航班恢復模型，能在較短CPU時間內給出恢復方案；白鳳等[10]建立了以航班延遲成本和取消成本之和最小為目標函數的多商品網絡流數學模型，使用列生成算法求解，算例驗證了模型的正確性；朱星輝等[11]將機型指派和飛機路線一體考慮，提出了多機型的一體化飛機排班多商品網絡流模型，用一種基于約束編程的動態列生成算法求解此模型，實驗結果證明了模型和算法的有效性；張力菠等[12]在航班延遲和航班取消這兩種基本策略上加入擺渡飛機策略并建立了以恢復成本最小為目標函數的數學模型，實例驗證了模型的有效性。樂美龍等[13]改進了時空網絡，提出了多機型不正常航班恢復模型，算例表明多機型航班恢復模型給出的方案優于單機型航班恢復的方案。

綜合來看，飛機路線恢復問題的文獻成果較為充足，特別是單機型的航班擾動恢復的研究較為豐富，但多機型的航班擾動恢復的研究較少；且在考慮恢復策略方面，大多數只考慮了延遲航班和取消航班兩種策略，同時考慮延遲航班、取消航班、替換飛機和擺渡閑置飛機的情況較少。因此，基于已有文獻，本文將在機場臨時關閉和飛機停場的情況下，同時考慮以上4種策略，改進經典的離散時空網絡，并以此建立多機型飛機路線恢復模型，用算例驗證模型的可行性。

1 航班擾動情形分析

在現實生活中，經常會碰見沙塵暴、大雪和臺風等極端天氣，導致能見度驟降、跑道摩擦系數不夠起降標準，迫使機場關閉；此外，機場活動區有異物、軍事演練和空中交通流量控制等人為因素同樣也會使機場關閉，只能延遲或取消受影響的航班。對有執行計劃航班的飛機來說，出發機場關閉和到達機場關閉是不同的兩種情況，所以本文將分別討論這兩種情況。

除了機場臨時關閉這種情形，若是機務故障或其他意外事故造成某飛機臨時喪失適航性造成飛機資源不足，不能執行原計劃飛行任務的情形稱為飛機停場(grounding)[14]。顯然，飛機停場也會引起航班計劃的擾動，這是需要考慮的第二種情形。

1.1 機場臨時關閉

如圖1所示，現分別假設兩種情況，情況1：由于臺風的影響，SHA、SZX這兩個出發機場需在12：30—15:00臨時關閉，在此期間起飛的航班需要在15:00之后機場再次開啟才能繼續執行；情況2：由于受大雪影響，PEK機場需在15:00—18:00臨時關閉，則在此期間到達PEK機場的航班需要在18:00之后才能降落。

圖1(a)為情況1的簡化時空網絡圖，節點1和節點2分別代表航班1的出發機場和到達機場以及各自的出發、到達時間，連接兩點形成的實線為航班1的原計劃路線12，路線34即是航班2的原計劃路線，由于機場在15:00之后才開啟，航班的出發時間需延后至節點1′和節點3′所在的15:00，航班1和航班2延后的到達時間節點分別為節點2′和節點4′，兩航班的新路線由圖中虛線所示，分別為1′2′和3′4′，圖中的t1和t2分別為航班1和航班2的延遲時間，可計算各自航班延遲成本Delaycostf(t)，f為航班號，t為延遲時間。為使網絡更簡單，減少建模的難度和求解時間，以航班1為例，在航班延遲后，不生成節點1′，而連接節點1和節點2′，形成的新路線12′由點劃線所示，在12′中計算航班1的延遲成本。

圖1(b)所示是情況2的簡化時空網絡圖，由于PEK機場再次開啟時間為18:00，所以航班1和航班2需要各自延遲t3和t4時間，到圖中的節點4′處，路線12和路線34代表原計劃航班路線，路線1′4′和路線3′4′代表延遲后航班執行路線，同樣不生成節點1′和節點3′，在路線14′和路線34′中計算各自航班的延遲成本Delaycostf(t)。

圖1 出發機場臨時關閉和到達機場臨時關閉

1.2 飛機停場

如圖2所示，現假設A320型飛機1臨時出現故障，當天無法修復，面對此種情形，有3種處理方法，一是取消航班3，二是選擇擺渡其他機場剛好閑置的A320型飛機到所需機場，三是選擇同機場的A321型飛機進行飛機替換，但需注意為了使替換飛機能有執行航班的可能性，A321型飛機執行航班時間不得晚于A320型飛機執行航班時間。

圖2的左圖和右圖分別是A320型飛機1和A321型飛機1的簡化時空網絡圖，由于A320發生故障且在當天無法恢復，PEK機場有一架閑置的A320型飛機在節點0處，可供航班3使用，航班邊-3和航班邊-4分別表示航班3和航班4，連接節點0和節點1形成擺渡邊-3，擺渡A320型飛機的費用可在擺渡邊中計算Ferrycostp(t)得到，p為擺渡飛機，t為擺渡飛機到所需機場的時間。除了擺渡飛機執行航班3以外，還可以采用飛機替換策略，利用同在SZX機場的A321型飛機1來執行航班3，連接節點1和節點3形成替換邊-3，替換飛機A321的費用可在替換邊中計算Substitutioncostf(u)得到，f為航班號，u為乘客人數。若A321型飛機1去執行了航班3，無法準時執行航班4，擺渡飛機、替換飛機的處理方法同航班3。

圖2 A320(左)和A321(右)雙機型簡化時空網絡圖

2 離散時空網絡的構建

經典離散時空網絡由節點和有向邊構成，用二維坐標系呈現，能夠很好地描述飛機在時間和空間位置上的變化。其中，橫坐標用離散的點標注機場代碼來代表各個機場，縱坐標代表時間，縱坐標的起點和終點分別代表受擾航班進行恢復的開始時間和受擾航班恢復的結束時間，若將時間離散化，則可得到若干個時間節點，這樣的節點可顯示具體的時間和空間位置。時空網絡中有3類節點：源節點、機場時間節點和沉沒節點；3類有向邊：航班邊、復制邊和沉沒邊；為避免網絡復雜后不方便查閱，一般省去各類邊的箭頭。以上3類節點和3類有向邊可較好地描述延遲航班、取消航班策略，但若是要考慮擺渡飛機和替換飛機策略，運用經典的離散時空網絡是無法體現的，需增加擺渡邊和替換邊。

首先分析實際情況，獲取受擾航班的恢復時期，可用飛機資源情況，包含閑置飛機所在機場和可用時間，根據原始航班計劃，確定離散時間區間大小，建立可用飛機的機場時間節點，閑置飛機從所在機場擺渡至其他機場所形成的邊為擺渡邊，對有可能達到的機場形成新的可用機場時間節點，然后在機場時間節點基礎上生成航班邊、復制邊、沉沒邊，最后將每個機場的孤立節點融合為一個節點，形成各機場的沉沒節點，輸出最終單機型離散時空網絡。若是有多余的機型資源可供進行飛機替換策略，注意這樣替換是發生在同一個機場內的，先依照同樣的方法生成替換飛機的離散時空網絡，然后將替換機型的各機場時間節點與被替換機型的各機場時間節點用替換邊依次連接，且被替換機型的各機場時間節點的時間要相同或較晚于替換機型的各機場時間節點的時間，這樣才能發生替換，產生替換邊，形成多機型離散時空網絡。改進后的簡化離散時空網絡可詳見圖3。

圖3 改進后的雙機型離散時空網絡

3 數學模型

文獻[12]在建立不正常航班調度模型時，只考慮了單機型的延遲航班、取消航班和擺渡飛機，沒有考慮多機型的替換；而文獻[13]雖考慮了多機型的替換，但忽略了擺渡飛機這個策略，并且也沒有考慮到機場關閉這種情形。所以基于以上兩篇文獻模型的優缺點以及第2節中改進后的雙機型離散時空網絡圖，定義以下索引、集合、參數和變量。

1)索引：i、j為節點索引；p為擺渡飛機索引；r為飛機替換邊索引；k為航班索引；b為擺渡邊索引；q為沉沒邊索引；f為航班邊索引；e為機型索引。

2)集合：T為機場時間節點集合；G為機場沉沒節點集合；F為航班集合；A為航班邊集合；Q為沉沒邊集合；A(k)為航班k的航班邊集合；P為擺渡飛機集合；B為擺渡邊集合；E為機型集合；R為飛機替換邊集合；B(p)為飛機p的擺渡邊集合；C(i)為節點i的擺渡邊集合；S(i,e)為機型e執行的從點i出發的航班邊集合；U(i,e)為機型e執行的終點為i的航班邊集合。

5)目標函數：

(1)

6)約束條件：

(2)

(3)

(4)

(5)

(6)

(7)

(8)

4 飛機路線生成算法

求解上述模型后，可得到最優執行的替換邊、擺渡邊和航班邊集合，通過替換邊可知飛機發生了替換；通過擺渡邊，可知將閑置飛機擺渡至哪一個機場可使成本最優，但對于航班邊，只能得到優于執行的航班，卻不知這些航班由哪一架飛機執飛。因此對于求解后的航班邊集合，需進行飛機指派，算法在文獻[15]基礎上進行改進，增加飛機替換策略，解決飛機指派問題，生成飛機路線。

算法1 飛機路線的生成

input:O={根據模型求解出來的最優執行的航班邊集合}、R={根據模型求解出來的最優執行的替換邊集合}、A={可用飛機(包含閑置飛機)}

output:Z={可用飛機和它們所執行的航班}

begin

for each在A中的飛機a do

begin

創建一個元素n，以飛機a的尾號、可用時間、當前所在機場來標記元素n，將元素n放入Z中

end

非降序排列Z中的飛機可用時間

非降序排列O中的航班標記的出發時間和原計劃出發時間

while當O不為空 do

begin

從O中移出第一個元素o

if 元素o所代表的航班邊的時間節點上沒有最優執行的替換邊rthen

從Z中搜尋位于航班o出發機場的第一架可用飛機n，將n指派給o

else 飛機n根據替換邊r指派給o

更新飛機n的可用時間和當前機場，將Z再次排序

end

end

5 算例分析

表1來自于北京某航空公司空客A321-200型飛機和空客A320-200型飛機的部分航班計劃，也是本文的算例數據，涉及8架飛機、32個航班和4個機場(深圳寶安國際機場、上海虹橋國際機場、北京首都國際機場和成都雙流國際機場)，各個航班的取消成本由Cf=mfwfsf計算而來，其中Cf為航班f的取消成本；mf為航班f最大載客人數；wf為航班f的平均票價水平；sf為航班f的客座率。

表1 321-200和A320-200的原航班計劃

現在原航班計劃執行前，發生以下航班擾動情形：受臺風影響，SHA機場將在17:30-20:00關閉，則受影響的有到達SHA機場的航班11和從SHA機場出發的航班12，A321-200中的飛機2和飛機4以及A320-200中的飛機3臨時出現故障，且當天都不可用， SZX機場有一架閑置的A321-200飛機可供擺渡到SHA機場、PEK機場、CTU機場，飛機的擺渡信息見表2，同時這兩機型飛機可發生飛機替換，飛機替換成本包含發生替換的機場產生的設備及人工成本和替換后飛機空間大小的改變引起乘客的心理反感成本，但這項成本只會發生在大機型被替換為小機型的情況下計算，反之則不用計算這一成本。這里引用文獻[13]采用的1 000元/人和50元/人進行計算，航班延遲成本以197元/min[16]計算。

表2 A321-200的擺渡信息

A320機型、A321機型在第一類機場的最少過站時間為60 min，取30 min為離散時間的間隔，以第2節的方法建立考慮了以上策略后的A321-200和A320-200的雙機型離散時空網絡，具體可見圖4。節點0處有一架閑置在SZX機場的A321-200飛機，虛線代表擺渡邊，共3條；點劃線代表替換邊，共173條。為避免時空網絡圖過于復雜，影響讀者閱讀，只在圖中畫出了34條替換邊，省略139條替換邊。

基于圖4，使用CPLEX優化軟件求解模型，表3為考慮航班延遲、取消、擺渡飛機和飛機替換這4種恢復策略的結果，飛機擺渡至SHA機場，A320-200型飛機2替換A321-200型飛機4執飛航班14和航班15，共取消航班8個航班，延遲6個航班，總恢復成本為1 435 409元。

表3 A321-200和A320-200的航班計劃恢復表

圖4 A321-200和A320-200的雙機型離散時空網絡

以上的飛機路線恢復同時考慮了①取消航班、②延遲航班、③擺渡飛機、④替換飛機4種策略，但也可能出現沒有閑置飛機可供擺渡以及機型不能發生替換的情況，所以總體來說有4種恢復方案，方案1為直接取消受影響航班；方案2考慮取消和延遲受影響的航班；方案3在方案2的基礎上加入擺渡飛機策略；方案4是綜合考慮取消航班、延遲航班、擺渡飛機和替換飛機4種策略，表4展示了4種恢復策略選取組合后的方案結果比較。

表4 4種恢復方案的比較

對比以上4個恢復方案的飛機路線恢復成本，同時考慮延遲航班、取消航班、擺渡飛機和替換飛機的方案4為最優恢復方案，與方案1、方案2、方案3相比分別減少了782 279元、736 063元、35 314元，結果優化分別達到35.27%、33.90%、2.40%。

6 結語

主要針對在機場臨時關閉和飛機停場兩種航班受擾情形下，考慮同時采取延遲航班、取消航班、擺渡閑置飛機和飛機替換策略，在經典離散時空網絡的基礎上增加擺渡邊和替換邊表達以上4種策略，以此建立了受擾航班飛機路線恢復成本最小模型。運用算例數據，使用CPLEX優化軟件進行求解，給出了較優的航班恢復計劃。對比了4種恢復方案的結果表明，同時采取4種策略進行飛機路線恢復為最優方案，驗證了模型的可行性。但是，本文沒有考慮機場時刻容量的約束，且飛機恢復結束時間截至當日，在飛機恢復后，未對后續機組人員和乘客的恢復進行考慮，在未來，這些也是本文需更深一步研究的方向。