多種群變異非線性動態(tài)粒子群算法求解機場登機口分配問題

宋阿妮 包賢哲

(湖北工業(yè)大學電氣與電子工程學院 湖北 武漢 430068)

0 引 言

隨著人民收入水平的提高和旅游業(yè)的蓬勃發(fā)展,機場客機數量開始迅速增長,各大機場登機口資源都面臨著嚴峻考驗。機場登機口的合理分配將會大幅度降低機場運營成本和旅客登機時間,減少支出的同時提升乘客服務質量,所以如何合理分配機場登機口資源是所有大型機場亟待解決的重要問題[1-3]。

目前機場分配登機口方案往往根據日常經驗,沒有理論依據,導致登機口數量無法滿足機場飛機的正常使用,而盲目新建航站樓和登機口又會造成資源浪費并增加乘客登機時間降低服務質量。

國內外學者針對登機口分配問題進行了大量研究,但到目前為止仍然沒有一套非常完整的處理方案和體系。其中文獻[4-6]運用遺傳算法求解登機口分配問題,但由于遺傳算法所需設置參數過多,模型建立復雜很難在實際情況中得到運用。Drex等[7]的模型中加入了機場對登機口的人為偏好因素,建立了多目標優(yōu)化數學模型,最后通過帕累托模擬退火算法求解其分配序列,但如何確定人為偏好因素的相關參數卻是一個難題。文獻[8-9]設計了以乘客轉機時間為優(yōu)化目標的分配模型,利用禁忌搜索算法以及混合的禁忌搜索算法求解登機口分配問題,雖然得到了登機口分配最優(yōu)解,但其數學模型和算法只適用于無約束的登機口分配問題,難以運用在復雜的現實登機口問題中。黃幫菊等[10]用貪心算法對機場登機口進行多目標優(yōu)化求解,獲得了較好的分配結果,但是卻出現了登機口分配不均勻的現象造成登機口閑置的資源浪費問題。衡紅軍等[11]利用最鄰近算法構建了由出港航班和到港航班組成的車輛行駛總路程最短的子路徑集合,再依據子路徑間的時間銜接關系將子路徑進行優(yōu)化組合,將所有子路徑任務合理分配給行李運輸車,并同時保證了所需車輛數最少和車輛任務量均衡的目標,這一規(guī)劃機場運輸車的調度問題與航班在某個登機口出發(fā)或降落有著密切的關系,提出的算法對機場登機口分配問題有一定的參考價值。該算法雖然能夠提供較為合理的分配方案,但其模型及實現較為復雜,對于大型機場而言,實際運用性不高,且仍然存在著算法結果收斂緩慢等問題;Bouras等[12]則嘗試用啟發(fā)式算法解決機場登機口分配問題,但在分配登機口的時間流程上依然存在不足。

因此本文對大型機場登機口分配問題進行了研究,提出了一種多種群變異非線性動態(tài)粒子群算法(Multi-population Mutation Nonlinear Dynamic Particle Swarm Algorithm, PMNDPSO)求解該模型。首先對機場登機口與飛機起落時間進行合理分類以簡化模型優(yōu)化相關參數,然后以分配的登機口數量最少作為優(yōu)化目標,設立多個粒子種群進化、變異并尋找最優(yōu)個體放入優(yōu)質種群,然后用典型線性遞減策略和動態(tài)策略相結合的復合方式改進的進化公式對優(yōu)質種群再次進行迭代進化,最終求解得到機場登機口的分配序列。

1 問題分析與模型建立

機場設有兩個航站樓分別為航站樓T與航站樓S,航站樓T擁有m個登機口,航站樓S擁有n個登機口,每個登機口負責接納固定機型的飛機,擁有供飛機停靠的所有技術設備,航站樓登機口情況如圖1所示。

圖1 機場航站樓和登機口示意圖

圖2 飛機分配方法框圖

1.1 模型假設

為了能夠讓研究問題時更加方便,作出以下假設:

(1) 航站樓T與航站樓S所有的登機口除了型號以外完全相同,統(tǒng)籌分配。

(2) 每個登機口都擁有著國際出發(fā)/國際到達,國內出發(fā)/國內到達,寬體機/窄體機等固定屬性,每個登機口只能停靠對應屬性的飛機。

