基于時(shí)間富余度控制的滑行道調(diào)度優(yōu)化模型

姜雨，童楚，劉振宇，胡志韜，徐成，張洪海

(1.南京航空航天大學(xué)，民航學(xué)院，南京211106；2.航空電子無(wú)線電研究所，上海200241)

0 引言

大型繁忙機(jī)場(chǎng)跑道端與停機(jī)坪出入口區(qū)域內(nèi)航空器滑行路徑多有交叉，為沖突多發(fā)區(qū)域。航空器早于預(yù)定時(shí)間到達(dá)該區(qū)域容易造成排隊(duì)累積，晚于預(yù)定時(shí)間到達(dá)該區(qū)域容易錯(cuò)過(guò)跑道端起飛時(shí)隙，導(dǎo)致航班不能按時(shí)起飛。因此，研究場(chǎng)面航空器到達(dá)滑行終點(diǎn)準(zhǔn)時(shí)性的調(diào)度優(yōu)化具有現(xiàn)實(shí)意義。

在大型機(jī)場(chǎng)航空器滑行調(diào)度方面，國(guó)內(nèi)外學(xué)者主要從有向圖建模與Petri 網(wǎng)建模方面開(kāi)展研究。有向圖模型采用圖論方法將場(chǎng)面結(jié)構(gòu)抽象化為“點(diǎn)-線”模型，通常結(jié)合混合整數(shù)規(guī)劃進(jìn)行建模。W.EISZER 等[1]構(gòu)建路徑集以簡(jiǎn)化調(diào)度，以最小化滑行耗時(shí)和燃油消耗為目標(biāo)建立滑行道優(yōu)化模型；YU C.等[2]采用基于最短路徑的路徑集簡(jiǎn)化模型，以有向圖的方式進(jìn)行機(jī)場(chǎng)場(chǎng)面建模，建立以油耗最小為目標(biāo)的混合整數(shù)規(guī)劃模型；姜雨等[3]聯(lián)合考慮滑行道與停機(jī)位子系統(tǒng)間的相互作用機(jī)理，構(gòu)建以滑行道調(diào)度和停機(jī)位指派為上、下層模型的雙層規(guī)劃模型。基于Petri 網(wǎng)的滑行道調(diào)度相對(duì)于有向圖結(jié)合混合整數(shù)規(guī)劃的建模方式起步較晚。PODGORSKI P.等[4]利用Petri網(wǎng)建立航空器動(dòng)態(tài)路徑選擇模型，能夠有效識(shí)別機(jī)場(chǎng)場(chǎng)面沖突熱點(diǎn)區(qū)域；LUO X.等[5]基于構(gòu)建的有向Petri 網(wǎng)，建立無(wú)沖突發(fā)生的場(chǎng)面資源調(diào)度優(yōu)化模型。在模型求解方面，國(guó)內(nèi)外學(xué)者大多采用智能算法。JUEPET J.等[6]提出順序啟發(fā)式算法，進(jìn)行航空器滑行路徑和跑道排序問(wèn)題的聯(lián)合求解，提高跑道效率的同時(shí)減少滑行時(shí)間；KAMILA B. K. B.等[7]采用蟻群算法尋求滑行總耗時(shí)最少的最優(yōu)滑行路徑；李善梅等[8]以優(yōu)化進(jìn)、離場(chǎng)航班的滑行路徑為目標(biāo)，提出基于變步長(zhǎng)的滑動(dòng)時(shí)間窗方法和A*算法相結(jié)合的模型求解算法，實(shí)現(xiàn)了對(duì)滑行沖突的智能識(shí)別與解脫。

