賈 媛 姜 雨 徐 成 蔡夢婷

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

0 引 言

近年來，我國航空運(yùn)輸業(yè)發(fā)展迅速，機(jī)場樞紐化趨勢日益明顯，航空運(yùn)輸系統(tǒng)的運(yùn)行和管理壓力與日俱增.針對航班延誤和機(jī)場擁堵現(xiàn)象日益嚴(yán)重的現(xiàn)狀，提高機(jī)場場面資源的運(yùn)行效率，增加場面容量已經(jīng)迫在眉睫.

目前國內(nèi)外學(xué)者對航空器場面滑行優(yōu)化的研究主要分為靜態(tài)和動態(tài)兩個(gè)方面.在航空器靜態(tài)場面滑行優(yōu)化方面，利用混合整數(shù)線性規(guī)劃(MILP)方法[1]、遺傳算法(GA)[2]、改進(jìn)的A*算法[3]等智能算法，得到基于固定路徑的滑行路徑優(yōu)化序列.在航空器動態(tài)場面滑行優(yōu)化方面，一部分學(xué)者通過利用復(fù)雜網(wǎng)絡(luò)[4]、遺傳算法[5]、元胞自動機(jī)(CA)[6]、改進(jìn)的粒子群算法(CPSO)[7]、主動路由選擇(AR)[8]、混合整數(shù)規(guī)劃(MIP)方法[9-10]、改進(jìn)的蟻群算法[11]、多目標(biāo)免疫優(yōu)化算法[12]等智能算法，對航空器場面滑行進(jìn)行動態(tài)優(yōu)化；另一部分學(xué)者對模型進(jìn)行改進(jìn)，例如，建立跑道和滑行道聯(lián)合調(diào)度的集成優(yōu)化模型[13]，建立多目標(biāo)多分枝的航空器場面滑行優(yōu)化模型[14-15]等.

縱觀國內(nèi)外研究成果，學(xué)者們已經(jīng)從滑行效率和安全兩個(gè)角度進(jìn)行航空器動態(tài)滑行優(yōu)化研究，并取得一定成果.但是隨著研究的深入，航空器屬性，尤其是航空器優(yōu)先級，越來越成為影響滑行效率和安全的關(guān)鍵因素.因此，如何從優(yōu)先級角度出發(fā)，提高航空器滑行效率和安全，降低場面擁堵，緩解運(yùn)行壓力已經(jīng)勢在必行.

本文以最小化所有進(jìn)離場航空器運(yùn)行成本為目標(biāo)，建立基于航空器優(yōu)先級的場面航空器動態(tài)滑行優(yōu)化模型.探討航空器優(yōu)先級的確定方法，設(shè)計(jì)滑行沖突解決策略，引入滾動時(shí)域方法進(jìn)行求解.使用MATLAB仿真平臺，驗(yàn)證該優(yōu)化方案的可行性和有效性.

1 基于航空器優(yōu)先級的滑行沖突解決策略

1.1 航空器優(yōu)先級的確定

航空器優(yōu)先級的確定考慮三個(gè)因素：時(shí)間優(yōu)先、機(jī)型優(yōu)先、延誤優(yōu)先.三種優(yōu)先級的高低順序分別為：時(shí)間優(yōu)先>機(jī)型優(yōu)先>延誤優(yōu)先.

“時(shí)間優(yōu)先”是指根據(jù)航班時(shí)刻表，預(yù)計(jì)起飛時(shí)間早的航空器比預(yù)計(jì)起飛時(shí)間晚的航空器具有優(yōu)先級.這樣設(shè)定優(yōu)先級，原因?yàn)椋孩俸桨鄷r(shí)刻表相對固定，為保證旅客權(quán)益，以及考慮到旅客的滿意度，一般不允許航空器提前起飛而造成旅客誤機(jī)；②不同的航班屬于不同的航空公司，不能僅憑機(jī)型來決定由哪家航空公司來承擔(dān)延誤損失，考慮到航空公司之間的公平性，只有按照航班時(shí)刻表才能保證相對公正，畢竟航班時(shí)刻表是各航空公司、空管單位和其他相關(guān)部門之間利益平衡的結(jié)果.

