彭連鎖，王梓旭，王興隆

（1.中國國際航空股份有限公司，北京 100621；2.北京大興國際機場，北京 102604；3.中國民航大學空中交通管理學院，天津 300300）

航空公司大面積受擾航班恢復包括分階段恢復與一體化恢復。分階段恢復是將整個恢復問題分為飛機恢復、機組恢復、旅客恢復3 個階段逐步求解；一體化恢復則是綜合考慮飛機、機組、旅客因素進行求解。兩者相比，一體化恢復模型復雜度高、結(jié)果更準確。

Lettovsky[1]于1997年提出一體化恢復方案，包括機組人員、飛機、旅客流的一體化恢復，開辟了一體化恢復的先河。樂美龍等[2]綜合考慮飛機、航班、機組和機場的動態(tài)時空銜接，建立了飛機和機組的優(yōu)化恢復模型，并設計了一種GRASP 算法求解。朱博等[3]分析了飛機和機組運行計劃的異同，建立了飛機和機組一體化恢復的約束規(guī)劃模型，利用混合集合規(guī)劃設計搜索算法求解。Bisaillon 等[4]設計大型鄰域搜索方法求解飛機與旅客一體化恢復問題。Sinclair 等[5]認為在未來的研究應考慮解決較大實例的方案，例如將列生成算法嵌入滾動時間窗中，解決擾動次數(shù)更多的情況。Teodorovic 等[6-9]在先后使用分支定界、動態(tài)規(guī)劃、啟發(fā)式算法對旅客恢復和機組恢復問題進行了求解。吳剛等[10]提出一種改進列生成算法，每次迭代過程中加入多個列，并對加入的多個列需滿足的條件進行了分析，算例驗證了該方法的正確性和有效性。田倩楠等[11]改進了時空網(wǎng)絡算法，給出占優(yōu)準則，有效減少了可恢復航線的組合數(shù)量，提升了計算效率。

已有文獻多采用時空網(wǎng)絡進行建模，需考慮航班邊、機場節(jié)點和時間節(jié)點，一體化模型過于復雜。Hanif等[12]系統(tǒng)介紹了航班網(wǎng)絡的使用，所用算法相比時空網(wǎng)絡模型復雜度低，但不能表現(xiàn)飛機維修約束、機組執(zhí)勤時間約束、客票取消等時間和地點屬性。Akturk等[13]在飛機恢復問題中首次使用巡航速度控制，并分析了該思路的優(yōu)勢。Ugur 等[14]基于此研究進一步將旅客行程加入模型，但均未達到真正的一體化恢復。

采用改進的航班網(wǎng)絡進行問題建模，能夠降低復雜度，并可避免航班網(wǎng)絡不易表達飛機維修約束、機組執(zhí)勤時間約束等屬性類約束的缺陷[15]。

1 航班網(wǎng)絡改進與算法設計

1.1 航班網(wǎng)絡的改進

傳統(tǒng)航班網(wǎng)絡中包括3 類節(jié)點、3 類弧，改進航班網(wǎng)絡中有4 類節(jié)點、5 類弧，新加入必經(jīng)節(jié)點、必經(jīng)弧和添加弧，如圖1所示。

圖1 改進后的航班網(wǎng)絡Fig.1 Improved flight network

源節(jié)點（sr）表示飛機、機組或旅客的初始狀態(tài)點，有時間、地點屬性；

末節(jié)點（tr）表示飛機、機組或旅客的中止狀態(tài)的點，有時間、地點屬性；

航班節(jié)點表示飛機、機組執(zhí)行的航班或旅客在其行程中要乘坐的航班；

必經(jīng)節(jié)點（mr）表示飛機在特定時段在特定機場維修的節(jié)點，或機組規(guī)定在特定機場休息；

出發(fā)弧連接源節(jié)點與航班節(jié)點的弧，表示飛機、機組、旅客執(zhí)行首個航班；

沉沒弧連接航班節(jié)點與末節(jié)點的弧，表示飛機、機組、旅客執(zhí)行完最后1 個航班；

