基于改進(jìn)蟻群算法的改航策略問(wèn)題研究

王莉莉，楊惠東，周　娟

（中國(guó)民航大學(xué)空中交通管理學(xué)院，天津　300300）

?

基于改進(jìn)蟻群算法的改航策略問(wèn)題研究

王莉莉，楊惠東，周娟

（中國(guó)民航大學(xué)空中交通管理學(xué)院，天津300300）

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

關(guān)鍵詞：空中交通規(guī)劃；改航策略；改進(jìn)蟻群算法；柵格法

隨著空中交通的不斷發(fā)展，航班越來(lái)越多，航線(xiàn)覆蓋范圍也越來(lái)越大，導(dǎo)致空中飛行在多變氣候下遭遇危險(xiǎn)天氣的概率也變大，而航空運(yùn)輸延誤的主要原因之一是危險(xiǎn)天氣。因此，為減小危險(xiǎn)天氣對(duì)航空飛行的不利影響，并充分利用現(xiàn)有空域資源，通過(guò)動(dòng)態(tài)變更航空器飛行航線(xiàn)，繞過(guò)危險(xiǎn)區(qū)，可以使航空器安全回避危險(xiǎn)天氣，提高航空運(yùn)輸?shù)倪\(yùn)行效率。

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

1　環(huán)境模型的建立

為更好地描述和處理航空器改航問(wèn)題，對(duì)航空器的飛行環(huán)境建立相關(guān)模型。航空器按預(yù)定飛行計(jì)劃飛行，若部分航段受惡劣天氣影響，需對(duì)該區(qū)域進(jìn)行網(wǎng)格的定義和柵格的劃分。為簡(jiǎn)化環(huán)境模型，文中只研究二維空間也就是同一高度層內(nèi)航空器在飛行受限區(qū)域側(cè)面繞過(guò)的情況。

航線(xiàn)上各位置報(bào)告點(diǎn)之間的連線(xiàn)組成航路。若氣象雷達(dá)探測(cè)到位于航路報(bào)告點(diǎn)ri與rj（i

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

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

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

2　基于改進(jìn)蟻群算法的改航路徑尋優(yōu)

2.1改進(jìn)蟻群算法的基本原理

蟻群優(yōu)化算法是一種通過(guò)模擬螞蟻依賴(lài)信息素的交流以選擇最短路徑來(lái)達(dá)到搜索食物的目的的群集智能方法。因?yàn)楦倪M(jìn)蟻群算法具有分布式并行機(jī)制、信息素正反饋機(jī)制和魯棒性等優(yōu)點(diǎn)，因而其能較好地適應(yīng)對(duì)流天氣實(shí)時(shí)動(dòng)態(tài)變化的環(huán)境并快速規(guī)劃出改航航線(xiàn)，使保持穩(wěn)定性能參數(shù)的航空器能在較短的反應(yīng)時(shí)間內(nèi)完成繞飛任務(wù)。惡劣天氣下的改航路徑規(guī)劃目的是讓航空器在二維網(wǎng)格空間內(nèi)安全避讓飛行受限區(qū)，以較少的航向改變次數(shù)及較短的改航航程為約束由起始節(jié)點(diǎn)出發(fā)沿一條優(yōu)化路徑至目標(biāo)節(jié)點(diǎn)。

為適應(yīng)所建立的環(huán)境模型，航空器飛行運(yùn)動(dòng)作如下簡(jiǎn)化：

1）相對(duì)于天氣的幾何尺度，航空器在二維平面上視為質(zhì)點(diǎn)。

2）航空器在巡航階段速度Vc保持不變，假設(shè)其各航段內(nèi)做勻速直線(xiàn)運(yùn)動(dòng)。

3）出于飛行安全及航空器性能考慮，航空器在改航過(guò)程中只能進(jìn)行3個(gè)方向的機(jī)動(dòng)飛行，即保持原航向、左轉(zhuǎn)45°、右轉(zhuǎn)45°，如圖2所示。

圖2　柵格環(huán)境下航向的選擇狀態(tài)Fig.2 Course selection state in grid environm ent

4）航空器在柵格環(huán)境模型中，每單位時(shí)間均是徑向飛往下一網(wǎng)格的中心點(diǎn)，航程為L(zhǎng)或1.414 L，計(jì)算航程時(shí)改航起始點(diǎn)與改航結(jié)束點(diǎn)均以其所在柵格的中心點(diǎn)為準(zhǔn)。

運(yùn)動(dòng)中的螞蟻k（k=1，2，…，m）會(huì)根據(jù)相鄰的柵格的連通航段上的已有信息素的多少來(lái)決定它下一步的轉(zhuǎn)移方向。螞蟻k在時(shí)刻t從柵格i向柵格j轉(zhuǎn)移的概率定義為

否則

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

經(jīng)過(guò)n個(gè)時(shí)刻，蟻群完成一輪循環(huán)后，對(duì)各條柵格連通航段進(jìn)行全局信息素的調(diào)整，為加快算法的收斂速度，僅對(duì)本次循環(huán)中最優(yōu)更新螞蟻k所走過(guò)的航線(xiàn)進(jìn)行信息素增強(qiáng)