縱觀國(guó)內(nèi)外研究現(xiàn)狀，建模方式以有向圖與Petri 網(wǎng)建模為主，仿真算法以智能算法為主，大多研究成果以優(yōu)化滑行路徑為主，最小化滑行時(shí)間、滑行距離或燃油消耗，通過(guò)優(yōu)化算法結(jié)構(gòu)提升模型求解效率。而航空器在機(jī)場(chǎng)場(chǎng)面滑行過(guò)程是連續(xù)過(guò)程，具有整體性，若不考慮航空器到達(dá)滑行終點(diǎn)的準(zhǔn)時(shí)性，以縮短滑行時(shí)間，降低滑行成本為目標(biāo)而進(jìn)行路徑優(yōu)化，則會(huì)對(duì)后續(xù)跑道調(diào)度和停機(jī)位指派造成不可避免的影響。本文以提高航空器到達(dá)滑行終點(diǎn)的準(zhǔn)時(shí)性為目標(biāo)，建立基于時(shí)間富余度控制(Time Margin Control,TMC)的滑行道調(diào)度優(yōu)化模型，使航空器到達(dá)滑行終點(diǎn)(跑道入口或停機(jī)坪入口)的時(shí)間盡可能契合預(yù)計(jì)到達(dá)時(shí)間，降低航空器到達(dá)誤差，減少跑道端與停機(jī)位的排隊(duì)等待；設(shè)計(jì)生物地理學(xué)算法(Biogeography- based Optimization，BBO)結(jié)合MATLAB進(jìn)行仿真驗(yàn)證。

1 問(wèn)題描述與建模

1.1 問(wèn)題描述

大型機(jī)場(chǎng)進(jìn)、離場(chǎng)航空器共同作用于跑道、滑行道和停機(jī)位資源系統(tǒng)。進(jìn)、離場(chǎng)航空器之間相互影響，相互制約。尤其在滑行道運(yùn)行部分，既要避免航空器滑行沖突，保障航空器滑行安全，又要保障航空器滑行的準(zhǔn)時(shí)性，提高場(chǎng)面資源運(yùn)行效率。因此，滑行道是航空器運(yùn)行安全和運(yùn)行效率的綜合作用體。大型機(jī)場(chǎng)航空器場(chǎng)面運(yùn)行過(guò)程如圖1所示。

圖1 進(jìn)離場(chǎng)航空器場(chǎng)面運(yùn)行過(guò)程Fig.1 Surface running process of approach and departure aircraft

1.2 模型假設(shè)

(1)研究時(shí)段內(nèi)所有航空器滑行起訖點(diǎn)，開(kāi)始滑行時(shí)間，預(yù)計(jì)結(jié)束滑行時(shí)間均為已知。

(2)機(jī)型決定航空器恒定的滑行速度。

(3)相鄰的若干停機(jī)位被整合成1塊停機(jī)坪，視為同1個(gè)節(jié)點(diǎn)，且停機(jī)位容量滿足航空器調(diào)度需求。

(4)不考慮航空器加速起步和減速靜止的過(guò)程。

1.3 模型建立

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

本文采用無(wú)向圖G(V,E)進(jìn)行大型機(jī)場(chǎng)場(chǎng)面網(wǎng)絡(luò)建模，調(diào)度目標(biāo)為最小化航空器總滑行時(shí)間和到達(dá)誤差的加權(quán)和，目標(biāo)函數(shù)為

式中：A、D分別為進(jìn)、離場(chǎng)航空器集合；R為預(yù)設(shè)路徑集合；Ri為航空器i的滑行路徑，Ri∈R，Ri由節(jié)點(diǎn)vi排列構(gòu)成，即Ri={vi,vi+1,…,vn} ，?vn∈V，V為節(jié)點(diǎn)集合；sm,n為邊(m,n)的空間距離，m,n為節(jié)點(diǎn)編號(hào)，(m,n)∈E，E為邊的集合；n0為起始節(jié)點(diǎn)編號(hào)；Tni、Tn′i、Tmni分別為航空器i在節(jié)點(diǎn)n處為避免3 類滑行沖突產(chǎn)生的等待時(shí)間，其中，n∈V，(m,n)∈E，i∈A?D；t′i,d為航空器i實(shí)際到達(dá)終點(diǎn)的時(shí)刻；ti,d為航空器i預(yù)計(jì)到達(dá)滑行終點(diǎn)的時(shí)刻；ui為航空器i的滑行速度；η為到達(dá)誤差的權(quán)重。

