基于延誤分級(jí)的航班過站松弛時(shí)間優(yōu)化研究＊

朱星輝 戚彥龍 吳薇薇 高 強(qiáng)

（南京航空航天大學(xué)民航學(xué)院 南京 210016）

0 引 言

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

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

1．1 航班延誤波及分析

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

圖1 連續(xù)航班i，j的離港、到達(dá)和延誤圖

1．2 基于航班延誤風(fēng)險(xiǎn)分級(jí)的過站松弛時(shí)間優(yōu)化模型

為進(jìn)行航班過站松弛時(shí)間優(yōu)化調(diào)整，做如下基本假設(shè)（或建?；A(chǔ)）．

1）保持原機(jī)組和飛機(jī)路線、航班聯(lián)線不變．

2）保持原航班聯(lián)線中總過站時(shí)間不變（航班時(shí)刻調(diào)整時(shí)，不出現(xiàn)紅眼航班）．

3）航班時(shí)刻（時(shí)隙資源）不能大幅度修改，不影響航班市場(chǎng)需求．

4）航班輪檔時(shí)間不變．

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

以調(diào)整過站松弛時(shí)間前后延誤波及時(shí)間之差為目標(biāo)函數(shù)建立模型，實(shí)現(xiàn)優(yōu)化調(diào)整效果最大化，即：

1）新的松弛時(shí)間滿足：

式中：xj－xi為松弛時(shí)間的變化量．式（3）保證每個(gè)航班聯(lián)線中過站時(shí)間的總和不變．

2）在航班實(shí)際運(yùn)行當(dāng)中，同1架飛機(jī)執(zhí)行的任意航班銜接（i，j）∈A，航班i到j(luò)的波及延誤為：

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

3）對(duì)于任意航班j，如果j是航班聯(lián)線的始發(fā)航班，航班j的獨(dú)立抵達(dá)延誤＝航班j的抵達(dá)延誤，即若j∈Fo，則iadwj＝tadwj；否則的話，iadwj＝tadwj－pdwij（獨(dú)立抵達(dá)延誤＝航班j的抵達(dá)延誤－航班j的波及延誤）．即

4）對(duì)于任意航班聯(lián)線?（i，j）∈As，調(diào)整后的波及延誤應(yīng)滿足：

同時(shí)，對(duì)任意航班j的抵達(dá)延誤滿足

5）對(duì)過站松弛時(shí)間的調(diào)整應(yīng)滿足：

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

為了保證末航班調(diào)整之后不為紅眼航班，且根據(jù)假設(shè)4），對(duì)于末航班應(yīng)該滿足式（12）：

6）另外，有非負(fù)約束條件：

2 實(shí)例驗(yàn)證

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

表1 某航空公司一天執(zhí)行的180條航班聯(lián)線

運(yùn)用ILOG OPL優(yōu)化軟件求解，目標(biāo)函數(shù)值z(mì)＝10 008min，即通過航班銜接松弛時(shí)間的調(diào)整，使總延誤波及減少了10 008min．通過計(jì)算，原始波及延誤TotalPD＝32 697min，波及延誤減少了30．6%，調(diào)整效果非常明顯．

部分?jǐn)?shù)據(jù)見表2．其中pdij是航班i對(duì)j的波及延誤，xi是航班離港時(shí)間的調(diào)整量，pdij和xi的單位均為分鐘．

表2 運(yùn)行結(jié)果的相關(guān)數(shù)據(jù)

3 結(jié)束語

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

［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］曹 嵩，孫富春，胡來紅，等．基于分布算法的離港航班排序優(yōu)化［J］．清華大學(xué)學(xué)報(bào)：自然科學(xué)版，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］曹衛(wèi)東，林翔宇．基于貝葉斯網(wǎng)絡(luò)的機(jī)場(chǎng)過站時(shí)間分析［J］．航空計(jì)算技術(shù)，2010，40（5）：5－9．

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

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

［10］丁建立，李華峰．基于免疫進(jìn)化算法的航班過站時(shí)間優(yōu)化模型［J］．計(jì)算機(jī)工程與設(shè)計(jì)，2012，33（9）：3637－3640．

［11］戚彥龍，王 琨，朱星輝，等．基于離差最大化原理的航班延誤風(fēng)險(xiǎn)分級(jí)研究［J］．武漢理工大學(xué)學(xué)報(bào)：交通科學(xué)與工程版，2014，38（1）：162－166．