“機(jī)型優(yōu)先”是指根據(jù)《國際民用航空公約》的相關(guān)規(guī)定和場面航空器運(yùn)行的實(shí)際情況，航空器優(yōu)先級的確定是由航空器的屬性(如專機(jī)、故障機(jī)、貨機(jī)等)、機(jī)型成本率、載客數(shù)、平均耗油率等參數(shù)決定.“機(jī)型成本率”主要由該機(jī)型載客數(shù)和平均耗油率這兩項(xiàng)主要性能指標(biāo)確定.“載客數(shù)”是估計(jì)該機(jī)型單位時(shí)間內(nèi)旅客地面等待成本的重要參數(shù)，“平均耗油率”是估計(jì)該機(jī)型在發(fā)動機(jī)工作時(shí)運(yùn)行成本的重要參數(shù).其他一些因素，如公司信譽(yù)、人員工作負(fù)荷、飛機(jī)維護(hù)成本等，可以將其折算到單位乘客等待成本或者航油價(jià)格中去.

“延誤優(yōu)先”是指延誤航班的優(yōu)先級低于正常航班的優(yōu)先級，其中“延誤航班”是指在航班時(shí)刻表預(yù)定的起飛時(shí)間15 min后還未能起飛的航班.同時(shí)，在所有延誤航班內(nèi)部仍然按照時(shí)間優(yōu)先和機(jī)型優(yōu)先順序來確定各航空器的優(yōu)先級.

1.2 航空器滑行沖突解決策略

本文提出的沖突解決策略是通過判斷沖突航空器的優(yōu)先級，優(yōu)先級高的航空器可以按原計(jì)劃路徑直接通過沖突區(qū)域，按原路徑繼續(xù)滑行；優(yōu)先級低的航空器有兩種滑行方案可選：①進(jìn)入沖突區(qū)域前減速等待；②提前選擇次優(yōu)可替代滑行路徑(一條不經(jīng)過沖突區(qū)域且到達(dá)終點(diǎn)的最短路徑).

設(shè)航空器的優(yōu)先級為p，航空器選擇減速等待的最短等待時(shí)間為Δt，航空器單位時(shí)間滑行成本與單位時(shí)間等待成本之比為λ，最短滑行路徑與次優(yōu)可替代滑行路徑的長度之差為替代成本Δc，平均滑行速度為v.分別計(jì)算兩種滑行方案的滑行時(shí)間成本：①進(jìn)入沖突區(qū)域前減速等待，將最短等待時(shí)間Δt乘以滑行成本與等待成本之比λ，轉(zhuǎn)換為滑行時(shí)間成本λΔt；②提前選擇次優(yōu)可替代滑行路徑，將替代成本Δc除以滑行速度v，轉(zhuǎn)換為滑行時(shí)間成本Δc/v.將Δc/v與λΔt進(jìn)行比較，選擇較小的滑行時(shí)間成本，進(jìn)而選擇合理的沖突解決策略，實(shí)現(xiàn)所有進(jìn)離場航空器無沖突滑行且運(yùn)行成本最小化的目標(biāo).當(dāng)滑行沖突無法通過減速等待或選擇次優(yōu)可替代滑行路徑解決時(shí)，即發(fā)生死鎖狀況.當(dāng)發(fā)生死鎖時(shí)，可不嚴(yán)格執(zhí)行優(yōu)先級策略，臨時(shí)交換航空器的優(yōu)先級，再按相應(yīng)的沖突解決方法來解決沖突.沖突解決之后，恢復(fù)航空器各自的優(yōu)先級.

2 基于航空器優(yōu)先級及滑行沖突解決策略的滑行優(yōu)化模型

2.1 模型假設(shè)

1) 航空器勻速滑行，并且速度不能超過機(jī)場規(guī)定的最大速度55 km/h.

2) 航空器間距符合規(guī)定的最小安全間距20 s.

3) 進(jìn)離場航空器滑行路徑連續(xù).

4) 在研究時(shí)段內(nèi)，所有進(jìn)離場航空器相關(guān)信息、標(biāo)準(zhǔn)坐席數(shù)、滑行油耗等信息己知.

