吳 虹， 趙 征

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

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

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

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

1 模型建立

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

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

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

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

1.2 模型構(gòu)建

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

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

(1)

2 算法設(shè)計(jì)

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

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

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

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

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

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

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

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

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

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

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

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

4 案例分析

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

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

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

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

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

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

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

5 結(jié) 語

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