基于雙層規(guī)劃模型的滑行道與停機(jī)位 再指派聯(lián)合調(diào)度

姜雨， 徐成， 蔡夢(mèng)婷， 陳麗麗

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

民航需求日益增大，延誤航班日益增多。航班延誤往往導(dǎo)致停機(jī)位預(yù)指派計(jì)劃無(wú)法正常實(shí)施。同時(shí)停機(jī)位指派結(jié)果的改變將影響滑行調(diào)度的起訖點(diǎn)，進(jìn)一步增加了其復(fù)雜度，對(duì)停機(jī)位和滑行道聯(lián)合調(diào)度提出了更高的要求。

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

縱觀國(guó)內(nèi)外研究成果，單資源系統(tǒng)調(diào)度對(duì)滑行調(diào)度或是停機(jī)位指派有較大簡(jiǎn)化，側(cè)重于對(duì)單一資源系統(tǒng)深入的研究。現(xiàn)有的多資源系統(tǒng)調(diào)度則主要采用先進(jìn)行停機(jī)位指派再進(jìn)行滑行道調(diào)度的分步驟的建模方式，難以體現(xiàn)停機(jī)位指派與滑行道調(diào)度之間的反饋?zhàn)饔?。如何在保障滑行道和停機(jī)位指派質(zhì)量的基礎(chǔ)上實(shí)現(xiàn)聯(lián)合調(diào)度這一問(wèn)題亟待研究。

本文以滑行道調(diào)度為上層規(guī)劃，停機(jī)位再指派為下層規(guī)劃，建立滑行道和停機(jī)位聯(lián)合調(diào)度雙層規(guī)劃模型。在提高停機(jī)位和滑行道運(yùn)行效率的同時(shí)減少航空器整體等待時(shí)間和停機(jī)位受擾動(dòng)影響，并設(shè)計(jì)遺傳算法結(jié)合MATLAB對(duì)所建雙層規(guī)劃模型進(jìn)行驗(yàn)證。

1 滑行道和停機(jī)位再指派雙層規(guī)劃模型建模

本文采用無(wú)向圖G(V,E)對(duì)機(jī)場(chǎng)場(chǎng)面網(wǎng)絡(luò)進(jìn)行建模，其中V為節(jié)點(diǎn)集合，E為邊的集合，并以航空器在無(wú)向圖中的運(yùn)行過(guò)程為研究對(duì)象建立停機(jī)位和滑行道雙層規(guī)劃模型。

1.1 基于滑行道調(diào)度的上層模型

上層模型為滑行道調(diào)度模型，滑行道調(diào)度基于停機(jī)位再指派結(jié)果，是場(chǎng)面調(diào)度規(guī)劃的上層模型。地面管制員將離場(chǎng)航空器由停機(jī)坪出口點(diǎn)經(jīng)滑行道滑行引導(dǎo)至跑道入口點(diǎn)排隊(duì)，將進(jìn)場(chǎng)航空器由跑道出口點(diǎn)引導(dǎo)至停機(jī)坪入口點(diǎn)。具體模型如下：

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 基于停機(jī)位再指派的下層模型

下層模型為停機(jī)位再指派模型。下層模型確定待調(diào)度航空器的具體停機(jī)位及其所屬停機(jī)坪，由此確定上層模型航空器滑行道調(diào)度中的起點(diǎn)和終點(diǎn)。下層模型目標(biāo)函數(shù)如下：

(11)

(12)

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

(13)

(14)

Mixik≤Nk

(15)

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

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

遺傳算法具有算法參數(shù)少、流程簡(jiǎn)潔、編程易實(shí)現(xiàn)、求解效率高、計(jì)算量小等特點(diǎn),在組合優(yōu)化問(wèn)題上有獨(dú)特優(yōu)勢(shì)。本文采用遺傳算法對(duì)模型進(jìn)行求解，首先采用整數(shù)編碼的方式，對(duì)從機(jī)場(chǎng)采集的數(shù)據(jù)按照時(shí)間順序排序并進(jìn)行編碼。染色體結(jié)構(gòu)如圖1所示。

圖1 染色體結(jié)構(gòu)Fig.1 Structure of a chromosome

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

本文結(jié)合雙層規(guī)劃模型在傳統(tǒng)遺傳算法基礎(chǔ)上引入單點(diǎn)交叉與循環(huán)嵌套的迭代方式如下：

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

本文采取循環(huán)嵌套的迭代方式以契合雙層規(guī)劃模型。即本文算法先進(jìn)行ig次停機(jī)位再指派迭代并在此基礎(chǔ)上對(duì)滑行道調(diào)度模型進(jìn)行it次迭代，此為1次聯(lián)立迭代，總計(jì)進(jìn)行iG次聯(lián)立迭代。其中每次聯(lián)立迭代初始解均包含上一次聯(lián)立迭代最優(yōu)解。

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

3 仿真驗(yàn)證

本文以中國(guó)華東某大型機(jī)場(chǎng)為例進(jìn)行仿真實(shí)驗(yàn)。本文依據(jù)該機(jī)場(chǎng)提供的2016年3月11日8:00—12:00的機(jī)位預(yù)指派計(jì)劃表，對(duì)40個(gè)航班對(duì)及其對(duì)應(yīng)的80架進(jìn)離場(chǎng)航空器進(jìn)行停機(jī)位再指派和滑行道調(diào)度。

