回 憶，魏志強，魏路歡

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

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

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

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

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

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

1 高空飛行航路優(yōu)化算法

1.1 高空氣象預(yù)報數(shù)據(jù)的處理算法

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

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

1.2 性能參數(shù)的迭代計算方法

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

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

1.3 飛行成本計算模型

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

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

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

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

1.4 航路數(shù)據(jù)的加載與處理流程

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

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

1.5 航路優(yōu)化算法的改進

基于已經(jīng)轉(zhuǎn)換成連通圖的航路網(wǎng)絡(luò)結(jié)構(gòu)，不同目標(biāo)下的航路優(yōu)化問題可看作是基于圖論的最短路徑問題。該問題的一般提法如下：設(shè)G=（V，E）為連通圖，圖中各邊（vi，vj）有權(quán)l(xiāng)ij（lij=∞表示vi、vj間無邊），va、vb為圖中任意兩點，求一條道路μ，使它是從va到vb的所有路中總權(quán)最小的路，即

最?。紤]單源點的最短路徑問題）。式中va、vb分別為航路的起點和終點，連通圖G即航路網(wǎng)絡(luò)。各邊的權(quán)重根據(jù)航路優(yōu)化目標(biāo)的不同，可以是兩航路點間的距離、飛過兩航路點所需的油耗、飛行時間、飛行成本。

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

圖3 航路網(wǎng)絡(luò)計算域的橢圓形裁剪Fig.3 Ellipse cropping of the computational domain of route network

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

2 計算分析

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

本部分的案例涉及的氣象數(shù)據(jù)來自某航空公司2020 年5 月7 日0 時的高空氣象GRIB2 文件，通過飛過航路點的經(jīng)緯度位置以及飛行高度層可以確定出當(dāng)?shù)氐膰H標(biāo)準(zhǔn)大氣（International stan?dard atmosphere，ISA）溫度偏差。

2.1 估計代價函數(shù)系數(shù)的影響

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

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

實際上，k=0 和k=0.1 情況下得到的優(yōu)化路線 是 完 全 一 致 的：ITE—SANDA—ROKKO—CUE40—TOZAN—TSUNO—JEC—BOKSA—NAMER-OK，該路線下的飛行油耗是60 124 kg；當(dāng)k取其他值時，會得到稍區(qū)別于上一條優(yōu)化路線的 另 一 條 路 線：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，比準(zhǔn)確解多消耗了0.02%的燃油。與此同時，觀察運算時間和累計訪問航路點數(shù)目可以看到，隨著k值的增加，計算開銷顯著減小，選取較大的k值可以在保證準(zhǔn)確性的基礎(chǔ)上提高計算效率，接下來的計算過程取k=0.9。

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

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

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

2.2 不同優(yōu)化目標(biāo)的結(jié)果對比

在全國航路網(wǎng)絡(luò)中，選取起點BUNTA，終點P13，按照成本指數(shù)50、飛機起始質(zhì)量255 000 kg、飛行高度層9 500 m的計算條件，分別以mins、minF、mint、minC為目標(biāo)進行航路優(yōu)化，結(jié)果見表3。

表3 BUNTA 至P13 不同優(yōu)化目標(biāo)結(jié)果對比Table 3 Comparison of results of different optimization goals from BUNTA to P13

2.3 成本指數(shù)對優(yōu)化結(jié)果的影響

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

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

2.4 飛機質(zhì)量對優(yōu)化結(jié)果的影響

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

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

2.5 飛行高度層對優(yōu)化結(jié)果的影響

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

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

3 結(jié) 論

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

成本指數(shù)不同決定優(yōu)化路線時，是燃油成本的影響更大還是時間成本的影響更大，在相同的某種優(yōu)化目標(biāo)下，對于得到的優(yōu)化路線，成本指數(shù)越高，油價影響越小，飛行油耗越高，時間影響越大，飛行時間越短；而飛機起始質(zhì)量越大、飛行高度層越低時，飛行油耗越高?？梢钥闯觯燥w機性能和氣象數(shù)據(jù)為基礎(chǔ)的航路優(yōu)化算法的影響因素較多，最低成本優(yōu)化結(jié)果與傳統(tǒng)最短路徑優(yōu)化相比，可減少燃油消耗，減少飛行時間，降低成本，產(chǎn)生不錯的經(jīng)濟效益。

由于各地區(qū)實際運行情況并不相同，本文的研究內(nèi)容沒有涉及當(dāng)?shù)氐南嚓P(guān)運行規(guī)則以及實際可能會碰到的相關(guān)管制情況，而是選擇使用了單一簡單圖模型來作為研究基準(zhǔn)對象，目的是為了保證算法的普適性。后續(xù)可根據(jù)研究的具體區(qū)域在該基準(zhǔn)模型的框架下進行相應(yīng)的限制修改，為后續(xù)研究服務(wù)。