（計(jì)算機(jī)應(yīng)用技術(shù)專業(yè)論文）航班著陸調(diào)度的實(shí)時(shí)優(yōu)化方法研究.pdf

摘要 摘要 航班著陸調(diào)度( a i r c r a f tl a n d i n gs c h e d u l i n g ，a l s ) 是機(jī)場(chǎng)終端區(qū)空中流量管理 ( a i rt r a 蕊cf l o wm a n a g e m e n t ，a t f m ) 的核心。它旨在為待著陸的航班給出有效的 著陸調(diào)度方案，保證這些航班能夠安全且經(jīng)濟(jì)地著陸。研究終端區(qū)航班調(diào)度問(wèn)題 對(duì)確保飛行安全和提高飛行效益具有重大的意義。 航班著陸調(diào)度是一個(gè)典型的組合優(yōu)化問(wèn)題，其存在的多約束等復(fù)雜性使得這 一問(wèn)題成為公認(rèn)的一個(gè)難解問(wèn)題；同時(shí)，應(yīng)用時(shí)的調(diào)度實(shí)時(shí)性要求進(jìn)一步增加了 這一問(wèn)題的求解難度。目前，業(yè)內(nèi)實(shí)際采用的先來(lái)先服務(wù)調(diào)度方案簡(jiǎn)單快速，但 它無(wú)法進(jìn)一步提高飛行效率，特別是在航班較密集的情況下可能無(wú)法給出合理的 調(diào)度方案。研究界提出的線性規(guī)劃算法具有高效性和正確性，但缺乏全局搜索能 力，在很多情況下很難得到最優(yōu)解或近似最優(yōu)解。計(jì)算智能算法是近年來(lái)解決航 班著陸調(diào)度問(wèn)題的一個(gè)研究熱點(diǎn)，但計(jì)算代價(jià)過(guò)大，特別是在較為繁忙的機(jī)場(chǎng)終 端區(qū)，需要結(jié)合有效的啟發(fā)式方法才能更好地解決航班著陸調(diào)度問(wèn)題。 本文提出了一種新型的優(yōu)化調(diào)度方法來(lái)解決航班著陸調(diào)度問(wèn)題。與以往側(cè)重 于尋找最優(yōu)解的方法不同，本文兼顧調(diào)度的實(shí)時(shí)性與最優(yōu)性要求，并將重點(diǎn)放在 達(dá)到航班著陸調(diào)度的實(shí)時(shí)性要求上。本文提出的是一種基于元胞自動(dòng)機(jī)的航班著 陸優(yōu)化調(diào)度方法( c e l l u l a ra u t o m a t ab a s e do p t i m i z a t i o n ，c a o ) 。它由三個(gè)部分組 成：首先，引入元胞自動(dòng)機(jī)( c e l l u l a ra u t o m a t a ，c a ) 用于模擬航班著陸過(guò)程，在 滿足約束條件的基礎(chǔ)上快速得到一個(gè)相對(duì)較好的航班著陸序列；接著，設(shè)計(jì)一個(gè) 本地優(yōu)化方法，來(lái)進(jìn)一步優(yōu)化航班著陸時(shí)間；最后，通過(guò)對(duì)比設(shè)計(jì)，給出一個(gè)深 度優(yōu)先搜索算法來(lái)進(jìn)一步優(yōu)化航班著陸順序。 在標(biāo)準(zhǔn)數(shù)據(jù)集o r - l i b r a r y 上的對(duì)比實(shí)驗(yàn)證實(shí)，本文提出的航班著陸調(diào)度方法 較其他方法具有更高效快速的優(yōu)點(diǎn)，可以滿足實(shí)際航班著陸調(diào)度的性能要求。 關(guān)鍵詞：航班著陸調(diào)度元胞自動(dòng)機(jī)實(shí)時(shí)深度優(yōu)先搜索遺傳算法 a b s t r a c t a b s t r a c t a so n eo ft h ec o r ec o n t e n t so fa i rt r a f f i cf l o wm a n a g e m e n t ( a t f m ) i nt e r m i n a l a r e a ，a i r c r a f tl a n d i n gs c h e d u l i n g ( a l s ) d e t e r m i n e sa ne f f i c i e n tl a n d i n gs c h e d u l i n g s c h e m ef o rag i v e ns e to fa i r c r a f t si no r d e rt oi n s u r et h es a f e t yo fa i r c r a f t s r e s e a r c h e s a b o u ta l sp r o b l e mh a v eg r e a ts i g n i f i c a n c ef o rf l i g h ts a f e t ya n di m p r o v i n gf l i g h t b e n e f i t a l si sat y p i c a lc o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m , t h ee x i s t e n c eo fs u c h c o m p l e xm u l t i - c o n s t r a i n tm a k e st h i sp r o b l e m a l li n t r a c t a b l e p r o b l e m ；a n dt h e r e a l - t i m er e q u i r e m e n ti n c r e a s e st h ed i f f i c u l t yo ft h es o l v i n gt h i sp r o b l e m w h e nt h e r e a r et o om a n yp l a n e sw a i t i n gf o rl a n d i n g ，f c f sm a yn o tp r o v i d eaf e a s i b l es o l u t i o n u n t i ln o w , t h e r eh a v eb e e nt w ok i n d so fs c h e d u l i n ga l g o r i t h m sf o ra d d r e s s i n ga l s p r o b l e m , o n ei sl i n e a rp r o g r a m m i n g ( l p ) a l g o r i t h m ，a n dt h eo t h e ri sc o m p u t a t i o n a l i n t e l l i g e n c e ( c i ) a l g o r i t h m l ps h o w sh i g he f f e c t i v e n e s sa n dc o r r e c t n e s s ；h o w e v e ri t c a nh a r d l yf i n dt h eg l o b a lo p t i m a ls o l u t i o no w i i 增t ol a c ko ft h ea b i l i t yf o rg l o b a l s e a r c h n e v e r t h e l e s sc in o to n l yh a st h ep o w e r f u la b i l i t yf o rg l o b a ls e a r c h , b u ta l s oi s a b l et oh a n d l en o n l i n e a rc o n s t r a i n ta n dg o a lf u n c t i o n t h e r e f o r ei th a sb e c o m eah o t t o p i ct or e s o l v ea l su s i n gc i h o w e v e rc il i k e l yp r o d u c e sl a r g ec o m p u t a t i o n a lc o s t e s p e c i a l l ya tb u s ya i r p o r t s t h e r e b yc in e e d st oc o m b i n es o m eh e u r i s t i cm e t h o d st o a d d r e s sa l sb e t t e r i nt h i sp a p e r , w ep r o p o s ean o v e la p p r o a c ht oa d d r e s st h ea l sp r o b l e m c o m p a r e dt op r e v i o u ss t u d i e s ，w ep u tm o r ee m p h a s i si nm e e t i n gt h er e q u i r e m e n to f r e a l t i m es c h e d u l i n gr a t h e rt h a ns e c u r i n gag l o b a lo p t i m a ls o l u t i o n o u ra p p r o a c h ， n a m e dc e l l u l a r a u t o m a t a - b a s e do p t i m i z a t i o n ( c a o ) c o n s i s t so ft h r e em a i ns t e p s a t f i r s t ，w ea i mt os e e kac o n s i d e r a b l yg o o da i r c r a f tl a n d i n gs e q u e n c ev i aac e l l u l a r a u t o m a t a ( c a ) m o d e l t h e nt h el a n d i n gs e q u e n c eo b t a i n e db yt h ec am o d e li s f u r t h e rf i n e - t u n e db yas i m p l ey e te f f e c t i v el o c a ls e a r c hp r o c e d u r e a tl a s td e p t hf i r s t s e a r c h i n gi sa p p l i e dt og e n e r a t eb e t t e rs c h e d u l eb a s e do nr e s u l t so fc a e x p e r i m e n t a ls t u d yo nt h es t a n d a r dd a t a b a s ew a sc o n d u c t e dt oc o m p a r et h e c a om e t h o da n ds e v e r a lp o p u l a ra p p r o a c h e si nt h el i t e r a t u r e i tw a so b s e r v e dt h a tt h e c a om e t h o dn o to n l ym a n a g e dt oa t t a i ns o l u t i o n so fh i g h e rq u a l i t y , b u ta l s ow a s m u c hf a s t e r ( i nc p ut i m e ) t h a nt h ec o m p a r e dm e t h o d s t 地m a k e si tp o s s i b l et o a p p l yo u rm e t h o di nr e a l t i m ea i r c r a f tl a n d i n gs c h e d u l i n g k e yw o r d s ：a i r c r a f tl a n d i n gs c h e d u l i n g ，c e l l u l a r - a u t o m a t a ，r e a lt i m e ，g a ，d f s 1 1 1 插圖 插圖 2 1a l s 模型示意圖9 2 2 額外開(kāi)銷和著陸時(shí)刻的關(guān)系1 0 2 3 先來(lái)先服務(wù)算法流程圖1 2 2 4 改進(jìn)的先來(lái)先服務(wù)算法流程圖1 3 2 5n = 5 ，k = l 的c p s 網(wǎng)絡(luò)示意圖1 4 2 6 門(mén)= 5 ，k = l 的c p s 網(wǎng)絡(luò)剪枝后示意圖1 5 2 7 遺傳算法流程示意圖1 7 2 8 禁忌表搜索算法流程和生態(tài)進(jìn)化算法流程1 8 3 1 基于元胞自動(dòng)機(jī)的航班著陸調(diào)度方法流程圖一2 1 3 2 元胞自動(dòng)機(jī)模型應(yīng)用于航班著陸模型的形式2 3 3 3 元胞自動(dòng)機(jī)中航班的位置以及元胞中包含的航班信息一2 4 3 4 元胞自動(dòng)機(jī)中航班的速度示意圖2 5 3 5 元胞自動(dòng)機(jī)中航班的鄰居關(guān)系示意圖2 6 3 6 兩種簡(jiǎn)單規(guī)則調(diào)度結(jié)果示意圖3 0 3 7 優(yōu)化規(guī)則對(duì)數(shù)據(jù)組l 、2 、3 的調(diào)度結(jié)果示意圖3 4 3 8 子序列示意圖3 5 3 9 本地啟發(fā)式搜索( 遺傳算法) 個(gè)體示意圖一3 8 3 1 0 交叉操作示意圖一3 8 4 1 不同的口和值造成的c a o 結(jié)果目標(biāo)函數(shù)值和約束違反數(shù)的對(duì)比圖4 6 4 2 元胞自動(dòng)機(jī)模型在不同下的結(jié)果4 7 4 3 第l o 組數(shù)據(jù)g a 解和d f s 解分布情況5 0 4 4 第1 1 組數(shù)據(jù)g a 解和d f s 解分布情況5 0 6 5 表格 表格 2 1 以= 5 ，k = l 時(shí)可能的航班分配1 4 3 1 加入遺傳算法的航班著陸優(yōu)化算法偽代碼4 0 3 2 加入深度優(yōu)先搜索算法的航班著陸優(yōu)化算法偽代碼4 3 4 1 幾種規(guī)則結(jié)果比較4 8 4 2g a 和d f s 對(duì)比實(shí)驗(yàn)統(tǒng)計(jì)結(jié)果一5 1 4 3c a o 方法和以往算法在小樣本數(shù)據(jù)集上的結(jié)果對(duì)比5 3 4 4 在較大規(guī)模數(shù)據(jù)集上，c a o 方法和s s ，b a 的結(jié)果對(duì)比5 5 4 6 在限時(shí)條件下c a o 方法和以往方法的結(jié)果對(duì)比5 6 4 7c a o 方法三個(gè)階段的結(jié)果自對(duì)比5 7 6 7 中國(guó)科學(xué)技術(shù)大學(xué)學(xué)位論文原創(chuàng)性聲明 本人聲明所呈交的學(xué)位論文，是本人在導(dǎo)師指導(dǎo)下進(jìn)行研究工作所取得的成 果。除已特別加以標(biāo)注和致謝的地方外，論文中不包含任何他人已經(jīng)發(fā)表或撰寫(xiě) 過(guò)的研究成果。與我一同工作的同志對(duì)本研究所做的貢獻(xiàn)均己在論文中作了明確 的說(shuō)明。 作者簽名：么耷彗盤(pán)魚(yú)簽字日期：漁! 里挈s 生蘭皇旦 中國(guó)科學(xué)技術(shù)大學(xué)學(xué)位論文授權(quán)使用聲明 作為申請(qǐng)學(xué)位的條件之一，學(xué)位論文著作權(quán)擁有者授權(quán)中國(guó)科學(xué)技術(shù)大學(xué)擁 有學(xué)位論文的部分使用權(quán)，即：學(xué)校有權(quán)按有關(guān)規(guī)定向國(guó)家有關(guān)部門(mén)或機(jī)構(gòu)送交 論文的復(fù)印件和電子版，允許論文被查閱和借閱，可以將學(xué)位論文編入有關(guān)數(shù)據(jù) 庫(kù)進(jìn)行檢索，可以采用影印、縮印或掃描等復(fù)制手段保存、匯編學(xué)位論文。本人 提交的電子文檔的內(nèi)容和紙質(zhì)論文的內(nèi)容相一致。 保密的學(xué)位論文在解密后也遵守此規(guī)定。 日呸開(kāi)口保密( 年) 作者簽名：么立壘蟈 簽字日期：蘭l ! 復(fù)皇坦蘭! 身 導(dǎo)師簽名： 簽字日期： 俘伏夕 第1 章引言 1 1 研究背景 第1 章引言 隨著世界經(jīng)濟(jì)的發(fā)展，對(duì)航空運(yùn)輸?shù)男枨笠膊粩嘣鲩L(zhǎng)，這導(dǎo)致飛機(jī)數(shù)量和飛 行流量急劇增加，空中交通擁堵已成為亟待解決的一個(gè)難題。每年因空中交通擁 擠造成的經(jīng)濟(jì)損失已經(jīng)達(dá)到了上百億美元，更重要的是空中交通擁擠嚴(yán)重影響了 空中飛行的安全。空中交通流量管理的研究也受到了國(guó)內(nèi)外廣大學(xué)者的廣泛注 意。在我國(guó)，隨著國(guó)民經(jīng)濟(jì)的高速增長(zhǎng)，我國(guó)民航事業(yè)的發(fā)展得到了良好的外部 環(huán)境。從1 9 9 4 年至今，我國(guó)民航的實(shí)際航班飛行量年均增長(zhǎng)1 6 據(jù)國(guó)際民航 組織統(tǒng)計(jì)，2 0 0 5 年我國(guó)航空公司定期航班完成的總周轉(zhuǎn)量達(dá)到2 5 7 7 6 5 億噸公 里，相比2 0 0 4 年增長(zhǎng)了1 2 世界排名也由第三上升到僅次于美國(guó)、而成為超 過(guò)航空強(qiáng)國(guó)德國(guó)的第二大航空運(yùn)輸大國(guó)。隨著空中交通運(yùn)輸量的增加，我國(guó)原來(lái) 的空中交通流量管理方法已經(jīng)不能滿足于日益增長(zhǎng)的交通量的需求。 空中交通流量管理源于航空發(fā)達(dá)國(guó)家，其英文為a i rt r a 伍cf l o w m a n a g e m e n t ，簡(jiǎn)稱a t f m 。早在2 0 世紀(jì)7 0 年代，由于多種因素致使某一空域 中的空中管制能力無(wú)法應(yīng)付管制局面，在探討其解決方法的過(guò)程中提出了“空中 交通流量控制”( a i rt r a f f i cf l o wc o n t r o l ，a t c ) 的概念。本質(zhì)上說(shuō)，a t f m 的目的 是為了安全而有效地使用現(xiàn)有的空域、a t c 的服務(wù)和機(jī)場(chǎng)能力，并且提供飛機(jī) 運(yùn)作者及時(shí)、精確的信息以規(guī)劃和實(shí)施一種經(jīng)濟(jì)的空中運(yùn)輸，以盡可能準(zhǔn)確地預(yù) 報(bào)飛行情況而減少延誤。從2 0 世紀(jì)6 0 、7 0 年代開(kāi)始，美國(guó)、歐洲、日本等國(guó)根 據(jù)當(dāng)?shù)靥攸c(diǎn)都建立了覆蓋整個(gè)區(qū)域的空中交通流量管理系統(tǒng)。與之相比，我國(guó)目 前的空中交通流量管理還是初步的，粗放的，自動(dòng)化程度很低；我國(guó)的空中交通 流量管理體系還沒(méi)有完全建立，相關(guān)研究工作正處在逐步展開(kāi)的階段。 空中交通流量管理可以分為先期流量管理、終端區(qū)交通流量管理以及具有尋 徑能力的空中流量管理。先期流量管理是在宏觀上對(duì)交通流量進(jìn)行管理和調(diào)度， 主要研究地面等待策略問(wèn)題；終端區(qū)交通流量管理主要是指在本終端區(qū)的范圍內(nèi) 進(jìn)行飛行前流量控制和實(shí)時(shí)交通管理，主要研究終端區(qū)飛機(jī)的著陸排序問(wèn)題；具 有尋徑能力的空中流量管理主要根據(jù)各個(gè)機(jī)場(chǎng)、區(qū)域以及航線容量的實(shí)時(shí)情況和 信息及時(shí)動(dòng)態(tài)調(diào)整各個(gè)航班的起飛時(shí)間、航路變化和著陸的時(shí)間。 本文研究的航班著陸調(diào)度方法屬于終端區(qū)交通流量管理范疇。終端區(qū)交通流 量管理旨在：在確保安全前提下，使到場(chǎng)飛機(jī)充分發(fā)揮各自的飛行性能，盡量減 少飛機(jī)之間的相互影響和飛行延誤，提高飛機(jī)的正點(diǎn)到達(dá)率。目前，處理終端區(qū) 第1 章引言 域流量管理的主要措施是對(duì)該區(qū)域內(nèi)的飛機(jī)進(jìn)行排序，這樣可以高效地為到達(dá)的 飛機(jī)合理安排著陸順序。機(jī)場(chǎng)終端區(qū)是航班從航線飛行到著陸的過(guò)渡區(qū)，因?yàn)樯?及機(jī)場(chǎng)容量、空域結(jié)構(gòu)等復(fù)雜特性，它成為影響整個(gè)空管系統(tǒng)運(yùn)行效率的一個(gè)瓶 頸。因此，作為機(jī)場(chǎng)終端區(qū)流量管理的核心環(huán)節(jié)，航班著陸調(diào)度優(yōu)化方法的研究 具有重大意義，能產(chǎn)生很大的應(yīng)用價(jià)值。 在美國(guó)、歐洲以及澳大利亞，不少繁忙機(jī)場(chǎng)和終端區(qū)都使用了航班進(jìn)港排序 輔助決策系統(tǒng)來(lái)配合空管員進(jìn)行航班著陸調(diào)度。以澳大利亞為例，2 0 0 0 年悉尼 奧運(yùn)會(huì)前，悉尼終端管制中心建設(shè)了進(jìn)港排序輔助決策系統(tǒng)( m a e s t r o ) ，該系 統(tǒng)與其使用的空管自動(dòng)化系統(tǒng)( e u r o e a t ) 相結(jié)合，有效地降低了區(qū)域和進(jìn)近雷達(dá)管 制員的工作壓力，達(dá)到了加速進(jìn)入終端區(qū)并降低延誤的目的。排序輔助決策系統(tǒng) 不僅使機(jī)場(chǎng)附近區(qū)域及終端區(qū)的空中交通更加有序，提高了管制安全水平，而且 減少了燃油消耗，為航空公司節(jié)約了大量的運(yùn)行成本。然而，我國(guó)在機(jī)場(chǎng)終端區(qū) 航班著陸調(diào)度方面基本上還處于人工管制階段，依靠管制員的個(gè)人經(jīng)驗(yàn)來(lái)對(duì)待著 陸的航班隊(duì)列進(jìn)行適當(dāng)?shù)恼{(diào)整；相比國(guó)外的航班進(jìn)港排序輔助決策系統(tǒng)，人工管 制不僅效率很低，而且沒(méi)有充分利用空域和地面的資源。因此，研究航班著陸調(diào) 度方法，設(shè)計(jì)高效的優(yōu)化調(diào)度算法，建立航班進(jìn)港排序的計(jì)算機(jī)輔助決策系統(tǒng)對(duì) 于我國(guó)民航事業(yè)的發(fā)展是非常必要的( 馬正平等，2 0 0 3 ；趙嶷飛和王健，2 0 0 3 ) 。 1 2研究意義 隨著世界范圍內(nèi)空中交通流量的快速增長(zhǎng)，特別是發(fā)達(dá)地區(qū)的航運(yùn)活動(dòng)密度 的急劇增大，不當(dāng)?shù)暮桨嗾{(diào)度不僅造成了巨大的經(jīng)濟(jì)損失，而且會(huì)由于航班問(wèn)的 影響導(dǎo)致不良的連鎖反應(yīng)，使局部甚至全區(qū)域的飛行管制陷入混亂。這時(shí)，飛行 安全無(wú)從保障，航運(yùn)效益也會(huì)受到巨大的損失。這使得很多國(guó)家、地區(qū)的空管部 門(mén)都面臨巨大的挑戰(zhàn)和壓力。據(jù)統(tǒng)計(jì)，目前歐美航空業(yè)因空中擁擠每年損失百億 美元之多，其中超過(guò)2 0 的航班延誤損失是由于不當(dāng)?shù)目展苷{(diào)度造成的。在我國(guó)， 由于人口經(jīng)濟(jì)區(qū)域分布的原因，局部發(fā)達(dá)地區(qū)聚集了大部分的空運(yùn)流量，如東部 地區(qū)的航空業(yè)務(wù)量超過(guò)了全國(guó)的9 0 ，僅北京首都機(jī)場(chǎng)、上海虹橋機(jī)場(chǎng)和廣州白 云機(jī)場(chǎng)三大機(jī)場(chǎng)就集中了我國(guó)民航空運(yùn)量中4 0 的旅客量和5 0 的貨物量。正 是由于這種地區(qū)分布的不均勻性，導(dǎo)致了航空流量的擁擠以及大量的航班延誤和 航線沖突，帶來(lái)了無(wú)法估量的經(jīng)濟(jì)損失。保守地估算，我國(guó)航空公司每年需要 9 0 億元的運(yùn)行成本，而因不正常航班運(yùn)行導(dǎo)致的年經(jīng)濟(jì)損失高達(dá)1 8 億元f 余江， 2 0 0 5 ) 。由此可以看出，如果采用合理的空管方案來(lái)調(diào)度空中流量，就可以挽回 大量的不必要的損失；并且，有效的空中交通管制可以確保飛行安全。因此采用 2 第1 章引言 先進(jìn)的交通流量管理方法對(duì)我國(guó)民航事業(yè)的成功發(fā)展是必要的。 在空中交通流量管理中，由于機(jī)場(chǎng)跑道、空域容量等因素，機(jī)場(chǎng)終端區(qū)是最 可能造成飛行事故的區(qū)域，而我國(guó)目前的終端區(qū)交通管制缺乏程序化的科學(xué)方法 的指導(dǎo)，還是依靠管制員的經(jīng)驗(yàn)來(lái)指導(dǎo)航班的調(diào)度。眾所周知，人工效率很低， 且處理問(wèn)題容易受主觀因素影響，無(wú)法充分利用機(jī)場(chǎng)資源。因此，研究機(jī)場(chǎng)終端 區(qū)的流量管理，形成科學(xué)有效的方法體系以指導(dǎo)終端區(qū)的流量調(diào)度，對(duì)解決我國(guó) 空中交通管理無(wú)法滿足需求的狀況具有極大的現(xiàn)實(shí)意義。而作為終端區(qū)交通流量 管理的核心內(nèi)容之一，航班著陸調(diào)度旨在為終端區(qū)待著陸的航班給出合理的著陸 順序和時(shí)刻表，在保證飛行安全的同時(shí)最小化航班延誤損失?？傊瑢?duì)航班著陸 調(diào)度方法的研究對(duì)整個(gè)空中交通流量管理具有重要的意義。 1 3 研究現(xiàn)狀 近二十年來(lái)，航班著陸調(diào)度問(wèn)題得到了各國(guó)學(xué)者的關(guān)注，相關(guān)研究也紛紛開(kāi) 展起來(lái)。目前應(yīng)用最廣泛、最簡(jiǎn)單的是先來(lái)先服務(wù)算法( f i r s tc o m ef i r s ts e r v e d f c f s ) 。這種調(diào)度方法是目前人工調(diào)度環(huán)境中管制員使用的方法，它根據(jù)各航班 到達(dá)終端區(qū)的先后順序來(lái)決定航班的著陸順序，并依據(jù)此順序分配航班著陸時(shí) 間。在考慮航班的到達(dá)順序和航班之間著陸的安全間隔的基礎(chǔ)上，使各航班在最 接近預(yù)計(jì)著陸時(shí)i 、甘j 的時(shí)刻著陸，是先來(lái)先服務(wù)調(diào)度的調(diào)度策略。但在終端區(qū)較繁 忙時(shí)，待著陸航班密集，先來(lái)先服務(wù)調(diào)度方法將難以得到最優(yōu)調(diào)度方案，甚至有 時(shí)無(wú)法給出一個(gè)合理的調(diào)度方案。 在終端區(qū)較繁忙時(shí)，待著陸航班較多，需要不斷根據(jù)終端區(qū)當(dāng)前的空中交通 情況，合理調(diào)度航班的著陸時(shí)間。這不但需要航班調(diào)度算法具備有效性，同時(shí)更 要求該算法具有實(shí)時(shí)性，以便在盡可能短的時(shí)間內(nèi)得到高效的調(diào)度方案，以跟上 空中交通的變化情況。目前，相關(guān)的代表性研究工作包括： f r a n kn e u m a n ( 1 9 9 0 ) 總結(jié)了航班調(diào)度模型，并且提到了受限位置偏移 ( c o n s t r a i n e dp o s i t i o ns h i n i n g ，c p s ) 豐i 時(shí)間預(yù)付( t i m e a d v a n c em e t h o d ) 兩種航班 調(diào)度方法。其中受限位置偏移方法包括最優(yōu)受限位置偏移( o p t i m a lc p s ) 和啟發(fā)式 受限偏移方法( h e u r i s t i cc p s ) 。 m a g i l l 于1 9 8 7 年提出了時(shí)間預(yù)付方法( t a ) ，其中稱之為負(fù)延遲效應(yīng)。這種 方法只改變每組航班的第一架航班的著陸時(shí)間，而保持根據(jù)先來(lái)先服務(wù)得到的航 班隊(duì)列。第一架飛機(jī)通過(guò)加速，在預(yù)計(jì)到達(dá)時(shí)間之前著陸，其后的所有航班都會(huì) 減少相同的延遲，同時(shí)會(huì)減少相鄰航班隊(duì)列之間的著陸間隙。由于加速需要付出 一定的代價(jià)，所以飛機(jī)只有在其后的飛機(jī)會(huì)造成延遲的情況下才會(huì)加速。 第1 章引言 d e a r ( 1 9 7 6 ) 首次提出受限位置偏移思想( c o n s t r a i n e dp o s i t i o ns h i f t i n g ) ，只調(diào)度 著陸航班，而航班的順序不能隨意改變。這種方法規(guī)定某架航班在調(diào)度后的位置 是其初始在f c f s 中位置前后一定的范圍內(nèi)。受限位置偏移思想可以大大縮小搜 索空間，加快搜索速度。后來(lái)，b a l a k r i s h n a n 和c h a n d r a n ( 2 0 0 6 ) 采用了動(dòng)態(tài)規(guī)劃 和c p s 結(jié)合的方法，在使用d e n v e r 國(guó)際機(jī)場(chǎng)的實(shí)際數(shù)據(jù)的仿真實(shí)驗(yàn)中取得了很 好的效果。 b e a s l e y ( 2 0 0 0 ) 給出了一個(gè)航班著陸調(diào)度問(wèn)題的數(shù)學(xué)模型，該模型綜合考慮了 航班延誤或提前帶來(lái)的額外開(kāi)銷。該模型假設(shè)開(kāi)銷和延誤或提前量成線性關(guān)系， 而該模型的約束條件也是線性的。因此，這是一個(gè)帶線性約束條件的線性目標(biāo)函 數(shù)優(yōu)化問(wèn)題，可以用線性規(guī)劃方法來(lái)求解。b e a s l e y 在提出這個(gè)模型的同時(shí)，也 提出了一種基于混合整數(shù)線性規(guī)劃的樹(shù)搜索算法，來(lái)解決靜態(tài)航班調(diào)度問(wèn)題。而 由于這也是一個(gè)空間搜索問(wèn)題，b e a s l e y 給出了一種高效的啟發(fā)式方法來(lái)加以解 決。之后，b e a s l e y 又提出了動(dòng)態(tài)調(diào)度的模型。在該模型中，每次新出現(xiàn)航班需 要調(diào)度的同時(shí)會(huì)修改之前的己調(diào)度方案：考慮到這會(huì)帶來(lái)一系列的額外開(kāi)銷，他 用一個(gè)移位懲罰函數(shù)來(lái)評(píng)估這個(gè)開(kāi)銷，然后提出了一種采用線性規(guī)劃算法的解決 方案。 b e a s l e y 提出的模型的最大貢獻(xiàn)在于不但考慮了航班延誤帶來(lái)的開(kāi)銷，而且 考慮了航班通過(guò)加速來(lái)提前著陸帶來(lái)的額外開(kāi)銷，加上航班間的安全著陸間隔和 航班的著陸時(shí)間窗的約束，從而將航班著陸調(diào)度問(wèn)題模型化為一個(gè)帶約束的復(fù)雜 優(yōu)化問(wèn)題。在此之后，該模型得到了眾多研究者的承認(rèn)，作為一個(gè)被廣泛接受的 航班著陸調(diào)度問(wèn)題的標(biāo)準(zhǔn)模型，不斷有新的方法被提出以提高調(diào)度的效果和算法 的運(yùn)行速度。 c i e s i e l s k i ( 1 9 9 7 ) 引入遺傳算法以解決這個(gè)問(wèn)題。在他的方法中，每架航班的 著陸時(shí)間和跑道被編碼為基因，采用交叉和變異算子，并利用精英池保存1 0 的最好的個(gè)體。其中，通過(guò)計(jì)算調(diào)度方案造成的總著陸耗費(fèi)來(lái)比較個(gè)體的優(yōu)劣； 而為了剔除違反約束的個(gè)體，違反約束的個(gè)體會(huì)導(dǎo)致在總耗費(fèi)上加上一個(gè)比較大 的耗費(fèi)。實(shí)驗(yàn)表明，遺傳算法對(duì)解決這個(gè)組合優(yōu)化問(wèn)題比線性規(guī)劃方法要快得多， 雖然有時(shí)無(wú)法達(dá)到全局收斂、得到最好的調(diào)度結(jié)果，但是在實(shí)時(shí)性問(wèn)題的解決上 比線性規(guī)劃方法更進(jìn)了一步。之后，c i e s i e l s k i ( 1 9 9 8 ) 又加入改進(jìn)，采用了帶滑動(dòng) 窗口的遺傳算法來(lái)解決，并在悉尼機(jī)場(chǎng)的航班數(shù)據(jù)上進(jìn)行了驗(yàn)證計(jì)算。 r a n d a l l ( 2 0 0 4 ) 弓i 入蟻群算法，將每架飛機(jī)的有限可能著陸時(shí)刻( 設(shè)為整數(shù)) 看成 若干條路徑，讓蟻群在這些路徑上不斷演化，得到最短路徑。 相對(duì)近期的研究成果是p i n o l ( 2 0 0 7 ) 弓l 入禁忌表搜索和生態(tài)算法來(lái)求解航班 著陸調(diào)度問(wèn)題。這兩種方法都是遺傳算法的變種，也屬于啟發(fā)式隨機(jī)搜索算法的 4 第1 章引言 范疇。二者采用不同的雙親選擇策略，通過(guò)過(guò)濾相同的著陸順序的個(gè)體來(lái)維持群 體的多樣性。這為我們將問(wèn)題分成兩個(gè)部分來(lái)解決提供了直接的技術(shù)依據(jù)。 總之，航班著陸調(diào)度是一個(gè)典型的組合優(yōu)化問(wèn)題，其存在的多約束等復(fù)雜性 使得這一問(wèn)題成為公認(rèn)的一個(gè)難解問(wèn)題；同時(shí)，應(yīng)用時(shí)的調(diào)度實(shí)時(shí)性要求進(jìn)一步 增加了這一問(wèn)題的求解難度。目前，業(yè)內(nèi)實(shí)際采用的先來(lái)先服務(wù)調(diào)度方案簡(jiǎn)單快 速，但它無(wú)法進(jìn)一步提高飛行效率，而且在航班較密集的情況下該算法可能無(wú)法 給出合理的調(diào)度方案；研究界提出的線性規(guī)劃算法具有高效性和正確性，但缺乏 全局搜索能力，在很多情況下很難找到最優(yōu)解：遺傳算法、蟻群算法等計(jì)算智能 算法是近年來(lái)解決航班著陸調(diào)度問(wèn)題的一個(gè)研究熱點(diǎn)，但計(jì)算代價(jià)過(guò)大，特別是 在較為繁忙的機(jī)場(chǎng)終端區(qū)，所以它需要結(jié)合有效的啟發(fā)式方法才能更好的解決航 班著陸調(diào)度問(wèn)題。 1 4 主要工作和內(nèi)容安排 1 4 1 本文的主要工作 本文重點(diǎn)研究機(jī)場(chǎng)終端區(qū)航班著陸調(diào)度問(wèn)題的快速優(yōu)化方法。在充分調(diào)研現(xiàn) 有航班著陸調(diào)度優(yōu)化方法之后，選擇了一種與實(shí)際航班著陸調(diào)度較為吻合的航班 著陸調(diào)度模型，設(shè)計(jì)了一種基于元胞自動(dòng)機(jī)的航班著陸調(diào)度優(yōu)化算法。實(shí)驗(yàn)表明， 該算法能快速得到較優(yōu)的航班著陸順序和在此基礎(chǔ)上的最優(yōu)著陸時(shí)間。 總之，本文的主要研究工作與特色包括： 1 ) 引入元胞自動(dòng)機(jī)來(lái)模擬航班著陸過(guò)程，建立了基于元胞自動(dòng)機(jī)的航班著陸調(diào) 度模型。其中，特別將航班的著陸時(shí)間窗借由元胞狀態(tài)的速度窗來(lái)控制；通 過(guò)將終端區(qū)映射到一條單行道上來(lái)簡(jiǎn)化航班著陸飛行過(guò)程，使元胞自動(dòng)機(jī)的 模擬更加形象。進(jìn)一步，針對(duì)航班著陸調(diào)度的特點(diǎn)，設(shè)計(jì)了可以優(yōu)化航班著 陸調(diào)度的元胞自動(dòng)機(jī)規(guī)則。 2 ) 針對(duì)航班著陸問(wèn)題的特點(diǎn)，提出了一個(gè)本地優(yōu)化方法來(lái)優(yōu)化航班著陸時(shí)間。 通過(guò)將航班著陸序列分成一個(gè)個(gè)緊密聯(lián)系的航班子序列，通過(guò)整體調(diào)整子序 列的方法來(lái)優(yōu)化航班著陸的時(shí)間。 3 ) 設(shè)計(jì)了一個(gè)深度優(yōu)先搜索算法來(lái)優(yōu)化航班著陸順序。本文設(shè)計(jì)了一個(gè)遺傳算 法和一個(gè)深度優(yōu)先搜索算法，在之前步驟的基礎(chǔ)上進(jìn)一步尋優(yōu)航班著陸順 序，通過(guò)對(duì)比實(shí)驗(yàn)確定了深度優(yōu)先搜索作為本文方法的最后一個(gè)尋優(yōu)步驟。 第1 章引言 1 4 2 本文的內(nèi)容安排 本文內(nèi)容共分為五章： 第1 章引言。介紹航班著陸調(diào)度的研究背景，研究意義和研究現(xiàn)狀。 第2 章終端區(qū)航班隊(duì)列調(diào)度模型與方法。介紹航班著陸調(diào)度模型，并介紹 了以往提出的較經(jīng)典的方法，特別是針對(duì)航班著陸調(diào)度模型的現(xiàn)有的各種典型的 調(diào)度方法。 第3 章基于元胞自動(dòng)機(jī)的航班著陸優(yōu)化方法。分三個(gè)部分介紹了我們的算 法。首先，介紹如何元胞自動(dòng)機(jī)引入航班著陸優(yōu)化；然后，介紹用于優(yōu)化航班著 陸時(shí)間的本地優(yōu)化算法；最后介紹了用于進(jìn)一步優(yōu)化航班著陸順序的算法( 遺傳 算法和深度優(yōu)先算法) 。由于我們的算法是基于元胞自動(dòng)機(jī)的，我們稱之為 c e l l u l a ra u t o m a t ab a s e do p t i m i z a t i o n ( c a o ) 。 第4 章實(shí)驗(yàn)及結(jié)果分析。介紹了驗(yàn)證本文方法的幾組實(shí)驗(yàn)并分析實(shí)驗(yàn)結(jié)果， 包括元胞自動(dòng)機(jī)的參數(shù)選取實(shí)驗(yàn)、不同元胞自動(dòng)機(jī)規(guī)則實(shí)驗(yàn)、不同后續(xù)優(yōu)化算法 實(shí)驗(yàn)以及驗(yàn)證本文方法有效性和實(shí)時(shí)性的實(shí)驗(yàn)。通過(guò)參數(shù)選取的實(shí)驗(yàn)確定其余實(shí) 驗(yàn)中使用的元胞自動(dòng)機(jī)參數(shù)。通過(guò)不同元胞自動(dòng)機(jī)規(guī)則對(duì)比明確了我們的優(yōu)化規(guī) 則的思路正確性。通過(guò)比較遺傳算法和確定深度優(yōu)先搜索算法，確定深度優(yōu)先搜 索算法作為完整優(yōu)化算法的組成部分。在和以往算法的結(jié)果對(duì)比實(shí)驗(yàn)中證實(shí)了 c a o 的有效性和實(shí)時(shí)性。在最后，通過(guò)對(duì)比c a o 三步驟結(jié)果，確認(rèn)了c a o 三 步驟的必要性。 第5 章總結(jié)與展望?？偨Y(jié)本文的主要貢獻(xiàn)，提出兩點(diǎn)未來(lái)可能的研究方向。 6 第2 章機(jī)場(chǎng)終端區(qū)航班隊(duì)列調(diào)度模型與方法 第2 章終端區(qū)航班隊(duì)列調(diào)度模型與方法 本章首先簡(jiǎn)要介紹航班著陸調(diào)度問(wèn)題，概括這一問(wèn)題的特點(diǎn)；之后介紹用于 解決航班著陸調(diào)度問(wèn)題的幾種典型方法，包括先來(lái)先服務(wù)算法、線性規(guī)劃算法和 啟發(fā)式搜索算法等；最后對(duì)比分析了這些算法。 2 1 航班著陸調(diào)度問(wèn)題 航班著陸調(diào)度的目的是：通過(guò)調(diào)度在終端區(qū)的航班的著陸時(shí)間，在確保安全 性的前提下，最小化調(diào)整航班著陸時(shí)間帶來(lái)的額外開(kāi)銷。本節(jié)將簡(jiǎn)介航班著陸調(diào) 度問(wèn)題的定義，并在其后給出航班著陸調(diào)度模型的數(shù)學(xué)描述。 2 2航班著陸調(diào)度定義 航班航行過(guò)程中，在機(jī)場(chǎng)終端區(qū)最容易受到機(jī)場(chǎng)擁擠等因素的影響，調(diào)度會(huì) 導(dǎo)致航班需要通過(guò)空中等待或者加速來(lái)確定具體的著陸時(shí)間并在此時(shí)間著陸。在 這個(gè)過(guò)程中，油耗的增加、顧客的滿意度下降等因素會(huì)增加額外的開(kāi)銷，給航空 公司等部門(mén)造成巨大的經(jīng)濟(jì)損失。因此，對(duì)終端區(qū)進(jìn)場(chǎng)航班進(jìn)行合理的排序和管 理，使航班安全有序地著陸，并保證航班著陸的額外開(kāi)銷盡可能小，成為了航班 著陸調(diào)度的研究重點(diǎn)。 航班著陸調(diào)度問(wèn)題是終端區(qū)交通流量管理的核心內(nèi)容之一。該調(diào)度指的是針 對(duì)給定的待著陸航班隊(duì)列( 其中包含各航班的預(yù)計(jì)著陸時(shí)間和時(shí)間窗約束等參 數(shù)) ，在滿足各種約束條件的同時(shí)給出一個(gè)合理的調(diào)度方案，其中包括隊(duì)列中每 架航班的著陸時(shí)間。這里的約束條件包括航班的著陸時(shí)間窗限制和航班之間的最 小著陸間隔限制。 在航班進(jìn)入機(jī)場(chǎng)的空中管銅j ( h t c ) 雷達(dá)區(qū)域后，它會(huì)要求空中管匍j ( h t c ) 為其 分配一個(gè)著陸時(shí)間，稱為廣播時(shí)間。航班的著陸時(shí)間必須控制在一個(gè)特定的時(shí)間 窗口中，時(shí)間窗口由最早著陸時(shí)間和最晚著陸時(shí)間規(guī)定。不同的飛機(jī)的時(shí)間窗大 小和相對(duì)預(yù)計(jì)著陸時(shí)間的偏移是不定的。最早著陸時(shí)間和航班的最快速度有關(guān)， 航班以最快速度飛行最快能著陸的時(shí)刻就是它的最早著陸時(shí)間。最晚著陸時(shí)間和 飛機(jī)的載油量有關(guān)，飛機(jī)以最省油的方式飛行不斷在空中等待直到燃油耗光著陸 的時(shí)間就是它的最晚著陸時(shí)間。 每架飛機(jī)都有一個(gè)最經(jīng)濟(jì)的飛行速度，稱作巡航速度，飛機(jī)以這種速度飛行 第2 章機(jī)場(chǎng)終端區(qū)航班隊(duì)列調(diào)度模型與方法 時(shí)額外開(kāi)銷( 燃料耗費(fèi)等) 最小。一架飛機(jī)以巡航速度飛行且不作空中等待就著 陸的著陸時(shí)間稱為該飛機(jī)的最佳著陸時(shí)間或目標(biāo)著陸時(shí)間。如果空中管制要求飛 機(jī)加速或減速，飛機(jī)會(huì)產(chǎn)生額外開(kāi)銷( 燃料耗費(fèi)等) ，這個(gè)開(kāi)銷會(huì)隨著飛機(jī)的加 減速幅度增大而增大，表現(xiàn)在航班著陸時(shí)間上就是航班的額外開(kāi)銷隨航班著陸時(shí) 間和最佳著陸時(shí)間偏差的增大而增大。 任意一架飛機(jī)和這架飛機(jī)之后的飛機(jī)之間的著陸時(shí)間差必須大于一個(gè)規(guī)定 的最小值( 間隔時(shí)間) ，這稱作航班著陸的安全間隔約束約束。安全間隔約束是 從空氣動(dòng)力學(xué)角度考慮的。( b e a s l e y2 0 0 0 ) 舉個(gè)例子，一架波音7 4 7 在飛行時(shí)會(huì)在 尾部產(chǎn)生大量的空氣湍流( 尾跡渦) ，如果之后的飛機(jī)飛行得過(guò)近就會(huì)失去氣動(dòng) 穩(wěn)定性。實(shí)際上確實(shí)有不少飛機(jī)事故被認(rèn)為是由這種情況產(chǎn)生的( m u l l i n s1 9 9 6 ) 。 所以為了安全方面的原因，波音7 4 7 著陸之后其他的飛機(jī)必須要在它著陸之后過(guò) 一段時(shí)間才能著陸。相對(duì)來(lái)說(shuō)，輕型飛機(jī)產(chǎn)生的尾跡渦非常小，所以其他飛機(jī)在 這種飛機(jī)著陸以后很快就可以著陸了。飛機(jī)起飛時(shí)，因?yàn)橄嗤脑蛞矔?huì)需要有 類似的延遲操作。國(guó)際民航組織( i c a o ) 依據(jù)允許最大起飛重量將飛機(jī)分為重型 機(jī)、中型機(jī)、輕型機(jī)，并規(guī)定了無(wú)風(fēng)條件下不同類型飛機(jī)之間尾流間隔的最低標(biāo) 準(zhǔn)。大型機(jī)比如波音7 4 7 自身能夠產(chǎn)生很強(qiáng)的尾流，同時(shí)也能夠承受很強(qiáng)的尾流 而不至于失控。安全間隔不僅和兩架航班的機(jī)型相關(guān)，還和兩架航班的相對(duì)位置 有關(guān)。如果前機(jī)是大型機(jī)，后機(jī)是輕型機(jī)，則這兩架航班之間的最小時(shí)間間隔一 定大于前機(jī)是輕型機(jī)，后機(jī)是大型機(jī)的情況。 d e a r ( 1 9 7 6 ) 對(duì)航班著陸調(diào)度問(wèn)題做了研究，指出航班調(diào)度可以分為靜態(tài)航班 調(diào)度和動(dòng)態(tài)航班調(diào)度兩種。靜態(tài)航班調(diào)度是指待調(diào)度的航班隊(duì)列是固定不變的， 算法只需要給出最優(yōu)的調(diào)度方案即可，并沒(méi)有考慮航班到達(dá)加入隊(duì)列以及航班著 陸離開(kāi)隊(duì)列的情況；動(dòng)態(tài)航班調(diào)度中，待調(diào)度的航班隊(duì)列是隨時(shí)間的改變而改變 的，每當(dāng)待調(diào)度的航班隊(duì)列發(fā)生變化時(shí)，模型需要在原來(lái)調(diào)度結(jié)果的基礎(chǔ)上進(jìn)行 重新優(yōu)化，并給出新的調(diào)度結(jié)果。 關(guān)于動(dòng)態(tài)優(yōu)化更新時(shí)機(jī)的選擇，我們可以歸納為事件驅(qū)動(dòng)型，時(shí)間驅(qū)動(dòng)型以 及事件、時(shí)間混合驅(qū)動(dòng)型。對(duì)于事件驅(qū)動(dòng)型，當(dāng)有新航班到達(dá)時(shí)，需要對(duì)新的隊(duì) 列進(jìn)行優(yōu)化。因?yàn)楹桨嗟竭_(dá)時(shí)間具有隨機(jī)性，當(dāng)多架航班同時(shí)或連續(xù)小時(shí)間間隔 從不同航路進(jìn)入終端區(qū)，將導(dǎo)致優(yōu)化過(guò)程短時(shí)間連續(xù)啟動(dòng)，對(duì)優(yōu)化算法實(shí)時(shí)性的 設(shè)計(jì)是一個(gè)極大的挑戰(zhàn)；對(duì)于時(shí)間驅(qū)動(dòng)型，以雷達(dá)掃描周期6 s ( 或倍數(shù)) 為單 位，當(dāng)雷達(dá)信息更新時(shí)，啟動(dòng)優(yōu)化算法，對(duì)隊(duì)列進(jìn)行優(yōu)化。相比事件驅(qū)動(dòng)型，時(shí) 間驅(qū)動(dòng)型以雷達(dá)周期為優(yōu)化間隔，更加符合管制實(shí)際，同時(shí)避免了短時(shí)間頻繁更 新。但有可能雷達(dá)信息更新時(shí)刻，無(wú)新的到達(dá)事件發(fā)生，這時(shí)并沒(méi)有必要進(jìn)行優(yōu) 化操作，反而增加了系統(tǒng)開(kāi)銷；對(duì)于事件、時(shí)間混合驅(qū)動(dòng)型，以時(shí)間驅(qū)動(dòng)型為基 第2 章機(jī)場(chǎng)終端區(qū)航班隊(duì)列調(diào)度模型與方法 礎(chǔ)，在雷達(dá)信息更新時(shí)，探測(cè)是否有新的航班到達(dá)事件，如沒(méi)有，則不進(jìn)行優(yōu)化： 反之，則對(duì)新的隊(duì)列進(jìn)行優(yōu)化。 2 2 1 航班著陸調(diào)度的模型描述 航班的著陸時(shí)間必須控制在一個(gè)特定的時(shí)間窗口中，時(shí)間窗口由最早著陸時(shí) e 間和最晚著陸時(shí)間規(guī)定。不同的飛機(jī)的時(shí)間窗大小和偏移是不定的。最早著 陸時(shí)間巨表示第f 架飛機(jī)以最大速度飛行能最早著陸的時(shí)間。最晚著陸時(shí)間工表 示第i 架飛機(jī)以最省油的速度飛行時(shí)，飛機(jī)的油量能支持其飛行的最長(zhǎng)時(shí)間之后 的著陸時(shí)間。 每架飛機(jī)都有一個(gè)最經(jīng)濟(jì)，最合適的飛行速度，稱作巡航速度。一架飛機(jī)如 果被調(diào)度為最佳著陸時(shí)間( 目標(biāo)著陸時(shí)間z ) ，它就能以巡航速度飛行直到著陸。 如果空中管制要求飛機(jī)加速或減速，就會(huì)產(chǎn)生額外的開(kāi)銷。這個(gè)開(kāi)銷會(huì)隨著飛機(jī) 的著陸時(shí)間和最佳著陸時(shí)間偏差的增大而增大。當(dāng)飛機(jī)在最佳著陸時(shí)間之前著 陸，會(huì)有一個(gè)隨著提前著陸時(shí)間增加以系數(shù)g 線性增加的額外開(kāi)銷，若飛機(jī)晚 于最佳著陸時(shí)間著陸，會(huì)有一個(gè)隨著延后著陸時(shí)間增加以系數(shù)忽線性增加的額外 開(kāi)銷。 航班f 和航班之間的最短著陸間隔表示為s ，。圖2 1 為該模型的約束示意 圖： 航班廠_ 厶 飛+ 卜一 e i t i x i l i 時(shí)間窗 航班j 圖2 1 航班著陸調(diào)度( a l s ) 模型示意圖 綜合以上所述，航班著陸調(diào)度參數(shù)定義如下： 尸表示航班數(shù)量 9 第2 章機(jī)場(chǎng)終端區(qū)航班隊(duì)列調(diào)度模型與方法 r 表示航班f 的預(yù)計(jì)著陸時(shí)間 e ，表示航班f 的最早著陸時(shí)間 厶表示航班f 的最遲著陸時(shí)間 置表示航班f 的調(diào)度后著陸時(shí)間 s ，表示航班f 和航班，之間的最小時(shí)間間隔，航班f 在航班之前著陸時(shí) & 表示航班f 先于預(yù)計(jì)著陸時(shí)間z 著陸的單位成本系數(shù) 扛表示航班f 后于預(yù)計(jì)著陸時(shí)間z 著陸的單位成本系數(shù) 時(shí)間窗約束：由著陸時(shí)間窗的規(guī)定，航班調(diào)度著陸時(shí)間必須在區(qū)間【巨，厶】 中，這使得航班受調(diào)度后著陸時(shí)間墨必須要滿足如下公式： 互誓厶( f = l d( 2 1 ) 安全間隔約束：每架航班必須與之前的航班保持一定的著陸時(shí)間間隔，即每 兩架航班f 和的著陸調(diào)度時(shí)間( 其中f 在7 之前著陸) 之差必須大于規(guī)定值，即 x j - 五品o = 1 ，只j = 1 ，只i d ( 2 2 ) 安全間隔約束是為了保證在一架飛機(jī)之后著陸的所有飛機(jī)都不會(huì)受此飛機(jī)的尾 跡渦影響，從而保證之后飛機(jī)的著陸安全。所以只要是在航班f 之后著陸的所有 航班的著陸時(shí)間都必須滿足與它的著陸時(shí)間的安全間隔約束，而不僅僅是相鄰的 航班需要滿足此約束。從這點(diǎn)可以看出航班著陸問(wèn)題的約束數(shù)目很可觀。 t i 圖2 2 額外開(kāi)銷和著陸時(shí)刻的關(guān)系 航班調(diào)度的目的是在符合約束的基礎(chǔ)上最小化航班的著陸額外開(kāi)銷。著陸過(guò) 程中每架航班的額外開(kāi)銷與航班著陸時(shí)間和最佳著陸時(shí)間之差( 以下稱為著陸偏 l o 第2 章機(jī)場(chǎng)終端區(qū)航班隊(duì)列調(diào)度模型與方法 移時(shí)間) 有關(guān)。此開(kāi)銷和著陸偏移時(shí)間的關(guān)系如圖2 2 所示， 銷的公式表示如下： ，一j 蜀( 巧一x i ) z 【紅( 毛一z ) z 1 ) ( 2 6 ) 黽=+ 墨，島) ，氣) ( = 1 ，一， ) p 一7 i 取下一架飛機(jī) 鉗 當(dāng)前航班的降航班降落時(shí)間為 落時(shí)間定為t i r a i n t i ，) 【( 1 一l ，+ s ( 1 一1 ) ，i ) 否 分段調(diào)整隊(duì)列 降落時(shí)間 圖2 4 改進(jìn)的先來(lái)先服務(wù)算法流程圖 基于先來(lái)先服務(wù)算法，有一些改進(jìn)被加入其中，比如在航班總隊(duì)列中選取能 夠調(diào)整的組，通過(guò)調(diào)整組頭尾航班的著陸時(shí)間來(lái)提升總體效果，降低航班隊(duì)列總 著陸耗費(fèi)，則改進(jìn)的算法流程如圖2 4 所示。 2 4 2 基于c p s 的航班著陸調(diào)度方法 c p s 是c o n s t r a i n e dp o s i t i o ns h i f t i n g 的縮寫(xiě)，意即受限位置偏移。由于可操 作性的限制，航班在著陸調(diào)度中在隊(duì)列中不能作相對(duì)于f c f s 順序的大的移位。 比如，若航班f 在f c f s 隊(duì)列中的位置為鼻位，則在調(diào)度之后的著陸隊(duì)列中，其 第2 章機(jī)場(chǎng)終端區(qū)航班隊(duì)列調(diào)度模型與方法 位置必須在區(qū)間f 只一七，鼻+ j i 】中。其中j 為受限偏移半徑，表示調(diào)度后位置的偏 移量的最大值。這樣，就可以通過(guò)構(gòu)造一個(gè)c p s 網(wǎng)絡(luò)來(lái)窮舉可能的航班著陸順 序，從而來(lái)搜索最優(yōu)的航班著陸調(diào)度順序。( b a l 婦i s h n a n2 0 0 6 ) 表2 1 刀= 5 ，k = l 時(shí)可能的航班分配 位置l23 4 5 11234 可能的航 22345 班分配 3 45 如表2 1 所示，k = l 時(shí)著陸隊(duì)列的每個(gè)位置可能有最多三個(gè)可能的航班。依 靠這樣的表就能得到如圖2 5 所示的c p s 網(wǎng)絡(luò)，通過(guò)構(gòu)建這樣的網(wǎng)絡(luò)可以窮舉所 有可能的航班著陸順序。 廠s l a g e l 、廠s l a g e2 、廠s l a g e 3 、，s l a g e 4 、，s l a g e 5 、 1 - 2 - 3 k 1 - 2 4 i 一1 2 - 3i l2 i 一1 2f l 1 - 2 - 5 l - l 1 - 2 4 l l1 l 、2 - 3 5 一一一一 f 乃體s 心 l 、 j 2 4 5一一1 - 孓2 、 1 4 3 、 1 fi 1 - 3 k 。| 嬉f q2 “ 、f1 一弘l 7 7 2 - 卜 、 2 2 _ 1 k j 一2 - 1 - 3 ， n 2 3 5k 抖5 | 、i2 3 kl f 1 2 4 3k 1 州l 厶4 1 5 ltt i | _ 似5 | 2 - 卜 例形 ， n 3 。5 、抖5 圖2 5 甩= 5 ，k = 1 的c p s 網(wǎng)絡(luò)示意圖 從圖2 5 可以看出，有很多節(jié)點(diǎn)是冗余的，它們并不能形成一個(gè)有效的著陸 1 4 第2 章機(jī)場(chǎng)終端區(qū)航班隊(duì)列調(diào)度模型與方法 順序，如1 2 3 4 ，1 - 2 3 5 等等。這時(shí)需要采用剪枝策略剪去不需要的路徑，剪 枝完畢的網(wǎng)絡(luò)如圖2 6 所示。 采用c p s 方法可以很容易得到以最大流量為目的的航班調(diào)度最優(yōu)方案。對(duì)于航 班偏離最佳著陸時(shí)間著陸產(chǎn)生最小額外開(kāi)銷為目的的航班調(diào)度，由于依靠著陸順 序得到最優(yōu)