基于延誤分級的航班過站松弛時間優化研究＊

朱星輝 戚彥龍 吳薇薇 高 強

（南京航空航天大學民航學院 南京 210016）

0 引 言

航班延誤問題，Rexing等［1－3］運用設置時間窗的方法，優化了航班離港時刻，為航班延誤調整提供了一定的靈活性．Paul［4］等把影響航班銜接和延誤波及因素分為可控因素和隨機因素，指出針對不同機場、不同飛機應有不同的航班地面操作緩沖時間以及空中飛行緩沖時間，用以補償隨機變化因素帶來的時間損失．Shervin等［5］考慮了飛機和飛行機組兩個因素在延誤樹中的影響，提出了利用調整松弛時間來減少延誤的傳播，不過沒有給出調整松弛時間的具體方法．Shervin等［6］指出延誤向下游航班的傳播加劇了延誤的發生和影響程度，并且通過對計劃過程中的松弛時間進行重新分配，不改變原來飛機路線和機組計劃的決策，最小程度地修改航班計劃，來減少延誤波及的影響．曹衛東等［7］利用貝葉斯推理建立了單機場和多機場過站時間貝葉斯模型，分析了前航延誤時間和機型類型對航班過站時間調整的影響，以及發生首發延誤時多機場間過站時間調整量的相互影響和對末航班到達延誤的影響，認為發生前航延誤時調整航班的機場過站時間可以有效減少延誤向下游機場的波及．牟德一等［8］提出了基于延誤概率的魯棒性飛機排班問題，但只考慮單機型情況，而且沒有限制飛機架次，計算結果飛機利用率明顯偏低．鄭曉洋［9］從航班取消可行性、取消原則、取消策略的選擇三個方面對航班取消策略進行了探討，并提出基于延誤波及的航班取消延誤成本模型，對航班延誤波及時的航班取消策略選擇具有一定的指導意義．丁建立等［10］在基于免疫進化算法的基礎上對過站時間進行了優化，但其對離港時間調整區間采用了統一閾值．以上文獻從飛機路線、機組排班以及一體化模型等不同角度對航班銜接的過站松弛時間進行了定性和定量方面的研究．不過對過站時間的調整沒有針對性的考慮每個航班的延誤程度．本文基于每個航班延誤風險分級，在原有飛機路線和機組任務不變情況下調整過站松弛時間，使延誤波及范圍減小，提高航班正點率及旅客的滿意度；即根據每個航班的延誤級別，設置相應的過站松弛時間調整區間，使調整更具有針對性．

1 航班延誤波及和過站松弛時間研究

1．1 航班延誤波及分析

航空公司為了優化資源利用，保障飛機平均日利用率，在航班計劃中往往安排1架飛機在1d連續執行多次航班．這些航班組成了一個航班聯線，相鄰的連續航班之間有一定的過站時間，包括地面服務時間和松弛時間．由于航班之間存在時間銜接關系，當上游航班由于某種原因產生延誤，在空中飛行時間不變的情況下，則延誤必然會波及到下游航班．上游航班延誤時，調整下游航班的過站時間可以有效的減少延誤的傳播．因此在實際操作中航空公司常通過調整飛機的過站時間來減小延誤的波及，圖1為連續航班i，j的離港、到達和延誤圖．其中Slack為過站松弛時間；PCT為計劃過站時間；MCT為最小過站時間；PDT為計劃離港時間；ADT為實際離港時間；PAT為計劃到達時間；AAT為實際到達時間；PD為波及延誤；IDD為獨立離港延誤；IAD為獨立抵達延誤；TDD為總的離港延誤；TAD為總的抵達延誤．且存在以下數量關系PCTij＝PDTj－PATi；Slackij＝PCTij－MCT；PDij＝Max（TADi－Slackij，0）．

圖1 連續航班i，j的離港、到達和延誤圖

1．2 基于航班延誤風險分級的過站松弛時間優化模型

為進行航班過站松弛時間優化調整，做如下基本假設（或建模基礎）．

1）保持原機組和飛機路線、航班聯線不變．

2）保持原航班聯線中總過站時間不變（航班時刻調整時，不出現紅眼航班）．

3）航班時刻（時隙資源）不能大幅度修改，不影響航班市場需求．

4）航班輪檔時間不變．

根據文獻［11］，航班延誤風險分為5個等級，即正常延誤，輕度延誤，中度延誤，重度延誤和超長延誤．設G表示航班延誤風險分級集合，有g∈G．模型涉及到的其他參數及變量如下：F為航班集合；Tg為航班延誤風險級別g對應的過站松弛時間調整閥值，相應調整區間為［0，Tg］；Tig為航班i（i∈F）延誤風險級別為g對應的過站松弛時間調整區間，其中Tig∈Tg；A為銜接航班的集合（如i－j）；S為航班聯線的集合，s∈S（通常指1架飛機執行的一個航班任務串）；As為航班聯線s中航班銜接的集合；W 為始發航班延誤時間集合，w∈W；Fo為所有航班聯線集合S中首航班的航班集合；Fl為所有航班聯線集合S中末航班的航班集合；pws為航班聯線s中，始發航班離港延誤w分鐘發生的概率，s∈S，w∈W；PATi為原計劃中，航班i的計劃到達時刻，i∈F；PDij為原計劃中，從航班i到后續航班j的波及延誤，（i，j）∈As，s∈S；PDwij為原計劃中，給出w 后，從航班i到后續航班j的波及延誤，（i，j）∈As，s∈S，w∈W；TADwi為原計劃中，給出w后，航班i的抵達延誤，i∈F，w∈W；IADwi為原計劃中，給出w后，航班i的獨立抵達延誤，i∈F，w∈W；Slackij為原計劃中，航班銜接（i，j）的松弛時間，（i，j）∈As，s∈S；pdwij為新計劃中，給出 w 后，從航班i到后續航班j的波及延誤，（i，j）∈As，s∈S；iadwi為新計劃中，給出w后，航班i的獨立抵達延誤；Slack′ij為調整過站時間后航班銜接（i，j）的松弛時間；tadwi為給出了延誤w 以后，航班i的抵達延誤；xi為航班i的離港時間變化量，按民航局規定，國內航班離港時刻不能提前，因此xi只能大于等于0，即i∈F，0≤xi≤Tig．

