基于改進(jìn)蟻群算法的動(dòng)態(tài)航路規(guī)劃研究

武丁杰 鄒德龍 葛昆

摘? 要：文章通過研究目前危險(xiǎn)天氣對(duì)航路航線的影響，在分析最優(yōu)航線選取的基礎(chǔ)上，細(xì)化航路航線的選取方向，定義空域元胞尺寸和速度位置演化的規(guī)則，構(gòu)造危險(xiǎn)天氣元胞自動(dòng)機(jī)模型，在此基礎(chǔ)上，利用改進(jìn)蟻群算法進(jìn)行最優(yōu)路徑規(guī)劃。提出了基于空域元胞位置演化規(guī)則的動(dòng)態(tài)局部航路規(guī)劃方法。在建模環(huán)境下的仿真結(jié)果表明，基于此元胞自動(dòng)機(jī)演化規(guī)則的方法，能夠完成在動(dòng)態(tài)環(huán)境下的最優(yōu)路徑選取的任務(wù)，并且在路徑的長(zhǎng)度上有較為明顯的改善，快速高效的規(guī)劃并選取出一條路徑，并隨環(huán)境的變化相應(yīng)的改變，具有一定的穩(wěn)定性和很強(qiáng)的適應(yīng)能力。

? 關(guān)鍵詞：元胞自動(dòng)機(jī);改進(jìn)蟻群算法;動(dòng)態(tài)環(huán)境;航路規(guī)劃

? 中圖分類號(hào)：F560? ? 文獻(xiàn)標(biāo)識(shí)碼：A

Abstract： In this paper， by studying the impact of current dangerous weather on air routes， based on the analysis of the selection of optimal routes， the selection direction of air routes is refined， the airspace cell size and the rules for the evolution of speed position are defined， and the dangerous weather cellular automaton is constructed. Based on this model， the improved ant colony algorithm is used for optimal path planning. A dynamic local route planning method based on airspace cell position evolution rules is proposed. The simulation results in the modeling environment show that the method based on this cellular automaton evolution rule can complete the task of selecting the optimal path in a dynamic environment， and there is a more obvious improvement in the length of the path， which is fast and efficient. Plan and select a path， and change accordingly with changes in the environment， with a certain degree of stability and strong adaptability.

Key words： cellular automata; improved ant colony algorithm; dynamic environment; route planning

0? 引? 言

? 隨著我國民航業(yè)的發(fā)展，航路航線上危險(xiǎn)天氣等氣象要素對(duì)航空運(yùn)輸?shù)挠绊懺絹碓斤@著。而目前針對(duì)該問題的處理方式，仍為人工判別，自動(dòng)化程度較低，這不僅增加了空中交通管制員的工作負(fù)荷，還給我國民航運(yùn)輸業(yè)帶來了不便。不僅如此，由于天氣預(yù)報(bào)的不確定性，空中交通管制員通常會(huì)選擇較為保守的距離繞過天氣活動(dòng)。天氣預(yù)報(bào)也并不總是將當(dāng)前條件與計(jì)劃航路的進(jìn)展相匹配，并且由于空中交通管制員在天氣事件中特別繁忙，因此他們可能會(huì)錯(cuò)過圍繞惡劣天氣的更有效路線的可行機(jī)會(huì)[1]。

改航路徑規(guī)劃是指在局部空域內(nèi)，由于受到隨機(jī)因素的影響而產(chǎn)生飛行受限區(qū)時(shí)，通過設(shè)置對(duì)受到該隨機(jī)因素干擾的航路進(jìn)行調(diào)整，規(guī)劃出臨時(shí)飛行路徑以實(shí)現(xiàn)空域障礙規(guī)避的方法。危險(xiǎn)天氣主要是指颶風(fēng)、雷暴、湍流、風(fēng)切變和強(qiáng)對(duì)流等中小規(guī)模天氣系統(tǒng)。危險(xiǎn)天氣區(qū)域根據(jù)其分布差異分為：塊狀區(qū)域、帶狀區(qū)域和散點(diǎn)狀區(qū)域。目前，針對(duì)危險(xiǎn)天氣影響下的改航路徑規(guī)劃研究主要包括：空域的劃設(shè)、單/多航班改航路徑規(guī)劃和空域流量分配等問題。

