基于蟻群算法的航空器滑行路徑優(yōu)化

吳 虹， 趙 征

(南京航空航天大學(xué) 民航學(xué)院， 南京 211106)

滑行道是連接停機(jī)位和跑道的必經(jīng)通道，在機(jī)場場面運(yùn)行中起著至關(guān)重要的作用，尤其對已經(jīng)實現(xiàn)機(jī)坪管制的機(jī)場而言，是僅次于停機(jī)位的重要資源.在大型樞紐機(jī)場，提高滑行道的運(yùn)行效率，一方面可以降低航空公司運(yùn)行成本，減少航空器運(yùn)行產(chǎn)生的環(huán)境污染;另一方面可以減輕機(jī)坪管制員的工作負(fù)荷，提高機(jī)場場面運(yùn)行的安全裕度.

提高滑行道運(yùn)行效率，主要方法是優(yōu)化航空器滑行路徑.在航空器滑行路徑優(yōu)化研究方面，國外起步較早，主要研究領(lǐng)域有靜態(tài)滑行優(yōu)化和動態(tài)滑行優(yōu)化.在靜態(tài)滑行優(yōu)化領(lǐng)域，2013年Lucas P·Rosa等[1-2]采用遺傳算法進(jìn)行航空器滑行路徑優(yōu)化，通過實驗數(shù)據(jù)分析，遺傳算法解決了航空器滑行沖突問題，提高了大型繁忙機(jī)場場面運(yùn)行效率.在動態(tài)滑行優(yōu)化領(lǐng)域，2015年Hang Zhou等[3-4]通過動態(tài)的對航空器滑行路徑進(jìn)行沖突檢測，并在此基礎(chǔ)上通過A*算法進(jìn)行航空器滑行路徑規(guī)劃.國內(nèi)相關(guān)研究起步較晚，主要是在國外研究成果的基礎(chǔ)上進(jìn)行開拓和創(chuàng)新，例如，2015年杜姍姍等[5]融合遺傳算法和蟻群算法各自的優(yōu)點，采用兩階段法求解最優(yōu)路徑，2017年付宇曉等[6]采用人工神經(jīng)網(wǎng)絡(luò)算法進(jìn)行動態(tài)滑行路徑研究.總的來說，國內(nèi)外學(xué)者研究的焦點集中在模型和算法上，對具體約束條件下的典型問題缺乏指導(dǎo)意義，本文在蟻群算法的基礎(chǔ)上，根據(jù)約束條件設(shè)計出符合現(xiàn)場實際運(yùn)行情況的仿真系統(tǒng)，并不斷驗證和優(yōu)化算法.

本文以南京機(jī)場為例，首先建立場面結(jié)構(gòu)數(shù)學(xué)模型，通過有向圖的方式，將機(jī)場場面抽象成節(jié)點路段型數(shù)學(xué)模型.其次，建立基于沖突檢測的滑行路徑優(yōu)化模型，并采用蟻群算法對模型進(jìn)行求解.最后結(jié)合機(jī)場實際運(yùn)行情況開發(fā)仿真系統(tǒng)，最后通過實例驗證說明了算法的可行性和有效性，降低了航空器滑行沖突概率，提升了滑行道系統(tǒng)的運(yùn)行效率.

1 模型建立

1.1 基于有向圖的場面結(jié)構(gòu)模型

目前，國內(nèi)外在機(jī)場場面結(jié)構(gòu)建模領(lǐng)域，采用的方法主要包括MILP模型、有向圖模型及Petri網(wǎng)建模等[7-9].本文采用有向圖模型進(jìn)行機(jī)場場面結(jié)構(gòu)建模.圖1為采用有向圖建模方法對機(jī)場場面結(jié)構(gòu)進(jìn)行抽象后的模型.場面模型中的節(jié)點表示機(jī)場場面運(yùn)行中的關(guān)鍵位置點，比如跑道與滑行道之間的交叉點、滑行道之間的交叉點以及滑行道與停機(jī)坪之間的交叉點等.模型中的有向邊則表示場面中兩個節(jié)點間的路徑.

圖1 機(jī)場場面有向圖模型Figure 1 Airport surface directed figure model