式(1)中航空器總滑行時(shí)間由航空器無(wú)沖突滑行時(shí)間和因沖突產(chǎn)生的等待時(shí)間構(gòu)成，到達(dá)誤差為實(shí)際完成滑行與預(yù)計(jì)完成滑行時(shí)間的偏差。當(dāng)航空器提前到達(dá)，即t′i,d＜ti,d時(shí)，η=1；當(dāng)航空器發(fā)生延誤，即t′i,d＞ti,d時(shí)，η=2。

(2)約束條件

式中：dmni為0-1 決策變量，當(dāng)航空器i依次由節(jié)點(diǎn)m至n通過(guò)邊(m,n)時(shí)，其值為1，否則為0；l為路徑節(jié)點(diǎn)編號(hào)；nO、nD分別為滑行路徑起點(diǎn)、終點(diǎn)；tf為規(guī)定的最小安全間隔；tni為航空器i滑行至節(jié)點(diǎn)n的時(shí)刻；bnij為航空器i比航空器j先通過(guò)節(jié)點(diǎn)n。

式(2)～式(4)為滑行路徑約束。式(3)和式(4)保障航空器在固定起、訖點(diǎn)且經(jīng)過(guò)任意節(jié)點(diǎn)不超過(guò)一次的滑行路徑。式(5)和式(6)分別表示避免航空器滑行的對(duì)頭沖突(保證兩相向航空器不同時(shí)處于同一鏈路)、超越?jīng)_突(保證同一鏈路上同向航空器滿足安全間隔)。式(7)和式(8)表示避免航空器交叉點(diǎn)沖突(保證先后通過(guò)同一節(jié)點(diǎn)的兩航空器滿足安全間隔)。

1.4 優(yōu)先級(jí)設(shè)立

解決滑行沖突的本質(zhì)是確定兩架航空器在通過(guò)沖突節(jié)點(diǎn)或滑行道鏈路的先后順序。本文引入時(shí)間富余度的概念，為航空器設(shè)置的動(dòng)態(tài)優(yōu)先級(jí)為

式中：Ti(fy)為時(shí)間富余度，度量航空器i滑行過(guò)程中的剩余時(shí)間；ti,o為計(jì)劃開(kāi)始滑行時(shí)間；si為航空器i滑行路徑的長(zhǎng)度；為理想狀態(tài)下的滑行時(shí)間；為航空器i為避免沖突產(chǎn)生的額外等待時(shí)間；Ei為航空器i的優(yōu)先級(jí)，航空器根據(jù)Ei的大小確定通過(guò)沖突區(qū)域的先后順序；Δti為航空器因避免沖突所造成的時(shí)間損失；P為燃油單價(jià)；Ki為航空器i的耗油率；H為旅客單位延誤成本；Ni為航空器i的旅客數(shù)。

時(shí)間富余度Ti(fy)在運(yùn)行過(guò)程中隨進(jìn)程更新，刻畫(huà)航空器i完成滑行任務(wù)的緊迫程度。當(dāng)Ti(fy)＞0，即航空器預(yù)計(jì)提前到達(dá)滑行終點(diǎn)時(shí)，應(yīng)將油耗成本作為優(yōu)先級(jí)的參考因素；當(dāng)Ti(fy)≤0，即航空器預(yù)計(jì)將發(fā)生滑行延誤。

2 算法實(shí)現(xiàn)

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

生物地理學(xué)算法(BBO)中的可行解對(duì)應(yīng)自然界中的棲息地，棲息地的優(yōu)劣程度以適宜程度(Habitat Suitability Index，HSI)衡量，并作為個(gè)體優(yōu)劣排序的依據(jù)，HSI 越高表明棲息地越適宜。HSI的設(shè)置結(jié)合模型的目標(biāo)函數(shù)式(1)，并對(duì)沖突鎖死情況進(jìn)行懲罰，即

式中：fHSI為適應(yīng)度函數(shù)；Xlock為沖突鎖死的次數(shù)；C為對(duì)應(yīng)的懲罰系數(shù)；M為用于調(diào)節(jié)數(shù)量級(jí)的正常數(shù)。

