基于改進蟻群算法的動態航路規劃研究

武丁杰 鄒德龍 葛昆

摘? 要：文章通過研究目前危險天氣對航路航線的影響，在分析最優航線選取的基礎上，細化航路航線的選取方向，定義空域元胞尺寸和速度位置演化的規則，構造危險天氣元胞自動機模型，在此基礎上，利用改進蟻群算法進行最優路徑規劃。提出了基于空域元胞位置演化規則的動態局部航路規劃方法。在建模環境下的仿真結果表明，基于此元胞自動機演化規則的方法，能夠完成在動態環境下的最優路徑選取的任務，并且在路徑的長度上有較為明顯的改善，快速高效的規劃并選取出一條路徑，并隨環境的變化相應的改變，具有一定的穩定性和很強的適應能力。

? 關鍵詞：元胞自動機;改進蟻群算法;動態環境;航路規劃

? 中圖分類號：F560? ? 文獻標識碼：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? 引? 言

? 隨著我國民航業的發展，航路航線上危險天氣等氣象要素對航空運輸的影響越來越顯著。而目前針對該問題的處理方式，仍為人工判別，自動化程度較低，這不僅增加了空中交通管制員的工作負荷，還給我國民航運輸業帶來了不便。不僅如此，由于天氣預報的不確定性，空中交通管制員通常會選擇較為保守的距離繞過天氣活動。天氣預報也并不總是將當前條件與計劃航路的進展相匹配，并且由于空中交通管制員在天氣事件中特別繁忙，因此他們可能會錯過圍繞惡劣天氣的更有效路線的可行機會[1]。

改航路徑規劃是指在局部空域內，由于受到隨機因素的影響而產生飛行受限區時，通過設置對受到該隨機因素干擾的航路進行調整，規劃出臨時飛行路徑以實現空域障礙規避的方法。危險天氣主要是指颶風、雷暴、湍流、風切變和強對流等中小規模天氣系統。危險天氣區域根據其分布差異分為：塊狀區域、帶狀區域和散點狀區域。目前，針對危險天氣影響下的改航路徑規劃研究主要包括：空域的劃設、單/多航班改航路徑規劃和空域流量分配等問題。

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

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

1? 空域元胞的演化

? Von Neumann在20世紀50年代提出元胞自動機（Cellular Automata，CA），是一種在狀態、空間、時間上都離散，時間因果關系與空間相互作用作為局部，能模擬復雜的系統時空演化過程的網絡動力學模型[7]。散布于規則網格中的每一個元胞取有限的離散狀態，遵照同樣的作用規則，依據確定的局部規則作同步更新。大量元胞依據簡單的相互作用構成了動態系統的演化。其特點是在狀態、空間、時間上都離散，每個變量只取有限的多個狀態，且其狀態改變的規則在空間和時間上均為局部的[8-9]。

? 當對航路進行的動態規劃時，可以將需要改航的空域看作是二維的空間。本文先將目標航路空域分解為柵格單元，每一個柵格單元都代表一個空域元胞。其中，空域元胞的狀態分別為1或0，0表示為自由的空域元胞，1為有天氣的空域限制元胞。由于危險天氣在實際情況中是不斷移動的，因此可以將已知的危險天氣區域用柵格法在空域中表示出來，如圖1所示。

并按照以下規則來模擬危險天氣區域的移動。其規則如下：（1）空域元胞的初始狀態為0，所有的元胞都是可以通過的，將已知的危險天氣的范圍與位置，在空域的相應位置劃設出來。（2）已知危險天氣區域的元胞按照一定的速度及方向進行移動。

設在t時刻，一個有天氣的空域限制元胞i的位置為

Xt，

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

Xt+1=Xt+kVt

Yt+1=Yt+kVt

其中：k為根據已知移動方向所設置的參數，取值為1或-1。

2? 改進蟻群算法的路徑尋優

目前，多種動態環境路徑規劃方法已經被廣泛應用，常用的算法包括勢場法、A*算法和Dijkstra算法等基本算法，以及蟻群算法、粒子群算法、遺傳算法和人工神經網絡等啟發式優化算法。蟻群算法、遺傳算法、粒子群算法及人工魚群算法等均為基于概率型的全局優化算法，約束條件的處理方式相對簡單，其中蟻群算法以其抗干擾能力強、并行性及易于其他算法結合等優點在解決路徑規劃問題時脫穎而出[10]。

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

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

