祁欣月, 張 汛, 陳長(zhǎng)煜, 張 濤

(1.西藏大學(xué)工學(xué)院, 拉薩 850000; 2.96951部隊(duì), 北京 100085)

隨著我國(guó)民航業(yè)迎來(lái)跨越式發(fā)展,機(jī)隊(duì)規(guī)模日益龐大,機(jī)場(chǎng)地面的交通擁堵成為制約航空運(yùn)輸效率的“瓶頸”,樞紐機(jī)場(chǎng)作為中樞航線(xiàn)網(wǎng)絡(luò)的節(jié)點(diǎn),面臨更大的挑戰(zhàn)。這種狀況導(dǎo)致機(jī)場(chǎng)資源利用不充分,同時(shí)加劇了航班延誤和廢氣排放等問(wèn)題。擴(kuò)大機(jī)場(chǎng)容量、完善基礎(chǔ)設(shè)施建設(shè)是最直接的解決方案,但考慮成本和機(jī)場(chǎng)環(huán)境,短時(shí)間內(nèi)擴(kuò)建不現(xiàn)實(shí)。為此,從航空器路徑規(guī)劃和減少燃油消耗兩方面入手,針對(duì)場(chǎng)面資源中滑行道容量不足問(wèn)題,在避免沖突基礎(chǔ)上進(jìn)一步縮短航空器滑行距離,可以在一定程度上緩解這一問(wèn)題。

國(guó)內(nèi)外學(xué)者在航空器路徑規(guī)劃方面展開(kāi)了大量研究。劉帆等[1]提出了場(chǎng)面滑行動(dòng)態(tài)規(guī)劃的A*算法,建立航空器總體滑行耗時(shí)最短、延誤最少的動(dòng)態(tài)優(yōu)化模型,減少了航空器總體滑行時(shí)間。張兆寧和余州[2]基于態(tài)勢(shì)感知對(duì)滑行路徑進(jìn)行優(yōu)化,在傳統(tǒng)的先到先服務(wù)算法基礎(chǔ)之上,加入了滑行道系統(tǒng)運(yùn)行態(tài)勢(shì)。黃邦菊和史繼龍[3]為解決多航空器之間的沖突問(wèn)題,以?xún)?yōu)化后的滑行路徑距離作為目標(biāo)代價(jià)函數(shù),提出一種滑動(dòng)時(shí)間窗與遺傳算法相融合的沖突解脫模型。姜雨等[4]提出適用于航空器滑行時(shí)空協(xié)同優(yōu)化模型的雙層規(guī)劃算法,以降低場(chǎng)面航空器滑行距離和等待時(shí)間。彭可欣等[5]通過(guò)對(duì)機(jī)場(chǎng)航班運(yùn)行管理程序的研究,建立了協(xié)調(diào)航班移交的整數(shù)線(xiàn)性規(guī)劃模型,優(yōu)化航班推出時(shí)刻及滑行時(shí)間,從而減少航班延誤。Idrissi等[6]利用決策支持系統(tǒng)為航空器滑行指定一條直達(dá)路線(xiàn)并更準(zhǔn)確地預(yù)測(cè)滑行時(shí)間,提高場(chǎng)面運(yùn)行效率。Ali等[7]以預(yù)測(cè)動(dòng)態(tài)熱點(diǎn)作為空側(cè)沖突的預(yù)兆事件,在時(shí)間和空間維度上模擬飛機(jī)到達(dá)不同滑行道的交叉口,使用統(tǒng)計(jì)學(xué)中的時(shí)空模型計(jì)算已識(shí)別交叉口的沖突概率并評(píng)估沖突系數(shù)及熱點(diǎn)值。Xiang等[8]提出了一種基于強(qiáng)化學(xué)習(xí)方法Q-Learning算法的改進(jìn)方法,為航空器提供滑行路徑引導(dǎo)。Ning等[9]采用改進(jìn)的A*算法求解滑行路徑優(yōu)化模型,生成無(wú)沖突滑行路徑及新的滑行軌跡占用時(shí)間窗,可進(jìn)一步減少航空器在場(chǎng)面運(yùn)行的總滑行時(shí)間,從而大幅減少航空器沖突次數(shù),保障機(jī)場(chǎng)運(yùn)行安全。

