基于粒子群算法的航空器滑行路徑優化研究

馮廣洪

摘 要：航空器滑行路徑的優化可以提高繁忙機場場面的運行效率，減小航空器的滑行成本。考慮實際情況，做出了相應的假設，以機場航空器地面滑行總時間為優化目標，考慮航空器的優先級和沖突節點避讓等問題，建立了航空器地面滑行路徑優化的0-1整數規劃模型，并采用了粒子群算法進行求解。通過實例求解仿真，實驗結果表明算法可以實現航空器滑行路徑優化問題，得到的路線具有可行性，也驗證了模型的可用性，可為復雜的路徑規劃問題提供有效的求解方法。

關鍵詞：航空運輸;地面滑行路徑;路徑優化;粒子群優化算法

滑行道的合理規劃與使用，影響著機場場面運行的安全和效率。隨著民航業的大力發展，各大型機場的航班數量也不斷上升，場面運行日益復雜，通過為航空器的滑行路徑進行優化管理，提高機場場面運行的效率成為熱門研究方向。

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

針對現有模型對航空器滑行系統刻畫不足的特點，提出0-1整數規劃模型，考慮航空器在滑行時所必須滿足的航班時刻、機場地面的實時動態、沖突解脫、特殊滑行道的限制等的現實問題的約束，更精確地描繪了航空器的滑行過程。針對傳統算法計算模型過大，精確度不高的問題，提出應用粒子群算法對模型進行求解，以達到減少航空器地面滑行時間，提高航班運行效率的目標。

1 符號說明及模型建立

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

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

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

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

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

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

算法的具體步驟如下：

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

（2）計算適應度值：根據目標函數，計算每個粒子的適應度函數值。

（3）計算個體極值pbest：將每個粒子當前所處的位置對應的適應度值同粒子歷史最佳位置對應的適應度值相比，若大于，則將當前位置更新為最佳位置pbest。

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

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

（6）重復迭代直至結束：回到（2），重復步驟迭代計算，直到達到最佳的迭代數量或者最優適應度值增量小于一定的閾值后，結束迭代，輸出所得結果。

3 算例分析

選取國內某國際機場，機場有三條平行跑道。航站樓東邊為兩條近距平行跑道。西北一條跑道與東邊兩條的運行關系為獨立平行運行，相互間不影響。選取機場的東機坪作為研究對象，進行優化計算。機場的東機坪一條跑道的編號為02L/20R，用于起飛;另一條跑道為02R/20L，用于著陸。航空器的平均滑行速度為15m/s，滑行安全間隔為200m。

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

圖2為目標函數值隨迭代進行下的變化情況。圖中可以看出，在經過187次迭代后，結果趨于收斂，收斂至約為52.19min。之后的500次迭代，結果的變化依然很小，則提前終止了迭代，輸出結果。

根據計算結果顯示，機場的3～9和13～19號結點為主要的沖突點，沖突類型主要為進場-離場航空器交叉沖突，進場的航空器提前等待避讓離場航空器的滑行。計算得全局最優的方差為0.00113，屬于較理想的結果。說明利用粒子群算法可以解決在復雜的環境中的路徑規劃搜尋最優解的問題，結果可靠。

4 結語

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

參考文獻：

[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].計算機仿真，2012，29（07）：88-92.

[4]谷潤平，崔朋，唐建勛，等.基于D*算法的場面滑行動態規劃研究[J].科學技術與工程，2015，15（1）：315-319.

[5]高明瑤，石紅國.基于改進PSO算法的軌道交通接運公交線路優化問題[J].交通運輸工程與信息學報，2019，17（04）：49-54.

[6]滕靖，林琳，陳童.純電動公交時刻表和車輛排班計劃整體優化[J].同濟大學學報（自然科學版），2019，47（12）：1748-1755.