基于路徑檢測的航空器動態(tài)滑行路徑優(yōu)化模型

張兆寧，孫英然

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

1 引言

隨著近年來航空器數(shù)量的不斷增加、擴(kuò)建的機(jī)場和新機(jī)場的不斷出現(xiàn)，與此同時滑行道系統(tǒng)越來越復(fù)雜，所以需要在保證安全的前提下，盡可能提高航空器在場面的滑行效率。

在航空器滑行路徑優(yōu)化方面，國外學(xué)者提出了多種方法，2011年，Gillian L.Clare等將路徑優(yōu)化和跑道排序結(jié)合，并考慮航班離場時間，構(gòu)建MILP模型，實現(xiàn)了滑行路徑優(yōu)化[1]；2014年，Zafar N A用圖理論和Z標(biāo)記法模擬航空器在機(jī)場的滑行和起飛過程，動態(tài)規(guī)劃了離場航班的最優(yōu)滑行路徑[2]；IoannisSimaiakis等提出控制航空器起飛率，即減少了滑行時間有節(jié)省了燃油[3]；2016年，Sassi N等將Petri網(wǎng)與機(jī)場地面約束相結(jié)合，規(guī)劃航空器的滑行路徑[4]；2017年，Okuniek等為提升A-SMGCS服務(wù)水平，提出為每架航空器設(shè)計無沖突的優(yōu)化路線和相關(guān)速度值組成，即航空器四維滑行軌跡(4DT)[5]。

國內(nèi)在這一方面的研究有：2016年，邢志偉等針對航空公司滿意度和滑行道負(fù)載率，提出了基于背壓路由的離港滑行路徑優(yōu)化算法[6]；2018年，張紅穎等使用了多Agant策略來優(yōu)化滑行路徑[7]；2019年，姜雨等引入雙層規(guī)劃方法，考慮了成本與沖突對場面航空器運(yùn)行效率和安全的影響，構(gòu)建了場面航空器滑行時空協(xié)同優(yōu)化模型[8]；張兆寧等采用遠(yuǎn)端繞行滑行道的辦法優(yōu)化了航空器的滑行路徑，并使用改進(jìn)的遺傳算法求解[9]；2020年，李善梅等提出滑動時間窗和A*算法相結(jié)合的方法，構(gòu)建以總滑行時間最短為目標(biāo)的模型，優(yōu)化了滑行路徑[10]；張兆寧等提出在航空器著陸后，分析其滑行運(yùn)動過程，選擇最優(yōu)的跑道出口滑行道脫離跑道來節(jié)省滑行總時間[11]。

綜上，近年來為提高飛機(jī)滑行效率，國內(nèi)外學(xué)者使用了多種模型和算法以優(yōu)化飛機(jī)的滑行路徑，但在路徑選擇的方法上，大部分的研究都是從某時間段內(nèi)航班波滑行總時間最短或滑行距離最短的角度出發(fā)直接得到規(guī)劃方案，當(dāng)沖突出現(xiàn)時再采取解脫沖突的辦法，這種方法在機(jī)場航班過多的情況下，很容易出現(xiàn)擁堵的情況，也會導(dǎo)致滑行道使用不均衡。

所以本文提出基于路徑檢測的方法，對航空器進(jìn)行動態(tài)路徑優(yōu)化，當(dāng)某條滑行道被檢測到發(fā)生擁堵情況時，航空器將選有可能選擇其滑行道來提高航班波的整體滑行效率，也能提高航班運(yùn)行的安全性。本文的創(chuàng)新點體現(xiàn)在：

1)給出路徑規(guī)劃中路徑的檢測方法，提出多航空器在同一路徑上可能產(chǎn)生擁堵這一類新約束；

2)提出了動態(tài)路徑優(yōu)化策略，提高航空器滑行路徑規(guī)劃效率；

3)針對滑行路徑問題提出改進(jìn)的蟻群算法。

2 航空器動態(tài)滑行路徑優(yōu)化模型

建立航空器動態(tài)滑行路徑優(yōu)化模型，首先對航空器滑行過程及需解決的問題進(jìn)行描述，然后設(shè)計動態(tài)路徑優(yōu)化策略，明確檢測沖突和擁堵的辦法，構(gòu)建以總滑行時間最短為目標(biāo)，無沖突，無擁擠的數(shù)學(xué)規(guī)劃模型。

2.1 問題描述