在機(jī)場場面模型中，節(jié)點根據(jù)用途可分為跑道節(jié)點(如圖1中節(jié)點1和節(jié)點2)、滑行道節(jié)點(如圖1中節(jié)點11和節(jié)點15)、停機(jī)位節(jié)點(如圖1中節(jié)點58～63).節(jié)點的屬性信息包括唯一標(biāo)識、位置坐標(biāo)、節(jié)點屬性、使用情況等.有向邊屬性信息包括唯一標(biāo)識、單雙向、航班類型、進(jìn)離場、最大速度、最大數(shù)量、使用情況等.有向圖模型具有構(gòu)建簡潔，能直觀反映場面各區(qū)域連接關(guān)系和相對位置關(guān)系，但對場面運(yùn)行規(guī)則的表達(dá)有所欠缺，本文通過在節(jié)點和有向邊上增加通行判斷條件，使得模型更加符合現(xiàn)場運(yùn)行規(guī)則和約束條件.

1.2 模型構(gòu)建

以機(jī)場某個時間段內(nèi)進(jìn)離港航班為研究對象進(jìn)行場面滑行路徑規(guī)劃，建立航空器滑行路徑優(yōu)化模型的基本原則是：進(jìn)港航空器滑行優(yōu)先級高于同時段內(nèi)的離港航空器，這一原則的目的是減少航空器占用跑道時間；離港航空器中正常航班滑行優(yōu)先級高于延誤航班，這一原則的目的是減少航空器起飛延誤.以所有進(jìn)離港航空器總滑行時間最小為目標(biāo)進(jìn)行航空器路徑規(guī)劃.

以航空器總滑行時間最小為目標(biāo)的模型目標(biāo)函數(shù)為：

(1)

2 算法設(shè)計

蟻群算法作為一種用于求解最短路徑問題的算法，結(jié)合了啟發(fā)式算法和正反饋的優(yōu)點，具有分布式計算、魯棒性等特點.航空器在場面滑行過程中，可能產(chǎn)生交叉沖突、追尾沖突、對頭沖突等各種沖突情況，航空器滑行的這種相互聯(lián)系制約與蟻群中轉(zhuǎn)移策略、信息素更新等機(jī)制存在著相似之處[10-12].本文采用蟻群算法對航空器滑行路徑優(yōu)化問題進(jìn)行求解，算法步驟如下：

1)讀取某個時間段內(nèi)的航班信息，初始化模型參數(shù)：具體包括最大迭代次數(shù)iter_max、信息素重要程度因子α、啟發(fā)函數(shù)因子β、揮發(fā)程度因子ρ、蟻群數(shù)量N、每個蟻群螞蟻數(shù)量M、節(jié)點數(shù)量G等；

2)進(jìn)入新一次迭代，當(dāng)前迭代次數(shù)iter+1，每輪搜索把N只螞蟻放在起點，循環(huán)進(jìn)行M輪搜索；

3)進(jìn)入新一輪搜索，當(dāng)前搜索輪數(shù)k+1，尋找N個航班的滑行路徑.為每個航班定義兩個列表，一個是允許列表，用于存放螞蟻下次允許前往的所有可行節(jié)點集合，初始化為起點允許前往的所有可行節(jié)點；一個是禁忌列表，用于存放螞蟻已經(jīng)訪問過的節(jié)點，初始化為起點(跑道或者停機(jī)位)；

4)計算所有螞蟻的轉(zhuǎn)移概率，根據(jù)計算結(jié)果選擇從節(jié)點i移動到下一個節(jié)點j，將節(jié)點j從允許列表轉(zhuǎn)移到禁忌列表中，并將節(jié)點j允許前往的所有可行節(jié)點放入允許列表中；

5)判斷各個蟻群的螞蟻在移動到下一個節(jié)點的過程中是否存在路徑?jīng)_突，如果存在則按照沖突熱點避讓機(jī)制進(jìn)行避讓；

6)判斷所有螞蟻當(dāng)前節(jié)點是否為航班的終點，如果是則記錄當(dāng)前N個航班的滑行路徑和總滑行時間；如果不是則轉(zhuǎn)至步驟4)；

7)判斷是否已經(jīng)完成M輪搜索，如果是則更新N個航班的最小總滑行時間及相應(yīng)的滑行路徑，并更新信息素；如果不是則轉(zhuǎn)至步驟3)；

8)判斷是否已經(jīng)完成iter_max次迭代，如果是則算法結(jié)束，輸出N個航班的最小總滑行時間及相應(yīng)的滑行路徑；如果不是則轉(zhuǎn)至步驟2).

信息素的更新方法分為三種：1)局部更新法，當(dāng)某一只螞蟻找到某一條路徑后進(jìn)行局部信息素更新；2)全局更新法，當(dāng)蟻群找到某一條最優(yōu)路徑后進(jìn)行全局信息素更新；3)沖突更新法，當(dāng)兩個蟻群間存在路徑?jīng)_突時，進(jìn)行全局信息素更新[13].采用蟻群算法求解航空器滑行路徑優(yōu)化問題的流程圖見圖2.