根據(jù)BBO算法的基本原理，設(shè)最大遷入、遷出概率分別為E和I，滿足E=I=1，每個(gè)棲息地的遷入概率μz，遷出概率λz分別為

式中：q為棲息地最多可容納的種群數(shù)量；z為棲息地當(dāng)前所擁有的種群數(shù)量。z由HSI 唯一確定。設(shè)當(dāng)前棲息地總數(shù)為h，序列中第g個(gè)棲息地的當(dāng)前種群數(shù)為z=h-g。

采用輪盤(pán)賭的方式隨機(jī)產(chǎn)生新的X′替換原物種X。設(shè)棲息地g發(fā)生變異的概率為wg，其中，wmax為最大突變概率，Ph-g為棲息地中當(dāng)前物種數(shù)量對(duì)應(yīng)的概率，Pmax為Ph-g的最大值，計(jì)算公式為

2.2 滑行道仿真設(shè)計(jì)

所有航空器均沿其規(guī)劃路徑滑行至終點(diǎn)。賦予各航空器經(jīng)過(guò)節(jié)點(diǎn)的時(shí)間信息，記作Bts=(i,m,c,t′)，其中：i為航空器編號(hào)；m為節(jié)點(diǎn)編號(hào)；c為該節(jié)點(diǎn)在航空器i的滑行路徑中的序號(hào)；t′為航空器i無(wú)沖突到達(dá)節(jié)點(diǎn)m的時(shí)間。例如，Bts=(2 ,18,5,463)表示2 號(hào)航空器無(wú)沖突到達(dá)節(jié)點(diǎn)18的時(shí)間為463 s，其中，節(jié)點(diǎn)18在該航空器的路徑中為第5 個(gè)節(jié)點(diǎn)。將所有節(jié)點(diǎn)按時(shí)間先后升序排列，生成含有節(jié)點(diǎn)信息的時(shí)間軸BTS=(Bts1,Bts2,…,Btsa)。從起始時(shí)間節(jié)點(diǎn)Bts1=(i1,m1,c1,t′1)起，搜索安全時(shí)間間隔δ內(nèi)的所有航空器信息，判斷m是否相同，如果相同，表明兩架航空器發(fā)生沖突，需要進(jìn)行沖突解脫。保持第一架通過(guò)該節(jié)點(diǎn)的航空器的信息不變，從第2架通過(guò)該節(jié)點(diǎn)的航空器開(kāi)始，直到最后一架通過(guò)該節(jié)點(diǎn)的航空器，通過(guò)優(yōu)先級(jí)依次判斷后續(xù)航空器通過(guò)該節(jié)點(diǎn)次序，其實(shí)際到達(dá)該節(jié)點(diǎn)時(shí)間依次順延。隨即相應(yīng)更新上述航空器通過(guò)后續(xù)節(jié)點(diǎn)的時(shí)間信息，重復(fù)搜索安全時(shí)間間隔這一步驟。示例如圖2所示。

3 仿真驗(yàn)證

選取我國(guó)某大型機(jī)場(chǎng)某日18:00-19:00的42架航空器作為研究對(duì)象，對(duì)滑行道調(diào)度進(jìn)行仿真，機(jī)場(chǎng)實(shí)際場(chǎng)面滑行道運(yùn)行數(shù)據(jù)，如具體機(jī)型參數(shù)，各機(jī)型航空器滑行過(guò)程中標(biāo)準(zhǔn)載客量，耗油和滑行速度如表1所示(數(shù)據(jù)來(lái)源于所選取機(jī)場(chǎng)的管制塔臺(tái)專業(yè)技術(shù)手冊(cè))。機(jī)場(chǎng)場(chǎng)面構(gòu)型如圖3所示，Q8 為進(jìn)場(chǎng)航空器著陸點(diǎn)，Q9為起飛跑道端點(diǎn)，滑行道系統(tǒng)共有70個(gè)節(jié)點(diǎn)。

圖2 航空器沖突解脫示例Fig.2 Example of aircraft conflict relief

表1 各機(jī)型標(biāo)準(zhǔn)載客量、油耗和滑行速度Table 1 Standard passenger capacity,fuel consumption and taxi speed of each model