(3) 同一架飛機起飛與降落必須在同一登機口期間不能改變其?？课恢谩６嗉茱w機?？坑谕坏菣C口時,間隔時間不得小于45分鐘,用于登機口故障檢修和清潔工作。

(4) 在登機口位置不足或兩架?？客坏菣C口的飛機間隔小于45分鐘時,飛機被安排到臨時登機口,臨時登機口的數量不限。

1.2 模型建立

設某大型機場在一天內一共有k架飛機?？?按照時間前后順序為全部飛機進行編號,分別為V=(V1,V2,…,Vk),即飛機的到達時間滿足:

TIV1

(1)

式中TIVi(i∈1,…,k)表示在該機場?？康娘w機到達時間。然后將機場登機口也按順序進行編號,T航站樓的登機口編號為T=(T1,T2,…,Tm),S航站樓的登機口編號為S=(S1,S2,…,Sn)。

將飛機按照屬性進行分類:I表示國際出發(fā)/國際到達,D表示國內出發(fā)/國內到達,W代表寬體機,N代表窄體機,共可以分成IIN、IIW、IDN、IDW、DIN、DIW、DDN、DDW8個類別,對應相同屬性的登機口。其中如IDN型飛機表示國際出發(fā)國內達到的窄體機。分類的方式如表1所示。

表1 飛機登機口分類示意表

在同一登機口?？康娘w機必須滿足后一架飛機到達時間與前一架飛機的起飛時間間隔45分鐘及以上,即:

(2)

(3)

式中:Ω用以記錄被分配到航站樓中的登機口?？康娘w機數量,當飛機滿足式(2)時,Ωi=1。

另外考慮到服務質量問題,為了讓乘客得到更好的登機旅行體驗,要盡可能保證乘客從候機室到達目的登機口的時間最短,這里假設所有乘客的步行速度相同,所以即要求乘客從候機廳到達登機口的距離最短,乘客的平均步行距離Lall為:

(4)

式中:Rj表示第j個乘客到達目的登機口的距離,一天之內一共有m位乘客在某機場登機出行;Rmax表示所有乘客中步行的最長距離。

機場每天會對登機口進行維護,在兩架飛機到達該登機口的登機間隙會讓工作人員對登機口進行基本清潔檢查維護稱為基本維護。另外,在一天的航班結束之后,會對當天啟用的登機口進行全面的檢查維修維護稱為啟用維護,這兩者都會產生一定的維護費用,為了讓機場每天的運維成本最低,要保證在安排時盡量少啟用登機口數目,并將飛機盡量安排在基本清潔檢查維護費用較低的登機口,產生的總體成本費用為:

(5)

式中:Si表示第i個登機口的每日的啟用維護費用;Ci表示第i個登機口每次的基本維護費用;wi則表示一共有第i個登機口當天的基本維護次數,當天一共啟用了y個登機口;Sall表示所有登機口全部啟用所需的啟用維護總費用;Cmax則表示所有登機口中的最大基本維護費用。

(6)

式中:Gpub為懲罰因子,表示所有未被分配到航站樓進入臨時登機口的飛機總數。

按照表1所示方法,將飛機按照不同的類別一一進行分類,并依據時間先后排序。

最終模型所需優(yōu)化的目標函數為:

(7)

式中:Gpub為懲罰因子,表示α1為懲罰因子的系數,可以根據實際需要更改該參數的數值,d表示分配所有飛機所使用的機場登機口總數。

2 改進的粒子群算法

2.1 經典粒子群算法

粒子群算法(Particle Swarm Optimization, PSO)是模仿鳥類覓食行為的一種群體協(xié)助的隨機搜索算法,最早是由Eberhart和Kennedy于1995年提出。

經典粒子群算法模仿鳥類捕食,在一定空間內存在許多鳥,但只有一塊食物,所有鳥不知道食物的具體位置,但卻知道和食物的距離。通過不斷地改變自身的方向和前進的速度最終讓所有鳥找到該食物的位置即得到最優(yōu)解。

首先設置最大迭代次數tmax表示種群搜索次數,設置粒子個數N,粒子的維數P,初始化所有粒子全部維數的前進速度,第n個粒子第p維的初始速度為Vnp,粒子速度的更新公式為:

Vnp=ωVnp+C1random(0,1)(Hnp-Xnp)+

C2random(0,1)(Hgd-Xnp)

(8)