綜上所述,國(guó)內(nèi)外學(xué)者在減少機(jī)場(chǎng)場(chǎng)面滑行時(shí)間,緩解交通壓力方面的研究取得了一定的成效,但現(xiàn)有的航空器滑行路徑優(yōu)化算法未能在充分考慮航空公司成本及節(jié)能減排效果的基礎(chǔ)上提出最優(yōu)路徑。針對(duì)機(jī)場(chǎng)整體運(yùn)行效能低下,尤其是滑行道容量不足、解決方式不夠全面等關(guān)鍵難題,通過(guò)研究樞紐機(jī)場(chǎng)高效運(yùn)行模式、優(yōu)化航空器總滑行距離來(lái)提高整體協(xié)同決策,分析航空器滑行規(guī)則,依據(jù)國(guó)內(nèi)某樞紐機(jī)場(chǎng)場(chǎng)面滑行系統(tǒng)實(shí)際航圖建立模型,保障場(chǎng)面運(yùn)行安全的前提下考慮經(jīng)濟(jì)、環(huán)保和公平性原則,重點(diǎn)規(guī)劃縮短航空器總滑行距離的路徑,提高滑行效率,擴(kuò)大滑行道容量。本文通過(guò)對(duì)路徑優(yōu)化問(wèn)題的研究分析,本文基于Dijkstra算法將機(jī)場(chǎng)場(chǎng)面滑行路徑轉(zhuǎn)換為鄰接矩陣,尋找固定起終點(diǎn)的最短路,并利用MATLAB模擬來(lái)執(zhí)行Dijkstra算法。研究?jī)?nèi)容包括:①建立機(jī)場(chǎng)場(chǎng)面資源網(wǎng)絡(luò)簡(jiǎn)圖,利用計(jì)算機(jī)輔助設(shè)計(jì)(computer aided design,CAD) 測(cè)量相鄰節(jié)點(diǎn)間的圖上距離,基于Dijkstra算法為多條航空器滑行路徑建立鄰接矩陣;②對(duì)滑行路徑進(jìn)行優(yōu)化求解,減少滑行距離及時(shí)間;③通過(guò)減少轉(zhuǎn)彎次數(shù)及滑行時(shí)間來(lái)降低燃油消耗和污染物排放。

1 滑行路徑規(guī)劃算法

1.1 滑行道運(yùn)行分析

滑行道系統(tǒng)是機(jī)場(chǎng)的重要組成部分,是供航空器滑行和連接機(jī)場(chǎng)各功能區(qū)的通道。滑行道容量在一定程度上影響機(jī)場(chǎng)的場(chǎng)面運(yùn)行效率。圖1為某機(jī)場(chǎng)滑行道示意圖,包括進(jìn)出口滑行道、主滑行道、機(jī)坪滑行道、輔助滑行道及滑行道道肩等。

TML表示航站樓;Apron表示相應(yīng)的停機(jī)坪;ARP表示機(jī)場(chǎng)基準(zhǔn)點(diǎn);A、B、C等均表示滑行道;數(shù)字表示停機(jī)位

一般將滑行道沖突分為3類(lèi):A交叉沖突、B追尾沖突、C對(duì)頭沖突。 對(duì)頭沖突是指同一滑行道上兩航空器相向滑行,在某時(shí)刻存在碰撞風(fēng)險(xiǎn),這是滑行過(guò)程中最危險(xiǎn)的狀況,應(yīng)當(dāng)各自靠右側(cè)滑行,保持一定距離。此外,針對(duì)交叉及追尾沖突,民航局嚴(yán)格規(guī)定了不同機(jī)型在滑行過(guò)程中前后機(jī)之間的安全間隔(表1),通過(guò)保持安全間隔主動(dòng)避讓或另選滑行路徑的方法解脫沖突。