因此采用基于CA的改進蟻群算法，根據起始位置以及終點的相對位置，設置一定的搜索策略。減少搜尋的節點數，縮小搜尋范圍，不僅節約時間成本，還能夠提高優化的效率。本文假設路徑優化航段的方向為從A到B，如圖3所示。

此時，進行路徑搜尋時只需要搜尋如圖中的1、2、3、4、5這個5個元胞（不考慮已經路過的空域元胞和障礙元胞）。

? 本文采用的是基于CA模型的改進蟻群算法，在危險天氣不斷移動的過程中，不斷規避危險天氣區域的基礎上尋求并優化路徑，流程圖如圖4所示，具體步驟如下：

（1）建立柵格環境及參數初始化。將目標空域轉化為一個二值矩陣，確定起始節點和目標節點在空域中的位置。根據不同的需要，本文設定螞蟻的數目以及算法的迭代次數均為100，將所有的螞蟻都放在起始點的位置，且各螞蟻之間保持相對獨立。

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

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

pt=? ? i∈

allowed; j∈otherwise

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

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

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

Δτt=∑Δτt

Δτ=

其中：Δτ表示的是螞蟻k在邊i，j中殘留的單位長度的信息素量;ρ為信息素揮發系數，1-ρ為信息素的殘留因子;L代表在這一輪路徑搜索中，第k只螞蟻所走過的路徑長度;Q則代表信息素強度，制約著此算法構造解收斂速度。

（5）更新禁忌表，各螞蟻轉移到新的空域元胞時，把該螞蟻當前所在元胞添加到它的禁忌表里面。

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

（7）若迭代完成，則循環結束。輸出最優的螞蟻經過的空域元胞順序以及該路徑的長度。

3? 動態路徑規劃仿真

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

（4）由于危險天氣區域的移動速度遠遠小于航空器的飛行速度，因此假設航空器在繞飛危險天氣區域時，危險天氣區域的移動速度為0。

? 本文是通過Matlab語言編程，進行仿真工作。整個路徑仿真的空域運行環境在25×25的元胞中，進行實時路徑規劃，元胞的網格邊長a=20km。隨著危險天氣元胞的不斷移動，分析在塊狀危險天氣區、帶狀危險天氣區以及散點狀危險天氣區，三種危險天氣情況下的基于改進蟻群算法的路徑規劃。塊狀危險天氣區的基于改進蟻群算法的動態航路規劃如圖5所示。

? 帶狀危險天氣區的基于改進蟻群算法的動態航路規劃如圖6所示。

? 散點狀危險天氣區的基于改進蟻群算法的動態航路規劃如圖7所示。

分析上述的仿真結果可以得知：在各類的危險天氣區域對空域航路航線造成影響的場景下，隨著危險天氣區域的移動，進行實時的動態航路規劃，可以有效地規劃出一條航路，保證航班安全地規避危險天氣的同時，提升航路的容量，減小飛行的成本。各類危險天氣場景下，路徑規劃的長度以及所消耗的時間（包括危險天氣區域移動、改航路徑規劃）如表1所示。

4? 結? 論

（1）構建目標空域的元胞自動機模型，描述已知危險天氣區，針對不斷移動的危險天氣區域，提出基于改進蟻群算法的動態航路規劃模型，并確定了約束條件。

? （2）改進傳統蟻群算法中的搜尋方式，以提高路徑搜索中的有效性，減少搜尋節點，節約搜尋時間成本，提高優化效率。仿真結果表明：運用該算法能夠針對動態的危險天氣，實時的進行路徑規劃。

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

參考文獻：

[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] 孟令航，徐肖豪，李善梅，等. 不確定強對流天氣下動態改航路徑規劃[J]. 西南交通大學學報，2012，47（4）：686-691.

[4] 張兆寧，魏中慧. 散點狀分布危險天氣下的終端區動態改航方法[J]. 中國安全科學學報，2016，26（1）：40-44.

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

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

[7] 酈晴云. 基于交通流特征的航路網絡節點布局優化[D]. 南京：南京航空航天大學（碩士學位論文），2018.

[8] 楊凱，康瑞. 基于元胞自動機的航空器起降間隔研究[J]. 工程科學與技術，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]. 中國航空學報（英文版），2017（30）：1184-1195.

[10] 梁凱，毛劍琳. 動態環境下基于改進蟻群算法的路徑規劃研究[J]. 電子測量技術，2020（1）：82-87.

[11] 王瑛，鄭煜坤，姚頔，等. 危險天氣下改航路徑網絡規劃[J]. 系統工程與電子技術，2019，41（6）：1309-1315.