基于飛機(jī)性能影響的路徑優(yōu)化算法

回 憶，魏志強(qiáng)，魏路歡

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

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

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

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

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

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

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

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

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

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

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

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

圖1 性能計(jì)算方法Fig.1 Algorithm of performance calculation

1.3 飛行成本計(jì)算模型

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

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

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

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

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

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

圖2 重名航路點(diǎn)處理流程Fig.2 Process of duplicated name waypoints

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

基于已經(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為圖中任意兩點(diǎn)，求一條道路μ，使它是從va到vb的所有路中總權(quán)最小的路，即

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

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

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

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

2 計(jì)算分析

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

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

2.1 估計(jì)代價(jià)函數(shù)系數(shù)的影響

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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