本文將G1～G34共34個(gè)停機(jī)位歸類在C1～C8共8個(gè)停機(jī)坪中，形成如圖2所示的機(jī)場(chǎng)場(chǎng)面網(wǎng)絡(luò)無(wú)向圖。圖中R1、R2為跑道節(jié)點(diǎn)，A1～A16為非停機(jī)坪區(qū)域滑行道節(jié)點(diǎn)，B1～B9為停機(jī)坪區(qū)域的滑行道節(jié)點(diǎn)。B1～B3、B4～B6、B9～B7及停機(jī)坪區(qū)域內(nèi)的滑行道為停機(jī)坪區(qū)域滑行道。C1～C5的出入口分別為B1～B5；C6的出入口為B6；C7的入口為B7，出口為B8；C8的入口為B9，出口為B8。根據(jù)各停機(jī)坪距離跑道出入口的距離設(shè)置C1～C6為近機(jī)位停機(jī)坪，C7和C8為遠(yuǎn)機(jī)位停機(jī)坪。

停機(jī)位信息及預(yù)指派計(jì)劃如表1和表2所示。

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

停機(jī)位仿真結(jié)果如圖3所示，滑行道仿真結(jié)果如圖4所示，停機(jī)位再指派模型前15代進(jìn)化程度劇烈。隨著迭代代數(shù)的增加，目標(biāo)函數(shù)逐漸降低，擾動(dòng)值逐漸升高最終在一個(gè)合理的范圍?；械勒{(diào)度前30代收斂速度較快，80代后趨于穩(wěn)定，這說(shuō)明本文所取迭代代數(shù)是足夠的。

本文采用2種方式進(jìn)行聯(lián)立迭代：每次迭代時(shí)僅參考前一次迭代結(jié)果的反饋和參考?xì)v次累積迭代結(jié)果的反饋。仿真結(jié)果如圖5和圖6所示。

圖2 機(jī)場(chǎng)場(chǎng)面網(wǎng)絡(luò)無(wú)向圖Fig.2 Undirected graph of airport surface network

停機(jī)位號(hào)停機(jī)坪號(hào)機(jī) 型G1C1DG2C1CG3C1CG4C1DG5C2CG6C2CG7C2CG8C2DG9C3DG10C3CG11C4CG12C4DG13C4CG14C4CG15C5CG16C5CG17C5CG18C5DG19C6CG20C6CG21C6CG22C6CG23C6CG24C7DG25C7DG26C7DG27C7DG28C7CG29C8CG30C8CG31C8CG32C8CG33C8CG34C8C

表2 停機(jī)位預(yù)指派計(jì)劃Table 2 Gate pre-assignment plan

圖3 停機(jī)位再指派迭代趨勢(shì)Fig.3 Iteration trend of gate re-assignment

圖4 滑行道調(diào)度趨勢(shì)Fig.4 Trend of taxiway scheduling

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

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

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

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

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

對(duì)迭代后期的實(shí)驗(yàn)結(jié)果進(jìn)行分析，結(jié)果如表4和圖7所示，表4中記錄不同指派方案受擾動(dòng)航空器被指派至的停機(jī)位序號(hào)。

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

表3 3種調(diào)度策略的求解結(jié)果Table 3 Solving results of three scheduling strategies

表4 受擾動(dòng)航空器的停機(jī)位再指派結(jié)果Table 4 Gate re-assignment result of affected aircraft

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

由表5可知，仿真過(guò)程中出現(xiàn)的滑行道沖突以進(jìn)場(chǎng)航班對(duì)頭沖突為主。離場(chǎng)航班中僅41號(hào)航班即1號(hào)航空器承載的離場(chǎng)航班發(fā)生沖突，同時(shí)平均沖突解脫時(shí)間為33.65 s，滑行道總體運(yùn)行較高。接近最大滑行時(shí)間的航空器僅有3架，說(shuō)明設(shè)置最大滑行時(shí)間250 s是合適的。

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

4 結(jié) 論

1) 本文構(gòu)建停機(jī)位再指派與滑行道調(diào)度的雙層模型，通過(guò)上下層模型的反復(fù)聯(lián)立迭代實(shí)現(xiàn)模型間的相互影響和作用，并設(shè)計(jì)改進(jìn)遺傳算法求解。

2) 仿真結(jié)果顯示，該雙層模型較好地體現(xiàn)了上下層模型的影響關(guān)系，聯(lián)立迭代有明顯趨勢(shì)性。停機(jī)位擾動(dòng)值降低26.3%，平均滑行時(shí)間降低24.79%，對(duì)場(chǎng)面運(yùn)行效率有明顯提高。

3) 在本文的研究基礎(chǔ)上，未來(lái)有關(guān)機(jī)場(chǎng)場(chǎng)面調(diào)度的研究應(yīng)考慮滑行道動(dòng)態(tài)調(diào)度，以及將場(chǎng)面各資源子系統(tǒng)進(jìn)行聯(lián)合調(diào)度以實(shí)現(xiàn)機(jī)場(chǎng)整體調(diào)度。