表1 航空器滑行尾流間隔標(biāo)準(zhǔn)

1.2 航空器燃油消耗和排放

在縮短總滑行距離的前提下兼顧場(chǎng)面運(yùn)行安全、航空公司經(jīng)濟(jì)以及環(huán)保效能。避免滑行沖突的同時(shí),控制滑行速度并減少轉(zhuǎn)彎次數(shù)可有效降低燃油消耗[10]。

根據(jù)不同運(yùn)行模式下的燃油流率和排放指數(shù),采用國(guó)際民航組織(ICAO)規(guī)定的燃油消耗和廢氣排放計(jì)算方法,公式為

(1)

(2)

當(dāng)發(fā)動(dòng)機(jī)處于怠速時(shí),部分機(jī)型的燃油流率及排放指數(shù)見(jiàn)表2。

表2 燃油流量及排放指數(shù)

1.3 滑行路徑規(guī)劃目標(biāo)函數(shù)

將安全間隔、沖突解脫和公平性原則作為約束條件,建立滑行路徑優(yōu)化模型。采用Dijkstra算法綜合考慮飛機(jī)的滑行距離、滑行過(guò)程中的大轉(zhuǎn)向及避撞情況,最小化飛機(jī)的總滑行時(shí)間,從而減少滑行階段的油耗及污染物排放。

(3)

式中:xijf=1表示飛機(jī)f通過(guò)滑行道節(jié)點(diǎn)Ni滑行到下一個(gè)相鄰節(jié)點(diǎn)Nj,否則xijf=0;tijf為飛機(jī)f從滑行道節(jié)點(diǎn)Ni滑行到下一個(gè)相鄰節(jié)點(diǎn)Nj所用的滑行時(shí)間;nf為飛機(jī)f在滑行路徑上累計(jì)轉(zhuǎn)彎的總數(shù);tn為飛機(jī)f平均每次轉(zhuǎn)彎所需的時(shí)間。

為避免滑行過(guò)程中發(fā)生沖突,考慮以下約束條件。

(1)滑行道容量限制:

Wisu≤Lsu,?fi∈F,?ns,nu∈N

(4)

式中:ns為滑行道起始節(jié)點(diǎn);nu為滑行道終點(diǎn);F為航空器集合;N為滑行節(jié)點(diǎn)集合;Wisu為航空器fi從節(jié)點(diǎn)s到節(jié)點(diǎn)u的滑行道容量;Lsu=1表示節(jié)點(diǎn)s到u之間存在可用滑行路徑,否則Lsu=0。約束條件(4)確保航空器fi從起點(diǎn)到終點(diǎn)存在有效的滑行路徑且滿(mǎn)足滑行道容量。

(2)優(yōu)先級(jí)約束:

(5)

式中:Gf1f2為優(yōu)先級(jí)因子;γfi為航空器fi的優(yōu)先級(jí)。

(3)滑行安全間隔:

L=[lsu/(Tiu-Tis)](Tjs-Tis)

(6)

式中:lsu為節(jié)點(diǎn)s與u之間的距離;Tis為航空器fi到達(dá)節(jié)點(diǎn)ns的時(shí)刻;Tjs為航空器fj到達(dá)節(jié)點(diǎn)ns的時(shí)刻;Tiu為航空器fi到達(dá)節(jié)點(diǎn)nu的時(shí)刻。式(6)是為了確保同一滑行道上兩架相鄰航空器之間保持一定的安全間隔。

(4)滑行沖突約束:

A對(duì)頭沖突

Xsuf1tuf1-Xsuf2tuf2≥0

(7)