? Dixon等人最早于1993年研究了危險(xiǎn)天氣影響下的改航路徑規(guī)劃問題[2]。1999年，Krozel等人發(fā)現(xiàn)航站樓附近的惡劣天氣是造成航空器延誤的主要原因，并對(duì)風(fēng)暴影響下的航路規(guī)劃問題展開研究。在國內(nèi)，孟令航等人在2012年利用云團(tuán)預(yù)測(cè)狀態(tài)的不確定性和外推位置的隨機(jī)誤差等現(xiàn)象，提出了考慮改航路徑偏差及距離的動(dòng)態(tài)航路規(guī)劃模型[3]。張兆寧等分別在2015年和2016年提出危險(xiǎn)天氣下基于多重Morphin算法的終端區(qū)三維實(shí)時(shí)改航方法和散點(diǎn)狀分布危險(xiǎn)天氣下的終端區(qū)動(dòng)態(tài)改航方法[4]。呂宗平等人也在2017年從雷暴圖中解析飛行限制區(qū)，以最短航段距離和最大轉(zhuǎn)彎角度為限制條件，建立的模型可以在航路網(wǎng)受到影響的情況下，為多個(gè)航空器規(guī)劃出改航路徑[5]。

危險(xiǎn)天氣會(huì)直接導(dǎo)致空域容量的減小，目前常見的應(yīng)對(duì)方法主要包括地面等待措施、空中等待措施和改航措施[6]。前兩者在實(shí)際運(yùn)行中相對(duì)容易實(shí)現(xiàn)，但是燃油和時(shí)間的成本大大增加;雖然空域容量減小，但是在空域流量未達(dá)到容量時(shí)，實(shí)施改航措施是最有效也是最經(jīng)濟(jì)的辦法。另外由于危險(xiǎn)天氣的位置是隨著時(shí)間不斷變化的，當(dāng)飛機(jī)臨近存在危險(xiǎn)天氣區(qū)域的空域時(shí)，僅采用起飛前所規(guī)劃的靜態(tài)航路，并不能滿足實(shí)際的應(yīng)用需求，因此進(jìn)行實(shí)時(shí)路徑規(guī)劃是非常有必要的。

1? 空域元胞的演化

? Von Neumann在20世紀(jì)50年代提出元胞自動(dòng)機(jī)（Cellular Automata，CA），是一種在狀態(tài)、空間、時(shí)間上都離散，時(shí)間因果關(guān)系與空間相互作用作為局部，能模擬復(fù)雜的系統(tǒng)時(shí)空演化過程的網(wǎng)絡(luò)動(dòng)力學(xué)模型[7]。散布于規(guī)則網(wǎng)格中的每一個(gè)元胞取有限的離散狀態(tài)，遵照同樣的作用規(guī)則，依據(jù)確定的局部規(guī)則作同步更新。大量元胞依據(jù)簡(jiǎn)單的相互作用構(gòu)成了動(dòng)態(tài)系統(tǒng)的演化。其特點(diǎn)是在狀態(tài)、空間、時(shí)間上都離散，每個(gè)變量只取有限的多個(gè)狀態(tài)，且其狀態(tài)改變的規(guī)則在空間和時(shí)間上均為局部的[8-9]。

? 當(dāng)對(duì)航路進(jìn)行的動(dòng)態(tài)規(guī)劃時(shí)，可以將需要改航的空域看作是二維的空間。本文先將目標(biāo)航路空域分解為柵格單元，每一個(gè)柵格單元都代表一個(gè)空域元胞。其中，空域元胞的狀態(tài)分別為1或0，0表示為自由的空域元胞，1為有天氣的空域限制元胞。由于危險(xiǎn)天氣在實(shí)際情況中是不斷移動(dòng)的，因此可以將已知的危險(xiǎn)天氣區(qū)域用柵格法在空域中表示出來，如圖1所示。

并按照以下規(guī)則來模擬危險(xiǎn)天氣區(qū)域的移動(dòng)。其規(guī)則如下：（1）空域元胞的初始狀態(tài)為0，所有的元胞都是可以通過的，將已知的危險(xiǎn)天氣的范圍與位置，在空域的相應(yīng)位置劃設(shè)出來。（2）已知危險(xiǎn)天氣區(qū)域的元胞按照一定的速度及方向進(jìn)行移動(dòng)。

