基于改進蟻群算法的改航策略問題研究

王莉莉，楊惠東，周　娟

（中國民航大學空中交通管理學院，天津　300300）

?

基于改進蟻群算法的改航策略問題研究

王莉莉，楊惠東，周娟

（中國民航大學空中交通管理學院，天津300300）

摘要：航班改航飛行是在空域受危險天氣及飛行沖突影響時的一種重要策略。為解決改航問題，惡劣天氣條件下，首先基于數值氣象預報特征，運用柵格法對空域場景進行改航環境建模。在考慮了空中交通規則及航空器性能的基礎上，對航向改變次數、轉彎角度、航段距離進行約束，提出基于改進蟻群算法的改航路徑規劃方法。最后，通過對貴陽—長沙航路的仿真分析，表明該算法能在局部受限區之間搜索到一條安全可行的臨時改航航線，達到提高空域利用率的目的。

關鍵詞：空中交通規劃；改航策略；改進蟻群算法；柵格法

隨著空中交通的不斷發展，航班越來越多，航線覆蓋范圍也越來越大，導致空中飛行在多變氣候下遭遇危險天氣的概率也變大，而航空運輸延誤的主要原因之一是危險天氣。因此，為減小危險天氣對航空飛行的不利影響，并充分利用現有空域資源，通過動態變更航空器飛行航線，繞過危險區，可以使航空器安全回避危險天氣，提高航空運輸的運行效率。

近年來，在改航問題方面的研究越來越多，已有研究成果主要包括：基于多邊形的改航路徑規劃算法[1-3]、基于原有航路網的啟發式搜索算法[4]、基于人工勢場的改航路徑規劃算法[5]、基于標準進離場程序的改航路徑規劃算法[6]。以上算法的不足之處分別在于將影響航空安全的危險天氣整體外邊緣簡化為多邊形飛行受限區，不利于提高空域利用率；對原航線依賴性強，在復雜環境下不易找到理想改航路徑；規劃過程中容易產生局部最優解，陷入死鎖；算法運算速度慢，實時性差。為克服以上缺點，本文在考慮相關空中交通規則的基礎上，首先基于數值氣象預報特征，將空域環境柵格化，增加了穿越局部危險天氣之間的搜索路徑；采用的改進蟻群算法[7-9]具有分布式并行機制特征，能較好地適應復雜多變的天氣環境模型；算法將轉移概率與優化參數相結合，并對當前最優螞蟻進行信息素全局更新，從而避免陷入局部最優解，增強了正反饋機制，提高了算法的收斂速度。最后通過仿真算例驗證了基于改進蟻群算法的改航策略的可行性。

1　環境模型的建立

為更好地描述和處理航空器改航問題，對航空器的飛行環境建立相關模型。航空器按預定飛行計劃飛行，若部分航段受惡劣天氣影響，需對該區域進行網格的定義和柵格的劃分。為簡化環境模型，文中只研究二維空間也就是同一高度層內航空器在飛行受限區域側面繞過的情況。

航線上各位置報告點之間的連線組成航路。若氣象雷達探測到位于航路報告點ri與rj（i

將左上角的第1個柵格的序號定為1，然后從左到右，從上至下依次編碼。記gi∈AP為任意柵格，（xi，yi）是gi的坐標，其與序號Si之間的映射關系由式（1）確定

圖1　基于柵格的環境模型示意圖Fig.1 Environm entm odel diagram based on grid

在基于網格的環境模型中，通過多普勒天氣雷達探測氣象數據，將采集到的數據用一個稱為垂直累積液態含水量VIL（vertically integrated liquid-water content）[10]的算法處理后得到。計算后的VIL值大小表示該柵格區天氣的惡劣程度，將受影響區域進行6個等級的劃分[11]，分別用不同顏色表示。對于雷達回波≥41 dBZ，也就是在級別3以上的天氣等級會嚴重影響航空器的飛行安全[12]。這時，航空器不可以穿越與此飛行受限區（已考慮了安全余度）所相交或重疊的網格，對于等級較低的天氣環境，航空器可以選擇性穿越。氣象信息采用算法柵格數值化后，便能在其影響范圍內生成改航環境模型，相比人工描繪受限區域邊界，顯得更為精準。

2　基于改進蟻群算法的改航路徑尋優

2.1改進蟻群算法的基本原理

蟻群優化算法是一種通過模擬螞蟻依賴信息素的交流以選擇最短路徑來達到搜索食物的目的的群集智能方法。因為改進蟻群算法具有分布式并行機制、信息素正反饋機制和魯棒性等優點，因而其能較好地適應對流天氣實時動態變化的環境并快速規劃出改航航線，使保持穩定性能參數的航空器能在較短的反應時間內完成繞飛任務。惡劣天氣下的改航路徑規劃目的是讓航空器在二維網格空間內安全避讓飛行受限區，以較少的航向改變次數及較短的改航航程為約束由起始節點出發沿一條優化路徑至目標節點。

為適應所建立的環境模型，航空器飛行運動作如下簡化：

1）相對于天氣的幾何尺度，航空器在二維平面上視為質點。