航班弧航班節(jié)點之間的弧，表示飛機、機組、旅客執(zhí)行完上游航班后執(zhí)行下游航班；

必經(jīng)弧連接航班節(jié)點與必經(jīng)節(jié)點之間的弧，表示飛機維修、機組休息等；

添加弧表示航班恢復的特殊操作，如加機組、調(diào)機操作，乘客客票取消操作。

1.2 航班網(wǎng)絡的算法設計

一體化恢復包含飛機、機組、旅客3 種子網(wǎng)絡，用r 表示。算法參數(shù)及含義如表1所示。

表1 算法參數(shù)及含義Tab.1 Algorithm parameter and meaning

航班網(wǎng)絡生成算法由Generatesubnetwork（r），Generatepath（Ntemp），Insert（Ntemp）3 部分組成。具體步驟如下：

Step 1初始化節(jié)點集合Nr，弧集合Vr，Ntemp=sr；

Step 2Generatesubnetwork（r），航班網(wǎng)絡生成主程序；

Step 3Generatepath（Ntemp），基于廣度優(yōu)先搜索可銜接航班，即航班網(wǎng)絡路徑中的節(jié)點；

Step 4Insert（Ntemp），得到航班網(wǎng)絡中的所有弧與節(jié)點；

Step 5對Vr 進行分類得到出發(fā)弧、沉沒弧、航班弧、必經(jīng)弧、添加??；對Nr 進行分類得到初始節(jié)點、航班節(jié)點、沉沒節(jié)點；

Step 6如果是機組子網(wǎng)絡，額外刪除不滿足機組執(zhí)勤時間和飛行時間的弧與節(jié)點。

2 航班擾動一體化恢復模型

2.1 集合

F：航班集合，F(xiàn) = {f|f1，f2，…}，f 為任意1 個航班，|F|為航班總量；

R：飛機路徑集合，R ={r|r1，r2，…}，r 為任意1個飛機路徑，|R|為路徑總數(shù)量；

A：飛機集合，A={a|a1，a2，…}，a 為任意1 架飛機，|A|為飛機總數(shù)量；

K：機組配對集合，K={k|k1，k2，…}，k 為任意機組配對，|K|為機組配對總數(shù)量；

C：機組集合，C={c|c1，c2，…}，c 為任意機組，|C|為機組配對總數(shù)量；

Q：旅客行程路徑集合，Q={q|q1，q2，…}，q 為任意旅客行程路徑，|Q|為路徑總數(shù)量；

P：旅客行程集合，P={p|p1，p2，…}，p 為任意旅客行程，|P|為旅客行程總數(shù)量；

FC：聯(lián)程航班對集合{f1，f2，f3}，f1、f2代表聯(lián)程航班，f3表示聯(lián)程航班拉直。

2.2 參數(shù)

參數(shù)及含義如表2所示。

表2 參數(shù)及含義Tab.2 Parameter and meaning

2.3 變量

模型將成本分解為航班延誤運營成本、航班取消成本、旅客延誤成本、旅客客票取消成本和機組空閑成本5 部分。中國民用航空局《航班延誤經(jīng)濟補償指導意見》規(guī)定，延誤8 h 以上給出的賠償標準接近于取消航班的賠償，故令航班取消成本為航班延誤8 h的運營成本；航班取消還導致旅客客票取消，這部分成本算為客票取消成本；模型中規(guī)定航班最多延誤8 h，目標函數(shù)如式（1）～式（2）所示。

其中，epp為旅客行程p 分配給路徑q 的人數(shù)比例。

在3 種航班網(wǎng)絡中，飛機、機組兩種網(wǎng)絡需滿足航班如果被執(zhí)行則必然有飛機、機組執(zhí)行該航班，否則航班被取消，稱作航班覆蓋約束，即

飛機與機組網(wǎng)絡，從源節(jié)點到末節(jié)點只能執(zhí)行1條路徑，稱作流平衡約束，如約束（5）與約束（6）。而旅客行程網(wǎng)絡沒有此約束，旅客行程可以將旅客分配到任一或多個旅客行程路徑，或者取消行程，但是其人數(shù)和應等于該旅客行程人數(shù)，如約束（7）。一個航班如果被執(zhí)行，則航班上被分配的各種行程的旅客人數(shù)之和不能大于執(zhí)行該航班飛機的座位數(shù)，即