航油價(jià)格以國(guó)家發(fā)展改革委2018年12月份核定的航空煤油價(jià)格4547 元?t-1為標(biāo)準(zhǔn)。假定每位旅客等待成本為1.7元?min-1。

3.1 優(yōu)化結(jié)果分析

通過(guò)不斷仿真驗(yàn)證，棲息地規(guī)模設(shè)為100，突變概率為0.08。不同滑行策略下的滑行道調(diào)度進(jìn)化曲線如圖4和圖5所示。

FCFS(First Come First Service)策略下航空器總滑行時(shí)間穩(wěn)步下降，最優(yōu)解出現(xiàn)在第196 代，此時(shí)航空器總滑行時(shí)間為12614 s；同時(shí)，航空器總到達(dá)誤差整體呈下降趨勢(shì)，過(guò)程中波動(dòng)幅度較小，原因在于FCFS 僅考慮滑行時(shí)間最小化，無(wú)法調(diào)整延誤時(shí)間較長(zhǎng)航空器的優(yōu)先級(jí)以提高準(zhǔn)時(shí)性，滑行調(diào)度缺乏動(dòng)態(tài)性。TMC 策略優(yōu)先保證航空器準(zhǔn)時(shí)性，以總到達(dá)誤差為主要目標(biāo)，最優(yōu)解出現(xiàn)在第189代。與FCFS相比，TMC策略下總滑行時(shí)間從第17至第132 代上下波動(dòng)劇烈，曲線鋸齒狀明顯，總滑行時(shí)間由12614 s 提高至12930 s，增加了2.3%；但TMC 策略以小幅增加總滑行時(shí)間為代價(jià)，使航空器總到達(dá)誤差縮短946 s，減少63.1%，提高航空器準(zhǔn)時(shí)性，有利于提升旅客滿意度。FCFS 策略與TMC 策略體現(xiàn)了滑行時(shí)間與準(zhǔn)時(shí)性兩者的博弈。兩種策略下仿真結(jié)果如表2所示。各航空器到達(dá) 滑行終點(diǎn)時(shí)間誤差對(duì)比及分布如表3和圖6所示。

圖3 國(guó)內(nèi)某機(jī)場(chǎng)滑行道網(wǎng)絡(luò)拓?fù)鋱DFig.3 Topology diagram of taxiway network in a domestic airport

圖4 FCFS策略迭代結(jié)果Fig.4 FCFS strategy iterative result

圖5 TMC策略迭代結(jié)果Fig.5 Time margin control strategy iterative result

表2 FCFS與TMC仿真結(jié)果對(duì)比Table 2 Comparison of simulation results of FCFS and TMC

從圖6和表3可以看出，F(xiàn)CFS策略下航空器到達(dá)誤差超過(guò)30 s的有16架，占比38.1%，其中6架航空器到達(dá)誤差在1 min以上。而TMC 策略下40 架航空器準(zhǔn)時(shí)性指標(biāo)完成度較高，比重高達(dá)95.2%。僅14 號(hào)、18 號(hào)兩架小機(jī)型航空器到達(dá)誤差超過(guò)30 s，分別為97.5 s 和34 s，分別為B738 和A322 機(jī)型。其中14號(hào)航空器滑行路徑與其他航空器重合區(qū)域較多，導(dǎo)致沖突等待時(shí)間較長(zhǎng)，因此準(zhǔn)時(shí)性較差。相比于FCFS策略，TMC策略將所有沖突航空器總到達(dá)誤差從1175.9 s 降至397.9 s，減少66.2%。可見(jiàn)TMC 策略可以將更多沖突解脫時(shí)間分配給時(shí)間富余度較大的航空器，從而提高延誤航班的準(zhǔn)時(shí)性。

表3 不同到達(dá)誤差時(shí)間段航空器數(shù)量對(duì)比Table 3 Comparison of number of aircraft in different time periods of arrival error

3.2 沖突解脫分析

表4為FCFS 策略與TMC 策略下航空器沖突次數(shù)與解脫時(shí)間對(duì)比，發(fā)生沖突航空器等待次數(shù)如圖7所示。