設(shè)在t時(shí)刻，一個(gè)有天氣的空域限制元胞i的位置為

Xt，

Yt，移動(dòng)速度為Vt，則在t+1時(shí)刻的該空域限制元胞的位置更新為：

Xt+1=Xt+kVt

Yt+1=Yt+kVt

其中：k為根據(jù)已知移動(dòng)方向所設(shè)置的參數(shù)，取值為1或-1。

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

目前，多種動(dòng)態(tài)環(huán)境路徑規(guī)劃方法已經(jīng)被廣泛應(yīng)用，常用的算法包括勢(shì)場(chǎng)法、A*算法和Dijkstra算法等基本算法，以及蟻群算法、粒子群算法、遺傳算法和人工神經(jīng)網(wǎng)絡(luò)等啟發(fā)式優(yōu)化算法。蟻群算法、遺傳算法、粒子群算法及人工魚群算法等均為基于概率型的全局優(yōu)化算法，約束條件的處理方式相對(duì)簡(jiǎn)單，其中蟻群算法以其抗干擾能力強(qiáng)、并行性及易于其他算法結(jié)合等優(yōu)點(diǎn)在解決路徑規(guī)劃問題時(shí)脫穎而出[10]。

? 蟻群算法的本質(zhì)是起始點(diǎn)和終點(diǎn)之間路徑的長(zhǎng)短與在路徑上殘留的信息素之間呈負(fù)相關(guān)，而信息素的濃度與該路徑被后續(xù)蟻群選中的可能性為正相關(guān)，因此路徑的長(zhǎng)短與被選概率的大小呈負(fù)相關(guān)的。蟻群算法只需要根據(jù)已有路徑中殘留的信息素這一局部信息而無需了解整個(gè)空域內(nèi)所有障礙物的情況便可搜索到起始點(diǎn)和終點(diǎn)之間的最優(yōu)路徑[11]。

? 如果僅采用基本蟻群算法的搜尋方式，航空器所在的空域元胞會(huì)存在8個(gè)相鄰的空域元胞作為可移動(dòng)的元胞（不考慮已經(jīng)路過的空域元胞和障礙元胞），這種搜尋方式會(huì)隨著空域元胞數(shù)量的增加以及設(shè)定的螞蟻數(shù)量，大量增加搜索時(shí)間，且容易造成如圖2所示的奇異航段。

因此采用基于CA的改進(jìn)蟻群算法，根據(jù)起始位置以及終點(diǎn)的相對(duì)位置，設(shè)置一定的搜索策略。減少搜尋的節(jié)點(diǎn)數(shù)，縮小搜尋范圍，不僅節(jié)約時(shí)間成本，還能夠提高優(yōu)化的效率。本文假設(shè)路徑優(yōu)化航段的方向?yàn)閺腁到B，如圖3所示。

此時(shí)，進(jìn)行路徑搜尋時(shí)只需要搜尋如圖中的1、2、3、4、5這個(gè)5個(gè)元胞（不考慮已經(jīng)路過的空域元胞和障礙元胞）。

? 本文采用的是基于CA模型的改進(jìn)蟻群算法，在危險(xiǎn)天氣不斷移動(dòng)的過程中，不斷規(guī)避危險(xiǎn)天氣區(qū)域的基礎(chǔ)上尋求并優(yōu)化路徑，流程圖如圖4所示，具體步驟如下：

（1）建立柵格環(huán)境及參數(shù)初始化。將目標(biāo)空域轉(zhuǎn)化為一個(gè)二值矩陣，確定起始節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)在空域中的位置。根據(jù)不同的需要，本文設(shè)定螞蟻的數(shù)目以及算法的迭代次數(shù)均為100，將所有的螞蟻都放在起始點(diǎn)的位置，且各螞蟻之間保持相對(duì)獨(dú)立。

? （2）禁忌表初始化，將各螞蟻禁忌表清空，再將所有螞蟻出發(fā)點(diǎn)以及所有危險(xiǎn)限制空域所在元胞存入各螞蟻的禁忌表。

（3）所有螞蟻從元胞i移動(dòng)j到的可行性大小為pt，公式如下：

pt=? ? i∈

allowed; j∈otherwise

