基于雙層規劃模型的滑行道與停機位 再指派聯合調度

姜雨， 徐成， 蔡夢婷， 陳麗麗

(南京航空航天大學民航學院， 南京 210016)

民航需求日益增大，延誤航班日益增多。航班延誤往往導致停機位預指派計劃無法正常實施。同時停機位指派結果的改變將影響滑行調度的起訖點，進一步增加了其復雜度，對停機位和滑行道聯合調度提出了更高的要求。

國內外學者已經對停機位與滑行道的聯合調度進行了大量研究，研究成果頗為豐富。目前，研究成果主要分為單資源系統調度和多資源系統調度2類。在單資源系統調度方面，國內外學者建立了考慮滑行調度影響的停機位指派模型[1]，部分學者采用車間調度[2]、預測[3-4]等手段得到航空器滑行時間，并以滑行時間作為停機位指派模型的輸入變量，建立考慮停機位指派影響的滑行道調度模型[5-6]，或是引入停機位推出時間控制策略建立滑行道調度模型進一步提升滑行道運行效率[7-8]。在多資源系統調度方面，則主要建立分步驟的滑行道與停機位多系統調度模型[9-10]，按照先進行停機位指派再進行滑行道調度的順序進行場面優化[11]，并在此基礎上允許路徑選擇[12-13]。部分學者嘗試在滑行道調度采用固定路徑的基礎上進行停機位指派最終實現航空器無沖突滑行[14]。此外，部分學者采用仿真軟件進行相關研究，如采用CPN Tools仿真航班過站時跑道與停機位的利用情況，探索如何提高場面資源利用率[15]，基于JADF(Java Agent Development Framework)平臺開發機場空側仿真系統，對跑道入侵與滑行沖突進行風險控制[16]等。

縱觀國內外研究成果，單資源系統調度對滑行調度或是停機位指派有較大簡化，側重于對單一資源系統深入的研究?，F有的多資源系統調度則主要采用先進行停機位指派再進行滑行道調度的分步驟的建模方式，難以體現停機位指派與滑行道調度之間的反饋作用。如何在保障滑行道和停機位指派質量的基礎上實現聯合調度這一問題亟待研究。

本文以滑行道調度為上層規劃，停機位再指派為下層規劃，建立滑行道和停機位聯合調度雙層規劃模型。在提高停機位和滑行道運行效率的同時減少航空器整體等待時間和停機位受擾動影響，并設計遺傳算法結合MATLAB對所建雙層規劃模型進行驗證。

1 滑行道和停機位再指派雙層規劃模型建模

本文采用無向圖G(V,E)對機場場面網絡進行建模，其中V為節點集合，E為邊的集合，并以航空器在無向圖中的運行過程為研究對象建立停機位和滑行道雙層規劃模型。

1.1 基于滑行道調度的上層模型

上層模型為滑行道調度模型，滑行道調度基于停機位再指派結果，是場面調度規劃的上層模型。地面管制員將離場航空器由停機坪出口點經滑行道滑行引導至跑道入口點排隊，將進場航空器由跑道出口點引導至停機坪入口點。具體模型如下：

minZ1=

(1)

s.t．

(2)

(3)

(4)

?i,j∈FA∪FD，bnij=1

(5)

(dmnitmi-dnmjtmj)(dmnitni-dnmjtnj)≥0

(6)

(dmnitmi-dmnjtmj)(dnmitni-dnmjtnj)≥0

(7)

(8)

(9)

(10)

1.2 基于停機位再指派的下層模型

下層模型為停機位再指派模型。下層模型確定待調度航空器的具體停機位及其所屬停機坪，由此確定上層模型航空器滑行道調度中的起點和終點。下層模型目標函數如下：

(11)

(12)

xikεij=xjkεij?i∈FA,?j∈FD

(13)

(14)

Mixik≤Nk

(15)

目標函數式(11)表示最小化遠(GC)和近機位(GR)更換擾動vik和wik，以及航空器進入停機坪的等待時間Tβτ最小。η為等待時間的權重，為常數，可由仿真得到；Tβτ來自上層模型求解結果,體現了上層模型向下層的數據傳輸；Mi為航空器i的機型；yiβτ為判斷航空器i是否在τ時段進入停機坪β的布爾變量；xik為判斷航空器i是否分配至停機位k的布爾變量。

