基于粒子群算法的航空器滑行路徑優(yōu)化研究

馮廣洪

摘 要：航空器滑行路徑的優(yōu)化可以提高繁忙機(jī)場(chǎng)場(chǎng)面的運(yùn)行效率，減小航空器的滑行成本?？紤]實(shí)際情況，做出了相應(yīng)的假設(shè)，以機(jī)場(chǎng)航空器地面滑行總時(shí)間為優(yōu)化目標(biāo)，考慮航空器的優(yōu)先級(jí)和沖突節(jié)點(diǎn)避讓等問題，建立了航空器地面滑行路徑優(yōu)化的0-1整數(shù)規(guī)劃模型，并采用了粒子群算法進(jìn)行求解。通過實(shí)例求解仿真，實(shí)驗(yàn)結(jié)果表明算法可以實(shí)現(xiàn)航空器滑行路徑優(yōu)化問題，得到的路線具有可行性，也驗(yàn)證了模型的可用性，可為復(fù)雜的路徑規(guī)劃問題提供有效的求解方法。

關(guān)鍵詞：航空運(yùn)輸;地面滑行路徑;路徑優(yōu)化;粒子群優(yōu)化算法

滑行道的合理規(guī)劃與使用，影響著機(jī)場(chǎng)場(chǎng)面運(yùn)行的安全和效率。隨著民航業(yè)的大力發(fā)展，各大型機(jī)場(chǎng)的航班數(shù)量也不斷上升，場(chǎng)面運(yùn)行日益復(fù)雜，通過為航空器的滑行路徑進(jìn)行優(yōu)化管理，提高機(jī)場(chǎng)場(chǎng)面運(yùn)行的效率成為熱門研究方向。

對(duì)于航空器的地面滑行路徑的優(yōu)化，國(guó)內(nèi)外學(xué)者從模型建立、求解方法等不同方面都已有了大量的研究。2003年，Visser[1]等建立了整數(shù)規(guī)劃模型來研究滑行路徑優(yōu)化的問題，但由于研究的假設(shè)理想化，后續(xù)不斷有更符合現(xiàn)實(shí)運(yùn)行的研究。2005年，Garacia[2]等分別用遺傳算法和最小費(fèi)用最大流法對(duì)滑行路徑優(yōu)化問題進(jìn)行求解，并做了相應(yīng)的對(duì)比;2012年，李楠[3]等、谷潤(rùn)平等[4]針對(duì)滑行沖突問題，考慮沖突避讓等規(guī)則，分別使用了A*算法、Dijkstra 算法和代價(jià)函數(shù)的 D*算法進(jìn)行優(yōu)化;

針對(duì)現(xiàn)有模型對(duì)航空器滑行系統(tǒng)刻畫不足的特點(diǎn)，提出0-1整數(shù)規(guī)劃模型，考慮航空器在滑行時(shí)所必須滿足的航班時(shí)刻、機(jī)場(chǎng)地面的實(shí)時(shí)動(dòng)態(tài)、沖突解脫、特殊滑行道的限制等的現(xiàn)實(shí)問題的約束，更精確地描繪了航空器的滑行過程。針對(duì)傳統(tǒng)算法計(jì)算模型過大，精確度不高的問題，提出應(yīng)用粒子群算法對(duì)模型進(jìn)行求解，以達(dá)到減少航空器地面滑行時(shí)間，提高航班運(yùn)行效率的目標(biāo)。

1 符號(hào)說明及模型建立

定義K=1，2，…，n為所有航空器的集合;滑行道布局為以節(jié)點(diǎn)和邊構(gòu)成的有向圖G=（P，R），其中P為滑行道交叉點(diǎn)集（共n個(gè)），R為連接交叉點(diǎn)的一段滑行道。i、j均為滑行道的連接節(jié)點(diǎn)，i∈P，j∈P，i≠j;

式（1）為目標(biāo)函數(shù)，表示所有航空器的地面滑行時(shí)間最短，其中地面滑行時(shí)間為航空器的實(shí)際滑行時(shí)間加上停機(jī)等待時(shí)間;式（2）表示優(yōu)先級(jí)更低的航空器在節(jié)點(diǎn)遇到?jīng)_突前需要進(jìn)行一次等待，即使其可能在時(shí)間窗內(nèi)先到達(dá)節(jié)點(diǎn);式（3）為沖突探測(cè)因子，若兩航空器到達(dá)節(jié)點(diǎn)的時(shí)間差大于要求保持的安全時(shí)間間隔，則不需要等待;式（4）為優(yōu)先級(jí)因子，優(yōu)先級(jí)高的不需要等待;式（5）為航空器到達(dá)節(jié)點(diǎn)的時(shí)刻;式（6）表明航空器的開始滑行時(shí)間不可以早于實(shí)際著陸時(shí)間;式（7）表示了航空器不可早于計(jì)劃起飛時(shí)間的前15分鐘;式（8）表示不允許在同一節(jié)滑行道產(chǎn)生對(duì)頭沖突;式（9）表示在同一節(jié)滑行道不允許超越前機(jī);式（10）、（11）分別為滑行的起點(diǎn)、終點(diǎn)約束，表示k航空器的起點(diǎn)s、終點(diǎn)e為必選點(diǎn)。