5) 航空器滑行優(yōu)化動態(tài)連續(xù)，本文只研究某一時(shí)段T內(nèi)所有航空器的滑行優(yōu)化.

2.2 定義符號及變量

2.3 目標(biāo)函數(shù)

(1)

式中：Z1為滑行距離目標(biāo)函數(shù)；Z2為滑行等待時(shí)間目標(biāo)函數(shù)；pi

當(dāng)λiΔti>Δci/ti時(shí)，低優(yōu)先級航空器fi選擇次優(yōu)可替代滑行路徑，繞過沖突區(qū)域，考慮其增加的滑行距離，滑行成本目標(biāo)函數(shù)Z轉(zhuǎn)化為滑行距離目標(biāo)函數(shù)Z1，最小化研究時(shí)段內(nèi)所有進(jìn)離場航空器的滑行距離，其表達(dá)式為

(2)

當(dāng)λiΔti<Δci/ti時(shí)，低優(yōu)先級航空器fi選擇減速等待，考慮其增加的滑行等待時(shí)間，滑行成本目標(biāo)函數(shù)Z轉(zhuǎn)化為滑行等待時(shí)間目標(biāo)函數(shù)Z2，最小化研究時(shí)段內(nèi)所有進(jìn)離場航空器的滑行等待時(shí)間，其表達(dá)式為

(3)

式中：(Tidi-TBTi)為航空器fi從最早可開始滑行時(shí)間起到達(dá)目的地所花費(fèi)的實(shí)際時(shí)間；(tidi-tioi)為航空器fi從最早可開始滑行時(shí)間起到達(dá)目的地?zé)o沖突滑行的最短時(shí)間.

2.4 約束條件

?fi∈F,?np,nq∈N

(4)

?p,q,s∈N

(5)

?p,q∈N

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

式(4)為滑行路徑需符合滑行道容量要求，滿足物理鏈接性；式(5)為滑行路徑需連續(xù)可行，滿足流動平衡性；式(6)為滑行速度約束；式(7)為安全間隔約束.式(8)～(9)為對頭沖突約束.式(10)～(11)為超越?jīng)_突約束.式(12)為高優(yōu)先級航空器優(yōu)先滑行的調(diào)度原則.式(13)為所有航空器要在開始滑行時(shí)間之后才能開始滑行.

3 基于滾動時(shí)域的模型求解過程

滾動時(shí)域方法是一種時(shí)間分解法，將一個(gè)全局大規(guī)模優(yōu)化問題分解為一系列相關(guān)聯(lián)的小規(guī)模優(yōu)化子問題，計(jì)算復(fù)雜度大大降低，且子問題部分利用全局信息，調(diào)度質(zhì)量明顯提高[16].基于滾動時(shí)域的航空器場面動態(tài)滑行優(yōu)化模型求解過程如下：

步驟1設(shè)調(diào)度開始時(shí)刻為t0，則ti=t0.

步驟2設(shè)在ti時(shí)刻，預(yù)測時(shí)域?yàn)棣?，選擇調(diào)度時(shí)域[ti,ti+Γ]內(nèi)將要開始滑行和正在滑行的航空器組成預(yù)測窗口，實(shí)時(shí)更新航空器的動態(tài)信息.

步驟3獲取航空器信息，根據(jù)Dijkstra最短路算法，求出預(yù)測窗口內(nèi)各航空器的理想滑行路徑.

步驟4在計(jì)劃時(shí)域窗口T內(nèi)形成滑行調(diào)度子問題.子問題的目標(biāo)函數(shù)和約束條件同原問題，除新加入的航空器外，還包括上一計(jì)劃時(shí)域窗口未完成滑行的航空器，其開始滑行時(shí)間和地點(diǎn)為上一計(jì)劃時(shí)域結(jié)束時(shí)的狀態(tài).

步驟5確定滾動窗口長度m，完成調(diào)度的航空器數(shù)量n，進(jìn)行迭代滾動.在滾動窗口內(nèi)航空器按照其理想滑行路徑滑行，若遇到?jīng)_突，則沖突解決策略確定等待時(shí)間或其他滑行路徑.直到該計(jì)劃時(shí)域窗口航空器數(shù)量不足n時(shí)，結(jié)束當(dāng)前調(diào)度.