2 算法實現

遺傳算法具有算法參數少、流程簡潔、編程易實現、求解效率高、計算量小等特點,在組合優化問題上有獨特優勢。本文采用遺傳算法對模型進行求解，首先采用整數編碼的方式，對從機場采集的數據按照時間順序排序并進行編碼。染色體結構如圖1所示。

圖1 染色體結構Fig.1 Structure of a chromosome

圖1為滑行道調度染色體結構，每個染色體由FA+FD個基因組成?；蛟谌旧w的位置代表航空器序號，基因的數值代表該航空器選取的路徑編號。如第1個基因位置序號為1，值為R1，代表1號航空器的滑行路徑編號為R1。停機位再指派模型中染色體結構與此相同，不再贅述。

本文結合雙層規劃模型在傳統遺傳算法基礎上引入單點交叉與循環嵌套的迭代方式如下：

因基本交叉可能產生停機位指派與滑行道調度的不可行解,本文采用單點交叉的方式進行交叉操作。即隨機選取染色體n1、n2片段n3∈[1,size]，概率p∈(0,1)，如果p

本文采取循環嵌套的迭代方式以契合雙層規劃模型。即本文算法先進行ig次停機位再指派迭代并在此基礎上對滑行道調度模型進行it次迭代，此為1次聯立迭代，總計進行iG次聯立迭代。其中每次聯立迭代初始解均包含上一次聯立迭代最優解。

本文設置適宜度為各模型目標函數，其余諸如選擇與變異等操作原理均與傳統遺傳算法相同，此處不再贅述。

3 仿真驗證

本文以中國華東某大型機場為例進行仿真實驗。本文依據該機場提供的2016年3月11日8:00—12:00的機位預指派計劃表，對40個航班對及其對應的80架進離場航空器進行停機位再指派和滑行道調度。

本文將G1～G34共34個停機位歸類在C1～C8共8個停機坪中，形成如圖2所示的機場場面網絡無向圖。圖中R1、R2為跑道節點，A1～A16為非停機坪區域滑行道節點，B1～B9為停機坪區域的滑行道節點。B1～B3、B4～B6、B9～B7及停機坪區域內的滑行道為停機坪區域滑行道。C1～C5的出入口分別為B1～B5；C6的出入口為B6；C7的入口為B7，出口為B8；C8的入口為B9，出口為B8。根據各停機坪距離跑道出入口的距離設置C1～C6為近機位停機坪，C7和C8為遠機位停機坪。

停機位信息及預指派計劃如表1和表2所示。

表2中,ETA(Estimated Time of Arrivals)為預計進場時刻，ETD(Estimated Time of Departures)為預計離場時刻。仿真測試中算法參數為：滑行道調度種群數目設為50，停機位再指派問題種群數目為100，突變概率0.02。對上層模型滑行道調度問題迭代100次，下層模型停機位再指派問題迭代150次，聯立迭代次數為20次。依據實際運行情況設置:ut=15 m/s，ug=10 m/s，Tent=60 s，Tpush=300 s，uf=50 m，Tmax=250 s。