其中：σ為信息啟發(fā)式因子，k為期望啟發(fā)式因子，該時(shí)刻t與上文中空域元胞演化時(shí)刻中的t相同，τt則表示在t時(shí)刻路徑i，j上的殘留信息素的濃度;η為啟發(fā)函數(shù)，表示路徑i，j上的能見度，同時(shí)體現(xiàn)了螞蟻在元胞間轉(zhuǎn)移時(shí)的啟發(fā)程度，一般取η=1/d，d為螞蟻待選的轉(zhuǎn)移元胞j與目標(biāo)節(jié)點(diǎn)之間的距離。

（4）每一代完成路徑搜索之后，基于以下公式，根據(jù)信息素?fù)]發(fā)程度以及本代蟻群留下的信息素，重新計(jì)算路徑上的信息素濃度。

τt+n=1-ρ·τt+Δτt

Δτt=∑Δτt

Δτ=

其中：Δτ表示的是螞蟻k在邊i，j中殘留的單位長(zhǎng)度的信息素量;ρ為信息素?fù)]發(fā)系數(shù)，1-ρ為信息素的殘留因子;L代表在這一輪路徑搜索中，第k只螞蟻所走過的路徑長(zhǎng)度;Q則代表信息素強(qiáng)度，制約著此算法構(gòu)造解收斂速度。

（5）更新禁忌表，各螞蟻轉(zhuǎn)移到新的空域元胞時(shí)，把該螞蟻當(dāng)前所在元胞添加到它的禁忌表里面。

? （6）記錄每只螞蟻經(jīng)過的空域元胞的順序以及所走過的路徑長(zhǎng)度。

（7）若迭代完成，則循環(huán)結(jié)束。輸出最優(yōu)的螞蟻經(jīng)過的空域元胞順序以及該路徑的長(zhǎng)度。

3? 動(dòng)態(tài)路徑規(guī)劃仿真

? 改航路徑在能夠繞飛危險(xiǎn)天氣區(qū)域并保證飛行安全的同時(shí)，不影響空域利用率且兼顧運(yùn)行的效率，因此在建立優(yōu)化模型前，提出合理的假設(shè)，假設(shè)條件如下：（1）假設(shè)航空器為一個(gè)質(zhì)點(diǎn)，沿航路的中心線以相同的速度勻速飛行，且不考慮航空器個(gè)體差異，例如速度、機(jī)型等;（2）航路網(wǎng)絡(luò)元胞是二維的平面網(wǎng)絡(luò)結(jié)構(gòu)，不考慮航空器的上升和下降，且將所有航空器都放置于同一高度層;（3）由于存在危險(xiǎn)天氣的限制空域內(nèi)部是不可以穿越的，對(duì)其邊界分別經(jīng)過擴(kuò)展處理后，屬于安全區(qū);

（4）由于危險(xiǎn)天氣區(qū)域的移動(dòng)速度遠(yuǎn)遠(yuǎn)小于航空器的飛行速度，因此假設(shè)航空器在繞飛危險(xiǎn)天氣區(qū)域時(shí)，危險(xiǎn)天氣區(qū)域的移動(dòng)速度為0。

? 本文是通過Matlab語言編程，進(jìn)行仿真工作。整個(gè)路徑仿真的空域運(yùn)行環(huán)境在25×25的元胞中，進(jìn)行實(shí)時(shí)路徑規(guī)劃，元胞的網(wǎng)格邊長(zhǎng)a=20km。隨著危險(xiǎn)天氣元胞的不斷移動(dòng)，分析在塊狀危險(xiǎn)天氣區(qū)、帶狀危險(xiǎn)天氣區(qū)以及散點(diǎn)狀危險(xiǎn)天氣區(qū)，三種危險(xiǎn)天氣情況下的基于改進(jìn)蟻群算法的路徑規(guī)劃。塊狀危險(xiǎn)天氣區(qū)的基于改進(jìn)蟻群算法的動(dòng)態(tài)航路規(guī)劃如圖5所示。

? 帶狀危險(xiǎn)天氣區(qū)的基于改進(jìn)蟻群算法的動(dòng)態(tài)航路規(guī)劃如圖6所示。

? 散點(diǎn)狀危險(xiǎn)天氣區(qū)的基于改進(jìn)蟻群算法的動(dòng)態(tài)航路規(guī)劃如圖7所示。

