基于nsga的多機(jī)場地面等待問題優(yōu)化模型

基于nsga的多機(jī)場地面等待問題優(yōu)化模型

近年來，多機(jī)場的地面等待問題一直是國內(nèi)外學(xué)術(shù)界研究的重點(diǎn)。其主要策略是調(diào)整幾個(gè)相關(guān)機(jī)場的出發(fā)和下降時(shí)間，并合理分配不可避免的總延誤時(shí)間。優(yōu)化多機(jī)場的飛機(jī)時(shí)間，提前緩解機(jī)場繁忙時(shí)間的運(yùn)輸壓力，解決基于航班時(shí)間優(yōu)化的多機(jī)場的地面等待問題，有效提高機(jī)場運(yùn)營效率和安全性。因此，本文根據(jù)航班時(shí)間優(yōu)化的多機(jī)場地面等待問題的理論和方法，合理制定了航機(jī)時(shí)間預(yù)算，是控制航空運(yùn)輸流量的基礎(chǔ)。文獻(xiàn)根據(jù)地面等待策略(groundholdingproblem,GHP),結(jié)合各種優(yōu)化模型和算法,解決多機(jī)場地面等待問題.文獻(xiàn)提出了基于整數(shù)規(guī)劃的多機(jī)場地面等待問題優(yōu)化模型.文獻(xiàn)對文獻(xiàn)的模型進(jìn)行了進(jìn)一步研究,提出在多機(jī)場模型中加入航路容量限制,建立了多元受限的網(wǎng)絡(luò)流模型,并采用啟發(fā)式算法求解該模型.文獻(xiàn)提出了基于序列約束的多機(jī)場地面等待問題模型.文獻(xiàn)提出了用分解式(disaggregate)整數(shù)規(guī)劃模型求解航班的離場時(shí)間和飛行路線.文獻(xiàn)將航空公司優(yōu)先權(quán)引入文獻(xiàn)的模型中.文獻(xiàn)提出了動(dòng)態(tài)、隨機(jī)的多機(jī)場地面等待問題整數(shù)規(guī)劃模型.文獻(xiàn)建立了多元受限的地面等待問題模型,并將啟發(fā)式算法和專家系統(tǒng)相結(jié)合,對模型求解.文獻(xiàn)建立了空中交通短期流量管理的動(dòng)態(tài)網(wǎng)絡(luò)流量模型.文獻(xiàn)研究了管制區(qū)短期空中交通流量管理問題,并提出了時(shí)隙-航線分配模型和算法.綜上所述,在多機(jī)場地面等待問題的研究中,建立的模型都是以系統(tǒng)的總延誤成本最小為單目標(biāo),因此,經(jīng)常造成個(gè)別航班超長時(shí)間延誤,無法滿足實(shí)際運(yùn)行需要.隨著模型中機(jī)場數(shù)量的增加,機(jī)場之間的耦合又會(huì)使航班優(yōu)化的求解空間迅速變得復(fù)雜起來,采用普通的整數(shù)規(guī)劃方法難以對其進(jìn)行有效處理,形成NP(non-deterministicpolynomial)型難題的組合優(yōu)化問題.因此,本文以航班時(shí)刻表為基礎(chǔ),考慮空域容量、飛機(jī)周轉(zhuǎn)等運(yùn)行限制,建立了一種多目標(biāo)、多機(jī)場的地面等待問題整數(shù)規(guī)劃模型,并采用NSGA-Ⅱ算法(non-dominatedsortinggeneticalgorithmII)進(jìn)行求解,用實(shí)例進(jìn)行了驗(yàn)證分析,表明了本文模型的正確性和有效性.1實(shí)現(xiàn)約束條件下的總有機(jī)回歸為建立多目標(biāo)、多機(jī)場地面等待問題模型,構(gòu)建一個(gè)以目標(biāo)機(jī)場集合Q為核心的開放型網(wǎng)絡(luò).對于從目標(biāo)機(jī)場集合Q中起飛的航班,采用地面等待策略對航班進(jìn)行調(diào)配;對于不在目標(biāo)機(jī)場集合Q中起飛、而在Q中降落的航班,采用空中等待策略對航班進(jìn)行調(diào)配.在進(jìn)行航班時(shí)刻優(yōu)化調(diào)整時(shí),根據(jù)實(shí)際需要,提出以下4個(gè)目標(biāo)函數(shù):(1)總延誤時(shí)間最少,即:min∑q∈Q∑f∈F∑t∈Γ[(t-Τd,f)(Xq,f,t-Xq,f,t-1)+(t-Τa,f)(Yq,f,t-Yq,f,t-1)]min∑q∈Q∑f∈F∑t∈Γ[(t?Td,f)(Xq,f,t?Xq,f,t?1)+(t?Ta,f)(Yq,f,t?Yq,f,t?1)],(2)總延誤成本最小,即:min∑q∈Q∑f∈F∑t∈Γ[(t-Τd,f)(Xq,f,t-Xq,f,t-1)Cg+(t-Τa,f)(Yq,f,t-Yq,f,t-1)Ca]min∑q∈Q∑f∈F∑t∈Γ[(t?Td,f)(Xq,f,t?Xq,f,t?1)Cg+(t?Ta,f)(Yq,f,t?Yq,f,t?1)Ca],(3)總調(diào)整航班架次最少,即:min∑q∈Q∑f∈F∑t∈Γ[Ag,f(Xq,f,t-Xq,f,t-1)+Aa,f(Yq,f,t-Yq,f,t-1)]min∑q∈Q∑f∈F∑t∈Γ[Ag,f(Xq,f,t?Xq,f,t?1)+Aa,f(Yq,f,t?Yq,f,t?1)],(4)總延誤航班(延誤時(shí)間超過15min)架次最少,即:min∑q∈Q∑f∈F∑t∈Γ[Dg,f(Xq,f,t-Xq,f,t-1)+Da,f(Yq,f,t-Yq,f,t-1)]min∑q∈Q∑f∈F∑t∈Γ[Dg,f(Xq,f,t?Xq,f,t?1)+Da,f(Yq,f,t?Yq,f,t?1)],約束條件如下:Xq,f,t-Xq,f,t-1≥0,?f∈F,q∈Q,t∈{Td,f,Td,f+1,…,T+1},(1)Yq,f,t-Yq,f,t-1≥0,?f∈F,q∈Q,t∈{Ta,f,Ta,f+1,…,T+1},(2)∑f∈Κt(Xq,f,t-Xq,f,t-1)-Τa,f-Sf≤0??f∈Κ,q∈Q,t∈{Τa,f,Τa,f+1,?,Τ+1},(3)∑f∈Kt(Xq,f,t?Xq,f,t?1)?Ta,f?Sf≤0??f∈K,q∈Q,t∈{Ta,f,Ta,f+1,?,T+1},(3)∑f∈Κt(Yq,f,t-Yq,f,t-1)-Τd,f-Sf≤0,?f∈F,q∈Q,t∈{Τd,f,Τd,f+1??,Τ+1},(4)∑f∈Kt(Yq,f,t?Yq,f,t?1)?Td,f?Sf≤0,?f∈F,q∈Q,t∈{Td,f,Td,f+1??,T+1},(4)∑f∈FXq,f,t+∑f∈FYq,f,t≤Μt,q,?f∈F,q∈Q,t∈{Τ1,2,?,Τ+1},(5)Xq,f,T+1=1,Yq,f,T+1=1,(6)式中:F為在目標(biāo)機(jī)場起飛、降落的航班集合;K為連程航班集合,K?F;Γ={1,2,…,T}為時(shí)間片集合,T為時(shí)間片數(shù)量;Mt,q為q機(jī)場在時(shí)間片t內(nèi)的動(dòng)態(tài)容量,其中t∈Γ,q∈Q;Ta,f為航班f預(yù)計(jì)到達(dá)目標(biāo)機(jī)場時(shí)間所屬的時(shí)間片,其中f∈F,Ta,f∈Γ;Td,f為航班f預(yù)計(jì)從目標(biāo)機(jī)場起飛時(shí)間所屬的時(shí)間片,其中f∈F,Td,f∈Γ;Sf為航班f的最小周轉(zhuǎn)時(shí)間,其中f∈K;Ag,f為航班地面等待調(diào)整參數(shù),Ag,f={1,航班f執(zhí)行地面等待,0,否則;Aa,f為航班空中等待調(diào)整參數(shù),Aa,f={1,航班f執(zhí)行空中等待,0,否則;Dg,f為航班地面延誤參數(shù),Dg,f={1,航班f地面等待時(shí)間＞15min,0,否則;Da,f為航班空中延誤參數(shù),Da,f={1,航班f空中等待時(shí)間＞15min,0,否則;Cg為地面等待單位成本;Ca為空中等待單位成本;Xf,t,q和Yf,t,q為決策變量采用二進(jìn)制的階躍函數(shù),Xf,t,q={1,航班f在時(shí)間片t內(nèi)從機(jī)場q起飛,0,否則,Yf,t,q={1,航班f在時(shí)間片t內(nèi)到達(dá)機(jī)場q,0,否則,t∈Γ,q∈Q,f∈F.假設(shè)在第T+1個(gè)時(shí)間片機(jī)場容量為無限大.約束條件(1)保證了決策變量Xq,f,t的非遞減性,即如果航班預(yù)計(jì)在時(shí)間片τ從機(jī)場q起飛,則所有Xq,f,t在t>τ時(shí)都為1.約束條件(2)保證了決策變量Yq,f,t+1的非遞減性,即如果航班預(yù)計(jì)在時(shí)間片τ在機(jī)場q降落,則Yq,f,t在t>τ時(shí)都為1.約束條件(3)保證航班f的空中等待時(shí)間不會(huì)影響它的后續(xù)航班.約束條件(4)保證航班f的地面等待時(shí)間不會(huì)影響它的后續(xù)航班.約束條件(5)是相關(guān)機(jī)場的起飛、降落容量限制.約束條件(6)保證了所有執(zhí)行空中等待和地面等待的航班在最終時(shí)間片T+1前都能到達(dá)目的機(jī)場.2數(shù)據(jù)初始算法建立NSGA-Ⅱ算法是一種基于Pareto最優(yōu)解的多目標(biāo)進(jìn)化算法,它在解決多目標(biāo)優(yōu)化時(shí),無需對各種目標(biāo)進(jìn)行歸一化處理,具有快速、均勻、多樣性的優(yōu)點(diǎn).針對本文建立的數(shù)學(xué)模型,多種目標(biāo)很難進(jìn)行歸一化處理,且計(jì)算量龐大,因此,本文采用NSGA-Ⅱ算法對模型進(jìn)行求解.根據(jù)NSGA-Ⅱ算法,利用獎(jiǎng)、罰函數(shù)技術(shù)制約算法的適應(yīng)度函數(shù),基于NSGA-Ⅱ的航班時(shí)刻優(yōu)化算法流程如圖1所示.(1)讀取航班相關(guān)數(shù)據(jù).從數(shù)據(jù)庫中讀取模型所需的基本信息,包括多機(jī)場系統(tǒng)中的航班號、起飛機(jī)場名稱、降落機(jī)場名稱、航班預(yù)計(jì)起飛時(shí)間、航班預(yù)計(jì)降落時(shí)間、航班周轉(zhuǎn)時(shí)間、連程航班信息、機(jī)場動(dòng)態(tài)容量等.(2)預(yù)處理航班信息,生成初始個(gè)體.對航班相關(guān)數(shù)據(jù)進(jìn)行預(yù)處理,按要求轉(zhuǎn)變成所需數(shù)據(jù)類型,處理后的數(shù)據(jù)存入航班信息數(shù)據(jù)庫中作為初始個(gè)體.航班信息包括:航班號、起飛機(jī)場名稱、降落機(jī)場名稱、預(yù)計(jì)起飛時(shí)間、預(yù)計(jì)降落時(shí)間、實(shí)際起飛時(shí)間、實(shí)際降落時(shí)間、航班調(diào)整時(shí)間片、最小周轉(zhuǎn)時(shí)間、調(diào)整標(biāo)志位、延誤標(biāo)志位、連程航班標(biāo)志位.(3)設(shè)初始化父種群為U0,種群代數(shù)w=0,從每個(gè)初始個(gè)體中抽取航班的實(shí)際起、降時(shí)間組成基因,通過對航班的實(shí)際起、降時(shí)間及相關(guān)信息進(jìn)行修改,生成初始化父種群.父種群的大小設(shè)置為400.(4)當(dāng)w小于終止代數(shù)時(shí),跳轉(zhuǎn)至(5);否則,算法結(jié)束.(5)確定個(gè)體的多目標(biāo)適應(yīng)度,并對Uw進(jìn)行非支配排序.首先,根據(jù)4個(gè)目標(biāo)函數(shù),結(jié)合各機(jī)場的容量約束條件,應(yīng)用獎(jiǎng)、罰函數(shù),確定多目標(biāo)函數(shù)的適應(yīng)度.對于滿足容量約束條件的個(gè)體,目標(biāo)函數(shù)的適應(yīng)度較高;對于不滿足約束條件的個(gè)體,根據(jù)超出容量約束的時(shí)間片個(gè)數(shù)使用罰函數(shù);對于調(diào)整波動(dòng)小,流量、容量匹配較好的個(gè)體,將根據(jù)匹配較好的個(gè)體數(shù)使用獎(jiǎng)函數(shù).確定多目標(biāo)適應(yīng)度后,依據(jù)個(gè)體適應(yīng)值,對種群Uw進(jìn)行非支配排序.(6)進(jìn)行選擇、交叉和變異,生成子種群Vw.通過選擇操作,優(yōu)化解集將朝Pareto最優(yōu)解集方向移動(dòng),并均勻分布.本文采用錦標(biāo)賽選擇方式,根據(jù)非支配關(guān)系和種群距離進(jìn)行排序.根據(jù)實(shí)際需求,個(gè)體之間的交叉采用多點(diǎn)、多次交叉方式,交叉次數(shù)及交叉點(diǎn)個(gè)數(shù)都取3,交叉點(diǎn)采用隨機(jī)選取方式,交叉系數(shù)取0.6.個(gè)體間的變異采用定點(diǎn)變異和隨機(jī)變異相結(jié)合的方式,以加快收斂速度,本算法中變異系數(shù)取0.1.(7)合并種群Uw與Vw,并進(jìn)行非支配排序,確定種群距離.取種群Uw與新生成種群Vw的并集,合并后種群大小變?yōu)?00,種群內(nèi)的支配關(guān)系及種群距離被破壞,需采用(5)中的非支配算法重新排序,排序完畢后,用種群距離算法重新計(jì)算個(gè)體之間距離.(8)根據(jù)排序結(jié)果和種群距離進(jìn)行精英選擇,生成新種群Uw+1.初始新種群Uw+1取空集,根據(jù)(7)中的非支配排序結(jié)果,逐層對新種群Uw+1進(jìn)行補(bǔ)充,直到達(dá)到種群規(guī)模400為止.如果加入某層個(gè)體后,種群大小大于400,則根據(jù)該層個(gè)體的種群距離,按降序重新選擇(優(yōu)先選擇種群距離大的個(gè)體),直至達(dá)到種群規(guī)模400.(9)種群代數(shù)加1,跳轉(zhuǎn)至(4).3優(yōu)化結(jié)果分析本節(jié)將根據(jù)多目標(biāo)航班時(shí)刻優(yōu)化模型,以我國北京、上海、廣州三大樞紐機(jī)場為研究對象,利用基于NSGA-Ⅱ的算法對航班時(shí)刻進(jìn)行優(yōu)化求解.算法使用整數(shù)編碼方式,以與三大機(jī)場相關(guān)的起、降時(shí)間片為基因,即如果航班從三大機(jī)場起飛,則基因?yàn)槠痫w時(shí)間,調(diào)整后的航班執(zhí)行地面等待;否則,為降落時(shí)間,調(diào)整后的航班執(zhí)行空中等待.因此,染色體的長度由三大機(jī)場在相關(guān)時(shí)間片內(nèi)的航班起降架次決定.利用VC設(shè)計(jì)出多目標(biāo)航班時(shí)刻優(yōu)化系統(tǒng).取2008年5月12日8:00～12:00在三大樞紐機(jī)場起降的航班作為算例,目標(biāo)機(jī)場集合Q包括首都機(jī)場、上海虹橋機(jī)場和廣州白云機(jī)場.假設(shè)首都機(jī)場的容量為60架次/h、廣州白云機(jī)場的容量為48架次/h、上海虹橋機(jī)場的容量為36架次/h.通過數(shù)據(jù)分析發(fā)現(xiàn),在8:00～12:00時(shí)段中,共有459架次航班在三大機(jī)場起降,造成35個(gè)時(shí)間片57架次航班超出機(jī)場的容量限制,按照先到先服務(wù)(firstcomefirstserve,FCFS)原則,總計(jì)需要調(diào)整約176架次航班,造成總延誤時(shí)間約為890min,見表1.用延誤時(shí)間表示總的延誤成本,地面等待時(shí)間與延誤成本的比值為1∶Cg,空中等待時(shí)間與延誤成本的比值為1∶1.5Cg.因?yàn)椴捎孟鹊较确?wù)策略,設(shè)5min為一個(gè)起降時(shí)間片,不考慮機(jī)場之間彼此的起降限制,總延誤航班為0.本算例中,種群大小取400,算法終止代數(shù)取800,變異系數(shù)取0.1,交叉系數(shù)取0.7.利用NSGA-Ⅱ算法對航班進(jìn)行優(yōu)化,第500代的Pareto前端解(即最優(yōu)解集合)見表2.經(jīng)過多次計(jì)算發(fā)現(xiàn),計(jì)算到500代后,優(yōu)化結(jié)果不再有明顯改進(jìn).因此,第500代的Pareto前端解可近似作為最優(yōu)解集合,即表2中的最優(yōu)方案集合為種群中的5個(gè)最優(yōu)方案,它們各有所長.通過分析可知,優(yōu)化后的方案中,總延誤成本明顯減少(平均減少了約24%),總延誤時(shí)間減少,總延誤航班數(shù)有所增加,總調(diào)整航班數(shù)明顯減少(平均減少了約62%),受影響的航班數(shù)量大大減少,實(shí)際運(yùn)行效率更高.根據(jù)決策人員的調(diào)整目的,可任選其中一個(gè)方案作為優(yōu)化后的解.本文選擇總延誤成本最小的解作為本次優(yōu)化方案,如圖2所示.方案1可以滿足本文的需求.下面將進(jìn)一步分析NSGA-Ⅱ算法的結(jié)果,考慮到四維圖形的表達(dá)效果不佳,本文選擇總延誤時(shí)間、總調(diào)整航班架次和總延誤航班架次3個(gè)目標(biāo)函數(shù)生成三維圖形進(jìn)行研究,利用Origin8.0進(jìn)行仿真,結(jié)果如圖3所示.通過分析可以發(fā)現(xiàn),最優(yōu)解集合在圖3中構(gòu)成了凸面,不斷地向3個(gè)最小坐標(biāo)值的交點(diǎn)方向逼近,形成了3個(gè)目標(biāo)函數(shù)的Pareto前端解.4基于航班時(shí)刻優(yōu)化的多目標(biāo)、多機(jī)場模型求解(1)在已有多機(jī)場地面等待問題模型的基礎(chǔ)上,提出了一種新的基于航班時(shí)刻優(yōu)化的多目標(biāo)、多機(jī)場地面等待問題模型,并給出了模型的多目標(biāo)函數(shù)