2）航空器在巡航階段速度Vc保持不變，假設其各航段內做勻速直線運動。

3）出于飛行安全及航空器性能考慮，航空器在改航過程中只能進行3個方向的機動飛行，即保持原航向、左轉45°、右轉45°，如圖2所示。

圖2　柵格環境下航向的選擇狀態Fig.2 Course selection state in grid environm ent

4）航空器在柵格環境模型中，每單位時間均是徑向飛往下一網格的中心點，航程為L或1.414 L，計算航程時改航起始點與改航結束點均以其所在柵格的中心點為準。

運動中的螞蟻k（k=1，2，…，m）會根據相鄰的柵格的連通航段上的已有信息素的多少來決定它下一步的轉移方向。螞蟻k在時刻t從柵格i向柵格j轉移的概率定義為

否則

其中：τij（t）表示t時刻連通航段（i，j）上的信息素強度；ηij（t）表示能見度的啟發式函數，設為1/εij（t），εij（t）為航空器航向改變因子，若保持原航向飛行其值設為0.5，機動轉彎飛行則為1；λij（t）=1/μij（t）與天氣的惡劣程度相關，μij（t）為t時刻柵格j處的天氣等級，μij（t）= {1，2，3，4，5，6}；β、α和φ 3個參數，分別表明在運動過程中螞蟻的航向選擇、所積累的信息素和避讓天氣塊時啟發因子在螞蟻選擇路徑中的相對重要性；allowedk={1，2，…n}表示螞蟻k下一時刻允許選擇的柵格，對于已走過的柵格則記錄在禁忌表tabuk中；為避免循環搜索陷入局部最優，式中引入參數ωx（x=1、2、3），若某條航線上的信息量過大時，令ωx為一較小值以平衡各條路徑上的信息量，當循環達到一定次數時，令ωx為一常數，使螞蟻找到最優航線。

經過n個時刻，蟻群完成一輪循環后，對各條柵格連通航段進行全局信息素的調整，為加快算法的收斂速度，僅對本次循環中最優更新螞蟻k所走過的航線進行信息素增強

2.2改進蟻群算法的實現步驟

步驟1：將探測到或預報的氣象信息數值化，利用柵格法建立環境模型。

步驟2：初始化蟻群算法搜索路徑的參數：循環次數n、最大循環次數N、改航起始點所在網格序號startsn、改航結束點所在網格序號endsn、禁忌表tabu、當前全局最短航程shorterlen。設置螞蟻數目為m，各相鄰柵格（僅3個方向）連通航段上的初始信息素為τij（0）=τ0。

步驟3：設初始柵格為每只螞蟻的當前柵格gi（i= 0，1…，m-1），同時將m只螞蟻置于初始柵格上，gi序號記入相應螞蟻的tabu。

步驟4：根據式（2）和式（3）分別計算從gi到與其相連通柵格的轉移概率，并根據概率移動至下一柵格gi’。

步驟5：將gi’序號記入對應的tabu。判斷此時是否有螞蟻到達目標柵格，若有，結束本輪循環，更新shorterlen，取本次循環中最優螞蟻序號為k。若沒有，令gi= gi’，轉到步驟4。

步驟6：根據公式（4）、（5）和（6）對各條航線上的信息素濃度進行衰減，并僅對螞蟻k所走過的改航路徑上的信息素進行增強。

步驟7：n=n+1。若n≤N，shorterlen=0，清空每只螞蟻對應的tabu，轉到步驟3。

步驟8：將相鄰柵格之間的部分彎曲航段拉直修正，輸出全局最優航線及其長度。

3　仿真算例分析

根據前面的數學模型，下面以貴陽—長沙航路為例來說明，當沿航線及其鄰近空域受惡劣天氣影響時，運用本文所提出的方法規劃臨時航線，航空器能安全有效地繞過飛行受限區。

貴陽—長沙航線沿途的報告點依次是：貴陽（KW E）—P173—P217—P293—懷化（ZHJ）—P159—老糧倉（LLC）—長沙（CSX）。氣象部門通過多普勒氣象雷達和氣象衛星測得航段P217—P293—懷化（ZHJ）—P159有雷暴，情報部門根據預報確定會受其影響的不同等級的飛行受限區，如圖3所示。在P217與P159之間建立柵格環境模型，柵格數量為14×12，L取10 nm。

應用改進后的蟻群算法進行仿真計算。為了驗證算法的效果，取不同的參數值進行實驗，參數的默認值設為m=100，N=50，α=1，β=1，φ=1，Q=10，ρ=0.9。每次實驗只有1個參數被改變，被測試的值為：α∈{0，0.5，1，5}，β∈{0，1，2，3}，φ∈{1，3，5，7}，Q∈{10，100}，ρ∈{0.3，0.5，0.7，0.9}。仿真結果表明當參數設置為表1中的數值時，能迅速規劃出一條較優的改航航線，柵格序號為99 - 100 - 101 - 102 - 103 - 90 - 91 - 92 - 93 - 94 - 81 - 68 - 55，如圖3虛線所示，同時生成的收斂曲線、各航線平均航程分別如圖4、圖5所示。

