基于飛機性能影響的路徑優化算法

回 憶，魏志強，魏路歡

（中國民航大學空中交通管理學院，天津 300300）

隨著歐洲空域一體化改革的推進，空域使用規則逐漸向更加靈活機動的方向發展，使得航空公司可以更加靈活地選擇各個航段，形成一條最佳航路，以降低從國內直飛歐洲航線的燃油消耗和飛行成本。

給定起點以及終點，尋找出一條可行路徑的問題 在 無 人 機［1?2］、機 器 人［3?5］、游 戲 地 圖［6?7］等 領 域 擁有廣泛的應用場景，其中尋路空間模型和尋路算法問題引起了學者們的大量關注。尋路空間模型可分為幾何模型和符號模型，前者的典型代表有基于柵格和基于邊界的模型，主要利用各對象的坐標信息對空間進行精細劃分；后者的典型代表是基于集［8?9］和基于圖［10?12］的模型，主要利用各對象間的拓撲關系處理模型。處理航路問題時涉及的航路網絡雖然也包含坐標信息，但它是典型的圖模型，利用航路點之間的已知關系建模更加方便合理。

常見的尋路算法［2］有傳統的圖遍歷算法，如深度優先搜索（Depth first search，DFS）、廣度優先搜索（Breadth first search，BFS）、BFS 在有權圖中的擴展Dijkstra 算法、在Dijkstra 算法基礎上引入啟發函數的A*算法；還有蟻群算法、粒子群算法、遺傳算法等優化算法［13?15］。Dijkstra 算法可以實現從一個頂點到其他各點的最短路徑，這種全局搜索在做替代方案決策時會有一定的優勢［1］，但缺點是對于大規模問題可能無法在可接受的時間內給出精確的最優解。啟發式A*算法則是在其基礎上針對目標有方向地進行搜索，適用于大規模圖中的尋路行為，其中最差的情況是將圖中的邊和點全部考慮到，它的關鍵在于找到一個合適的估值函數，在保證能得到最優解的前提下盡量提高搜索效率。

康文雄等［16］提出了基于回溯法的分層Dijkstra算法，通過分層結構尋找局部最優解來求得全局最優解或次優解，出解速度較快，數據量較大時能快速找到次優解；薛雙飛等［17］在處理船舶航線規劃問題時考慮到海上風電場區內船舶避碰問題，利用改進的人工勢場模型分別建立風機威脅和他船威脅的勢場，柵格化地圖生成威脅地圖，以此作為權重，利用A*算法找到優化航線。類似地，黃冬梅等［18］考慮到風浪因素對航行造成的危險，篩選出危險點集后，使用動態風浪網格數據確定權重并得到優化航線。

上述研究所涉及的圖模型中的各邊權重有些是固定值，有些是針對動態環境不斷變化的，但這種外界的變化與尋路過程本身是不相關的，也就是說并不會因為前續路線的選擇問題影響圖中各邊權重變化。但是，在巡航航路優化過程中，邊權重（如航段油耗、成本等）與飛機在該邊起始點的重量有關，而該重量值又與前續路線的實際油耗有關，也就是說不同的前續路線會造成同一條邊的權重不同，因此需要在優化中實時計算邊權重和估值函數。再結合計算權重時需要將航路劃分成段進行重量迭代計算，每次分段后的計算都需要進行相應的飛機性能參數的積分計算與高空風溫數據插值計算，這樣的處理過程與傳統的權重為距離常值相比，計算資源消耗較大［19］，該問題本身規模也較大，如何處理此類權重計算和尋路算法是值得研究的。首先對高空氣象預報數據、航路數據、飛機性能參數計算模型進行了處理，在此基礎上建立了高空航路優化算法，然后找出使尋路算法有最佳表現的A*算法估值函數系數和性能計算步長，最后針對典型飛行任務，對不同優化目標下的結果進行對比，分析了成本指數、飛機起始質量和飛行高度層等因素對航路優化的影響。

1 高空飛行航路優化算法

1.1 高空氣象預報數據的處理算法