航空器在場面的滑行是指航空器在跑道入口/出口和停機(jī)位之間的滑行。在航空器滑行過程中可能發(fā)生的沖突有尾追沖突、相向沖突、節(jié)點交叉沖突。圖1為有兩條跑道的機(jī)場的滑行系統(tǒng)水平布局圖，其中航空器可能存在的沖突如圖所示。在其機(jī)場布局中的沖突情況也類似。

圖1 機(jī)場滑行系統(tǒng)水平布局圖

航空器滑行過程中首先要避免這三種沖突，也要盡量避免在機(jī)場繁忙時段，滑行道上出現(xiàn)的擁堵情況，使航班波安全高效地從停機(jī)坪滑到跑道入口或者從跑道出口滑入指定的停機(jī)坪。

2.2 動態(tài)路徑優(yōu)化思路

為避免滑行過程中沖突和擁堵情況的發(fā)生，本文采用動態(tài)路徑優(yōu)化模型，即對隨機(jī)生成的滑行路徑進(jìn)動態(tài)監(jiān)控，若出現(xiàn)沖突和擁堵的現(xiàn)象，及時采取解決措施。

動態(tài)路優(yōu)化模型分為兩個模塊：航空器的路徑生成模塊將其搜索到的路徑實時反饋給滑行網(wǎng)絡(luò)的狀態(tài)模塊，滑行網(wǎng)絡(luò)的狀態(tài)模塊再對路徑生成模塊進(jìn)行動態(tài)監(jiān)控，兩個模塊相互配合相互制約，對路徑進(jìn)行動態(tài)優(yōu)化。

圖2 動態(tài)路徑優(yōu)化模型

2.3 路徑檢測方法

1)沖突檢測

對航空器運(yùn)行空間的檢測：檢測各架航空器的滑行路徑之間是否存在相同的路徑或節(jié)點；并且檢測航空器之間是否滿足最小安全滑行間隔；

對航空器運(yùn)行時間的檢測：若存在空間沖突，則要檢測出現(xiàn)在沖突的路徑或節(jié)點上是否有時間重疊。

2)擁堵檢測

采用交通流理論刻畫航空器滑行路徑的擁堵程度和航空器滑行速度：隨著滑行道上航空器密度的增加，導(dǎo)致航空器滑行速度逐漸減小，直至擁堵態(tài)。航空器滑行路段擁堵程度可根據(jù)交通流理論得

K=RN/RL

(1)

式中，K為滑行道路段的擁堵程度；RN為滑行道路段中航空器數(shù)量；RL為滑行道路段中可容納航空器總數(shù)。

航空器的滑行速度

v=vf(1-K)

(2)

式中，vf為航空器的最大滑行速度，本文根據(jù)機(jī)場滑行系統(tǒng)運(yùn)行規(guī)定vf=10m/s。

2.4 模型構(gòu)建

在動態(tài)路徑優(yōu)化策略，基于上述路徑檢測的方法，建立路徑優(yōu)化模型，假設(shè)如下：

1)航空器實際滑行過程中，所有航空器最小間隔相同；

2)所有飛機(jī)已經(jīng)指定好停機(jī)位或跑道入口；

模型參數(shù)定義如下：

M={1，2…m}為需要規(guī)劃航班的集合；N={1，2…n}為機(jī)場滑行道節(jié)點的集合；R={1，2…r}為機(jī)場滑行道中所有路段的集合；Dr為路段r的長度；L為航空器之間所需的最小安全間隔；H為滑行可利用時間。

模型變量定義如下：

其中

(7)

模型的目標(biāo)函數(shù)如下

模型的約束條件如下

(11)

式(8)保證航空器數(shù)量不超過此條滑行道上的容量；式(9)保證每個節(jié)點最多只有一架航空器；式(10)保證兩架相互沖突的航空器到達(dá)下一路段時間差不小于優(yōu)先級低的航空器的等待時間；式(11)保證滑行過程中不能出現(xiàn)相向沖突的情況。

3 求解算法

本文針對航空器在滑行道上的滑行規(guī)則及特點，設(shè)計了改進(jìn)的蟻群算法對問題進(jìn)行求解。

3.1 算法思路

運(yùn)用蟻群算法對航空器滑行路徑進(jìn)行優(yōu)化，將每一架航空器的滑行任務(wù)抽象為螞蟻組，每一組中包括多只螞蟻。在螞蟻為航空器搜索滑行路徑時，采用動態(tài)規(guī)劃策略，其算法基本思路如下：

1)路徑搜索：螞蟻根據(jù)其任務(wù)和轉(zhuǎn)移概率搜索下一節(jié)點，并留下信息素，該信息素僅對同組其螞蟻有效。