3 仿真系統(tǒng)設(shè)計

為驗證本文提出的優(yōu)化算法，開發(fā)了航空器滑行路徑優(yōu)化仿真系統(tǒng).系統(tǒng)主要包括場面模型編輯模塊、運(yùn)行環(huán)境配置模塊、航空器路徑規(guī)劃模塊和航空器運(yùn)行仿真模塊等四個模塊.仿真系統(tǒng)采用Microsoft VisioStudio平臺基于C++語言開發(fā).其中場面模型編輯模塊通過直接在界面上編輯生成有向圖，提供給路徑規(guī)劃和運(yùn)行仿真模塊使用，具有增加、修改、刪除、加載、保存等功能.在場面運(yùn)行環(huán)境配置模塊完成相應(yīng)的參數(shù)配置后，路徑規(guī)劃模塊調(diào)用優(yōu)化算法計算航空器滑行最優(yōu)路徑，最后通過運(yùn)行仿真模塊在用戶界面上模擬航空器滑行軌跡.通過對航空器運(yùn)行的仿真模擬，檢驗航空器滑行路徑優(yōu)化算法的準(zhǔn)確性、有效性和可用性.

4 案例分析

以南京機(jī)場為研究對象進(jìn)行實際算例的驗證，對南京機(jī)場3號機(jī)坪航空器進(jìn)離港滑行路徑進(jìn)行研究.航空器起飛使用06跑道方向，降落使用07跑道方向，選取某個運(yùn)營日的1200～1300時間段的航班為研究對象.

下面針對上述兩個沖突航班HO1748和HO1657滑行路徑進(jìn)行分析研究.進(jìn)港航班HO1748在跑道07方向降落，計劃停機(jī)位為229，離港航班HO1657計劃停機(jī)位211，在跑道06方向起飛，兩個航班在沖突熱點HS5相遇，根據(jù)沖突熱點避讓機(jī)制，進(jìn)港航空器優(yōu)先離港航空器通過熱點區(qū)域，因此需要對離港航班HO1657重新規(guī)劃滑行路徑.

通過滑行路徑優(yōu)化算法，對航班HO1657滑行路徑進(jìn)行優(yōu)化，通過沖突熱點避讓機(jī)制，將沖突熱點作為約束條件，重新計算滑行路徑，得到HO1657航班的次優(yōu)滑行路徑.離港航班HO1657次優(yōu)滑行路徑結(jié)果如圖3.新的滑行路徑避開了沖突熱點，提高了該區(qū)域的安全水平和運(yùn)行效率.

圖3 沖突航班優(yōu)化前后的滑行路徑Figure 3 Before and after conflict flight optimization

對1200～1300時間段內(nèi)的航班，采用滑行路徑優(yōu)化算法進(jìn)行優(yōu)化，優(yōu)化后的滑行時間和實際滑行時間對比如圖4.

圖4 路徑優(yōu)化結(jié)果對比Figure 4 Comparison of path optimization results

優(yōu)化后有3架航班滑行路徑發(fā)生了變化，航班HO1657、DZ6257、MU2855通過優(yōu)化后滑行時間分別節(jié)省了55、38、43 s，這幾個航班滑行路徑優(yōu)化后有效避免了沖突情況，減少了沖突熱點區(qū)域的沖突架次和概率，提高了機(jī)場安全運(yùn)行裕度.1200～1300時間段內(nèi)的航班優(yōu)化后的總滑行時間比實際滑行總時間減少了136 s，對提高滑行道運(yùn)行效率和減少滑行沖突起到了積極的作用.

5 結(jié) 語

本文以最短滑行時間為目標(biāo)建立了航空器滑行路徑優(yōu)化模型，采用蟻群算法對滑行路徑優(yōu)化模型進(jìn)行求解，提出基于沖突檢測的航空器滑行優(yōu)化算法[14-15]；結(jié)合南京機(jī)場的實際運(yùn)行資源配置和約束，開發(fā)了南京機(jī)場的滑行路徑優(yōu)化仿真系統(tǒng).通過實例驗證，經(jīng)過優(yōu)化后的方案，符合南京機(jī)場實際情況，有效降低了沖突發(fā)生的頻率，減少了航空器地面滑行時間，提高了機(jī)場安全水平和運(yùn)行效率.