根據二進制的通用規則分布信息版本2（Gen?eral regularly?distributed information in binary form，GRIB2）格式原始氣象數據［20?21］，提取出特定時刻下，由不同經緯度以及不同氣壓高度確定的網格氣象數據，包括且不限于：對流層頂溫度、各等壓面溫度、各等壓面風速u方向分量和v方向分量等。其中風速是矢量，由東西方向風分量u和南北方向風分量v共同決定，其大小ws與方向wd分別為

當需要考慮某段航路上的風速時，找到該航段中點，采用雙線性插值法得到該中點處的風速，并用此值近似代表整段航路上的風速。該風速矢量在航向上的投影即順（逆）風分量，直接影響地速和航行時間，是稍后的性能計算中所需的重要參數。中點溫度可通過類似的方法進行計算，并用以代表整段航路上的溫度。

1.2 性能參數的迭代計算方法

航油成本在民航運輸中所占比重相當高，合理的飛行油耗可以有效地降低成本。在給定飛機質量、飛行高度和氣象風溫的條件下，燃油流量和飛行速度可根據性能數據庫求出，繼而飛行時間可求，而飛機油耗由燃油流量和飛行時間共同決定。但是，隨著燃油的消耗，飛機質量越來越小，該參數又會對燃油流量和飛行速度的計算帶來影響。所以，采取如圖1 所示的迭代方法，針對研究路徑內的每段航路，計算過程中將飛機質量迭代至不再發生變化為止，再據此計算該段航路上的飛行油耗和飛行時間。

圖1 性能計算方法Fig.1 Algorithm of performance calculation

1.3 飛行成本計算模型

飛行成本指數可以用來衡量航班的總成本，它被定義為小時成本與燃油成本的比值，即

式中：Chr為除燃油成本外的每小時使用成本，單位元/時；Clb為每百磅燃油成本，單位元/百磅。與飛行有關的航班總成本由燃油成本和時間成本組成，即

式中：t為飛行總時間，單位小時；F為飛行燃油總消耗量，單位千克。整理可得

在剛剛計算飛行油耗和飛行時間的基礎上，筆者可以計算出航班飛行成本C，單位元。

1.4 航路數據的加載與處理流程

使用航空無線電通信公司（Aeronautical radio incorporated，ARINC424）格式的航路數據，根據格式規則將數據文件導出整理形成csv 文件。其中每行數據代表一個航段，包括航段所屬航路名、相對位置、起始航路點、終止航路點經緯度等。分析該航路數據文件，發現其中存在了一些名稱相同但經緯度位置不同的航路點。故數據處理前需要進行數據檢查，對重名航路點重新進行命名。具體流程如圖2 所示。

圖2 重名航路點處理流程Fig.2 Process of duplicated name waypoints

1.5 航路優化算法的改進

基于已經轉換成連通圖的航路網絡結構，不同目標下的航路優化問題可看作是基于圖論的最短路徑問題。該問題的一般提法如下：設G=（V，E）為連通圖，圖中各邊（vi，vj）有權lij（lij=∞表示vi、vj間無邊），va、vb為圖中任意兩點，求一條道路μ，使它是從va到vb的所有路中總權最小的路，即

最小（考慮單源點的最短路徑問題）。式中va、vb分別為航路的起點和終點，連通圖G即航路網絡。各邊的權重根據航路優化目標的不同，可以是兩航路點間的距離、飛過兩航路點所需的油耗、飛行時間、飛行成本。

航路網絡圖中的航路點密集程度很高，在這種情況下，尋找起點和終點間的最優路線對計算量的需求相當大。考慮到制定航線的實際情況，起點和終點間的大圓航線幾何距離最短，根據不同目標尋找到的最優路線會有一定程度的偏離但不會偏離過多。因此，在進行航路優化時，研究范圍被縮減在以起點和終點為焦點的橢圓內，橢圓長軸的長度控制可變，通過適當選取起點和終點間距離的倍數確定（見圖3），使用該圖替換原航路網絡圖。

圖3 航路網絡計算域的橢圓形裁剪Fig.3 Ellipse cropping of the computational domain of route network