式中:Xsufi為航空器fi從節(jié)點(diǎn)s滑行到節(jié)點(diǎn)u;tufi為航空器fi滑行到節(jié)點(diǎn)u的時(shí)刻。

B超越?jīng)_突

(Xsuf1tsf1-Xsuf2tsf2)(Xsuf1tuf1-Xsuf2tuf2)>0

(8)

式中:tsfi為航空器fi滑行到節(jié)點(diǎn)s的時(shí)刻。

航空器在滑行道系統(tǒng)中的沖突如圖2所示。

R1～R4表示跑道節(jié)點(diǎn);G3表示停機(jī)坪;m、n、k表示滑行道節(jié)點(diǎn)

(5)公平性約束:

(9)

式中:Dα為α航空公司產(chǎn)生額外滑行路線(xiàn)的總長(zhǎng)度,A為航空公司集合;Pα為α航空公司的數(shù)量占總航空公司數(shù)的比值;∑Pα為α航空公司航班數(shù)累計(jì)占總航空數(shù)的比值;ε1為Gini系數(shù)的參數(shù)值(Gini系數(shù)可以反映資源分配的公平程度,值越小,分布越平均)。式(9)旨在確?；新肪€(xiàn)長(zhǎng)度的公平性。

2 MATLAB仿真與算法流程

2.1 場(chǎng)面滑行仿真

基于國(guó)內(nèi)某樞紐機(jī)場(chǎng)的航班數(shù)據(jù),使用MATLAB程序模擬來(lái)執(zhí)行Dijkstra的算法。

算法1：

2.2 Dijkstra算法流程

Dijkstra算法用于求解指定兩點(diǎn)Vi、Vj間的最短路,或從指定點(diǎn)Vi到其余各點(diǎn)的最短路,是求解非負(fù)權(quán)值網(wǎng)絡(luò)最短路問(wèn)題的最佳方法。若序列Vi-Vj為最優(yōu)路徑,則其任意子集也被定義為最優(yōu)解[11]。

基于Dijkstra算法的航空器滑行路徑規(guī)劃基本步驟如下。

(1)固定滑行路徑起終點(diǎn)。用Xij表示滑行道權(quán)值,Xij≥0。若節(jié)點(diǎn)Vi與Vj不相鄰,則定義Xij=+∞。給起點(diǎn)Vi以P標(biāo)號(hào),其中P為永久性標(biāo)號(hào),P(Vi)=0,將剩余節(jié)點(diǎn)標(biāo)注T,T為試探性標(biāo)號(hào),T(Vj)=+∞。

(2)將P標(biāo)號(hào)的節(jié)點(diǎn)與T標(biāo)號(hào)節(jié)點(diǎn)劃分為兩個(gè)集合,從T標(biāo)號(hào)的集合中選取任意與P點(diǎn)相鄰的節(jié)點(diǎn),對(duì)T標(biāo)號(hào)進(jìn)行如下計(jì)算:T(Vj)=min[T(Vj),P(Vi)+Xij]。

(3)比較所有T標(biāo)號(hào)的權(quán)值,將最小值定義為P標(biāo)號(hào),更新兩個(gè)集合,重復(fù)此過(guò)程,直到所有節(jié)點(diǎn)均為P標(biāo)號(hào)。此時(shí),找到一條權(quán)值最小的滑行路徑。

3 實(shí)例分析

以國(guó)內(nèi)某樞紐機(jī)場(chǎng)2018年某日18:00—19:00的實(shí)際航班滑行數(shù)據(jù)為例,基于該機(jī)場(chǎng)航圖選取T1、T2航站樓兩側(cè)跑道、滑行道和停機(jī)坪區(qū)域,省略部分無(wú)關(guān)滑行道,并將停機(jī)位抽象為6個(gè)綜合停機(jī)坪,構(gòu)建機(jī)場(chǎng)場(chǎng)面資源網(wǎng)絡(luò)圖(圖3)。

