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

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

0 引言

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

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

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

1 問題描述與建模

1.1 問題描述

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

圖1 進離場航空器場面運行過程Fig.1 Surface running process of approach and departure aircraft

1.2 模型假設

(1)研究時段內(nèi)所有航空器滑行起訖點，開始滑行時間，預計結(jié)束滑行時間均為已知。

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

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

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

1.3 模型建立

(1)目標函數(shù)

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

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

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

(2)約束條件

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

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

1.4 優(yōu)先級設立

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

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

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

2 算法實現(xiàn)

2.1 算法設計

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

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

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

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

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

2.2 滑行道仿真設計

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

3 仿真驗證

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

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

表1 各機型標準載客量、油耗和滑行速度Table 1 Standard passenger capacity,fuel consumption and taxi speed of each model

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

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

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

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

圖3 國內(nèi)某機場滑行道網(wǎng)絡拓撲圖Fig.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é)果對比Table 2 Comparison of simulation results of FCFS and TMC

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

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

3.2 沖突解脫分析

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

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

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

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

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

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

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

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

4 結(jié)論

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