Dijkstra 算法雖然可以得到準確的最優解，但全局搜索耗時較久，此處采用啟發式A*算法進行加速。A*算法中涉及的估值函數h是在考慮氣象條件的情況下，基于當前點與結束點間的大圓航線對飛行油耗、時間、成本等性能進行計算，由于它本身是一種估計值，可以設計對h乘以一個系數k來表征所選估值函數的變化程度，然后選取合適的參數使得在計算代價相對較小的情況下得到滿意的目標路徑。

2 計算分析

前面介紹的算法部分適用于飛機性能允許范圍內的任意飛機初始質量、成本指數、飛行高度值，這些參數的變化雖然直接影響優化結果，但通過大量的算例分析，發現他們的變化趨勢是一致的。所以，為了使計算結果的呈現更加簡潔清晰，本部分從一到兩個具體的飛行任務案例出發，分析算法涉及的相關參數以及不同的優化目標（最短飛行路徑mins，最少飛行油耗minF，最快飛行時間mint，最低飛行成本minC）帶來的優化結果。

本部分的案例涉及的氣象數據來自某航空公司2020 年5 月7 日0 時的高空氣象GRIB2 文件，通過飛過航路點的經緯度位置以及飛行高度層可以確定出當地的國際標準大氣（International stan?dard atmosphere，ISA）溫度偏差。

2.1 估計代價函數系數的影響

當A*算法中估值函數h的系數k等于零時，正是Dijkstra 算法的實現步驟。因為Dijkstra 算法是可以給出準確的目標路徑的，變化估值函數的系數k，在全球航路網絡中選取起點ITE，終點OK，按照成本指數50、飛機起始質量295 000 kg、飛行高度層9 500 m 的計算條件，以minF為目標進行航路優化。對比優化結果、運算時間（以Dijkstra 算法得到準確解的時間為基準1，計算運算時間比值）、累計訪問航路點數目，具體如表1 所示。

表1 不同估值函數系數對應的優化結果、運算時間和累計訪問航路點數目Table 1 Optimization results, calculation time and cu?mulative number of visited waypoints for differ?ent estimated cost coefficients

實際上，k=0 和k=0.1 情況下得到的優化路線 是 完 全 一 致 的：ITE—SANDA—ROKKO—CUE40—TOZAN—TSUNO—JEC—BOKSA—NAMER-OK，該路線下的飛行油耗是60 124 kg；當k取其他值時，會得到稍區別于上一條優化路線的 另 一 條 路 線：IT E—S A N D A—R O K K O—C U E 4 0—T O Z A N—RAKDA—JEC—BOKSA—NAMER—OK，該路線下的飛行油耗是60 135 kg，比準確解多消耗了0.02%的燃油。與此同時，觀察運算時間和累計訪問航路點數目可以看到，隨著k值的增加，計算開銷顯著減小，選取較大的k值可以在保證準確性的基礎上提高計算效率，接下來的計算過程取k=0.9。

另外，涉及性能計算的質量迭代問題，原則上令計算中涉及的每段航路距離盡可能小，這樣飛機質量值能夠得及時更新，結果會更加準確。實際上考慮到航程距離和計算代價，選取固定的計算步長，每次計算時取該步長與它和下一航路點間的距離中的較小值作為計算步長。與前文研究估計代價函數系數對優化結果的影響類似，變化該計算步長，在全球航路網絡中選取起點ITE，終點OK，按照成本指數50、飛機起始質量295 000 kg、飛行高度層9 500 m 的計算條件，以minF為目標進行航路優化。對比優化結果、運算時間（以固定步長等于20 km 時的所需運算時間為基準1，計算運算時間比值）、累計訪問航路點數目，具體如表2 所示。

表2 不同固定步長對應的優化結果、運算時間和累計訪問航路點數目Table 2 Optimization results, calculation time and cu?mulative number of visited waypoints for differ?ent calculation steps