FCFS 策略下航空器共發(fā)生18 次滑行沖突。18次沖突由12架航空器分配，除2號(hào)、4號(hào)和7號(hào)這3 架航空器分別承擔(dān)2 次、3 次和3 次沖突以外，其余航空器均只發(fā)生1 次沖突。TMC 策略下共發(fā)生12次沖突，減少33%，除去1次交叉點(diǎn)沖突，其余11次均為超越?jīng)_突。在航空器滑行過(guò)程中，發(fā)生超越?jīng)_突的解脫方式為后機(jī)減速，與前機(jī)保持相同速度，直至2 架航空器共用路段節(jié)點(diǎn)分離后，后機(jī)恢復(fù)原速度繼續(xù)滑行。

圖6 各航空器到達(dá)誤差分布Fig.6 Arrival error distribution map of each aircraft

表4 航空器滑行沖突次數(shù)與解脫總時(shí)間對(duì)比Table 4 Comparison of aircraft taxi conflicts and total free time

交叉點(diǎn)沖突解脫是根據(jù)優(yōu)先級(jí)別的高低安排在沖突節(jié)點(diǎn)的滑行順序，2 架航空器在滿足安全間隔后方可通過(guò)沖突節(jié)點(diǎn)。其沖突解決過(guò)程大大增加了管制員的工作負(fù)荷。因此TMC策略將交叉點(diǎn)沖突轉(zhuǎn)化為超越?jīng)_突，能夠在航空器運(yùn)行安全的前提下降低滑行道調(diào)度難度。FCFS 與TMC 兩種策略下滑行距離增量如圖8所示。

圖7 航空器沖突等待次數(shù)對(duì)比Fig.7 Comparison chart of waiting times of conflict aircraft

圖8 各航空器滑行距離增量對(duì)比Fig.8 Comparison chart of increment of taxiing distance of each aircraft

兩種策略下，絕大多數(shù)航空器選擇最短路滑行。FCFS策略下總滑行距離增量為3830 m，其中，8 架航空器滑行距離增量超過(guò)400 m，6 架為大型機(jī)，2架為小型機(jī)。TMC策略下總滑行距離增量為4440 m，比FCFS策略增加610 m。4架航空器滑行距離增量超過(guò)400 m，其中，13 號(hào)航空器為大機(jī)型航空器，其余3架均為小型機(jī)。11號(hào)和21號(hào)這2架航空器均為時(shí)間富余度較大的航空器，滑行距離均增加1060 m。為保障時(shí)間富余度較小航空器的準(zhǔn)時(shí)性，其以犧牲自身滑行距離為代價(jià)，優(yōu)先保障其他航空器的滑行。TMC策略將滑行距離較長(zhǎng)的路線更多分配給小型機(jī)，符合實(shí)際運(yùn)行中優(yōu)先保障大型機(jī)的規(guī)則，有利于減少機(jī)場(chǎng)和航空公司雙方運(yùn)行成本。

4 結(jié)論

本文在兼顧航空器油耗與載客量的動(dòng)態(tài)優(yōu)先級(jí)基礎(chǔ)上，設(shè)置以航空器滑行時(shí)間富余度為主，以最小化航空器到達(dá)誤差和場(chǎng)面滑行時(shí)間為調(diào)度目標(biāo)，建立基于TMC 的滑行道調(diào)度優(yōu)化模型。結(jié)果表明：TMC 策略下航空器到達(dá)滑行終點(diǎn)的準(zhǔn)時(shí)性提高顯著，航空器到達(dá)誤差顯著降低，航空器場(chǎng)面運(yùn)行效率得以有效提升?？紤]航空器滑行準(zhǔn)時(shí)性的場(chǎng)面調(diào)度研究目前比較少，未來(lái)的研究應(yīng)考慮如何在機(jī)場(chǎng)協(xié)同決策環(huán)境下，在保證航空器滑行準(zhǔn)時(shí)性基礎(chǔ)上實(shí)現(xiàn)后續(xù)停機(jī)位的指派和跑道的調(diào)度，從而提升整個(gè)場(chǎng)面的聯(lián)合調(diào)度效率。