2 基于粒子算法的模型求解算法

本文采用粒子群算法進(jìn)行求解，粒子群算法（PSO，Particle Swarm Optimization）是一種智能優(yōu)化算法，源于研究鳥類捕食問題。和遺傳算法的染色體信息共享的傳播機(jī)制不一樣，粒子群算法是粒子間的單向的信息傳遞，收斂速度快，結(jié)果理想且可以解決一些遺傳算法中容易產(chǎn)生的問題。粒子群算法在函數(shù)優(yōu)化方面易于實(shí)現(xiàn)，已得到了廣泛的使用。

因此本文在目標(biāo)函數(shù)和約束條件的基礎(chǔ)上，PSO算法以粒子的形式，在可行解空間先生成初始解。每個(gè)粒子都可能是一個(gè)最優(yōu)解，以適應(yīng)度函數(shù)來評(píng)判粒子值的優(yōu)劣。通過判定個(gè)體極值和整體極值來不斷迭代計(jì)算，更新粒子所處的位置，逐步搜索到全局較優(yōu)的區(qū)域，獲得問題的最優(yōu)解[5～6]。

算法中，所有航空器的可行滑行軌跡的解集，都是一個(gè)粒子。設(shè)有n個(gè)粒子，其中k粒子所處的位置為Xk=（xk1，xk2，…，xkn），其速度為Vk=（vk1，vk2.…，vkn）。粒子k搜尋到了其最佳的位置pbestk=（pbestk1，pbestk2，…，pbestkn），整體種群最佳的位置gbest=（gbest1，gbest2，…，gbestn）。經(jīng)過迭代，k粒子更新其速度為Vmk=ωVm-1k+c1rand（）（pbestk-Xm-1k）+c2Rand（）（gbestk-Xkm-1）位置為：Xmk=Xm-1kn+Vm-1k。其中，m表示粒子從第m-1次運(yùn)動(dòng)到下一次的過程;ω是用來調(diào)節(jié)搜索范圍的慣性權(quán)重;c1和c2是源于我們對(duì)這兩部分分量的把握而加的系數(shù);rand（）和Rand（）是出于對(duì)共享和認(rèn)知提供的隨機(jī)系數(shù)，均在[0，1]區(qū)間內(nèi)分布。

算法的具體步驟如下：

（1）種群粒子初始化：粒子群體規(guī)模為n，在模型的可行解集空間的基礎(chǔ)上，初始化粒子群體，每個(gè)粒子攜帶的其隨機(jī)位置和速度的信息。

（2）計(jì)算適應(yīng)度值：根據(jù)目標(biāo)函數(shù)，計(jì)算每個(gè)粒子的適應(yīng)度函數(shù)值。

（3）計(jì)算個(gè)體極值pbest：將每個(gè)粒子當(dāng)前所處的位置對(duì)應(yīng)的適應(yīng)度值同粒子歷史最佳位置對(duì)應(yīng)的適應(yīng)度值相比，若大于，則將當(dāng)前位置更新為最佳位置pbest。

（4）計(jì)算全局極值gbest：同理，將粒子當(dāng)前所處的位置對(duì)應(yīng)的適應(yīng)度值同群體的歷史最佳位置對(duì)應(yīng)的適應(yīng)度值相比，若大于，則將當(dāng)前位置更新為最佳位置gbest。

（5）更新粒子位置和速度：按照前述公式更新粒子所處的位置與速度。

（6）重復(fù)迭代直至結(jié)束：回到（2），重復(fù)步驟迭代計(jì)算，直到達(dá)到最佳的迭代數(shù)量或者最優(yōu)適應(yīng)度值增量小于一定的閾值后，結(jié)束迭代，輸出所得結(jié)果。

3 算例分析

