非正常航班管理中的飛機(jī)恢復(fù)問題研究.pdf

第3 0 卷第2 期 2 0 1 2 年4 月 中國(guó)民航大學(xué)學(xué)報(bào) J O U R N A LO FC I V I LA V I A T I O NU N I V E R S I T YO FC H I N A V 0 1 3 0N 0 2 A p r i l 2 0 1 2 非正常航班管理中的飛機(jī)恢復(fù)問題研究 詹晨旭，樂美龍 ( 上海海事大學(xué)物流研究中心，上海2 0 0 1 3 5 ) 摘要：航空運(yùn)輸中時(shí)常會(huì)受到各種因素的干擾。形成非正常航班。非正常航班若得不到及時(shí)有效處理，會(huì)給航空 公司帶來巨大損失因此航空恢復(fù)問題顯得十分重要。主要針對(duì)航空公司飛機(jī)恢復(fù)問題進(jìn)行了研究。利用 原時(shí)刻表，綜合考慮航班時(shí)間約束、飛機(jī)維護(hù)約束、機(jī)場(chǎng)容量約束和飛機(jī)容量約束，并結(jié)合航空公司運(yùn)行實(shí) 際建立了飛機(jī)恢復(fù)模型。模型中對(duì)飛機(jī)恢復(fù)成本進(jìn)行了細(xì)分并以成本最小為目標(biāo)函數(shù)。為解決該問題， 設(shè)計(jì)了一個(gè)啟發(fā)式算法。通過使用巢航空公司的數(shù)據(jù)，對(duì)模型進(jìn)行了計(jì)算，對(duì)算法進(jìn)行了測(cè)試。計(jì)算結(jié)果表 明，啟發(fā)式算法可以較好解決飛機(jī)恢復(fù)問題，所得該方案能較好地符合航空公司要求。 關(guān)鍵詞：航空運(yùn)輸；飛機(jī)恢復(fù)；啟發(fā)式算法；非正常航班 中圖分類號(hào)：V 3 5 5 2文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1 6 7 4 5 5 9 0 ( 2 0 1 2 ) 0 2 0 0 4 3 0 5 S t u d yo na i r c r a f tr e c o v e r yp r o b l e mu n d e ra i r l i n e 7 Si r r e g u l a rf l i g h tm a n a g e m e n t Z H ANC h e n - x u ，L EM e i - l o n g ( L o g i s t i c sR e s e a r c hC e n t e r ，S h a r t g t u u M a r i t i m eU n i v e r s 咖，S h a n g h a 2 0 0 1 3 5 ，C h i n a ) A b s t r a c t ：I nt h ec i v i la i rt r a n s p o r t ，ar e s u l to fv a r i o u sf a c t o r s ，i r r e g u l a rf l i g h ti sd i f f i c u l tt oa v o i d I ft h ea i r l i n e sd on o t t a k ee r i e e t i v em e a s u r e s 。i tw i l lc a u s et r e m e n d o u sl o s s e st ot h ea i r l i n e sa n dp a s s e n g e r s i n c o n v e n i e n c e S o a i r c r a f tr e c o v e r yp r o b l e mi sv e r yi m p o r t a n ta n di t i sa l w a y sd i v i d e di n t ot h r e ep a r t s ：a i r c r a f tr e c o v e r y ，c r e w r e c o v e r ya n dp a s s e n g e rr e c o v e r y T h i sp a p e rw a sf o c u s e do na i r c r a f tr e c o v e r yp r o b l e m A n da c c o r d i n gt ot h e i n t e r f e r e n c e ，a na i r c r a f tr e c o v e r ym o d e li se s t a b l i s h e d ，a n dah e n f i s t i cm e t h o di sp r e s e n t e d W et a k ef l i g h t t i m ec o n s t r a i n t s ，m a i n t a i nc o n s t r a i n t si n t oa c c o u n t I no d d i t i o nt ot h i s ，t h ea r t i c l ea l S Oa d o p t e dac o r r e c t e d d a t ao fo n ea i r l i n et ot e s tt h em o d e la n dm e t h o d T h er e s u l t ss h o wt h a tt h ep r o g r a mc a nb eab e t t e rs o l u t i o no f t h ea i r c r a f tr e c o v e r yp r o b l e m K e yw o r d s ：a i rt r a n s p o r t a t i o n ；a i r c r a f tr e c o v e r y ；h e u r i s t i cm e t h o d ；i r r e g u l a rf l i g h t 中國(guó)民航局發(fā)布的民航行業(yè)發(fā)展統(tǒng)計(jì)公報(bào)披露， 2 0 1 0 年，中國(guó)國(guó)內(nèi)大型航空公司計(jì)劃航班1 8 8 8 萬 次。其中，正常航班1 4 3 1 萬次，不正常航班4 5 7 萬 次，航班不正常率為2 4 2 。2 0 1 0 年，中國(guó)中小航空公 司計(jì)劃航班2 6 0 萬次。其中，正常航班1 7 9 萬次，不 正常航班8 1 萬次，航班不正常率3 1 2 。根據(jù)民航局 披露的數(shù)據(jù)，2 0 1 0 年，在導(dǎo)致主要航空公司航班不正 常的原因中，航空公司自身原因占到4 1 1 ；流量控制 占2 7 6 ；天氣占1 9 5 ，其他占到1 1 8 。在對(duì)中小 航空公司航班不正常原因進(jìn)行的統(tǒng)計(jì)中，航空公司自 身原因高達(dá)4 7 9 。 無論是由于飛機(jī)故障、機(jī)組人員病假等航空公司 的原因，還是天氣、流量控制等其他原因，航班不正常 難以避免。在發(fā)生航班不正常時(shí)，采用科學(xué)的方法，盡 快恢復(fù)航班尤其重要。 目前的航空恢復(fù)研究主要關(guān)注飛機(jī)資源，這是因 為飛機(jī)資源是航空公司最為重要的資源( K o h le ta 1 2 0 0 7 ) 【l 】o T e o d o r o v i c 和G u b e r i n i c ( 1 9 8 4 ) 1 2 1 是最早研究飛機(jī) 恢復(fù)問題的學(xué)者之一。他們從運(yùn)營(yíng)的角度研究這一問 題，考慮當(dāng)出現(xiàn)某一架飛機(jī)無法執(zhí)行任務(wù)的情況時(shí)， 通過交換航段和延誤航班達(dá)到最小化乘客延誤的目 收稿日期：2 0 1 2 - 0 1 1 0 ；修回1 3 期：2 0 1 2 - 0 3 - 0 9 基金項(xiàng)目：上海市自然科學(xué)基金創(chuàng)新行動(dòng)計(jì)劃項(xiàng)目( 1 0 1 9 0 5 0 2 5 0 0 ) ；海海事大學(xué)啟動(dòng)基金項(xiàng)目；上海市科委工程中心項(xiàng)目( 0 9 D Z 2 2 5 0 4 0 0 ) ；I - 海市 教委重點(diǎn)學(xué)科項(xiàng)目( J 5 0 6 0 4 ) 作者簡(jiǎn)介：詹晨旭( 1 9 8 8 一) 男，浙江溫州人，碩士研究生，研究方向?yàn)楹娇沼?jì)劃與排程 萬方數(shù)據(jù) 一4 4 一 中國(guó)民航大學(xué)學(xué)報(bào) 2 0 1 2 年4 月 的。他們構(gòu)建了一個(gè)數(shù)學(xué)模型，并通過分支定界法求 解該模型。但是許多實(shí)際運(yùn)營(yíng)中的約束條件，例如機(jī) 場(chǎng)宵禁、飛機(jī)維護(hù)約束和飛機(jī)平衡約束等在他們的模 型中并未體現(xiàn)。此外，航班取消這一選項(xiàng)也未被考慮。 而C l a r k e ( 1 9 9 8 ) 3 1 ，F(xiàn) i l a re ta 1 ( 2 0 0 1 ) 4 1 。A n d e r $ s o n 和 V a r b r a n d ( 2 0 0 4 ) l ”，K o h le ta 1 ( 2 0 0 7 ) 【1 1 ，Y ua n dQ i ( 2 0 0 5 ) 1 6 1 以及C l a u s e ne ta 1 ( 2 0 1 0 ) m 等對(duì)飛機(jī)恢復(fù)問題 的概念與模型均提出了綜合性的回顧。Y a nS a n d Y a n gD ( 1 9 9 6 ) s 3 提出了一個(gè)包含航班取消、航班延誤 和調(diào)用飛機(jī)等選項(xiàng)的模型，以解決飛機(jī)恢復(fù)問題。他 們的模型基于若干假設(shè)：?jiǎn)我粰C(jī)隊(duì)；所有的航班都是 不經(jīng)停航班；僅有1 架飛機(jī)出現(xiàn)無法執(zhí)行航班狀況。 同時(shí)，他們還提出了一個(gè)時(shí)空網(wǎng)絡(luò)用以表述飛機(jī)恢復(fù) 問題，該網(wǎng)絡(luò)滿足前述的3 個(gè)選項(xiàng)。該模型的目標(biāo)函 數(shù)是最小化航班時(shí)刻表受干擾時(shí)間。通過利用中華航 空的實(shí)際數(shù)據(jù)，運(yùn)用拉格朗日松弛方法，對(duì)模型進(jìn)行 了檢驗(yàn)。 J a yM R o s e n b e r g e r ，E l l i sL J o h n s o n ，G e o r g eL N e m h a u s e r ( 2 0 0 3 ) 叫鋅飛機(jī)恢復(fù)問題轉(zhuǎn)化為一個(gè)帶時(shí)間 窗約束和時(shí)間槽約束的集覆蓋( s e t p a c k i n g ) 問題。在他 們的模型中，目標(biāo)函數(shù)是最小化總成本，包含飛機(jī)重 新指派路徑成本和航班取消成本。T e o d o r o v i e 和S t o j k o v i c ( 1 9 9 0 ) t o l 提出了一個(gè)啟發(fā)式算法用來解決飛機(jī) 恢復(fù)問題。在他們的文章中，最小化取消航班數(shù)量與 乘客延誤總數(shù)是目標(biāo)函數(shù)，但是沒有考慮航班延誤成 本以及取消成本。M i c h a e lF A r g u e l l o ，J o n a t h a nF B a r d ，G a n gY u ( 1 9 9 7 ) l a l 提出了一個(gè)基于隨機(jī)臨近搜 索的啟發(fā)式算法用以解決飛機(jī)恢復(fù)問題。在文章中， 他們創(chuàng)造了一個(gè)貪婪隨機(jī)適應(yīng)搜索程序( G R S A P ) ，用 這一程序重建飛機(jī)路徑以應(yīng)對(duì)干擾。目標(biāo)函數(shù)是最小 化飛機(jī)路徑指派成本和航班取消成本。但是在他們的 程序與模型中并沒有考慮飛機(jī)維護(hù)要求和機(jī)組限制。 J o n a t h a nF B a r d ，G a n gY u 和M i c h a e lF A r g u e l l o ( 2 0 0 1 ) 【1 地對(duì)飛機(jī)恢復(fù)問題提出了一個(gè)時(shí)間帶優(yōu)化模 型。通過將飛機(jī)路徑問題轉(zhuǎn)化為一個(gè)基于時(shí)間的網(wǎng) 絡(luò)，他們構(gòu)建了時(shí)間帶模型，并將飛機(jī)恢復(fù)問題視作 一個(gè)最小成本流問題。T h e n g v a l lB ，B a r dJ ，Y uG ( 2 0 0 0 ) ( 1 3 j 對(duì)M i c h a e lF A r g u e l l o ，J o n a t h a nF B a r d ， G a n gY u ( 1 9 9 7 ) 1 l 的網(wǎng)絡(luò)模型進(jìn)行了拓展。他們所提 出的模型中，目標(biāo)函數(shù)中使用了偏離原時(shí)刻表罰值， 并以其最小化為目標(biāo)。同時(shí)，其允許人工計(jì)劃員指定 與恢復(fù)操作相關(guān)的參數(shù)。測(cè)試數(shù)據(jù)包括2 個(gè)機(jī)隊(duì)的2 7 架飛機(jī)。E g g e n b e r gN B i e r l a i r eM ，S a l a n iM ( 2 0 0 7 ) 【州 提出了一個(gè)擴(kuò)展的時(shí)空網(wǎng)絡(luò)模型，目標(biāo)函數(shù)是最小化 包括航班延誤、取消成本，飛機(jī)航段交換成本以及完 成成本( m a k e s p a nc o s t ) 在內(nèi)的總成本。 本文以飛機(jī)恢復(fù)為主要研究?jī)?nèi)容，提出一個(gè)飛機(jī) 恢復(fù)的優(yōu)化模型，并給出一個(gè)解決飛機(jī)恢復(fù)問題的啟 發(fā)式算法。第1 章闡述恢復(fù)模型；第2 章介紹啟發(fā)式 算法；在第3 章中，若干算例將被應(yīng)用，利用算例對(duì)模 型和算法進(jìn)行了驗(yàn)證分析；最后，第4 章對(duì)模型及算 法進(jìn)行了總結(jié)，并提出了后續(xù)研究改進(jìn)的方向。 1 飛機(jī)恢復(fù)模型 依照航空公司的日常運(yùn)營(yíng)，考慮所關(guān)注的飛機(jī)資 源，本文為某一時(shí)間周期內(nèi)的飛機(jī)恢復(fù)問題建立了模 型。在建立模型時(shí)，考慮到飛機(jī)恢復(fù)的最終目標(biāo)是恢 復(fù)航班時(shí)刻表，因而本文引入原始時(shí)刻表和修正時(shí)刻 表兩個(gè)概念。原始時(shí)刻表是指在干擾情況發(fā)生之前， 航空公司所計(jì)劃執(zhí)行的時(shí)刻表；修正時(shí)刻表是指產(chǎn)生 干擾后，經(jīng)過恢復(fù)操作所得到的時(shí)刻表。本文將機(jī)場(chǎng) 分為兩類，一類是可執(zhí)行飛機(jī)維護(hù)操作的機(jī)場(chǎng)，剩余 的機(jī)場(chǎng)歸為一類。具體參數(shù)、變量如下： T = i t _ ，胡為時(shí)間周期；O S 為原時(shí)刻表；R S 為修正 的時(shí)刻表；F 為航班集合；A 為機(jī)場(chǎng)集合；A c 為飛機(jī)集 合；日為需要在丁內(nèi)維護(hù)的飛機(jī)集合；A 橢為可以執(zhí) 行飛機(jī)的計(jì)劃維護(hù)的機(jī)場(chǎng)集合；T F 為原時(shí)刻表中的航 班總數(shù)；C A 只a n ( r ，) 為在時(shí)刻礦和時(shí)刻之間機(jī)場(chǎng)口 的到達(dá)容量；c A r ( r ，) 為在時(shí)刻r 和時(shí)刻；。之間機(jī) 場(chǎng)口的離開容量；F ( r ，礦) 為在r 和尸之間進(jìn)入機(jī)場(chǎng)。 的航班集合；C ( 礦，r ) 為在嚴(yán)和之間離開機(jī)場(chǎng)a 的航 班集合；c a ，s ”為將航班廠F 指派給修正時(shí)刻表R S 的 成本；c “為航班廠E F 的取消成本；c 為航班廠E F 的每分鐘延誤成本；c a 。l t a r 為航班，上乘客的每分 鐘延誤成本；c ：為將飛機(jī)n A c 指派給航班， 的成本；c ：”“為飛機(jī)n A c 上每個(gè)座位空閑的成 本；s e a t ( 忍) 為飛機(jī)乃E A c 上的座位數(shù)量；C A P ( 廠) 為 航班廠E F 要求的座位數(shù)；姆為航班廠F 的實(shí)際到 達(dá)時(shí)間；耳為航班，E ，的計(jì)劃到達(dá)時(shí)間；t 4 為航班 f EF 的實(shí)際離開時(shí)間；D 乃為航班f EF 的飛行時(shí) 間；T u r n T m e ( 乃) 為飛機(jī)7 , A C 的轉(zhuǎn)向( t u r n a r o u n d ) 時(shí)間；x i 為l ，如果航班廠E F 被指派給修正時(shí)刻表R S ； z m 。為l ，如果一個(gè)合格的維護(hù)機(jī)場(chǎng)m E “被飛機(jī) 萬方數(shù)據(jù) 第3 0 卷第2 期詹晨旭，樂美龍：非正常航班管理中的飛機(jī)恢復(fù)問題研究 4 5 n E A C 訪I N ；y ，為l ，如果飛機(jī)r t E A c 被指派給航班 f eF ；z f , , y 為1 ，如果航班廠是航班，的后接航班。 r a i n ( c o s t I + C O S t 。) ( 木) c ，= i 一誓c 咒，+ 一。( 1 - x i ) + n e A C ，F(xiàn)f e F 薹( 蘆) ( t 虧一弓) 號(hào) ( 1 a ) c O S t a e = 咒，。t o m e ”洲( s e a t ( n ) 一C A W ) ) ( 1 b ) 8 【t t x f “F ( 尸，) ( 2 )8 乞“只( r ，廣) ( 2 ) ，l r ，】 x z c A 乎( 礦，) ( 3 ) 卜( ( ，- ) x T F ( 4 )上( 4 ) ，= x l E F ( 5 ) 托，= 1 Y n e A C ( 6 ) f m 。，靠。，= 1 V ne H ( 7 ) ，E ，m E 一 托，s e a t ( r t ) “P V r gE A Cf eF ( 8 ) t d I 墨V f e F ( 9 ) t a y = t d f + D 乃暫V f e F ( 1 0 ) y o t - t 4 ) 一0 Y J T u r n T i m e ( n ) V 扎E A C 工f F ( 1 1 ) t 磚tv ，EF ( 1 2 ) t 一t o y ；y 廠EF ( 1 3 ) 即 0 ，l V f e F ( 1 4 ) h ， 0 ，lJ V F Vr t e A c ( 1 5 ) k 。1 0 ，l V m E A 7 一V t l , E A C ( 1 6 ) 式( t ) 是總成本目標(biāo)，即最小化航班成本與飛機(jī)成本。 式( 1 a ) 中，第l 項(xiàng)是指派成本，即將航班廠指派給 修正時(shí)刻表尺s ，且由飛機(jī)r 執(zhí)行航班廠的成本；第2 項(xiàng)是航班取消成本；第3 項(xiàng)是航班延誤成本，與延誤 時(shí)間有關(guān)。延誤成本既包括航班自身延誤產(chǎn)生的成 本，也包括該航班上乘客的延誤成本。式( 1 b ) 是因座 位空閑而造成的成本。 約束條件中，式( 2 ) 指在時(shí)段，內(nèi)，進(jìn)入機(jī)場(chǎng)。的 航班數(shù)量受機(jī)場(chǎng)到達(dá)容量的限制。式( 3 ) 指在時(shí)段r 內(nèi)，離開機(jī)場(chǎng)的航班數(shù)量受機(jī)場(chǎng)離開容量的限制。航 班數(shù)量約束，即被指派的航班數(shù)量不超過總航班數(shù)， 在式( 4 ) 中體現(xiàn)。式( 5 ) 約束航班指派，即航班指派給 飛機(jī)時(shí)的0 1 約束。飛機(jī)指派約束在式( 6 ) 中限制，每 架飛機(jī)只能被指派1 次。式( 7 ) 體現(xiàn)飛機(jī)維護(hù)約束，需 維護(hù)的飛機(jī)要求訪問有維修資格的機(jī)場(chǎng)。航班容量約 束在式( 8 ) 中體現(xiàn)，如果飛機(jī)n 被指派給航班廠 則飛 機(jī)上的座位數(shù)應(yīng)不小于航班要求的座位數(shù)。式( 9 ) 一 式( 1 3 ) 約束航班時(shí)間。式( 9 ) 約束離開時(shí)間，即航班廠 的實(shí)際離開時(shí)間應(yīng)不小于其計(jì)劃離開時(shí)間。式( 1 0 ) 約 束到達(dá)時(shí)間，即航班廠的實(shí)際到達(dá)時(shí)間等于其實(shí)際離 開時(shí)間加上飛行時(shí)間。式( 1 1 ) 體現(xiàn)飛機(jī)轉(zhuǎn)向( t u m a r o u n d ) 時(shí)間約束，即如果航班廠是航班廠的緊接航班。若它們 由l 架飛機(jī)執(zhí)行，則這兩個(gè)航班間的到達(dá)和離開時(shí)間 差應(yīng)大于該飛機(jī)的t u r n a r o u n d 時(shí)間。式( 1 2 ) 、式( 1 3 ) 表 明實(shí)際離開時(shí)間和實(shí)際到達(dá)時(shí)間應(yīng)在時(shí)間范圍r 內(nèi)。 式( 1 4 ) 一式( 1 6 ) 是0 、l 變量約束。 2 解決方法 本文設(shè)計(jì)了一種基于改進(jìn)的隨機(jī)搜索策略的啟 發(fā)式算法，該算法主要參考G A 算法思路。通過迭代計(jì) 算，得到每次迭代結(jié)果較優(yōu)的可行解，并在迭代中對(duì) 解搜索方向加以引導(dǎo)，逐次逼近最優(yōu)解，提高搜索精 度，加快搜索速度。參考G A 求解思路，首先定義可行 解空間容量為M 。該空問里的叮行解是迭代的對(duì)象； 然后對(duì)每次迭代得到的可行解按照成本最小( 目標(biāo)函 數(shù)要求) 排序，并保留前M a 個(gè)可行解，將其直接作為 下次迭代的結(jié)果；再對(duì)可行解進(jìn)行迭代，直至迭代次 數(shù)達(dá)到之前所設(shè)定的值。算法流程如圖l 所示。具體 算法步驟如下： 步驟l 按照F C F S ( 先來先服務(wù)) 策略延誤或取 消0 5 中受干擾航班，得到M 個(gè)初始R S ，若調(diào)整受干 擾航班無法得到M 個(gè)初始解，則復(fù)制任意一個(gè)初始 解，填充剩余初始解空間，將所有初始解記為尺5 0 l ，一， 兄受h 。 步驟2 對(duì)尺+ 按成本升序排列，保留前M a 個(gè) R & + ，將其視作本次調(diào)整所得的結(jié)果，并調(diào)整剩余的 l f ( 1 - a ) 個(gè)R & ，。隨機(jī)挑選一個(gè)剩余R S 啦，調(diào)整其解結(jié) 構(gòu)( 即調(diào)整其航班屬性到達(dá)時(shí)間或離開時(shí)間，以 及執(zhí)行飛機(jī)) ，得到一個(gè)新R S ，如果新R S 的成本不比 調(diào)整前的R & 。成本大，則將其保留，并記為R S 。 步驟3 對(duì)R S 。重復(fù)步驟2 ，得到R 島。 步驟4 重復(fù)步驟2 與步驟3 ，直至完成之前設(shè) 定的迭代次數(shù)，得到R S 。 步驟5 按成本，升序排列R 。，將尺& + 中成本 最小的解作為解決方案，并輸出。 萬方數(shù)據(jù) 4 6 中國(guó)民航大學(xué)學(xué)報(bào)2 0 1 2 年4 月 圈1 算法流程 F i g , 1A l g o r i t h mp r o c e s s 3 算例與結(jié)果分析 3 1 算例 本文使用國(guó)內(nèi)一家航空公司的實(shí)際數(shù)據(jù)來測(cè)試 模型與算法的有效性。該航空公司主要運(yùn)營(yíng)國(guó)內(nèi)航 班，以P V G 與S Z X 為其運(yùn)營(yíng)基地，在N K G 、P V G 、S Z X 、 P E K 、X I Y 等5 個(gè)機(jī)場(chǎng)具備飛機(jī)維護(hù)資格。該航空公司 一個(gè)周期內(nèi)的航班時(shí)刻表包含1 9 8 個(gè)航班，由3 2 架 飛機(jī)執(zhí)行，飛機(jī)機(jī)型計(jì)有5 種，包括B 7 4 7 、B 7 7 7 、 A 3 0 0 、A 3 1 0 以及A 3 2 0 。本文所用數(shù)據(jù)節(jié)選自該航班 時(shí)刻表，基本數(shù)據(jù)匯總?cè)绫? 所示，飛機(jī)具體數(shù)據(jù)如 表2 所示。 裹1 基本情況 飛機(jī)數(shù)量 機(jī)型數(shù)量航班數(shù)量機(jī)場(chǎng)數(shù)量 J 1 356 0 2 5 J 本上為短途航班，即飛行時(shí)間在3h 以下。將時(shí)間窗設(shè) 定為T ：i t , 刁= 【0 7 ：0 0 ，2 4 ：0 0 】，設(shè)c ；一：o 元，c t ，r a n 。“： 2 50 0 0 元，c = 5 0 元，m i n ，c = = 5 0 元_ J m i n ，c 吖a s s i g n 如 表2 所示，c u p e d 為每個(gè)航班上的座位票價(jià)。在求解 時(shí)，設(shè)可行解空間容量M = 5 0 ，解保留比率O t = 1 0 ， 迭代次數(shù)N = 50 0 0 。 對(duì)于干擾情況，由于在模型中較為關(guān)注機(jī)場(chǎng)某時(shí) 段的容量變化，因而本文將干擾情況設(shè)定為：某日因 天氣狀況，P V G 機(jī)場(chǎng)在1 2 ：0 0 關(guān)閉，直至1 3 ：3 0 ，即在 1 2 ：0 0 1 3 ：3 0 內(nèi)，P V G 容量減為O 。 3 2 結(jié)果分析 使用C 語言實(shí)現(xiàn)啟發(fā)式算法，在C P U 為C O R E i 32 1 3G H z ，內(nèi)存為2G B 的P c 上運(yùn)行該算法，求解 問題。針對(duì)前述的干擾情況，按照不同的迭代次數(shù)，得 到不同的解決方案?？梢园l(fā)現(xiàn)，隨著迭代次數(shù)的增加， 成本越來越趨近于某一值。在迭代50 0 0 次之后，發(fā)現(xiàn) 成本值曲線接近平緩，得到的成本值為2 85 8 7 4 5 元。 迭代次數(shù)與成本值之間的關(guān)系如圖2 所示。而使用 L I N G O9 0 求解該問題，最優(yōu)解為2 83 1 4 1 0 元。使用 啟發(fā)式算法得到的最終解。較最優(yōu)解高0 9 7 。因此， 認(rèn)為該最終解可被接受，可被視作最終解決方案。 圖2 迭代次數(shù)與成本 F i g 2 I t c r a t i o ma n dc o s t 在最終解決方案中，取消航班數(shù)為0 ，延誤航班數(shù) 為1 3 班次，占總航班的2 1 6 7 ，產(chǎn)生的總成本為 2 85 8 7 4 5 元。而按照迭代次數(shù)的不同，產(chǎn)生不同的解 決方案，各方案航班信息如表3 所示。 衰3 備方案航班信息 T a b 3 師g h ti n f o r m a t i o no fe a c hs o l u t i o n 迭代次數(shù)取消航班數(shù) 延誤航班數(shù)延誤比例 1 0 0 5 0 0 l0 0 0 20 0 0 3O 5 0 4 5 3 4 2 7 2 2 1 7 1 3 7 5 o o 5 6 6 7 4 5 0 0 3 6 6 7 2 8 3 3 2 1 6 7 由于該航空公司以國(guó)內(nèi)航班為主，因而其航班基啟發(fā)式算法得到的最終解決方案產(chǎn)生2 85 8 7 4 5 咖咖咖咖咖竹鉆鴝虬扮” 候趔禱毽 萬方數(shù)據(jù) 第3 0 卷第2 期詹晨旭，樂美龍：非正常航班管理中的飛機(jī)恢復(fù)問題研究 4 7 元的總成本，較按F C F S 策略延誤航班產(chǎn)生的成本 ( 3 55 6 9 9 5 元) 減少1 9 6 3 ，所花費(fèi)的求解時(shí)間為1 9 r a i n ，較精確解求解所花時(shí)間( 4 2r a i n ) 減少5 4 7 6 。 4 結(jié)語 本文所提出的模型主要針對(duì)于航空公司非正常 航班管理中的飛機(jī)恢復(fù)問題。當(dāng)受到干擾時(shí)，可以輔 助管制員實(shí)施調(diào)度。在盡量恢復(fù)原計(jì)劃的同時(shí)，其延 誤率也大大降低。由于該模型所涉及到的數(shù)據(jù)量較 多，因此該模型適用于中小型航空公司。 對(duì)于所設(shè)計(jì)的啟發(fā)式算法，使用了不同規(guī)模的數(shù) 據(jù)進(jìn)行了測(cè)試。在較小規(guī)模數(shù)據(jù)( 3 架飛機(jī)、1 8 個(gè)航 班、1 2 個(gè)機(jī)場(chǎng)) 情況下，算法表現(xiàn)良好，迭代50 0 0 次， 花費(fèi)8m i n 得到結(jié)果；中型數(shù)據(jù)( 1 3 架飛機(jī)、6 0 個(gè)航班、 2 5 個(gè)機(jī)場(chǎng)) 情況下，迭代50 0 0 次，花費(fèi)1 9m i n 得到結(jié) 果；而對(duì)于大規(guī)模數(shù)據(jù)( 2 5 架飛機(jī)、1 5 4 個(gè)航班、4 6 個(gè) 機(jī)場(chǎng)) 情況下，迭代50 0 0 次，花費(fèi)5 1m i n 。可以看出， 隨著數(shù)據(jù)規(guī)模的擴(kuò)大，本文所設(shè)計(jì)的啟發(fā)式算法的搜 索效率則大為下降，因而可考慮使用其他效率較高的 啟發(fā)式算法。 需要指出的是，本文所提出的模型屬于非線性， 因此，其結(jié)果為局部最優(yōu)解。本文最大的約束在于不 允許產(chǎn)生新的航班，但是在實(shí)際活動(dòng)中產(chǎn)生的干擾情 況是多種多樣的。因此，針對(duì)不同的情況，應(yīng)該建立一 個(gè)適應(yīng)度更強(qiáng)的模型。針對(duì)本文所提出的方案也可有 多方面的拓展。 參考文獻(xiàn)： 1 1 l K O H LN ，L A R S E NA ，L A R S E NJ ，e ta 1 A i r l i n ed i s m p t i 0 1 1 m a n a g e m e n tp e r s p e c t i v e s ，e x p e r i e n c e sa n do u t l o o k J J o u r n a lo fA i r T r a n s p o r tM a n a g e m e n t ，2 0 0 7 1 3 ：1 4 9 - 1 6 2 1 2 】T E O D O R V I CD ，G U B E R N I CS O p t i m a ld i s p a t c h i n gs t r a t e g yo na n d a i d i n en e t w o r ka f t e ras c h e d u l ep e r t u r b a t i o n J E u r o p e a nJ o u r n a lo f O p e r a t i o n s R e s e a r c h 。1 9 8 4 。1 5 ：1 7 8 1 8 2 【3 】 c L A R K EMDD I r r e g l l l 盯a i r l i n eo p e r a t i o n s ：ar e v i e wo f t h e 時(shí)a t e o f - t h e - p r a c t i c ei na i r l i n eo p e r a t i o n sc o n t r o lc e n t e t 叨J o u r n a lo fA i r T r a n s p o r tM a n a g e m e n t ，1 9 9 8 4 ：6 7 - 7 6 1 4 F I L A RJA ，M A N Y E MP ，W H I T EK H o wa i r l i n e sa n da i r p o r t sl e c o v c g f r o ms c h e d u l ep e r t u r b a t i o n s ：a s u r v e y 們A n a a h0 fO p e r a t i o n sR p s e a r c h ，2 0 0 1 1 0 8 ：3 1 5 3 3 3 【5 】A N D E R S S O NT ，V A R B R A N DP 1 1 l en i s h tp e r t u r b a t i o np r o b l e mI J l T r a n s p o r t a t i o n P l a n n i n g a n d T e c h n o l o g y 。2 0 0 4 ，2 7 ：9 1 一l 】7 【6 】Y uG 。Q IX D i s r u p t i o nM m a n a g e m e n t ：F r a m e w o r k s ，M o d e l sa n d A p p l i c a t i o n s M S i n g a p o r e ：w o d dS c i e n t i f i cP u b l i s h i n g 2 0 0 4 1 7 1J E N SC L A U S E N ，A L L A NL A R S E N ，J E S P E RL A R S E N A ，e ta L D i s r u p t i o nm a n a g e m e n ti nt h e a i r l i n ei n d u s t r y _ _ c o n c e p t s 。m o d e l s a n dm e t h o d s 【J 】C o m p u t e r s & O p e r a t i o n sR e s e m c h ，2 0 1 0 ，3 7 ：8 0 9 - 8 2 1 【8 Y A NS ，Y A N GD A d e c i s i o ns u p p o r tf r a n * w o r kf o rh a n d l i n gs c h e d u l e p e r t u r b a t i o n s J T r a n s p o r t a t i o nR e s e a r c h ，1 9 9 6 3 0 ( 6 ) ：4 0 5 - - 4 1 9 【9 】J A Y M R 0 s E N B E R G E R ，E L L