R1～R19為跑道節(jié)點(diǎn);G1～G6表示不同區(qū)域的停機(jī)坪;剩余標(biāo)號(hào)均表示滑行道節(jié)點(diǎn);虛線(xiàn)段表示進(jìn)場(chǎng);雙線(xiàn)段表示離場(chǎng)

該機(jī)場(chǎng)跑道實(shí)施隔離平行運(yùn)行模式,采取“固定、單向、順向、循環(huán)”的滑行規(guī)則。停機(jī)坪區(qū)域通過(guò)機(jī)坪滑行道與普通滑行道和停機(jī)位相連接[12]。

利用Dijkstra算法對(duì)航班數(shù)據(jù)進(jìn)行模擬計(jì)算,基于MATLAB仿真得到航空器地面滑行的具體最優(yōu)路徑。考慮不同機(jī)型的滑行速度、滑行時(shí)間及熱點(diǎn)沖突路段,分析不同的沖突類(lèi)型,劃分航空器優(yōu)先級(jí),采取加權(quán)的方法合理規(guī)劃路徑。

首先確定機(jī)場(chǎng)場(chǎng)面資源網(wǎng)絡(luò)圖的節(jié)點(diǎn)個(gè)數(shù)和節(jié)點(diǎn)間相對(duì)距離,見(jiàn)表3。基于該機(jī)場(chǎng)航圖,利用CAD測(cè)量出相鄰節(jié)點(diǎn)間的圖上距離。在實(shí)際運(yùn)用中,可依據(jù)比例尺進(jìn)行換算,不影響算法結(jié)論。

表3 節(jié)點(diǎn)距離(部分)

運(yùn)用Dijkstra算法構(gòu)建滑行路徑起終點(diǎn)間的鄰接矩陣,在首次規(guī)劃不考慮熱點(diǎn)沖突及特殊因素的情況下,尋找經(jīng)過(guò)節(jié)點(diǎn)數(shù)最少、距離Sij及滑行時(shí)間Tij最短的滑行路徑。飛機(jī)時(shí)刻表中的最優(yōu)滑行路徑見(jiàn)表4。

表4 滑行路徑優(yōu)化結(jié)果

以航班3U8173滑行路徑為例,假設(shè)E1-E2段因緊急狀況暫時(shí)關(guān)閉,則需另選最短路徑。經(jīng)簡(jiǎn)化,以Q1為起點(diǎn),E3為終點(diǎn)不斷尋優(yōu),由MATLAB最終輸出1-3-10,故更新路徑為R7-A5-A4-A3-E1-Q1-Q2-E2-E3,路徑長(zhǎng)度為195 m,滑行時(shí)間為234 s。

考慮航空器滑行路徑?jīng)_突狀況,圖3中虛線(xiàn)段表示進(jìn)場(chǎng),雙劃線(xiàn)段表示離場(chǎng)?？梢?jiàn),航班CZ6338與HU7268在節(jié)點(diǎn)Q6處存在交叉沖突。此時(shí)不再運(yùn)用傳統(tǒng)的先到先服務(wù)原則,而通過(guò)比較優(yōu)先級(jí)以解脫沖突。由于離場(chǎng)航空器相對(duì)進(jìn)場(chǎng)航空器具有絕對(duì)優(yōu)先權(quán),故航班HU7268應(yīng)選擇其他滑行路徑或在沖突區(qū)域前等待。通過(guò)加權(quán)的方法為航空器重新規(guī)劃滑行路徑,賦予滑行道不同的權(quán)值,假設(shè)“100”表示權(quán)重上限,分別為停機(jī)坪滑行道、聯(lián)絡(luò)滑行道、平行滑行道沖突路段賦值80、50、30。故Q5-Q6段距離為57,根據(jù)Dijksrta算法重新建立其鄰接矩陣,確定其次優(yōu)路徑:R7-A5-A4-A3-E1-Q1-P1-P2-P3-P4-P5-P6-Q6,路徑長(zhǎng)度為257 m,在有效避免沖突的情況下,與最短滑行路徑相比,距離略有增加,在可接受范圍內(nèi)。根據(jù)實(shí)際滑行距離及該航班滑行速度得出避撞前后滑行時(shí)間,顯然,兩種方案之間僅有17 s時(shí)間差,不影響場(chǎng)面運(yùn)行效率。結(jié)果對(duì)比見(jiàn)表5。

