武丁杰 鄒德龍 葛昆

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

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

? 中圖分類號：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? 引? 言

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

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

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

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

1? 空域元胞的演化

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

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

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

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

Xt，

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

Xt+1=Xt+kVt

Yt+1=Yt+kVt

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

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

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

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

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

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

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

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

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

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

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

pt=? ? i∈

allowed; j∈otherwise

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

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

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

Δτt=∑Δτt

Δτ=

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

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

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

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

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

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

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

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

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

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

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

4? 結? 論

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

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

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

參考文獻：

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

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

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

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

[7] 酈晴云. 基于交通流特征的航路網絡節(jié)點布局優(yōu)化[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] 梁凱，毛劍琳. 動態(tài)環(huán)境下基于改進蟻群算法的路徑規(guī)劃研究[J]. 電子測量技術，2020（1）：82-87.

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