2.2改進(jìn)蟻群算法的實(shí)現(xiàn)步驟

步驟1：將探測(cè)到或預(yù)報(bào)的氣象信息數(shù)值化，利用柵格法建立環(huán)境模型。

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

步驟3：設(shè)初始柵格為每只螞蟻的當(dāng)前柵格gi（i= 0，1…，m-1），同時(shí)將m只螞蟻置于初始柵格上，gi序號(hào)記入相應(yīng)螞蟻的tabu。

步驟4：根據(jù)式（2）和式（3）分別計(jì)算從gi到與其相連通柵格的轉(zhuǎn)移概率，并根據(jù)概率移動(dòng)至下一柵格gi’。

步驟5：將gi’序號(hào)記入對(duì)應(yīng)的tabu。判斷此時(shí)是否有螞蟻到達(dá)目標(biāo)柵格，若有，結(jié)束本輪循環(huán)，更新shorterlen，取本次循環(huán)中最優(yōu)螞蟻序號(hào)為k。若沒(méi)有，令gi= gi’，轉(zhuǎn)到步驟4。

步驟6：根據(jù)公式（4）、（5）和（6）對(duì)各條航線(xiàn)上的信息素濃度進(jìn)行衰減，并僅對(duì)螞蟻k所走過(guò)的改航路徑上的信息素進(jìn)行增強(qiáng)。

步驟7：n=n+1。若n≤N，shorterlen=0，清空每只螞蟻對(duì)應(yīng)的tabu，轉(zhuǎn)到步驟3。

步驟8：將相鄰柵格之間的部分彎曲航段拉直修正，輸出全局最優(yōu)航線(xiàn)及其長(zhǎng)度。

3　仿真算例分析

根據(jù)前面的數(shù)學(xué)模型，下面以貴陽(yáng)—長(zhǎng)沙航路為例來(lái)說(shuō)明，當(dāng)沿航線(xiàn)及其鄰近空域受惡劣天氣影響時(shí)，運(yùn)用本文所提出的方法規(guī)劃臨時(shí)航線(xiàn)，航空器能安全有效地繞過(guò)飛行受限區(qū)。

貴陽(yáng)—長(zhǎng)沙航線(xiàn)沿途的報(bào)告點(diǎn)依次是：貴陽(yáng)（KW E）—P173—P217—P293—懷化（ZHJ）—P159—老糧倉(cāng)（LLC）—長(zhǎng)沙（CSX）。氣象部門(mén)通過(guò)多普勒氣象雷達(dá)和氣象衛(wèi)星測(cè)得航段P217—P293—懷化（ZHJ）—P159有雷暴，情報(bào)部門(mén)根據(jù)預(yù)報(bào)確定會(huì)受其影響的不同等級(jí)的飛行受限區(qū)，如圖3所示。在P217與P159之間建立柵格環(huán)境模型，柵格數(shù)量為14×12，L取10 nm。

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

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

表1　實(shí)驗(yàn)最優(yōu)參數(shù)設(shè)置Tab.1 Experim ental optim al param eter settings

圖4　改進(jìn)蟻群算法收斂曲線(xiàn)Fig.4 Convergence curves of im proved ant colony algorithm

圖5　各航線(xiàn)平均航程Fig.5 Average distance of all courses

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

4　結(jié)語(yǔ)

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

參考文獻(xiàn)：

[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]李雄，徐肖豪，朱承元，等.基于幾何算法的空中交通改航路徑規(guī)劃[J].系統(tǒng)工程，2008，26（8）：37-40.

[3]李雄，徐肖豪，王超，等.基于凸多邊形的飛行改航區(qū)劃設(shè)及路徑規(guī)劃研究[C]//中國(guó)控制與決策會(huì)議.沈陽(yáng)：東北大學(xué)出版社，2008：3083-3088.

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

[5]徐肖豪，李成功，趙嶷飛，等.基于人工勢(shì)場(chǎng)算法的改航路徑規(guī)劃[J].交通運(yùn)輸工程學(xué)報(bào)，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]李士勇.蟻群算法及其應(yīng)用[M].哈爾濱：哈爾濱工業(yè)大學(xué)出版社，2004.

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

[9]任春明，張建勛.基于優(yōu)化蟻群算法的機(jī)器人路徑規(guī)劃[J].計(jì)算機(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，F(xiàn)IDALGO 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.

（責(zé)任編輯：黃月）

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

作者簡(jiǎn)介：王莉莉（1973—），女，陜西興平人，教授，博士，研究方向?yàn)榭沼蛞?guī)劃、空中交通管理.

收稿日期：2014-03-26；修回日期：2014-09-01基金項(xiàng)目：國(guó)家自然科學(xué)基金項(xiàng)目（61179042）；中央高校基本科研業(yè)務(wù)費(fèi)專(zhuān)項(xiàng)（ZXH2012L005）

中圖分類(lèi)號(hào)：V355

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1674-5590（2016）01-0015-04