式中:ω為慣性權重,為非負固定常數,通過調整ω的大小可以改變算法的前期和后期的搜索能力。C1、C2為加速常數,一般當C1=C2∈[0,4]時,算法有較好的搜索能力,Hnp表示第n個粒子進化過程中歷史最優(yōu)個體的第p維數值,Hgd則表示全局最優(yōu)解的第p維數值。全部粒子的所有維數隨著迭代次數的增加,其速度也在發(fā)生變化。每一次迭代,粒子就按照當前速度向全局最優(yōu)解和歷史最優(yōu)解的方向改變自身位置,其位置更新公式為:

Xnp=Xnp+Vnp

(9)

所有粒子在不停的迭代過程中不斷向著全局最優(yōu)解和個體歷史最優(yōu)解靠近,最終收斂于最優(yōu)值附近,這就是經典粒子群的搜索原理。

2.2 多種群非線性動態(tài)粒子群算法

2.2.1 多種群變異進化策略

經典粒子群算法很容易陷入局部最優(yōu)導致早熟情況,為了能夠保證粒子群算法在前期的搜索范圍能夠覆蓋最優(yōu)解,設定初始種群m+1個,其中前m個種群中粒子數都為N,最后一個種群為無任何粒子的空種群,將此空種群稱為優(yōu)質群,前m個粒子群按照式(8)的進化方式單獨搜索最優(yōu)解,當種群陷入局部最優(yōu)解后將其當前全局最優(yōu)解Higk放入第m+1個空種群中作為該優(yōu)質群的新粒子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)之間的隨機數,tmax為最大迭代次數,t為當前迭代次數。其搜索變異過程如圖3所示。

圖3 多種群搜索變異過程圖

粒子按照此方式依次將每個種群第k次變異的最優(yōu)粒子放入優(yōu)質群中,k是可以根據解的最終解的情況設定的變異次數,當所有種群已經達到最大變異次數并再次陷入局部最優(yōu)時,優(yōu)質群粒子成熟,此時該種群的優(yōu)質個體的整體搜索范圍將會覆蓋所有可能的最優(yōu)解,按照改進的進化公式可以快速準確地找到全局最優(yōu)解,有效防止粒子群陷入早熟情況。

2.2.2 非線性動態(tài)慣性權重策略

經典粒子群算法以其搜索速度快,效率高且算法簡單等優(yōu)勢很快被運用于各種優(yōu)化問題上,但隨著對粒子群算法了解的逐步深入,也發(fā)現了其容易陷入局部最優(yōu)解的缺點。

為了能夠使得登機口分配中粒子群算法不陷入局部最優(yōu)解,提出一種非線性動態(tài)粒子群的改進方式,其慣性權重將典型非線性遞減策略和動態(tài)策略相結合,能夠有效地提高粒子群在后期的搜索準確性和速度。

(1) 非線性遞減策略。粒子群算法的搜索過程是一個非線性搜索過程,在搜索前、中、后期的位置移動速度和收斂快慢都有所不同,所以為了能夠盡可能符合粒子群的搜索規(guī)律,設定其非線性部分的慣性權重ω為:

(11)

式中:當ωmax=0.9,ωmin=0.4時,整個非線性部分的搜索效果較好,在計算式中加入指數函數,在算法前期即迭代次數較小時,算法前期的慣性權重較大、搜索步長較長,保證了算法前期的搜索范圍,在搜索后期,t較大時,慣性權重跟隨著算法的搜索規(guī)律快速減小,能夠有效減小步長以縮小搜索域在局部范圍內精確搜索找到最優(yōu)結果。

(12)

(13)

(14)

式(14)中的ωq=1,ωp=0.5,ωu=0.13時,其搜索效果最好,進化速度因子小時,表明進化速度快,此時應適當降低粒子的進化速度不至于過快而導致部分粒子無法收斂,當進化速度因子逐漸增大時,表明算法進化速度在逐漸減慢,說明算法開始接近最優(yōu)解附近,此時應逐漸減小慣性權重以保證算法的局部搜索精度,聚集度因子作為算法的另一特征參數,其功能與進化速度因子類似,聚集度因子較低時,表明粒子的搜索范圍較廣,搜索速度較快,聚集度因子較高時,粒子進入局部搜索,搜索速度減慢。將兩個特征參數進行組合,使粒子群算法進化過程中不斷根據自身規(guī)律更新慣性權重以滿足當前迭代條次數下的搜索精度要求。