步驟6ti+1=ti+T，i=i+1，若ti<Γ，轉(zhuǎn)步驟2，否則求解結(jié)束.

4 仿真算例

選取我國某大型機(jī)場作為研究對象，為方便起見，選取該機(jī)場西半?yún)^(qū)域，將多個(gè)相鄰?fù)C(jī)位抽象成三個(gè)集中停機(jī)區(qū)G1、G2和G3，去掉一些無關(guān)滑行道和節(jié)點(diǎn)，形成包含37個(gè)節(jié)點(diǎn)、48條邊、2條跑道和3個(gè)集中停機(jī)區(qū)的網(wǎng)絡(luò)圖，見圖1.

圖1 我國某大型機(jī)場西半?yún)^(qū)域滑行道系統(tǒng)部分構(gòu)型圖

航空器數(shù)據(jù)選取該機(jī)場2016年7月某天08:00-08:15內(nèi)的高峰小時(shí)航班數(shù)據(jù)，見表1.

表1 我國某大型機(jī)場研究時(shí)段內(nèi)進(jìn)離場航空器相關(guān)信息

本文使用滾動時(shí)域方法求解模型時(shí)，具體參數(shù)設(shè)置如下：高峰時(shí)段內(nèi)預(yù)測窗口航空器數(shù)量為16架，計(jì)劃時(shí)域窗口T為3 min，即180 s，由Dijkstra最短路徑算法求得的航空器理想滑行路徑集可知，最后一架航空器完成調(diào)度的時(shí)間是1 094 s，|1 094/180|=7(向上取整)，則共有7個(gè)調(diào)度時(shí)域窗口，形成7個(gè)調(diào)度子問題.求解這7個(gè)調(diào)度子問題，得出在基于理想滑行路徑的調(diào)度方案下，航空器沖突點(diǎn)的總個(gè)數(shù)為11個(gè)，共有6對航空器發(fā)生沖突.本文的算法設(shè)計(jì)就是建立在理想調(diào)度的基礎(chǔ)上，通過基于航空器優(yōu)先級的沖突解決策略動態(tài)處理滑行沖突，以此保證航空器滑行安全并最小化滑行成本.

4.1 仿真結(jié)果分析

通過采用滾動時(shí)域方法，對研究時(shí)段內(nèi)的16架航空器進(jìn)行基于航空器優(yōu)先級的場面滑行優(yōu)化仿真.優(yōu)化后的滑行路徑集避免了11處滑行沖突.為體現(xiàn)本文優(yōu)化算法的優(yōu)越性，增加基于先到先服務(wù)(FCFS)的固定路徑下的調(diào)度結(jié)果作為比較，調(diào)度結(jié)果對比見圖2.

圖2 基于FCFS與基于優(yōu)先級調(diào)度結(jié)果對比圖

分別比較基于理想滑行路徑、基于FCFS的固定路徑滑行和基于航空器優(yōu)先級的動態(tài)路徑滑行的總等待時(shí)間、總滑行距離、總替代成本和沖突數(shù)，結(jié)果見表2.

表2 三種不同優(yōu)化方案的結(jié)果對比

綜合比較三種方案的優(yōu)化結(jié)果，在理想滑行路徑的優(yōu)化方案下，各航空器選擇最短滑行路徑到達(dá)其終點(diǎn)，過程中無需等待，但這必然造成滑行沖突.在本仿真中，沖突點(diǎn)的總個(gè)數(shù)為11個(gè).而在實(shí)際滑行過程中，不允許有滑行沖突點(diǎn)存在.雖然后兩種優(yōu)化方案都能解決滑行沖突問題，但是付出的代價(jià)卻不同.

由圖2和表2可知， 基于航空器優(yōu)先級的動態(tài)路徑滑行方法的結(jié)果顯著優(yōu)于基于FCFS的固定路徑滑行方法，這是因?yàn)榍罢呖梢酝ㄟ^運(yùn)行沖突解決機(jī)制，令優(yōu)先級較低的航空器選取次優(yōu)可替代滑行路徑，或者減速等待來規(guī)避沖突，并選取成本較低的方法完成滑行；而后者無法選擇較短路徑，只能通過減速等待方式避免沖突，所以無論是在滑行路徑長度上還是在等待時(shí)間上，基于航空器優(yōu)先級的動態(tài)路徑滑行方法都優(yōu)于基于FCFS的固定路徑滑行方法.