分析上述的仿真結(jié)果可以得知：在各類的危險(xiǎn)天氣區(qū)域?qū)沼蚝铰泛骄€造成影響的場(chǎng)景下，隨著危險(xiǎn)天氣區(qū)域的移動(dòng)，進(jìn)行實(shí)時(shí)的動(dòng)態(tài)航路規(guī)劃，可以有效地規(guī)劃出一條航路，保證航班安全地規(guī)避危險(xiǎn)天氣的同時(shí)，提升航路的容量，減小飛行的成本。各類危險(xiǎn)天氣場(chǎng)景下，路徑規(guī)劃的長(zhǎng)度以及所消耗的時(shí)間（包括危險(xiǎn)天氣區(qū)域移動(dòng)、改航路徑規(guī)劃）如表1所示。

4? 結(jié)? 論

（1）構(gòu)建目標(biāo)空域的元胞自動(dòng)機(jī)模型，描述已知危險(xiǎn)天氣區(qū)，針對(duì)不斷移動(dòng)的危險(xiǎn)天氣區(qū)域，提出基于改進(jìn)蟻群算法的動(dòng)態(tài)航路規(guī)劃模型，并確定了約束條件。

? （2）改進(jìn)傳統(tǒng)蟻群算法中的搜尋方式，以提高路徑搜索中的有效性，減少搜尋節(jié)點(diǎn)，節(jié)約搜尋時(shí)間成本，提高優(yōu)化效率。仿真結(jié)果表明：運(yùn)用該算法能夠針對(duì)動(dòng)態(tài)的危險(xiǎn)天氣，實(shí)時(shí)的進(jìn)行路徑規(guī)劃。

? （3）方法僅考慮航空器二維的路徑規(guī)劃，未涉及改變航空器的飛行高度，該問題將是下一階段的研究方向。

參考文獻(xiàn)：

[1]? Evans A D， Sridhar B， Mcnally D. Improving Operational Acceptability of Dynamic Weather Routes Through Analysis of Commonly Use Routings[C] // Aiaa Aviation Technology， Integration & Operations Conference， 2016.

[2]? DIXON M， WEINER G. Automated Aircraft Routing Through Weather-Impacted Airspace[C] // Vienna， VA： Fifth International Conference on Aviation Weather Systema， 1993：295-298.

[3] 孟令航，徐肖豪，李善梅，等. 不確定強(qiáng)對(duì)流天氣下動(dòng)態(tài)改航路徑規(guī)劃[J]. 西南交通大學(xué)學(xué)報(bào)，2012，47（4）：686-691.

[4] 張兆寧，魏中慧. 散點(diǎn)狀分布危險(xiǎn)天氣下的終端區(qū)動(dòng)態(tài)改航方法[J]. 中國安全科學(xué)學(xué)報(bào)，2016，26（1）：40-44.

[5] 呂宗平，王清琦，靳宇波，等. 超級(jí)單體雷暴下的改航模型研究[J]. 飛行力學(xué)，2017，2（2）：88-91，96.

[6] 向征，張文奇，張文軍. 雷暴天氣下基于多航空器沖突避讓的路徑規(guī)劃[J]. 中國安全科學(xué)學(xué)報(bào)，2019，29（8）：155-160.

[7] 酈晴云. 基于交通流特征的航路網(wǎng)絡(luò)節(jié)點(diǎn)布局優(yōu)化[D]. 南京：南京航空航天大學(xué)（碩士學(xué)位論文），2018.

[8] 楊凱，康瑞. 基于元胞自動(dòng)機(jī)的航空器起降間隔研究[J]. 工程科學(xué)與技術(shù)，2016（S2）：127-134.

[9] Wang S， Cao X， Haiyun L I， et al. Air route network optimization in fragmented airspace based on cellular automata[J]. 中國航空學(xué)報(bào)（英文版），2017（30）：1184-1195.

[10] 梁凱，毛劍琳. 動(dòng)態(tài)環(huán)境下基于改進(jìn)蟻群算法的路徑規(guī)劃研究[J]. 電子測(cè)量技術(shù)，2020（1）：82-87.

[11] 王瑛，鄭煜坤，姚頔，等. 危險(xiǎn)天氣下改航路徑網(wǎng)絡(luò)規(guī)劃[J]. 系統(tǒng)工程與電子技術(shù)，2019，41（6）：1309-1315.