(3) 復合慣性權重。根據上述給出的動態(tài)策略部分的慣性權重式(14)和非線性遞減策略部分慣性權重式(11)可以得到最終的復合慣性權重ωN為:

(15)

式中:λ1,λ2∈[0,1],根據式(15)得到的復合慣性權重綜合了粒子迭代非線性變化過程以及其進化狀態(tài)對算法的影響,相對于單獨的慣性權重設定,前期能夠保證足夠大的搜索范圍防止早熟,后期能夠根據粒子的進化狀態(tài)迅速收縮搜索范圍得到局部精確解。

最終得到的復合慣性權重粒子群算法的速度更新公式為:

Vnp=ωNVnp+C1random(0,1)(Hnp-Xnp)+

C2random(0,1)(Hgd-Xnp)

(16)

優(yōu)質群按照改進后的進化式(16)繼續(xù)迭代進化,最終得到最優(yōu)解。算法的整體運算過程如圖4所示。

圖4 MNPDPSO框圖

3 實例驗證

3.1 改進效果測試

為了測試改進策略的效果,現將提出的不同改進策略加在原先的算法上,分別得到采用多種群變異進化策略粒子群算法(PMPSO)、采用非線性動態(tài)復合策略粒子群算法(NDPSO),以及三者同時采用的本文提出的PMNDPSO,并采用Rastrigin’s、Ackley’s、Easom、Eggholder四種典型測試函數對這四種算法進行測試,粒子個數N=200,其他各參數設置全部采取實際問題中的變量取值,四種函數求解函數得到的最終各項信息數據如表2所示。

表2 改進策略測試效果表

表2中Min表示算法得到的最優(yōu)解數值,Time則表示得到最優(yōu)解所用的時間,Rate表示收斂到最優(yōu)解的粒子個體數占總個體數的比例,可以看到采用多粒子群變異策略的粒子群算法(PMPSO)由于優(yōu)化了初始粒子群,提高了粒子的多樣性和優(yōu)質性,前三個函數都能得到最優(yōu)解且收斂率較高,但整體的搜索速度卻較慢。加入了非線性動態(tài)復合策略的粒子群算法(DPSO)得到了前兩個函數的最優(yōu)解,但因為前期搜索范圍和初始粒子多樣性不足,導致在搜索后面兩個較復雜的函數時其精度不高,由于其縮小了后期搜索范圍改善了算法后期的搜索速度,所以找到最優(yōu)解的時間較短,兩種改進后的算法相對于傳統(tǒng)PSO在搜索精度和搜索速度上都有顯著提升,證明了上述改進策略的有效性,將所有改進策略同時引入PSO即本文提出的PMNDPSO,其改進效果如表3所示。

表3 整體改進效果信息表

根據表3數據可以得到看到,相對于傳統(tǒng)PSO,改進后的PMNDPSO四個函數都能夠搜索到最優(yōu)解,且粒子收斂率相對于PSO有了顯著提升,但是由于多種群進化方式提升了系統(tǒng)的時間復雜度,所以求解得到最優(yōu)解的速度下降了,但由于機場登機口分配系統(tǒng)會提前安排次日的飛機登機口順序,所以對時間響應度要求不高,影響可以忽略。根據上述函數測試表明,改進后的PMNDPSO在精度和收斂率上較傳統(tǒng)PSO都有顯著提升,也證明了算法改進的有效性。取最具代表性的Eggholder函數的迭代過程圖如圖5所示。

圖5 Eggholder函數測試迭代圖

3.2 求解登機口分配實例

設某國內機場有航站樓T與航站樓S,其中航站樓T一共擁有15個飛機登機口分別為T=(T1,T2,…,T15),航站樓S一共擁有22個飛機登機口分別為S=(S1,S2,…,S22),在某一天內一共有295架飛機在該機場降落,按照時間先后順序給所有飛機排序分別表示為V=(V1,V2,…,V295)。

首先將登機口與飛機按屬性進行分類匹配,一共可分為8種類型的登機口和飛機,每個型號的登機口以及該登機可以?？康娘w機數量等信息如表4所示。

表4 登機口與飛機匹配圖

根據表4中登機口與飛機的匹配情況,將不同屬性的飛機按照時間前后進行排序,該順序就是飛機進入特定登機口的順序序列,部分匹配相應登機口的飛機起飛降落時間表如表5所示。