4.2 優(yōu)先級保障分析

在航空器的滑行過程和沖突解決過程中，都必須考慮航空器的優(yōu)先級，本文提出的基于航空器優(yōu)先級的動態(tài)滑行優(yōu)化算法能夠確保當(dāng)發(fā)生滑行沖突時(shí)，優(yōu)先保障優(yōu)先級高的航空器的滑行，見表3.

由表3得知，當(dāng)發(fā)生滑行沖突時(shí)，在基于航空器優(yōu)先級的優(yōu)化方法下，保障了所有優(yōu)先級高的航空器的優(yōu)先權(quán).而FCFS方法根據(jù)到達(dá)時(shí)間調(diào)度，只有航空器3,15,14在遇到滑行沖突時(shí)是因其先到達(dá)滑行區(qū)域而優(yōu)先滑行的，并不能保障優(yōu)先級高的航空器能夠優(yōu)先滑行.故本文提出的基于航空器優(yōu)先級的優(yōu)化能夠保證優(yōu)先級高的航空器優(yōu)先滑行，符合實(shí)際情況.

表3 航空器優(yōu)先級保障

4.3 沖突解決策略過程分析

在沖突方面，若所有航空器采用理想滑行路徑滑行，將存在11個(gè)沖突點(diǎn)，采用基于FCFS的固定路徑滑行和基于航空器優(yōu)先級的動態(tài)路徑滑行都不存在沖突點(diǎn)，但是其解決沖突的方式有所差異.

圖3為超越?jīng)_突解決策略過程分析圖，由圖3可知，當(dāng)提前檢測到航空器3和航空器4在滑行道(4,3)段發(fā)生超越?jīng)_突時(shí)，基于FCFS的固定路徑滑行方法是令后機(jī)(航空器3)降低滑行速度，不改變其原來的滑行路徑，跟隨前機(jī)，增加了后機(jī)的等待時(shí)間.而基于航空器優(yōu)先級的動態(tài)路徑滑行方法是令后機(jī)提前在節(jié)點(diǎn)6處選擇次優(yōu)可替代滑行路徑6-7-5-2通過沖突區(qū)域，到達(dá)滑行終點(diǎn).有效避免滑行沖突，無需進(jìn)行等待，不增加滑行距離.

圖3 超越?jīng)_突解決策略過程分析圖

圖4為交叉點(diǎn)沖突解決策略過程分析圖，由圖4可知，當(dāng)提前檢測到航空器14跟航空器16在節(jié)點(diǎn)14處將發(fā)生交叉點(diǎn)沖突時(shí)，基于FCFS的固定路徑滑行方法是令后到達(dá)的航空器16在到達(dá)節(jié)點(diǎn)14前等待18.2 s，以使兩架航空器滿足最小安全間隔要求.而基于航空器優(yōu)先級的動態(tài)路徑滑行方法是令航空器16提前在節(jié)點(diǎn)15處選擇次優(yōu)可替代路徑15-16-17通過沖突區(qū)域，繞行距離160 m，用時(shí)13.3 s，小于18.2 s，由此可見本文動態(tài)滑行的優(yōu)越性.

圖4 交叉點(diǎn)沖突解決策略過程分析圖

本文基于航空器優(yōu)先級的動態(tài)路徑?jīng)_突解決策略明顯優(yōu)于基于FCFS的固定路徑?jīng)_突解決策略，主要區(qū)別在于后者僅考慮到前后兩架航空器到達(dá)沖突區(qū)域(滑行道節(jié)點(diǎn)或路段)時(shí)間順序，令先到達(dá)沖突區(qū)域的航空器優(yōu)先通過，而沒有考慮到航空器的機(jī)型、任務(wù)性質(zhì)、突發(fā)狀況等方面，這不符合場面實(shí)際運(yùn)行情況，不利于航空公司控制運(yùn)行成本，也不利于機(jī)場提高場面運(yùn)行效率.而本文提出的基于航空器優(yōu)先級的動態(tài)路徑?jīng)_突解決策略克服了FCFS方法的種種缺點(diǎn)，可以有效緩解大型樞紐機(jī)場場面運(yùn)行效率無法滿足實(shí)際運(yùn)行需求的現(xiàn)狀，增加場面容量.

