宋阿妮 包賢哲
(湖北工業(yè)大學(xué)電氣與電子工程學(xué)院 湖北 武漢 430068)
隨著人民收入水平的提高和旅游業(yè)的蓬勃發(fā)展,機(jī)場客機(jī)數(shù)量開始迅速增長,各大機(jī)場登機(jī)口資源都面臨著嚴(yán)峻考驗。機(jī)場登機(jī)口的合理分配將會大幅度降低機(jī)場運(yùn)營成本和旅客登機(jī)時間,減少支出的同時提升乘客服務(wù)質(zhì)量,所以如何合理分配機(jī)場登機(jī)口資源是所有大型機(jī)場亟待解決的重要問題[1-3]。
目前機(jī)場分配登機(jī)口方案往往根據(jù)日常經(jīng)驗,沒有理論依據(jù),導(dǎo)致登機(jī)口數(shù)量無法滿足機(jī)場飛機(jī)的正常使用,而盲目新建航站樓和登機(jī)口又會造成資源浪費并增加乘客登機(jī)時間降低服務(wù)質(zhì)量。
國內(nèi)外學(xué)者針對登機(jī)口分配問題進(jìn)行了大量研究,但到目前為止仍然沒有一套非常完整的處理方案和體系。其中文獻(xiàn)[4-6]運(yùn)用遺傳算法求解登機(jī)口分配問題,但由于遺傳算法所需設(shè)置參數(shù)過多,模型建立復(fù)雜很難在實際情況中得到運(yùn)用。Drex等[7]的模型中加入了機(jī)場對登機(jī)口的人為偏好因素,建立了多目標(biāo)優(yōu)化數(shù)學(xué)模型,最后通過帕累托模擬退火算法求解其分配序列,但如何確定人為偏好因素的相關(guān)參數(shù)卻是一個難題。文獻(xiàn)[8-9]設(shè)計了以乘客轉(zhuǎn)機(jī)時間為優(yōu)化目標(biāo)的分配模型,利用禁忌搜索算法以及混合的禁忌搜索算法求解登機(jī)口分配問題,雖然得到了登機(jī)口分配最優(yōu)解,但其數(shù)學(xué)模型和算法只適用于無約束的登機(jī)口分配問題,難以運(yùn)用在復(fù)雜的現(xiàn)實登機(jī)口問題中。黃幫菊等[10]用貪心算法對機(jī)場登機(jī)口進(jìn)行多目標(biāo)優(yōu)化求解,獲得了較好的分配結(jié)果,但是卻出現(xiàn)了登機(jī)口分配不均勻的現(xiàn)象造成登機(jī)口閑置的資源浪費問題。衡紅軍等[11]利用最鄰近算法構(gòu)建了由出港航班和到港航班組成的車輛行駛總路程最短的子路徑集合,再依據(jù)子路徑間的時間銜接關(guān)系將子路徑進(jìn)行優(yōu)化組合,將所有子路徑任務(wù)合理分配給行李運(yùn)輸車,并同時保證了所需車輛數(shù)最少和車輛任務(wù)量均衡的目標(biāo),這一規(guī)劃機(jī)場運(yùn)輸車的調(diào)度問題與航班在某個登機(jī)口出發(fā)或降落有著密切的關(guān)系,提出的算法對機(jī)場登機(jī)口分配問題有一定的參考價值。該算法雖然能夠提供較為合理的分配方案,但其模型及實現(xiàn)較為復(fù)雜,對于大型機(jī)場而言,實際運(yùn)用性不高,且仍然存在著算法結(jié)果收斂緩慢等問題;Bouras等[12]則嘗試用啟發(fā)式算法解決機(jī)場登機(jī)口分配問題,但在分配登機(jī)口的時間流程上依然存在不足。
因此本文對大型機(jī)場登機(jī)口分配問題進(jìn)行了研究,提出了一種多種群變異非線性動態(tài)粒子群算法(Multi-population Mutation Nonlinear Dynamic Particle Swarm Algorithm, PMNDPSO)求解該模型。首先對機(jī)場登機(jī)口與飛機(jī)起落時間進(jìn)行合理分類以簡化模型優(yōu)化相關(guān)參數(shù),然后以分配的登機(jī)口數(shù)量最少作為優(yōu)化目標(biāo),設(shè)立多個粒子種群進(jìn)化、變異并尋找最優(yōu)個體放入優(yōu)質(zhì)種群,然后用典型線性遞減策略和動態(tài)策略相結(jié)合的復(fù)合方式改進(jìn)的進(jìn)化公式對優(yōu)質(zhì)種群再次進(jìn)行迭代進(jìn)化,最終求解得到機(jī)場登機(jī)口的分配序列。
機(jī)場設(shè)有兩個航站樓分別為航站樓T與航站樓S,航站樓T擁有m個登機(jī)口,航站樓S擁有n個登機(jī)口,每個登機(jī)口負(fù)責(zé)接納固定機(jī)型的飛機(jī),擁有供飛機(jī)??康乃屑夹g(shù)設(shè)備,航站樓登機(jī)口情況如圖1所示。
圖1 機(jī)場航站樓和登機(jī)口示意圖
圖2 飛機(jī)分配方法框圖
為了能夠讓研究問題時更加方便,作出以下假設(shè):
(1) 航站樓T與航站樓S所有的登機(jī)口除了型號以外完全相同,統(tǒng)籌分配。
(2) 每個登機(jī)口都擁有著國際出發(fā)/國際到達(dá),國內(nèi)出發(fā)/國內(nèi)到達(dá),寬體機(jī)/窄體機(jī)等固定屬性,每個登機(jī)口只能??繉?yīng)屬性的飛機(jī)。
(3) 同一架飛機(jī)起飛與降落必須在同一登機(jī)口期間不能改變其??课恢?。多架飛機(jī)停靠于同一登機(jī)口時,間隔時間不得小于45分鐘,用于登機(jī)口故障檢修和清潔工作。
(4) 在登機(jī)口位置不足或兩架??客坏菣C(jī)口的飛機(jī)間隔小于45分鐘時,飛機(jī)被安排到臨時登機(jī)口,臨時登機(jī)口的數(shù)量不限。
設(shè)某大型機(jī)場在一天內(nèi)一共有k架飛機(jī)停靠,按照時間前后順序為全部飛機(jī)進(jìn)行編號,分別為V=(V1,V2,…,Vk),即飛機(jī)的到達(dá)時間滿足:
TIV1 (1) 式中TIVi(i∈1,…,k)表示在該機(jī)場??康娘w機(jī)到達(dá)時間。然后將機(jī)場登機(jī)口也按順序進(jìn)行編號,T航站樓的登機(jī)口編號為T=(T1,T2,…,Tm),S航站樓的登機(jī)口編號為S=(S1,S2,…,Sn)。 將飛機(jī)按照屬性進(jìn)行分類:I表示國際出發(fā)/國際到達(dá),D表示國內(nèi)出發(fā)/國內(nèi)到達(dá),W代表寬體機(jī),N代表窄體機(jī),共可以分成IIN、IIW、IDN、IDW、DIN、DIW、DDN、DDW8個類別,對應(yīng)相同屬性的登機(jī)口。其中如IDN型飛機(jī)表示國際出發(fā)國內(nèi)達(dá)到的窄體機(jī)。分類的方式如表1所示。 表1 飛機(jī)登機(jī)口分類示意表 在同一登機(jī)口停靠的飛機(jī)必須滿足后一架飛機(jī)到達(dá)時間與前一架飛機(jī)的起飛時間間隔45分鐘及以上,即: (2) (3) 式中:Ω用以記錄被分配到航站樓中的登機(jī)口??康娘w機(jī)數(shù)量,當(dāng)飛機(jī)滿足式(2)時,Ωi=1。 另外考慮到服務(wù)質(zhì)量問題,為了讓乘客得到更好的登機(jī)旅行體驗,要盡可能保證乘客從候機(jī)室到達(dá)目的登機(jī)口的時間最短,這里假設(shè)所有乘客的步行速度相同,所以即要求乘客從候機(jī)廳到達(dá)登機(jī)口的距離最短,乘客的平均步行距離Lall為: (4) 式中:Rj表示第j個乘客到達(dá)目的登機(jī)口的距離,一天之內(nèi)一共有m位乘客在某機(jī)場登機(jī)出行;Rmax表示所有乘客中步行的最長距離。 機(jī)場每天會對登機(jī)口進(jìn)行維護(hù),在兩架飛機(jī)到達(dá)該登機(jī)口的登機(jī)間隙會讓工作人員對登機(jī)口進(jìn)行基本清潔檢查維護(hù)稱為基本維護(hù)。另外,在一天的航班結(jié)束之后,會對當(dāng)天啟用的登機(jī)口進(jìn)行全面的檢查維修維護(hù)稱為啟用維護(hù),這兩者都會產(chǎn)生一定的維護(hù)費用,為了讓機(jī)場每天的運(yùn)維成本最低,要保證在安排時盡量少啟用登機(jī)口數(shù)目,并將飛機(jī)盡量安排在基本清潔檢查維護(hù)費用較低的登機(jī)口,產(chǎn)生的總體成本費用為: (5) 式中:Si表示第i個登機(jī)口的每日的啟用維護(hù)費用;Ci表示第i個登機(jī)口每次的基本維護(hù)費用;wi則表示一共有第i個登機(jī)口當(dāng)天的基本維護(hù)次數(shù),當(dāng)天一共啟用了y個登機(jī)口;Sall表示所有登機(jī)口全部啟用所需的啟用維護(hù)總費用;Cmax則表示所有登機(jī)口中的最大基本維護(hù)費用。 (6) 式中:Gpub為懲罰因子,表示所有未被分配到航站樓進(jìn)入臨時登機(jī)口的飛機(jī)總數(shù)。 按照表1所示方法,將飛機(jī)按照不同的類別一一進(jìn)行分類,并依據(jù)時間先后排序。 最終模型所需優(yōu)化的目標(biāo)函數(shù)為: (7) 式中:Gpub為懲罰因子,表示α1為懲罰因子的系數(shù),可以根據(jù)實際需要更改該參數(shù)的數(shù)值,d表示分配所有飛機(jī)所使用的機(jī)場登機(jī)口總數(shù)。 粒子群算法(Particle Swarm Optimization, PSO)是模仿鳥類覓食行為的一種群體協(xié)助的隨機(jī)搜索算法,最早是由Eberhart和Kennedy于1995年提出。 經(jīng)典粒子群算法模仿鳥類捕食,在一定空間內(nèi)存在許多鳥,但只有一塊食物,所有鳥不知道食物的具體位置,但卻知道和食物的距離。通過不斷地改變自身的方向和前進(jìn)的速度最終讓所有鳥找到該食物的位置即得到最優(yōu)解。 首先設(shè)置最大迭代次數(shù)tmax表示種群搜索次數(shù),設(shè)置粒子個數(shù)N,粒子的維數(shù)P,初始化所有粒子全部維數(shù)的前進(jìn)速度,第n個粒子第p維的初始速度為Vnp,粒子速度的更新公式為: Vnp=ωVnp+C1random(0,1)(Hnp-Xnp)+ C2random(0,1)(Hgd-Xnp) (8) 式中:ω為慣性權(quán)重,為非負(fù)固定常數(shù),通過調(diào)整ω的大小可以改變算法的前期和后期的搜索能力。C1、C2為加速常數(shù),一般當(dāng)C1=C2∈[0,4]時,算法有較好的搜索能力,Hnp表示第n個粒子進(jìn)化過程中歷史最優(yōu)個體的第p維數(shù)值,Hgd則表示全局最優(yōu)解的第p維數(shù)值。全部粒子的所有維數(shù)隨著迭代次數(shù)的增加,其速度也在發(fā)生變化。每一次迭代,粒子就按照當(dāng)前速度向全局最優(yōu)解和歷史最優(yōu)解的方向改變自身位置,其位置更新公式為: Xnp=Xnp+Vnp (9) 所有粒子在不停的迭代過程中不斷向著全局最優(yōu)解和個體歷史最優(yōu)解靠近,最終收斂于最優(yōu)值附近,這就是經(jīng)典粒子群的搜索原理。 2.2.1 多種群變異進(jìn)化策略 經(jīng)典粒子群算法很容易陷入局部最優(yōu)導(dǎo)致早熟情況,為了能夠保證粒子群算法在前期的搜索范圍能夠覆蓋最優(yōu)解,設(shè)定初始種群m+1個,其中前m個種群中粒子數(shù)都為N,最后一個種群為無任何粒子的空種群,將此空種群稱為優(yōu)質(zhì)群,前m個粒子群按照式(8)的進(jìn)化方式單獨搜索最優(yōu)解,當(dāng)種群陷入局部最優(yōu)解后將其當(dāng)前全局最優(yōu)解Higk放入第m+1個空種群中作為該優(yōu)質(zhì)群的新粒子xik,陷入局部最優(yōu)解的粒子群開始變異并重新搜索下一個局部最優(yōu)解,變異公式為: xinpk=xinp(k-1)+random(0,1)× (fmax(xinpk)-fmin(xinp))×(tmax-t)/tmax (10) 式中:xinpk表示第i個種群第n個粒子第p維第k次變異的值,fmax(xinpk)即該粒子第p維第k次變異的歷史最大值,fmin(xinpk)即該粒子第p維第k次變異的歷史最小值, random(0,1)為(0,1)之間的隨機(jī)數(shù),tmax為最大迭代次數(shù),t為當(dāng)前迭代次數(shù)。其搜索變異過程如圖3所示。 圖3 多種群搜索變異過程圖 粒子按照此方式依次將每個種群第k次變異的最優(yōu)粒子放入優(yōu)質(zhì)群中,k是可以根據(jù)解的最終解的情況設(shè)定的變異次數(shù),當(dāng)所有種群已經(jīng)達(dá)到最大變異次數(shù)并再次陷入局部最優(yōu)時,優(yōu)質(zhì)群粒子成熟,此時該種群的優(yōu)質(zhì)個體的整體搜索范圍將會覆蓋所有可能的最優(yōu)解,按照改進(jìn)的進(jìn)化公式可以快速準(zhǔn)確地找到全局最優(yōu)解,有效防止粒子群陷入早熟情況。 2.2.2 非線性動態(tài)慣性權(quán)重策略 經(jīng)典粒子群算法以其搜索速度快,效率高且算法簡單等優(yōu)勢很快被運(yùn)用于各種優(yōu)化問題上,但隨著對粒子群算法了解的逐步深入,也發(fā)現(xiàn)了其容易陷入局部最優(yōu)解的缺點。 為了能夠使得登機(jī)口分配中粒子群算法不陷入局部最優(yōu)解,提出一種非線性動態(tài)粒子群的改進(jìn)方式,其慣性權(quán)重將典型非線性遞減策略和動態(tài)策略相結(jié)合,能夠有效地提高粒子群在后期的搜索準(zhǔn)確性和速度。 (1) 非線性遞減策略。粒子群算法的搜索過程是一個非線性搜索過程,在搜索前、中、后期的位置移動速度和收斂快慢都有所不同,所以為了能夠盡可能符合粒子群的搜索規(guī)律,設(shè)定其非線性部分的慣性權(quán)重ω為: (11) 式中:當(dāng)ωmax=0.9,ωmin=0.4時,整個非線性部分的搜索效果較好,在計算式中加入指數(shù)函數(shù),在算法前期即迭代次數(shù)較小時,算法前期的慣性權(quán)重較大、搜索步長較長,保證了算法前期的搜索范圍,在搜索后期,t較大時,慣性權(quán)重跟隨著算法的搜索規(guī)律快速減小,能夠有效減小步長以縮小搜索域在局部范圍內(nèi)精確搜索找到最優(yōu)結(jié)果。 (12) (13) (14) 式(14)中的ωq=1,ωp=0.5,ωu=0.13時,其搜索效果最好,進(jìn)化速度因子小時,表明進(jìn)化速度快,此時應(yīng)適當(dāng)降低粒子的進(jìn)化速度不至于過快而導(dǎo)致部分粒子無法收斂,當(dāng)進(jìn)化速度因子逐漸增大時,表明算法進(jìn)化速度在逐漸減慢,說明算法開始接近最優(yōu)解附近,此時應(yīng)逐漸減小慣性權(quán)重以保證算法的局部搜索精度,聚集度因子作為算法的另一特征參數(shù),其功能與進(jìn)化速度因子類似,聚集度因子較低時,表明粒子的搜索范圍較廣,搜索速度較快,聚集度因子較高時,粒子進(jìn)入局部搜索,搜索速度減慢。將兩個特征參數(shù)進(jìn)行組合,使粒子群算法進(jìn)化過程中不斷根據(jù)自身規(guī)律更新慣性權(quán)重以滿足當(dāng)前迭代條次數(shù)下的搜索精度要求。 (3) 復(fù)合慣性權(quán)重。根據(jù)上述給出的動態(tài)策略部分的慣性權(quán)重式(14)和非線性遞減策略部分慣性權(quán)重式(11)可以得到最終的復(fù)合慣性權(quán)重ωN為: (15) 式中:λ1,λ2∈[0,1],根據(jù)式(15)得到的復(fù)合慣性權(quán)重綜合了粒子迭代非線性變化過程以及其進(jìn)化狀態(tài)對算法的影響,相對于單獨的慣性權(quán)重設(shè)定,前期能夠保證足夠大的搜索范圍防止早熟,后期能夠根據(jù)粒子的進(jìn)化狀態(tài)迅速收縮搜索范圍得到局部精確解。 最終得到的復(fù)合慣性權(quán)重粒子群算法的速度更新公式為: Vnp=ωNVnp+C1random(0,1)(Hnp-Xnp)+ C2random(0,1)(Hgd-Xnp) (16) 優(yōu)質(zhì)群按照改進(jìn)后的進(jìn)化式(16)繼續(xù)迭代進(jìn)化,最終得到最優(yōu)解。算法的整體運(yùn)算過程如圖4所示。 圖4 MNPDPSO框圖 為了測試改進(jìn)策略的效果,現(xiàn)將提出的不同改進(jìn)策略加在原先的算法上,分別得到采用多種群變異進(jìn)化策略粒子群算法(PMPSO)、采用非線性動態(tài)復(fù)合策略粒子群算法(NDPSO),以及三者同時采用的本文提出的PMNDPSO,并采用Rastrigin’s、Ackley’s、Easom、Eggholder四種典型測試函數(shù)對這四種算法進(jìn)行測試,粒子個數(shù)N=200,其他各參數(shù)設(shè)置全部采取實際問題中的變量取值,四種函數(shù)求解函數(shù)得到的最終各項信息數(shù)據(jù)如表2所示。 表2 改進(jìn)策略測試效果表 表2中Min表示算法得到的最優(yōu)解數(shù)值,Time則表示得到最優(yōu)解所用的時間,Rate表示收斂到最優(yōu)解的粒子個體數(shù)占總個體數(shù)的比例,可以看到采用多粒子群變異策略的粒子群算法(PMPSO)由于優(yōu)化了初始粒子群,提高了粒子的多樣性和優(yōu)質(zhì)性,前三個函數(shù)都能得到最優(yōu)解且收斂率較高,但整體的搜索速度卻較慢。加入了非線性動態(tài)復(fù)合策略的粒子群算法(DPSO)得到了前兩個函數(shù)的最優(yōu)解,但因為前期搜索范圍和初始粒子多樣性不足,導(dǎo)致在搜索后面兩個較復(fù)雜的函數(shù)時其精度不高,由于其縮小了后期搜索范圍改善了算法后期的搜索速度,所以找到最優(yōu)解的時間較短,兩種改進(jìn)后的算法相對于傳統(tǒng)PSO在搜索精度和搜索速度上都有顯著提升,證明了上述改進(jìn)策略的有效性,將所有改進(jìn)策略同時引入PSO即本文提出的PMNDPSO,其改進(jìn)效果如表3所示。 表3 整體改進(jìn)效果信息表 根據(jù)表3數(shù)據(jù)可以得到看到,相對于傳統(tǒng)PSO,改進(jìn)后的PMNDPSO四個函數(shù)都能夠搜索到最優(yōu)解,且粒子收斂率相對于PSO有了顯著提升,但是由于多種群進(jìn)化方式提升了系統(tǒng)的時間復(fù)雜度,所以求解得到最優(yōu)解的速度下降了,但由于機(jī)場登機(jī)口分配系統(tǒng)會提前安排次日的飛機(jī)登機(jī)口順序,所以對時間響應(yīng)度要求不高,影響可以忽略。根據(jù)上述函數(shù)測試表明,改進(jìn)后的PMNDPSO在精度和收斂率上較傳統(tǒng)PSO都有顯著提升,也證明了算法改進(jìn)的有效性。取最具代表性的Eggholder函數(shù)的迭代過程圖如圖5所示。 圖5 Eggholder函數(shù)測試迭代圖 設(shè)某國內(nèi)機(jī)場有航站樓T與航站樓S,其中航站樓T一共擁有15個飛機(jī)登機(jī)口分別為T=(T1,T2,…,T15),航站樓S一共擁有22個飛機(jī)登機(jī)口分別為S=(S1,S2,…,S22),在某一天內(nèi)一共有295架飛機(jī)在該機(jī)場降落,按照時間先后順序給所有飛機(jī)排序分別表示為V=(V1,V2,…,V295)。 首先將登機(jī)口與飛機(jī)按屬性進(jìn)行分類匹配,一共可分為8種類型的登機(jī)口和飛機(jī),每個型號的登機(jī)口以及該登機(jī)可以停靠的飛機(jī)數(shù)量等信息如表4所示。 表4 登機(jī)口與飛機(jī)匹配圖 根據(jù)表4中登機(jī)口與飛機(jī)的匹配情況,將不同屬性的飛機(jī)按照時間前后進(jìn)行排序,該順序就是飛機(jī)進(jìn)入特定登機(jī)口的順序序列,部分匹配相應(yīng)登機(jī)口的飛機(jī)起飛降落時間表如表5所示。 表5 不同登機(jī)口匹配飛機(jī)起飛降落時刻表 該機(jī)場22個登機(jī)口的每次的基本維護(hù)費用以及啟用維護(hù)費用和距離候機(jī)廳的距離信息如表6所示。 表6 登機(jī)口維護(hù)費用與位置信息表 為了能夠驗證PMNDPSO的運(yùn)用效果,用傳統(tǒng)粒子群(PSO)、蟻群算法(AG)、螢火蟲算法以及PMNDPSO三種算法求解分類后的機(jī)場登機(jī)口匹配最佳方案。設(shè)粒子迭代次數(shù)t=250,粒子個數(shù)N=20,由于一共有295架飛機(jī),所以粒子的維數(shù)P=295,進(jìn)化粒子表示為x=(xi1,xi2,…,xi295),初始粒子進(jìn)化速度Vnp=1,慣性權(quán)重式(10)中參數(shù)取值分別為ωq=1,ωp=0.5,ωu=0.13,最終得到的算法迭代結(jié)果如圖6所示。 圖6 算法迭代圖 由圖6中可以看到,改進(jìn)后的PMNDPSO在迭代次數(shù)達(dá)到40次左右時收斂到最優(yōu)解,而傳統(tǒng)粒子群算法、螢火蟲算法、蟻群算法的收斂相對較慢,且PMNDPSO能夠得到更好的優(yōu)化結(jié)果。四種算法求解得到的最終結(jié)果參數(shù)如表7所示。 表7 四種算法結(jié)果對比表 由表5可看出,PMNDPSO求解飛機(jī)登機(jī)口的綜合效果要更好,其最優(yōu)目標(biāo)求解精度相對于FA、GA、PSO分別提高了23.13%、14.94%、8.01%,一共只啟用了33個登機(jī)口就能基本滿足所有飛機(jī)的降落起飛??啃枨蟛⒊晒Ψ峙淞?76架飛機(jī)。但由于改進(jìn)策略增加了算法的時間復(fù)雜度,所以計算解決方案的平均迭代時間相對下降了13.56%、27.03%、37.45%,不過機(jī)場登機(jī)口分配系統(tǒng)對時間響應(yīng)度要求并不高,且算法之間時間差距并不大,所以此時間差對系統(tǒng)影響可以忽略。除此之外,相對于另外三種算法,PMNDPSO能夠為機(jī)場節(jié)省更多預(yù)算,分配的方案所需成本最低,相對于另外三種算法分別提高了21.62%、22.52%、10.33%。且在該算法分配的方案下,乘客到達(dá)目標(biāo)登機(jī)口的距離最短,距離相對于另外三種算法分別提高了52.43%、36.74%、23.90%,能夠顯著提升乘客的出行體驗,提升機(jī)場服務(wù)質(zhì)量。所以綜合上述多個特性可以看出,PMNDPSO算法相對于GA、FA以及PSO,其各方面性能提升較為顯著,在機(jī)場登機(jī)口分配問題上有著更好的適應(yīng)性。用PMNDPSO計算所得飛機(jī)??康菣C(jī)口的匹配順序結(jié)果如表8所示。 表8 飛機(jī)??康菣C(jī)口匹配順序表 當(dāng)日在該機(jī)場??康?95架飛機(jī)中有276架飛機(jī)成功匹配,進(jìn)入臨時登機(jī)口的飛機(jī)僅為19架,匹配成功率達(dá)到93.56%,使用33個登機(jī)口,其中T6、T11、S5、S8四個登機(jī)口可以閑置不需要安排航班。 為了能夠更為直觀地看出每個登機(jī)口的飛機(jī)停靠時間的相對情況,將得出的匹配結(jié)果繪制成甘特圖,如圖7與圖8所示。 圖7 T航站樓飛機(jī)匹配登機(jī)口停靠時間甘特圖 圖8 S航站樓飛機(jī)匹配登機(jī)口??繒r間甘特圖 本文針對機(jī)場登機(jī)口分配問題提出了一種PMNDPSO,該算法在初期設(shè)立多個種群進(jìn)化變異,將每次變異迭代得到的每個種群的最優(yōu)個體放入優(yōu)質(zhì)種群中,有效避免了粒子群前期陷入局部最優(yōu)解,并讓其搜索范圍變得更廣、更精確。優(yōu)質(zhì)種群進(jìn)化公式中的慣性權(quán)重考慮到了粒子搜索的非線性過程以及粒子進(jìn)化自身的狀態(tài),能夠在搜索前期根據(jù)算法自身特性調(diào)整參數(shù)避免陷入早熟,在搜索后期也能夠快速減小搜索范圍在局部范圍內(nèi)找到更精確的結(jié)果,通過在傳統(tǒng)PSO中逐步加入不同的策略進(jìn)行測試,證明了上述改進(jìn)的有效性。將其運(yùn)用到登機(jī)口分配實例中,新提出的算法能夠很好地為機(jī)場找到最佳的登機(jī)口分配方案并節(jié)省運(yùn)營成本避免登機(jī)口資源的浪費和航班受阻并大幅度縮短旅客的登機(jī)時間,提升機(jī)場的整體服務(wù)質(zhì)量。研究機(jī)場中途新增、取消相關(guān)航班的動態(tài)登機(jī)口優(yōu)化系統(tǒng)問題將是下一步研究的目標(biāo)。2 改進(jìn)的粒子群算法
2.1 經(jīng)典粒子群算法
2.2 多種群非線性動態(tài)粒子群算法
3 實例驗證
3.1 改進(jìn)效果測試
3.2 求解登機(jī)口分配實例
4 結(jié) 語