表5 不同登機口匹配飛機起飛降落時刻表

該機場22個登機口的每次的基本維護費用以及啟用維護費用和距離候機廳的距離信息如表6所示。

表6 登機口維護費用與位置信息表

為了能夠驗證PMNDPSO的運用效果,用傳統(tǒng)粒子群(PSO)、蟻群算法(AG)、螢火蟲算法以及PMNDPSO三種算法求解分類后的機場登機口匹配最佳方案。設粒子迭代次數t=250,粒子個數N=20,由于一共有295架飛機,所以粒子的維數P=295,進化粒子表示為x=(xi1,xi2,…,xi295),初始粒子進化速度Vnp=1,慣性權重式(10)中參數取值分別為ωq=1,ωp=0.5,ωu=0.13,最終得到的算法迭代結果如圖6所示。

圖6 算法迭代圖

由圖6中可以看到,改進后的PMNDPSO在迭代次數達到40次左右時收斂到最優(yōu)解,而傳統(tǒng)粒子群算法、螢火蟲算法、蟻群算法的收斂相對較慢,且PMNDPSO能夠得到更好的優(yōu)化結果。四種算法求解得到的最終結果參數如表7所示。

表7 四種算法結果對比表

由表5可看出,PMNDPSO求解飛機登機口的綜合效果要更好,其最優(yōu)目標求解精度相對于FA、GA、PSO分別提高了23.13%、14.94%、8.01%,一共只啟用了33個登機口就能基本滿足所有飛機的降落起飛?？啃枨蟛⒊晒Ψ峙淞?76架飛機。但由于改進策略增加了算法的時間復雜度,所以計算解決方案的平均迭代時間相對下降了13.56%、27.03%、37.45%,不過機場登機口分配系統(tǒng)對時間響應度要求并不高,且算法之間時間差距并不大,所以此時間差對系統(tǒng)影響可以忽略。除此之外,相對于另外三種算法,PMNDPSO能夠為機場節(jié)省更多預算,分配的方案所需成本最低,相對于另外三種算法分別提高了21.62%、22.52%、10.33%。且在該算法分配的方案下,乘客到達目標登機口的距離最短,距離相對于另外三種算法分別提高了52.43%、36.74%、23.90%,能夠顯著提升乘客的出行體驗,提升機場服務質量。所以綜合上述多個特性可以看出,PMNDPSO算法相對于GA、FA以及PSO,其各方面性能提升較為顯著,在機場登機口分配問題上有著更好的適應性。用PMNDPSO計算所得飛機?？康菣C口的匹配順序結果如表8所示。

表8 飛機?？康菣C口匹配順序表

當日在該機場?？康?95架飛機中有276架飛機成功匹配,進入臨時登機口的飛機僅為19架,匹配成功率達到93.56%,使用33個登機口,其中T6、T11、S5、S8四個登機口可以閑置不需要安排航班。

為了能夠更為直觀地看出每個登機口的飛機?？繒r間的相對情況,將得出的匹配結果繪制成甘特圖,如圖7與圖8所示。

圖7 T航站樓飛機匹配登機口?？繒r間甘特圖

圖8 S航站樓飛機匹配登機口?？繒r間甘特圖

4 結 語

本文針對機場登機口分配問題提出了一種PMNDPSO,該算法在初期設立多個種群進化變異,將每次變異迭代得到的每個種群的最優(yōu)個體放入優(yōu)質種群中,有效避免了粒子群前期陷入局部最優(yōu)解,并讓其搜索范圍變得更廣、更精確。優(yōu)質種群進化公式中的慣性權重考慮到了粒子搜索的非線性過程以及粒子進化自身的狀態(tài),能夠在搜索前期根據算法自身特性調整參數避免陷入早熟,在搜索后期也能夠快速減小搜索范圍在局部范圍內找到更精確的結果,通過在傳統(tǒng)PSO中逐步加入不同的策略進行測試,證明了上述改進的有效性。將其運用到登機口分配實例中,新提出的算法能夠很好地為機場找到最佳的登機口分配方案并節(jié)省運營成本避免登機口資源的浪費和航班受阻并大幅度縮短旅客的登機時間,提升機場的整體服務質量。研究機場中途新增、取消相關航班的動態(tài)登機口優(yōu)化系統(tǒng)問題將是下一步研究的目標。