圖3　基于改進蟻群算法的改航路徑示意圖Fig.3 Diverting path diagram based on im p roved ant colony algorithm

表1　實驗最優參數設置Tab.1 Experim ental optim al param eter settings

圖4　改進蟻群算法收斂曲線Fig.4 Convergence curves of im proved ant colony algorithm

圖5　各航線平均航程Fig.5 Average distance of all courses

改進蟻群算法對每次迭代中當前的最優航線進行信息素更新，可提高全局航線的生成速度，這樣，可較快收斂較優解。生成的臨時航線距離為136.57 nm，較原飛行計劃P217至P159航段距離127 nm增加了7.5％，符合改航增加距離在20％范圍內的規定。航空器沿新航線通過3個機動轉彎就能安全有效地避讓危險天氣到達改航結束點，較其他多轉彎航線，減輕了飛行員與管制員的工作負荷，增加了旅客的舒適度。若將飛行受限區用多邊形算法劃設[2]，航空器只能從整體惡劣天氣的最外緣繞飛，如圖3所示，此時改航距離為181.81 nm，比原計劃航線增加了54.81 nm。通過對比，本算法規劃的改航航線較優。

4　結語

本文針對危險天氣下航路不能正常使用的情況，對氣象信息柵格化的環境模型提出基于改進蟻群算法的臨時航線規劃方法。本算法在繞飛過程中，所需轉彎次數少，能減輕相關人員的工作負荷；改航航程較短，提高了空域的使用效率及航空運營的經濟性。通過對實例進行仿真，得到了令人滿意的改航效果，所提出的改航策略具有一定的有效性和可行性。

參考文獻：

[1] SRIDHAR B，CHATTERJIG，GRABBE S，et al.Integration of Traffic Flow Management Decisions[C]//AIAA Guidance，Navigation，and ControlConference.Monterey，California，2002：1-9.

[2]李雄，徐肖豪，朱承元，等.基于幾何算法的空中交通改航路徑規劃[J].系統工程，2008，26（8）：37-40.

[3]李雄，徐肖豪，王超，等.基于凸多邊形的飛行改航區劃設及路徑規劃研究[C]//中國控制與決策會議.沈陽：東北大學出版社，2008：3083-3088.

[4]宋柯.空中交通流量管理改航策略初步研究[D].南京：南京航空航天大學，2002.

[5]徐肖豪，李成功，趙嶷飛，等.基于人工勢場算法的改航路徑規劃[J].交通運輸工程學報，2009，9（6）：64-68.

[6] KROZEL J，W EIDNER T，HUNTER.Terminal AreaGuidance Incorporating Heavy W eather[C]//AIAA Guidance，Navigation and Control Conference.New Orleans，LA，1997：411-421.

[7]李士勇.蟻群算法及其應用[M].哈爾濱：哈爾濱工業大學出版社，2004.

[8]朱慶保，張玉蘭.基于柵格法的機器人路徑規劃蟻群算法[J].機器人，2005，27（2）：132-136.

[9]任春明，張建勛.基于優化蟻群算法的機器人路徑規劃[J].計算機工程，2008，34（15）：1-3，35.

[10]PANNEQUIN JJ，BAYEN A M，MITCHELL IM，etal.Multiple AircraftDeconflicted Path PlanningwithW eatherAvoidanceConstraints[C] //AIAA Guidance，Navigation and ControlConference，2007.

[11] MUELLER C K，FIDALGO C B，MCCANN D W G，et al.National ConvectiveW eather Forecast Product[C]//8th Conference on Aviation，Range，and AerospaceMeteorology，1999.

[12]RHODA D A，PAW LAK M L.The Thunderstorm Penetration/Deviation Decision in the Terminal Area[C]//American Meteorological Society，8th Conf.on Aviation，Rangeand AerospaceMeteorology，1999：308-312.

（責任編輯：黃月）

Rerouting strategy research based on im proved ant colony algorithm

W ANG Lili，YANG Huidong，ZHOU Juan
（College of Air Traffic Management，CAUC，Tianjin 300300，China）

Abstract：Flight rerouting is an important strategy in the airspace with the limit of heavy weather and flight conflict.To solve rerouting problem，the gridmethod is firstly utilized to build themodel for diverting airspace environment based on numerical weather prediction features in severe weather. Taking air traffic rules and aircraft performance into consideration，a new rerouting path planning method basing on the improved ant colony algorithm is proposed under the limitation of head changing times，turning angels and travelling distance. Finally，the flight path ofGuiyang-Changsha is studied.Simulation results show that the proposed method can search a safe and feasible temporary flight rerouting path between local flow constrained area and others，and can improve the utilization rate of the airspace effectively.

Key words：air traffic planning；rerouting strategy；improved antcolony algorithm；gridmethod

作者簡介：王莉莉（1973—），女，陜西興平人，教授，博士，研究方向為空域規劃、空中交通管理.

收稿日期：2014-03-26；修回日期：2014-09-01基金項目：國家自然科學基金項目（61179042）；中央高校基本科研業務費專項（ZXH2012L005）

中圖分類號：V355

文獻標志碼：A

文章編號：1674-5590（2016）01-0015-04