停機位仿真結果如圖3所示，滑行道仿真結果如圖4所示，停機位再指派模型前15代進化程度劇烈。隨著迭代代數的增加，目標函數逐漸降低，擾動值逐漸升高最終在一個合理的范圍?；械勒{度前30代收斂速度較快，80代后趨于穩定，這說明本文所取迭代代數是足夠的。

本文采用2種方式進行聯立迭代：每次迭代時僅參考前一次迭代結果的反饋和參考歷次累積迭代結果的反饋。仿真結果如圖5和圖6所示。

圖2 機場場面網絡無向圖Fig.2 Undirected graph of airport surface network

停機位號停機坪號機 型G1C1DG2C1CG3C1CG4C1DG5C2CG6C2CG7C2CG8C2DG9C3DG10C3CG11C4CG12C4DG13C4CG14C4CG15C5CG16C5CG17C5CG18C5DG19C6CG20C6CG21C6CG22C6CG23C6CG24C7DG25C7DG26C7DG27C7DG28C7CG29C8CG30C8CG31C8CG32C8CG33C8CG34C8C

表2 停機位預指派計劃Table 2 Gate pre-assignment plan

圖3 停機位再指派迭代趨勢Fig.3 Iteration trend of gate re-assignment

圖4 滑行道調度趨勢Fig.4 Trend of taxiway scheduling

圖5 僅考慮前一次迭代結果的仿真結果Fig.5 Simulation results only considering the last iterative result

圖6 考慮歷次累積迭代結果的仿真結果Fig.6 Simulation results considering all previous cumulative iteration results

圖5顯示，僅考慮前一次迭代結果的反饋方式不具有穩定性，而考慮歷次累積迭代結果的反饋方式具有明顯的趨勢性(見圖6)，可見考慮歷次累積反饋方式具有較好的反饋效果。因此本文采取該迭代方式進行仿真。

迭代后期的雙層模型求解結果，基于人工停機位再指派的雙層模型求解結果和采用理論最短滑行路徑的雙層模型求解結果的對比如表3所示。

可見，在人工指派將較多的航空器指派至遠機位，導致平均滑行時間增長,航空器平均滑行時間高于迭代后期的結果,沖突增加達75%，嚴重影響場面運行效率。相比于人工指派，雙層規劃策略停機位擾動值由441降至325，降低了26.3%，平均滑行時間由121.65 s降低至91.86 s，降低了24.49%，優化效果明顯。在滑行道調度使用最短路徑的情況下，不僅產生49次沖突，還產生滑行路徑鎖死的情況，遠高于其他類型的仿真結果,不能應用于實際調度。

對迭代后期的實驗結果進行分析，結果如表4和圖7所示，表4中記錄不同指派方案受擾動航空器被指派至的停機位序號。

迭代后期的停機位再分配共影響6架航空器，其中30號航空器被指派至遠機位34，其余5架航空器再指派與預指派間隔8.625個停機位，處于旅客可接受的范圍。更換的停機位與原停機位處于不同的停機坪，減少了停機坪沖突發生的可能性。迭代后期的仿真結果顯示滑行道調度過程中，大部分航空器滑行時間在150 s以內。經統計，最短路A1～A11使用頻率最高，而遠機位停機坪C8僅有1架航空器經過，多數航空器的滑行路徑較短?？傆?7架航空器選取最短路徑，占總航空器數的33.75%；有8架航空器選取了迂回的路徑，占總航空器數的10%，其他航空器均選取了較短的路徑。迂回路徑和較短路徑的選擇有效避免了滑行路徑沖突，減少了沖突時間?；械罌_突情況如表5所示。

表3 3種調度策略的求解結果Table 3 Solving results of three scheduling strategies

表4 受擾動航空器的停機位再指派結果Table 4 Gate re-assignment result of affected aircraft

圖7 各航班滑行時間Fig.7 Taxiing time of each flight

由表5可知，仿真過程中出現的滑行道沖突以進場航班對頭沖突為主。離場航班中僅41號航班即1號航空器承載的離場航班發生沖突，同時平均沖突解脫時間為33.65 s，滑行道總體運行較高。接近最大滑行時間的航空器僅有3架，說明設置最大滑行時間250 s是合適的。

表5 滑行道沖突情況Table 5 Taxiway conflict

4 結 論

1) 本文構建停機位再指派與滑行道調度的雙層模型，通過上下層模型的反復聯立迭代實現模型間的相互影響和作用，并設計改進遺傳算法求解。

2) 仿真結果顯示，該雙層模型較好地體現了上下層模型的影響關系，聯立迭代有明顯趨勢性。停機位擾動值降低26.3%，平均滑行時間降低24.79%，對場面運行效率有明顯提高。

3) 在本文的研究基礎上，未來有關機場場面調度的研究應考慮滑行道動態調度，以及將場面各資源子系統進行聯合調度以實現機場整體調度。