其中，cpp為旅客行程p 取消旅客人數(shù)比例。

將旅客分為普通旅客、中轉(zhuǎn)旅客和聯(lián)程旅客。令中轉(zhuǎn)旅客最多中轉(zhuǎn)1 次。圖2為聯(lián)程旅客在航班網(wǎng)絡中的表示。

圖2 聯(lián)程航班在航班網(wǎng)絡中的表示Fig.2 Connecting flights represented in flight network

聯(lián)程航班如果兩段都不取消，則兩段必須使用同1 架飛機，并且繼續(xù)聯(lián)程；模型規(guī)定只有當中間機場出現(xiàn)問題時才可以進行聯(lián)程拉直，否則兩段飛行都被取消，即

飛機與機組的每1 個路徑中的航班為滿足限制條件都有不同的出發(fā)和到達時間，應滿足機組最早可用時間比飛機的最早可用時間早，保證飛機可以起飛時一定有機組可以執(zhí)飛，即

約束（11）表示取消行程旅客數(shù)為整數(shù)。約束（12）和（13）表示旅客行程p 分配給行程路徑q 的旅客人數(shù)或取消人數(shù)比例小于1，約束（14）和約束（15）為變量的取值約束，即

3 DW 分解子問題設計

Dantzig-Wolfe（DW）分解算法是求解特定結(jié)構、不能使用標準單純形法進行求解的大規(guī)模線性規(guī)劃問題。由于該方法具有運行時間快、運算求解速率高等優(yōu)點，故嘗試運用該算法對模型進行求解。以順延航班計劃作為初始解構造增廣約束矩陣，以路徑變量表示的模型作為主問題，λi（i=1，2，…，8）分別對應約束（3）～約束（10）的對偶變量值。構建子問題的目的是不斷發(fā)現(xiàn)簡約成本為負的路線，子問題可分為飛機子問題、機組子問題、旅客子問題。算法參數(shù)及含義如表3所示。

表3 DW 算法參數(shù)及含義Tab.3 Parameters and meanings of DW algorithm

子問題可表示為

子問題求解過程是一個單源最短路問題。由于飛機、機組、旅客的航班網(wǎng)絡結(jié)構稀疏，長度短，采用SPFA 算法求解子問題的最短路徑，同時對路徑包含的最多節(jié)點數(shù)進行限制，1 架飛機1 天最多執(zhí)行的航班數(shù)設為6；1 個機組每天最多執(zhí)行航班數(shù)設為4。模型求解流程如下：

Step 1根據(jù)順延航班計劃給出初始解構造主問題；

Step 2求解步驟1 得到的主問題，并返回約束的對偶變量λi（i=1，2，…，8）；

Step 3使用對偶變量分別修改飛機、機組、旅客子問題中的邊的權值；

Step 4分別求解每個子問題當前邊權值下的最小成本路徑，將子問題的解以路徑變量代入主問題求解其影子價格；

Step 5選擇簡約成本最小的路徑，判斷是否為負，若為負則加入主問題中繼續(xù)求解，回到Step 3；否則問題已達到最優(yōu)解。

其中，求解子問題最短路徑SPFA 算法流程如下：

Step 1將子模型航班網(wǎng)絡圖中源節(jié)點sr 與每個節(jié)點f 之間的距離儲存在路由表d（f），備用節(jié)點儲存在先進先出隊列Q 中，w（f，g）表示邊（f，g）的權值；

Step 2遍歷圖中每個節(jié)點f，如果f≠sr，d（f）=∞；否則d（f）=0；

Step 3Q=Q∪sr；

Step 4如果Q 不是空集，刪除其中第1 個節(jié)點f；

Step 5遍歷所有從f 出發(fā)的邊，如果d（f）+w（f，g）

Step 6轉(zhuǎn)到Step 3，直到Q 為空。

4 算例分析