5 結(jié) 束 語

本文結(jié)合準(zhǔn)確的機(jī)場場面網(wǎng)絡(luò)結(jié)構(gòu)，以最小化研究時(shí)段內(nèi)所有進(jìn)離場航空器滑行成本為目標(biāo)，建立基于航空器優(yōu)先級的大型機(jī)場場面航空器動態(tài)滑行優(yōu)化模型，探討了場面滑行優(yōu)化中航空器優(yōu)先級的確定方法，提出基于航空器優(yōu)先級的滑行沖突解決策略，在保證航空器優(yōu)先級和滑行安全的前提下最小化滑行成本，為大型機(jī)場場面航空器的動態(tài)滑行提供符合實(shí)際運(yùn)行情況的優(yōu)化理論與方法.

在此研究基礎(chǔ)上，未來可進(jìn)一步考慮航空公司間的公平性、航空器碳排放等因素，對大型機(jī)場場面航空器動態(tài)滑行進(jìn)行更深層次的研究.

參考文獻(xiàn)

[1] SMELTINK J W, SOOMER M J, WAAL P R D, et al. An optimisation model for airport taxi scheduling [J]. Mathematical Problems in Engineering,2008(1):55-58.

[2] DEAU R, GOTTELAND J B, DURAND N. Airport surface management and runways scheduling[J]. Transportation Research Part C: Emerging Technologies ,2009(2):478-482.

[3] ZHOU H, JIANG X. Research on taxiway path optimization based on conflict detection [J]. Plos One, 2014,10(7):897-901.

[4] LANDRY S J, CHEN X W, NOF S Y. A decision support methodology for dynamic taxiway and runway conflict prevention[J]. Decision Support Systems, 2013,55(1):165-174.

[5] JIANG Y, LIAO Z, ZHANG H. A collaborative optimization model for ground taxi based on aircraft priority[J]. Mathematical Problems in Engineering, 2013(2):1-9.

[6] MORI R. Aircraft ground-taxiing model for congested airport using cellular automata[J]. Intelligent Transportation Systems, IEEE Transactions on, 2013,14(1):180-188.

[7] JINGNAN Z. Airport taxi scheduling strategy based on particle swarm optimization algorithm[J]. 2014.

[8] WEISZER M, CHEN J, STEWART P. A real-time active routing approach via a database for airport surface movement[J]. Transportation Research Part C: Emerging Technologies, 2015,58:127-145.

[9] GUéPET J, BRIANT O, GAYON J P, et al. The aircraft ground routing problem: analysis of industry punctuality indicators in a sustainable perspective[J]. European Journal of Operational Research, 2016,248(3):827-839.

[10] 張?zhí)齑?丁萌,左洪福,等.基于區(qū)域控制的航空器滑行軌跡優(yōu)化模型[J].系統(tǒng)工程與電子技術(shù),2016,38(1):136-141.

[11] 高加凱.基于廣州白云機(jī)場平行跑道航空器滑行路徑優(yōu)化研究[D].德陽:中國民用航空飛行學(xué)院,2017.

[12] 王湛,熊佳俊,陳浩.航空器場面滑行速度與油耗研究[J].武漢理工大學(xué)學(xué)報(bào)(交通科學(xué)與工程版),2017,41(3):391-394.

[13] YU C. Integrated optimization of airport taxiway and runway scheduling[J]. Journal of Automation and Control Engineering ,2014(4):578-586.

[14] RAVIZZA S, CHEN J, ATKIN J A D, et al. Aircraft taxi time prediction: Comparisons and insights[J]. Applied Soft Computing, 2014,14:397-406.

[15] CHEN J, WEISZER M, ATKIN J, et al. A heuristic approach to greener airport ground movement[J]. European Journal of Operational Research,2014(3):587-596.

[16] 王冰.滾動時(shí)域調(diào)度方法及其性能分析研究[D].上海：上海交通大學(xué),2005.