表5 避撞前后滑行效率結(jié)果對(duì)比

此外,對(duì)比傳統(tǒng)A*算法對(duì)滑行路徑的規(guī)劃,A*算法[13]是通過(guò)比較當(dāng)前路徑柵格鄰域的啟發(fā)式函數(shù)值F來(lái)確定下一路徑柵格,但當(dāng)存在多個(gè)最小值時(shí)A*算法不能保證搜索路徑最優(yōu)。A*算法求解15個(gè)航班的滑行路徑見(jiàn)表6。

表6 傳統(tǒng)A*算法求解滑行路徑

對(duì)比表4和表6兩種算法下的路徑規(guī)劃可知,傳統(tǒng)A*算法下15個(gè)航班的總滑行距離為4 180 m,總滑行時(shí)間為5 284 s,共計(jì)轉(zhuǎn)彎44次;Dijkstra算法求解的航空器總滑行距離為4 052 m,總滑行時(shí)間為5 115 s,共計(jì)轉(zhuǎn)彎25次。

較少的轉(zhuǎn)彎次數(shù)及滑行時(shí)間有利于降低燃油消耗和污染物排放。根據(jù)式(1)、式(2)及部分機(jī)型的燃油消耗和排放指數(shù)計(jì)算兩種算法下的航空器滑行油耗及污染物排放總量。圖4為15個(gè)航空器分別在兩種算法求解下的滑行路徑油耗量,圖5為航空器滑行產(chǎn)生的3種污染物HC、CO及NOx排放總量對(duì)比。由圖4、圖5可知,本文提出的Dijkstra算法在相比傳統(tǒng)A*算法油耗總量下降了3.29%,同時(shí)3種污染物總量分別減少了3.32%、3.34%、3.28%。樞紐機(jī)場(chǎng)繁忙時(shí)段航空器起降頻繁,采用Dijkstra算法為多架航空器滑行提供合理路徑,將顯著提升滑行效率,大幅減少油耗及污染物排放。

圖4 兩種算法求解下15個(gè)航空器滑行油耗量對(duì)比

圖5 兩種算法求解下15個(gè)航空器滑行產(chǎn)生的3種污染物HC、CO及NOx排放量對(duì)比

4 結(jié)語(yǔ)

針對(duì)機(jī)場(chǎng)場(chǎng)面滑行道容量不足問(wèn)題,構(gòu)建了滑行路徑規(guī)劃模型,設(shè)計(jì)了Dijsktra求解算法,并利用國(guó)內(nèi)某樞紐機(jī)場(chǎng)航空器地面實(shí)際滑行數(shù)據(jù)進(jìn)行了驗(yàn)證對(duì)比。結(jié)果表明,基于Dijsktra算法的路徑規(guī)劃有助于縮短滑行時(shí)間從而減少燃油消耗及污染物排放,所提出的模型及算法可行,可顯著提升滑行效率。

為保證該算法的魯棒性,在未來(lái)的實(shí)際運(yùn)用中可將機(jī)場(chǎng)場(chǎng)面滑行路徑以固定的鄰接矩陣編入代碼中。此外,基于航空器滑行的動(dòng)態(tài)性特點(diǎn),應(yīng)充分考慮多方因素,如地面特種車(chē)輛對(duì)航空器滑行路徑的影響等,綜合運(yùn)行現(xiàn)狀,確?；械廊萘孔畲蠡?。