2)信息更新和記錄：根據(jù)蟻群的路徑搜索和信息素值更新和記錄路網(wǎng)狀態(tài)表、蟻群狀態(tài)表、信息素表。

3)目標(biāo)：以所有蟻群組的總運(yùn)動時間最短為目標(biāo)，找出最優(yōu)路徑。

3.2 算法的基本規(guī)則設(shè)置

1)初始蟻群設(shè)置

以往運(yùn)用蟻群算法求解航空器滑行路徑問題時，將全都螞蟻的起點設(shè)置在航空器的起始位置然后開始路徑搜索，導(dǎo)致航空器開始滑行的一段路徑基本相同，從而導(dǎo)致算法的全局搜索能力不足。

因此本章引入雙向搜索機(jī)制，對于每個蟻群，將其分為兩組，其中第一組的螞蟻起點設(shè)置為航空器的起始位置(對于離場航空器為航空器所在的停機(jī)位位置，對于進(jìn)場航空器則為跑道出口位置)，然后向航空器的目標(biāo)位置開始搜索路徑；第二組的螞蟻起點設(shè)置為航空器的目標(biāo)位置，然后向航空器的起點位置開始搜索。當(dāng)兩只螞蟻相遇后會生成一條新的路徑。

2)轉(zhuǎn)移策略

蟻群算法中各個螞蟻根據(jù)下一可達(dá)節(jié)點的選擇概率選擇路徑，根據(jù)上文路徑優(yōu)化模型，適當(dāng)調(diào)整傳統(tǒng)蟻群算法的轉(zhuǎn)移概率公式，改進(jìn)公式如下

(12)

式(12)中，Pm(i，j)表示航空器m在節(jié)點i上選擇轉(zhuǎn)移到節(jié)點j的概率；τij表示路段(i，j)上信息素濃度；Cij表示路段(i，j)的航空器容量；vmij表示規(guī)劃的航空器m在路段(i，j)上的速度；Li表示節(jié)點i的可達(dá)節(jié)點的集合；α、β、γ各個因素對于路徑選擇的相對重要程度。

3)狀態(tài)表更新規(guī)則

在螞蟻對某一路段進(jìn)行選擇后，先更新路網(wǎng)狀態(tài)表；然后根據(jù)當(dāng)前路段情況和式(4)中得到螞蟻在路段中的滑行速度、式(6)中得到的螞蟻滑行總時間，更新蟻群狀態(tài)表。

4)信息素更新規(guī)則

本文采用信息素全局更新規(guī)則，完成一次循環(huán)后，信息素按式(13)更新

(13)

(14)

式中，Q是信息素的強(qiáng)度，為定值，Lk是螞蟻k在本次循環(huán)中走過路徑的總長度。根據(jù)所需搜索的路徑特點，引進(jìn)獎懲因子，增加最優(yōu)路徑的信息素，減少最差路徑的信息素。如式(15)(16)(17)(18)

(18)

式(15)中，Δ*τij代表每次迭代最優(yōu)路徑經(jīng)過節(jié)點i、j的信息素大小，Δ**τij代表每次迭代最差路徑經(jīng)過節(jié)點i、j的信息素大小。Δ*τij由式(16)得到，其中L*表示這次迭代最優(yōu)路徑總長度。并且根據(jù)式(17)對全局最優(yōu)進(jìn)行獎勵，獎勵因子為Re ；Δ**τij由式(18)得到，其中L**表示本次迭代中最差路徑長度。式(19)引入最大最小信息素閾值，避免某路徑經(jīng)過多次迭代后，其上信息素濃度遠(yuǎn)高于其路徑而導(dǎo)致的搜索停滯。

(19)

3.3 算法步驟

綜上，基于改進(jìn)蟻群算法的航空器動態(tài)滑行路徑優(yōu)化模型的求解如下所示。

算法具體步驟如下：

Step 1：參數(shù)初始化，令迭代次數(shù)NC=1；

Step 2：為各個航空器分配至不同的蟻群組，同時在航空器的滑行起點和終點放置共a只螞蟻；

Step 3：按照目標(biāo)函數(shù)和機(jī)場場面約束條件為螞蟻分配初始路線；

Step 4：判斷各螞蟻當(dāng)前所在節(jié)點i是否為其搜索路徑的終點，若是轉(zhuǎn)至Step7；若不是轉(zhuǎn)至Step5：

Step 5：按照路徑選擇規(guī)則選擇下一滑行節(jié)點i′；

Step 6：更新蟻群狀態(tài)表，轉(zhuǎn)至Step4；

Step7：判斷這組蟻群是否都完成搜索，若是，則轉(zhuǎn)至Step8；否則，令螞蟻n=n+1，轉(zhuǎn)至Step3；

