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

武丁杰，鄒德龍，葛 昆

（中國民用航空飛行學(xué)院 空中交通管理學(xué)院，四川 廣漢 618307）

0 引 言

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

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

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

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

1 空域元胞的演化

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

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

圖1 危險天氣區(qū)域運行環(huán)境元胞

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

設(shè)在t 時刻，一個有天氣的空域限制元胞i 的位置為（X（t ）,Y（t）），移動速度為V（t ），則在t+1 時刻的該空域限制元胞的位置更新為：

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

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

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

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

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

圖2 基本蟻群算法的舉例

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

圖3 改進蟻群的搜索策略

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

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

圖4 基于元胞自動機的改進蟻群算法流程圖

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

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

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

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

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

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

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

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

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

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

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

圖5 塊狀天氣區(qū)實時路徑規(guī)劃

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

圖6 帶狀天氣區(qū)實時路徑規(guī)劃

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

圖7 散點狀天氣區(qū)實時路徑規(guī)劃

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

表1 三種天氣下的最優(yōu)路徑長度及耗時結(jié)果

4 結(jié) 論

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

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

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