采用某航空公司一天的運營數(shù)據(jù)，構建兩類共8個算例進行計算分析。包括機場關閉、飛機故障兩種運營中最常見的場景，算例信息如表4所示。規(guī)定航班最長延誤時間為8 h；機組最長執(zhí)勤時間為14 h，最長飛行時間為8 h；航班之間最短銜接時間為40 min；航班單位運營延誤成本按機型尾流強度分為，重型機4 167 元/h，中型機2 916 元/h，輕型機208 元/h，算例中包含中型機24 架，重型機2 架；旅客單位延誤經(jīng)濟損失，國內(nèi)旅客50 元/h，國際旅客100 元/h；機組空閑成本以50 元/min 計算。

表4 場景算例信息Tab.4 Scenario computational instance information

求解結(jié)果如表5所示，場景1 中4 個算例編號分別為1～4，場景2 中4 個算例編號分別為5～8。

表5 求解結(jié)果Tab.5 Solution results

隨著機場關閉時間和飛機不可用時間變長，恢復成本隨之增長，由于時刻表的靈活性，當擾動在一定范圍時，可以做出相應調(diào)整使航班不被取消，當時間較長時依然會出現(xiàn)航班取消。從模型來看，出現(xiàn)航班取消的時間閾值取決于航空公司所能接受的航班最長延誤時間，最長延誤時間不同構造出的航班網(wǎng)絡不同，如本算例設置為8 h，在航空公司實際應用中可以自行設置模型中的航班最大延誤時間，使恢復效果更好。

機場關閉場景的旅客延誤分布如圖3所示，當機場關閉時間變長時，旅客的延誤時間會變長。算例3比算例2 旅客延誤分布所在時間段變小，這是由于航班的取消使飛機執(zhí)行更少的航班，有更大的靈活性保證沒有被取消的航班延誤程度更小，但是在恢復成本上是不利的。圖4顯示前4 個算例的成本分布，算例1與算例2 中的客票取消成本顯示，一體化恢復模型在不必要取消航班時盡量減少客票取消成本。算例1 ～算例2 的延誤損失所占比重大，算例3 ～算例4 中客票取消成本達到近50%，這是由于航班取消導致旅客行程的可行路徑減少，取消人數(shù)增多。

圖4 成本分布Fig.4 Cost distribution

圖5～圖6對恢復結(jié)果中受干擾機場的延誤人數(shù)與累計延誤時間進行統(tǒng)計。算例中設置浦東機場關閉，所采用的航班時刻表中受到影響的航班，其出發(fā)機場與目的機場都是武漢或浦東機場，而恢復結(jié)果中受影響機場不限于武漢與浦東機場。模型求解中的初始解是順延方案，不涉及其他機場，一體化恢復模型求解后將兩個機場導致的延誤分攤到其他機場，降低總成本。

圖5 各機場延誤人數(shù)Fig.5 Delay-passenger number of each airport

圖6 各機場累計延誤時間Fig.6 Cumulative delay of each airport

飛機故障場景算例旅客延誤分布與成本分布如圖7～圖8所示。飛機故障6 h 與8 h 總成本變化一樣，這是因為出現(xiàn)取消航班操作后，被取消航班的后續(xù)航班的起飛時間大于故障飛機的最早可用時間。當故障時間變?yōu)?0 h，總成本會變成301 095 元?？推比∠杀九c旅客延誤損失仍然是主要部分，算例7 與算例8 故障時間較長，但航班取消后，其他航班延誤時間比算例6 有所減緩。

圖8 成本分布Fig.8 Cost distribution

5 結(jié)語

以航班恢復成本為目標函數(shù)，摒棄以往分階段恢復的問題分析方法，綜合考慮飛機、機組、旅客建立一體化恢復模型。模型易于理解、算法易實現(xiàn)，擾動場景模擬表明，該模型可在短時間內(nèi)獲得調(diào)整方案，并通過機場延誤人數(shù)、機場累計延誤時間、旅客延誤分布、恢復成本分布4 個指標說明恢復效果，對航班延誤恢復問題具有實際意義。