Step8：分析蟻群的搜索結(jié)果，得到該次迭代最優(yōu)路徑方案，更新滑行網(wǎng)絡(luò)狀態(tài)表、全局信息素；

Step9：判斷是否達(dá)到指定迭代次數(shù)，若不是，則轉(zhuǎn)至Step10：若是，則轉(zhuǎn)至Step11；

Step10：令NC=NC+1，開始下一次迭代，轉(zhuǎn)至Step2；

Step11：算法結(jié)束，輸出最優(yōu)滑行方案。

算法流程如圖3所示。

圖3 算法流程

4 算例分析

為驗證本文模型與算法的有效性，選取國內(nèi)某機(jī)場的實際數(shù)據(jù)進(jìn)行實驗，并對比不同模型下的結(jié)果，加以分析。

4.1 算例描述

選取國內(nèi)某機(jī)場地面滑行系統(tǒng)為算例，分析了以34L、34R兩條平行跑道和T1，T2航站樓組成的地面滑行網(wǎng)絡(luò)，其地面交通網(wǎng)絡(luò)圖如圖4所示，圖中顯示各個滑行節(jié)點編號，本文所研究的滑行路徑是指跑道中的滑行道入口/出口與停機(jī)坪前的滑行道交叉點之間的路徑，因此航班的滑行路徑可用連續(xù)的節(jié)點組合來模擬。

圖4 國內(nèi)某機(jī)場滑行道系統(tǒng)構(gòu)型

4.2 模型仿真

根據(jù)機(jī)場運(yùn)行實際情況，選取該機(jī)場2020年7月某天13：00～13：30內(nèi)需要滑行的航空器，其中包括11個離場航空器和12個進(jìn)場航空器，對航空器進(jìn)行動態(tài)路徑規(guī)劃。則模型參數(shù)如下：需要規(guī)劃的航班的集合M={1，2…23}；滑行系統(tǒng)節(jié)點的集合N={1，2…96}；航空器之間所需最小的安全間隔L=250m；航空器滑行可利用的時間H=55min。

經(jīng)過多次實驗，蟻群算法中的參數(shù)設(shè)定為：α=1，ρ=0.4，β=0.9，γ=2.5，a=20，Re=1.5，δ=1.5，ω=1.5，τmin=0.5，τmax=20。

在MATLAB中進(jìn)行仿真，最終得出各航班滑行時間及對應(yīng)的路徑，如表1所示。

表1 航空器路徑規(guī)劃方案

圖5 迭代次數(shù)與航班波滑行總時間關(guān)系

4.3 對比分析

為驗證本文模型的有效性，采用同樣的蟻群算法，使用傳統(tǒng)的不考慮路段狀況的模型，計算航空器的滑行路徑，結(jié)果如表2，比較不同模型下航班滑行序列號和航班滑行時間的關(guān)系，如圖6所示。

圖6 航空器序號與航空器滑行時間關(guān)系

表2 航空器路徑規(guī)劃方案

由表2可知，不考慮路段狀況的方案路段重復(fù)率大，由圖6可知，不考慮路段狀況的航空器滑行相對緩慢，其中2，3，5，8，11，12，13，14，15，20，22，23號航空器滑行時間都比實施路徑檢測的方案時間長，在路徑搜索中進(jìn)行路徑檢測，航空器滑行時間累計節(jié)省234s。相比之下，本文模型滑行時間較短，不同航空器之間的路徑重復(fù)率較低，完成時間較為均衡，故本文模型具有一定的優(yōu)化能力，可提高滑行效率。

5 結(jié)論

本文基于路經(jīng)檢測，對航空器在機(jī)場的滑行進(jìn)行動態(tài)優(yōu)化。從提高航空器整體運(yùn)行效率的角度上，以滑行總時間最短為目標(biāo)，建立路徑規(guī)劃模型，并設(shè)計了基于動態(tài)路徑優(yōu)化策略的改進(jìn)的蟻群算法，通過實例驗證了該方法的有效性。實驗結(jié)果表明動態(tài)優(yōu)化策略可以對航空器滑行路徑進(jìn)行合理優(yōu)化，基于路徑檢測的優(yōu)化模型可以有效的解決航空器滑行過程中的擁堵問題，提高滑行效率。

本文在考慮減少航空器滑行時遇到的擁堵情況時，沒有計算繞開擁堵路徑時成本消耗問題，航空器能夠安全高效并且盡可能的節(jié)約成本的滑行，是后續(xù)研究的主要方向。