實際上，表格中的3 種情況下得到的優化路線是完全一致的：ITE—SANDA—ROKKO—CUE40—TOZAN-RAKDA—JEC—BOKSA—NAMER—OK，取不同的固定步長導致最終計算得到的飛行油耗有細微區別。前面已經提到固定步長越短，質量迭代越精確，此處以20 km 固定步長所對應的運算時間作為基準，可以發現隨著步長的進一步提高運算時間的減少并不明顯，但計算油耗值卻越來越偏離準確值，接下來的計算過程取固定步長等于100 km。

2.2 不同優化目標的結果對比

在全國航路網絡中，選取起點BUNTA，終點P13，按照成本指數50、飛機起始質量255 000 kg、飛行高度層9 500 m的計算條件，分別以mins、minF、mint、minC為目標進行航路優化，結果見表3。

表3 BUNTA 至P13 不同優化目標結果對比Table 3 Comparison of results of different optimization goals from BUNTA to P13

2.3 成本指數對優化結果的影響

根據前面的優化結果可知，以minF、mint和minC為優化目標時會得到相同的航路優化結果。所以接下來選定minC和最短路徑為優化目標，考慮由成本指數帶來的影響，分別選取成本指數等于20、50、80 和110，按照飛機起始質量255 000 kg、飛行高度層9 500 m 的計算條件，在全國航路網絡中選取起點BUNTA、終點P13 進行航路優化（見圖4）。

圖4 不同成本指數對BUNTA 至P13(全國航路)的航路優化的影響Fig.4 Impact of different cost indices on optimization from BUNTA to P13 (national airways)

2.4 飛機質量對優化結果的影響

類似地，選定minC和最短路徑為優化目標，考慮由飛機起始質量帶來的影響。分別選取飛 機 起 始 質 量 等 于215 000、235 000、255 000 和275 000 kg，按照成本指數50、飛行高度層9 500 m的計算條件，在全國航路網絡中選取起點BUN?TA、終點P13 進行航路優化（見圖5）。

圖5 不同飛機起始質量對BUNTA 至P13(全國航路)的航路優化的影響Fig.5 Impact of different aeroplane masses on optimization from BUNTA to P13 (national airways)

2.5 飛行高度層對優化結果的影響

最后，選定minC和最短路徑為優化目標，考慮由飛行高度層帶來的影響。分別選取飛行高度層等于8 900、9 500、10 100 和10 700 m，按照成本指數50、飛機起始質量255 000 kg 的計算條件，在全國航路網絡中選取起點BUNTA、終點P13 進行航路優化（見圖6）。

圖6 不同飛行高度層對BUNTA 至P13(全國航路)的航路優化的影響Fig.6 Impact of different flight altitudes on optimization from BUNTA to P13 (national airways)

3 結 論

分別以mins、minF、mint、minC為目標進行高空巡航航路優化，討論了經過改進的A*算法在大規模航路圖中的適用性。優化目標不同，所得優化路徑不一致，其中以飛行性能為目標minF、mint、minC可以得到相同的優化路線，而以傳統最短路mins為目標得到的優化路線是不同于其他情況的，此結果與預期相符，一方面改進A*算法相對于傳統最短路算法會增加計算時間，另一方面同樣以飛行性能最優為目標的情況下，相較于Dijkstra 算法它可以更迅速地找到優化路線。

成本指數不同決定優化路線時，是燃油成本的影響更大還是時間成本的影響更大，在相同的某種優化目標下，對于得到的優化路線，成本指數越高，油價影響越小，飛行油耗越高，時間影響越大，飛行時間越短；而飛機起始質量越大、飛行高度層越低時，飛行油耗越高。可以看出，以飛機性能和氣象數據為基礎的航路優化算法的影響因素較多，最低成本優化結果與傳統最短路徑優化相比，可減少燃油消耗，減少飛行時間，降低成本，產生不錯的經濟效益。

由于各地區實際運行情況并不相同，本文的研究內容沒有涉及當地的相關運行規則以及實際可能會碰到的相關管制情況，而是選擇使用了單一簡單圖模型來作為研究基準對象，目的是為了保證算法的普適性。后續可根據研究的具體區域在該基準模型的框架下進行相應的限制修改，為后續研究服務。