選取國(guó)內(nèi)某國(guó)際機(jī)場(chǎng)，機(jī)場(chǎng)有三條平行跑道。航站樓東邊為兩條近距平行跑道。西北一條跑道與東邊兩條的運(yùn)行關(guān)系為獨(dú)立平行運(yùn)行，相互間不影響。選取機(jī)場(chǎng)的東機(jī)坪作為研究對(duì)象，進(jìn)行優(yōu)化計(jì)算。機(jī)場(chǎng)的東機(jī)坪一條跑道的編號(hào)為02L/20R，用于起飛;另一條跑道為02R/20L，用于著陸。航空器的平均滑行速度為15m/s，滑行安全間隔為200m。

使用MATLAB 2017b，在Win10環(huán)境中運(yùn)行算法程序。設(shè)置初始粒子數(shù)為500，c1=1.5，c2=1.8，設(shè)置的最大迭代數(shù)量為2000，慣性權(quán)重從0.8～0.4逐步線性遞減。加入了參數(shù)終止閾值1e-25和終止次數(shù)500，即，當(dāng)連續(xù)的500次迭代的結(jié)果都小于此閾值時(shí)，終止算法。

圖2為目標(biāo)函數(shù)值隨迭代進(jìn)行下的變化情況。圖中可以看出，在經(jīng)過187次迭代后，結(jié)果趨于收斂，收斂至約為52.19min。之后的500次迭代，結(jié)果的變化依然很小，則提前終止了迭代，輸出結(jié)果。

根據(jù)計(jì)算結(jié)果顯示，機(jī)場(chǎng)的3～9和13～19號(hào)結(jié)點(diǎn)為主要的沖突點(diǎn)，沖突類型主要為進(jìn)場(chǎng)-離場(chǎng)航空器交叉沖突，進(jìn)場(chǎng)的航空器提前等待避讓離場(chǎng)航空器的滑行。計(jì)算得全局最優(yōu)的方差為0.00113，屬于較理想的結(jié)果。說明利用粒子群算法可以解決在復(fù)雜的環(huán)境中的路徑規(guī)劃搜尋最優(yōu)解的問題，結(jié)果可靠。

4 結(jié)語

本文以機(jī)場(chǎng)所有航空器在地面滑行時(shí)間最短為優(yōu)化目標(biāo)，考慮航空器的沖突避讓問題和航空器優(yōu)先級(jí)等限制條件，建立了航空器滑行路徑優(yōu)化模型。采用粒子群算法進(jìn)行求解，實(shí)驗(yàn)結(jié)果表明，粒子群算法在實(shí)現(xiàn)路徑規(guī)劃問題求解中存在有效的效果，計(jì)算精度高，實(shí)驗(yàn)結(jié)果貼近實(shí)際。為了便于建模，文章對(duì)于著陸的航空器滑行至機(jī)位需要穿越起飛跑道而可能增加的等待時(shí)間，文章沒有考慮;算法在初始粒子群的給定中也是按照隨機(jī)的分配，實(shí)驗(yàn)容易陷入局部最優(yōu)而導(dǎo)致結(jié)果偏差大，后續(xù)還可在此問題上繼續(xù)深入研究。

參考文獻(xiàn)：

[1]VISSER H，ROLING P.Optimal airport surface traffic planning using mixed integer linear programming.Proc.of AIAAs 3rd Annual Aviation Technology，Integration，and Operations（ATIO）Technology conference.Denver，CO，2003：17-19.

[2]GARCIA，J，BER;ANGA A，MOLINA JM，et al.Planning techniques for airport ground operations[C].Proc.of the 2002 Digital Avionics Systems Conference.IEEE Press，2002：1：1D5-1-1D5-12.

[3]李楠，趙擎，徐肖豪.基A～*算法的機(jī)場(chǎng)滑行路徑優(yōu)化研究[J].計(jì)算機(jī)仿真，2012，29（07）：88-92.

[4]谷潤(rùn)平，崔朋，唐建勛，等.基于D*算法的場(chǎng)面滑行動(dòng)態(tài)規(guī)劃研究[J].科學(xué)技術(shù)與工程，2015，15（1）：315-319.

[5]高明瑤，石紅國(guó).基于改進(jìn)PSO算法的軌道交通接運(yùn)公交線路優(yōu)化問題[J].交通運(yùn)輸工程與信息學(xué)報(bào)，2019，17（04）：49-54.

[6]滕靖，林琳，陳童.純電動(dòng)公交時(shí)刻表和車輛排班計(jì)劃整體優(yōu)化[J].同濟(jì)大學(xué)學(xué)報(bào)（自然科學(xué)版），2019，47（12）：1748-1755.