以調整過站松弛時間前后延誤波及時間之差為目標函數建立模型，實現優化調整效果最大化，即：

1）新的松弛時間滿足：

式中：xj－xi為松弛時間的變化量．式（3）保證每個航班聯線中過站時間的總和不變．

2）在航班實際運行當中，同1架飛機執行的任意航班銜接（i，j）∈A，航班i到j的波及延誤為：

PDwij＝ max（TADwi－slackij，0） （4）

3）對于任意航班j，如果j是航班聯線的始發航班，航班j的獨立抵達延誤＝航班j的抵達延誤，即若j∈Fo，則iadwj＝tadwj；否則的話，iadwj＝tadwj－pdwij（獨立抵達延誤＝航班j的抵達延誤－航班j的波及延誤）．即

4）對于任意航班聯線?（i，j）∈As，調整后的波及延誤應滿足：

同時，對任意航班j的抵達延誤滿足

5）對過站松弛時間的調整應滿足：

為了使首末航班的離港時間變化不大，令T＝5，即滿足否則，

為了保證末航班調整之后不為紅眼航班，且根據假設4），對于末航班應該滿足式（12）：

6）另外，有非負約束條件：

2 實例驗證

選取國內某航空公司每天的180條航班聯線數據，每個航班聯線包括4～8個航節，見表1．其中Stringnumber為航班聯線編號，Stringdata第一維為相應的航班聯線編號，第二維為航節序號；如果航班聯線小于8個航節，則通過設置虛擬航班進行補充，如航班聯線Stringnumber［2］實際只有7個航節，則Stringdata［2，8］為虛擬航班．過站松弛時間調整閥值Tg既要保證離港時間調整幅度不能太大，又要保持機組和飛機路線、航班聯線不變，因此，根據實際情況和歷史數據的聚類分析，取Tg＝｛5，10，15，15，15｝．

表1 某航空公司一天執行的180條航班聯線

運用ILOG OPL優化軟件求解，目標函數值z＝10 008min，即通過航班銜接松弛時間的調整，使總延誤波及減少了10 008min．通過計算，原始波及延誤TotalPD＝32 697min，波及延誤減少了30．6%，調整效果非常明顯．

部分數據見表2．其中pdij是航班i對j的波及延誤，xi是航班離港時間的調整量，pdij和xi的單位均為分鐘．

表2 運行結果的相關數據

3 結束語

航班延誤給航空公司成本、乘客出行及航空運輸生產等帶來很大的負面影響，其中波及延誤的影響更為突出，而過站松弛時間在減緩延誤波及中起到關鍵的作用．本文基于航班延誤分級，在保持原有飛機路線和機組任務，以及總的過站時間不變的基礎上，對航班過站時間進行優化．研究結果表明，基于航班延誤風險分級的過站時間調整，針對不同延誤級別設置不同的調整區間，小范圍的改變離港時間，有效地減少了延誤波及現象；基于航班延誤風險分級的過站松弛時間優化為提高航班計劃抗干擾能力，制定更具魯棒性的航班計劃提供了理論支持．不過，此模型沒有具體考慮調整過站松弛時間后對經濟成本的影響，僅是從航班延誤時間上考慮了過站時間的重新分配，這也是下一步研究的內容．

［1］REXING B，BARNHART C，KNIKER T．Airline fleet assignment with time windows［J］．Transportation Science，2000：34（1）：1－20．

［2］LAN S，CLARKE J P，BARNHART C．Planning for robust airline operations：Optimizing aircraft routings and flight departure times to minimize passenger disruptions［J］．Transportantion Science，2006，40（1）：15－28．

［3］曹 嵩，孫富春，胡來紅，等．基于分布算法的離港航班排序優化［J］．清華大學學報：自然科學版，2012，52（1）：66－71．

［4］PAUL T R，LISA A S，LEONARD A W．Flight connections and their impacts on delay propagation［J］．Digital Avionics Systems Conference，2003，5（1）：1－9．

［5］SHERVIN A，AMY C，YIHAN G，et al．Analysis of the potential for delay propagation in passenger airline networks［J］．Journal of Air Transport Management，2008，14（5）：221－236．

［6］SHERVIN A，AMY C，LAPP M．Decreasing airline delay propagation by re－allocating scheduled slack［J］．IIE Transactions，2010，42（7）：478－489．

［7］曹衛東，林翔宇．基于貝葉斯網絡的機場過站時間分析［J］．航空計算技術，2010，40（5）：5－9．

［8］牟德一，張宗賢．基于航班延誤概率的魯棒性飛機排班模型［J］．中國民航大學學報，2010，28（6）：35－39．

［9］鄭曉洋．航班延誤波及問題中的航班取消策略探討［D］．濟南：山東大學，2011．

［10］丁建立，李華峰．基于免疫進化算法的航班過站時間優化模型［J］．計算機工程與設計，2012，33（9）：3637－3640．

［11］戚彥龍，王 琨，朱星輝，等．基于離差最大化原理的航班延誤風險分級研究［J］．武漢理工大學學報：交通科學與工程版，2014，38（1）：162－166．