大型機(jī)場單通道U型機(jī)坪區(qū)推出等待點(diǎn)優(yōu)化設(shè)計(jì)

李治寒, 朱新平, 張?zhí)煨? 陳洪浩

(中國民用航空飛行學(xué)院空中交通管理學(xué)院, 廣漢 618307)

全球民航逐步恢復(fù)并迎來快速發(fā)展,傳統(tǒng)的飛行區(qū)場面運(yùn)行保障壓力將逐步增加,而由此導(dǎo)致的航班延誤和場面沖突問題也將日益凸顯,采用機(jī)場改擴(kuò)建增加保障資源供給能力因其耗資耗時(shí),或場地受限往往難以實(shí)施或快速奏效。鑒于此,對場面關(guān)鍵區(qū)域的運(yùn)行程序進(jìn)行優(yōu)化,成為經(jīng)濟(jì)有效的解決辦法。

對于場面運(yùn)行優(yōu)化,徐川等[1]使用模糊C均值聚類算法(fuzzyC-means, FCM)確定預(yù)測的擁堵狀態(tài)數(shù)據(jù)聚類中心,對擁堵狀態(tài)進(jìn)行分類確定場面擁堵狀態(tài)等級,為管制員提供了宏觀層面的決策信息。朱曉波等[2]改進(jìn)反向傳播(back propagation, BP)神經(jīng)網(wǎng)絡(luò),能夠更加精確地對航空器滑行時(shí)間進(jìn)行預(yù)測。謝春生等[3]提出了一種基于模糊規(guī)則系統(tǒng)的滾動(dòng)模糊時(shí)間窗算法,對滑行路徑進(jìn)行動(dòng)態(tài)優(yōu)化。與飛機(jī)推出環(huán)節(jié)相關(guān)的研究有潘衛(wèi)軍等[4]基于飛機(jī)的運(yùn)動(dòng)學(xué)建模和(computer-aided design,CAD)二次開發(fā),對飛機(jī)后推過程中飛機(jī)翼尖的安全間距進(jìn)行了實(shí)時(shí)量化。張亞平等[5]提出一種基于停機(jī)位等待懲罰的推出控制策略,將航班滑行道等待時(shí)間轉(zhuǎn)化為機(jī)位等待時(shí)間,減少了燃油消耗。Jiang等[6]建立了跑道、滑行道、停機(jī)坪的元胞傳輸模型,分析了場面交通演變規(guī)律,探究了飛機(jī)在不同的推出率下對機(jī)場場面交通的影響。Coupe等[7]使用機(jī)器人模擬實(shí)驗(yàn)?zāi)M飛機(jī)推出和滑行至移交點(diǎn)的過程,分析了此過程中飛機(jī)之間的軌跡沖突,探究了沖突概率與推出時(shí)刻的關(guān)系。Lian等[8]提出了一種基于預(yù)測飛機(jī)滑行時(shí)間的動(dòng)態(tài)推出控制(pushdown control flow analysis,PDPC)方法,分析滑行道排隊(duì)長度閾值,通過動(dòng)態(tài)調(diào)整飛機(jī)的推出時(shí)刻,提高了滑行道使用率。Bubalo等[9]開發(fā)了一種基于(large neighborhood search,LNS)算法的定位方法,對出港航班的備選順序進(jìn)行評估,找到總排放量和延誤最少的航班推出順序。何庶等[10]構(gòu)建了側(cè)向跑道航空器滑行路徑優(yōu)化模型,通過動(dòng)態(tài)優(yōu)化航班優(yōu)先級。Ali等[11]使用深度強(qiáng)化學(xué)習(xí)(deep reinforcement learning,DRL)預(yù)測空域接收出港飛機(jī)的能力和出港飛機(jī)滑行道運(yùn)行時(shí)間,回推飛機(jī)最優(yōu)推出時(shí)刻,提高了機(jī)場地面運(yùn)行效率。

縱觀中外研究成果,在場面運(yùn)行優(yōu)化領(lǐng)域,工作集中在航班優(yōu)化排序、滑行路徑優(yōu)化、滑行時(shí)間預(yù)測、航班推出率優(yōu)化等方面,鮮有針對U型機(jī)坪區(qū)的研究,而存在U型機(jī)坪區(qū)域的機(jī)場在民用機(jī)場中占比較高,且運(yùn)行環(huán)境復(fù)雜,運(yùn)行效率較低,因此,提高U型區(qū)運(yùn)行效率,對于緩解場面運(yùn)行瓶頸問題起到關(guān)鍵作用。基于上述考慮,現(xiàn)聚焦場面關(guān)鍵區(qū)域,針對大型機(jī)場內(nèi)的單通道U型機(jī)坪區(qū)的飛機(jī)推出等待點(diǎn)進(jìn)行優(yōu)化研究,推出等待點(diǎn)一般是推出線與滑行通道的切點(diǎn)。

1 推出等待點(diǎn)設(shè)計(jì)方案

1.1 傳統(tǒng)推出等待點(diǎn)運(yùn)行特征分析

飛機(jī)離港地面運(yùn)行過程主要分為3個(gè)階段:機(jī)坪運(yùn)行階段、滑行道運(yùn)行階段、跑道運(yùn)行階段。對于傳統(tǒng)單通道U型區(qū)機(jī)坪運(yùn)行階段,首先是由牽引車沿著推出線頂推停機(jī)位內(nèi)飛機(jī),直至飛機(jī)鼻輪落在推出傳統(tǒng)等待點(diǎn)上(傳統(tǒng)推出等待點(diǎn)設(shè)置在靠近滑行道的飛機(jī)推出線端點(diǎn),等待點(diǎn)垂直于推出線方向,推出等待點(diǎn)為飛機(jī)鼻輪的停止點(diǎn)[12]),頂推過程到此結(jié)束;頂推過程結(jié)束后飛機(jī)需要在等待點(diǎn)等待開始滑行指令,收到塔臺允許滑行指令后,飛機(jī)由自身動(dòng)力沿滑行通道滑至機(jī)坪移交點(diǎn),至此機(jī)坪運(yùn)行階段結(jié)束。此過程中,牽引車將飛機(jī)頂推至傳統(tǒng)等待點(diǎn)即服務(wù)結(jié)束,等待點(diǎn)位置固化。

對于單通道U型區(qū)出港航班,這種固化的運(yùn)行方式會(huì)產(chǎn)生兩種沖突,一種是對位飛機(jī)推出沖突,即通道兩側(cè)相對機(jī)位的飛機(jī)因機(jī)位推出時(shí)間相同或相近而導(dǎo)致的沖突,如圖1中A、B飛機(jī);另一種是滑行通道占用沖突,即已推出完成并開始滑行的飛機(jī)與通道兩側(cè)其他機(jī)位上、即將推出的離港飛機(jī)之間的沖突,如圖1中D、C飛機(jī)位置情況。上述沖突隨著航班量的增加,將可能對U型機(jī)坪區(qū)運(yùn)行安全產(chǎn)生影響。動(dòng)態(tài)配置單通道U型機(jī)坪區(qū)域的等待點(diǎn),有望提高此類機(jī)坪的運(yùn)行效率,正是研究的出發(fā)點(diǎn)。

圖1 推出方式示意圖Fig.1 Diagram of push-back method

1.2 優(yōu)化推出等待點(diǎn)設(shè)計(jì)基本思路

不同于傳統(tǒng)固定式推出等待點(diǎn),優(yōu)化推出等待點(diǎn)設(shè)計(jì)思路為,根據(jù)航班計(jì)劃及實(shí)時(shí)運(yùn)行狀況來動(dòng)態(tài)設(shè)置等待點(diǎn)位置,且等待點(diǎn)的備選位置可在U型機(jī)坪內(nèi)滑行通道上的任一位置點(diǎn)(也即不再局限于機(jī)位推出線與滑行通道的交點(diǎn))。主要考慮因素為航班所在機(jī)位之間的相對位置關(guān)系以及機(jī)坪運(yùn)行安全距離約束。因此,在使用優(yōu)化等待點(diǎn)的過程中,航班的離位過程可能包括牽引車頂推至航班所在機(jī)位推出線與滑行通道的交點(diǎn)、牽引車拖拽航班至新的推出等待點(diǎn),或兩者先后組合。通過這種設(shè)計(jì),基于航班計(jì)劃,將靜態(tài)等待點(diǎn)轉(zhuǎn)化為動(dòng)態(tài)等待點(diǎn),可提高U型區(qū)運(yùn)行效率。

以圖1中A、E飛機(jī)為例具體說明上述優(yōu)化思路。假設(shè)根據(jù)給定航班計(jì)劃,A飛機(jī)先于E飛機(jī)推出,那么按照傳統(tǒng)運(yùn)行方式,E飛機(jī)只能在機(jī)位等待A飛機(jī)推出結(jié)束,收到滑行指令,并且滑過E飛機(jī)所在機(jī)位安全距離才能開始推出。如果兩架飛機(jī)的計(jì)劃推出時(shí)間間隔較小,那么E飛機(jī)會(huì)遲于計(jì)劃推出時(shí)間推出,即產(chǎn)生了機(jī)位延誤,降低了運(yùn)行效率;假設(shè)計(jì)算所得飛機(jī)A的優(yōu)化等待點(diǎn)為圖1中紅色點(diǎn)位,A飛機(jī)由牽引車頂推至傳統(tǒng)等待點(diǎn)位后(圖1中鼻輪黑色點(diǎn)位),立刻再由牽引車將A飛機(jī)向前牽引直至鼻輪落在新等待點(diǎn)上(圖1中紅色點(diǎn)位)。那么即使兩架飛機(jī)的計(jì)劃推出時(shí)間間隔較小,也不會(huì)對E飛機(jī)推出產(chǎn)生影響,E飛機(jī)可以按照計(jì)劃時(shí)間推出。

2 優(yōu)化推出等待點(diǎn)數(shù)學(xué)模型及算法設(shè)計(jì)

2.1 優(yōu)化推出等待點(diǎn)數(shù)學(xué)模型

模型假設(shè)如下。

(1)每架飛機(jī)到達(dá)優(yōu)化等待點(diǎn)后等待開車的時(shí)長固定。

(2)飛機(jī)推至傳統(tǒng)等待點(diǎn)耗時(shí)相同。

(3)飛機(jī)在滑行通道內(nèi)滑行的速度固定且不發(fā)生滑行偏移。

(4)不考慮進(jìn)入U(xiǎn)型區(qū)飛機(jī)的影響。

以U型區(qū)指定點(diǎn)位作為零點(diǎn),滑行通道為X軸,建立平面直角坐標(biāo)系(如圖1所示)。每一架飛機(jī)滑出U型區(qū)總耗時(shí)由三部分組成,第一部分是牽引車頂推和牽引飛機(jī)到達(dá)優(yōu)化等待點(diǎn)所耗時(shí)間;第二部分是到達(dá)優(yōu)化等待點(diǎn)等待開車指令所耗時(shí)間;第三部分是機(jī)長收到開車指令后滑行至U型區(qū)指定點(diǎn)所耗時(shí)間。

則目標(biāo)函數(shù)可表示為

(1)

航班計(jì)劃中第一架飛機(jī)實(shí)際推出時(shí)間為

(2)

兩個(gè)優(yōu)化等待點(diǎn)需要滿足安全間距為

xk-xk-1>S,k≥2

(3)

式(3)中:S為等待點(diǎn)間最小安全間距。

情形1前序飛機(jī)優(yōu)化等待點(diǎn)較后序飛機(jī)傳統(tǒng)等待點(diǎn)更靠近U型區(qū)底部,即Ck

圖2 情形1所對應(yīng)前后飛機(jī)推出等待點(diǎn)相對位置關(guān)系Fig.2 Relative position of aircraft push-back spot before and after scenario 1

(4)

式(4)中:L2為根據(jù)飛機(jī)推出翼尖凈距要求,航班計(jì)劃中前序飛機(jī)需要滑過后序飛機(jī)傳統(tǒng)等待點(diǎn)的安全距離。

情形2后序飛機(jī)傳統(tǒng)等待點(diǎn)較前序飛機(jī)優(yōu)化等待點(diǎn)更靠近U型區(qū)底部,且距離不滿足安全間距。即0≤Ck-xk-1≤L2,如圖3所示。

圖3 情形2所對應(yīng)前后飛機(jī)推出等待點(diǎn)相對位置關(guān)系Fig.3 Relative position of aircraft push-back spot before and after scenario 2

(5)

情形3后序飛機(jī)傳統(tǒng)等待點(diǎn)較前序飛機(jī)優(yōu)化等待點(diǎn)更靠近U型區(qū)底部,且距離大于安全間距,且前序飛機(jī)優(yōu)化等待點(diǎn)較后序飛機(jī)優(yōu)化等待點(diǎn)更靠近U型區(qū)底部。即L2

圖4 情形3所對應(yīng)前后飛機(jī)推出等待點(diǎn)相對位置關(guān)系Fig.4 Relative position of aircraft push-back spot before and after scenario 3

(6)

情形4后序飛機(jī)傳統(tǒng)等待點(diǎn)較前序飛機(jī)優(yōu)化等待點(diǎn)更靠近U型區(qū)底部,且距離大于安全間距,且后序飛機(jī)優(yōu)化等待點(diǎn)較前序飛機(jī)優(yōu)化等待點(diǎn)更靠近U型區(qū)底部;同時(shí),后序飛機(jī)傳統(tǒng)等待點(diǎn)較前序飛機(jī)傳統(tǒng)等待點(diǎn)更靠近U型區(qū)底部,且距離大于安全間距。即L2L2,如圖5所示。

圖5 情形4所對應(yīng)前后飛機(jī)推出等待點(diǎn)相對位置關(guān)系Fig.5 Relative position of aircraft push-back spot before and after scenario 4

(7)

情形5后序飛機(jī)傳統(tǒng)等待點(diǎn)較前序飛機(jī)優(yōu)化等待點(diǎn)更靠近U型區(qū)底部,且距離大于安全間距,且后序飛機(jī)優(yōu)化等待點(diǎn)較前序飛機(jī)更靠近U型區(qū)底部;同時(shí),后序飛機(jī)傳統(tǒng)等待點(diǎn)較前序飛機(jī)傳統(tǒng)等待點(diǎn)更靠近U型區(qū)底部,且距離小于或等于安全間距。即L2

圖6 情形5所對應(yīng)前后飛機(jī)推出等待點(diǎn)相對位置關(guān)系Fig.6 Relative position of aircraft push-back spot before and after scenario 5

(8)

2.2 雙層改進(jìn)模擬退火算法設(shè)計(jì)

2.2.1 算法設(shè)計(jì)基本思路

模擬退火算法(simulated annealing algorithm,SA)源于金屬熱處理過程中固體退火原理,對于組合優(yōu)化問題有較好的求解效果[13]。

根據(jù)航班計(jì)劃計(jì)算每架航班的最優(yōu)等待點(diǎn)位置。為了達(dá)到計(jì)算目的,將目標(biāo)問題拆解為兩個(gè)子問題,一是求解最優(yōu)等待點(diǎn)組合;二是求解該最優(yōu)組合下與N個(gè)航班的最優(yōu)匹配,兩個(gè)子問題是具有上下層關(guān)系的組合優(yōu)化問題。基于此,提出雙層改進(jìn)模擬退火算法進(jìn)行計(jì)算。上層采用改進(jìn)模擬退火算法,輸入等待點(diǎn)組合給下層;下層采用改進(jìn)模擬退火算法,以上層輸入等待點(diǎn)組合為基礎(chǔ),模型目標(biāo)函數(shù)作為評價(jià)函數(shù),尋優(yōu)結(jié)果反饋給上層,直至上層算法迭代結(jié)束。即將目標(biāo)函數(shù)作為下層評價(jià)函數(shù),將下層算法整體作為上層算法的評價(jià)函數(shù)。

2.2.2 雙層算法具體流程

首先,結(jié)合單通道U型區(qū)滑行通道的長度、等待點(diǎn)間的最小安全間隔、需求解的精度,生成待選等待點(diǎn)組合空間K,等待點(diǎn)位置用橫坐標(biāo)表示。具體的生成方式如下。

(1)假設(shè)航班計(jì)劃中N個(gè)航班均使用同一個(gè)等待點(diǎn),對應(yīng)若干可能的優(yōu)化等待點(diǎn)。

(2)假設(shè)航班計(jì)劃中N個(gè)航班使用兩個(gè)不同等待點(diǎn),對應(yīng)若干兩兩等待點(diǎn)組合。

(3)以此類推,直至滑行通道上能夠設(shè)置的最大數(shù)量等待點(diǎn)個(gè)數(shù)為止。將所有可能的組合存入組合空間K中。

其次,從組合空間K中隨機(jī)抽取一個(gè)組合,輸入給下層,將組合元素與航班序列依次匹配作為下層算法初始解,以模型目標(biāo)函數(shù)作為下層算法的評價(jià)函數(shù),輸出最優(yōu)匹配,以及該匹配下全部航班滑出U型區(qū)總耗時(shí),將總耗時(shí)反饋給上層,作為上層算法每次迭代評價(jià)函數(shù)值,上層算法迭代結(jié)束輸出最優(yōu)等待點(diǎn)組合、與航班最優(yōu)匹配、和對應(yīng)滑出U型區(qū)總耗時(shí),達(dá)到計(jì)算目的。以滑行通道長度280 m,等待點(diǎn)間隔60 m,需求解精度1 m,其過程與雙層算法流程如圖7所示。

圖7 雙層算法結(jié)構(gòu)示意圖Fig.7 Schematic diagram of two-layer algorithm structure

2.2.3 上下層算法改進(jìn)方式

傳統(tǒng)模擬退火算法基本步驟如下。

步驟1參數(shù)初始化,初始溫度T0,令當(dāng)前溫度T=T0,生成初始解K1,計(jì)算評價(jià)函數(shù)值f(K1)。

步驟2對當(dāng)前解K1進(jìn)行擾動(dòng),產(chǎn)生新解K2,計(jì)算評價(jià)函數(shù)值f(K2)。

步驟3計(jì)算評價(jià)函數(shù)值增量ΔE=f(K2)-f(K1)。若ΔE<0,則接受新解K2為當(dāng)前解;否則,計(jì)算p=exp(-ΔE/T)值,再生成(0,1)均勻分布隨機(jī)數(shù)r,若p>r,則接受K2為當(dāng)前解,否則不接受,即Mtropolis準(zhǔn)則。

步驟4判斷在當(dāng)前溫度是否充分搜索,是則降溫重復(fù)步驟2,否則在當(dāng)前溫度下重復(fù)步驟2。

步驟5判斷是否滿足終止條件,滿足則輸出當(dāng)前解,否則重復(fù)步驟2。

傳統(tǒng)模擬退火算法流程圖如圖8所示。

圖8 傳統(tǒng)模擬退火算法流程圖Fig.8 Flow chart of traditional simulated annealing algorithm

許多學(xué)者對傳統(tǒng)模擬退火算法進(jìn)行了改進(jìn),李建國等[14]提出了一種帶有記憶功能的模擬退火算法,提高了解的質(zhì)量;李朝遷等[15]將遺傳算法與模擬退火算法融合,使用混合生成初始解的方式,提高初始解質(zhì)量;王旭等[16]利用貝葉斯優(yōu)化,實(shí)現(xiàn)模擬退火算法自動(dòng)調(diào)參。針對組合空間K以及等待點(diǎn)匹配特征,對于上層模擬退火算法,設(shè)計(jì)變降溫系數(shù)的重回溫操作;對于下層模擬退火算法,設(shè)計(jì)多鄰域并行搜索產(chǎn)生新解。以此提高解的質(zhì)量以及滿足管制員決策實(shí)時(shí)性要求。

步驟1上下層算法編碼方式與初始解。對于上層算法,對組合空間K中的組合編號,從1開始,每個(gè)編號對應(yīng)上層算法中的一個(gè)解,隨機(jī)抽取一個(gè)編號作為初始解;對于下層算法,將上層輸入編號解譯為對應(yīng)等待點(diǎn)組合,將組合依次與航班序列匹配,作為下層算法初始解。

步驟2上層與下層生成新解。對于上層算法,結(jié)合上層解的特征,設(shè)計(jì)一種變步長的搜索方式,步長與溫度相關(guān),以契合算法的收斂特征。具體生成方式如式(9)所示。

H=H1+CT0

(9)

式(9)中:H為新解;H1為初始解;T0為當(dāng)前溫度;C為常數(shù)。若解超出編號范圍,則重新向反方向搜索生成新解。

對于下層算法的步驟2,設(shè)計(jì)多鄰域并行搜索,傳統(tǒng)模擬退火算法對于新解的產(chǎn)生主要使用2-opt法,考慮等待點(diǎn)與航班的匹配特征,這種擾動(dòng)方式產(chǎn)生新解的能力有限,故設(shè)計(jì)6種鄰域并行搜索的策略,即單點(diǎn)插入、兩點(diǎn)交換、兩點(diǎn)間倒置、片段倒置移位、片段重組、多點(diǎn)聚合。使用模型目標(biāo)函數(shù)對每次產(chǎn)生的6個(gè)新解進(jìn)行計(jì)算,根據(jù)貪婪準(zhǔn)則,選擇最優(yōu)新解參與下一階段運(yùn)算。此策略可以提高算法迭代后期跳出局部最優(yōu)的能力。6種操作如圖9所示。

圖9 新解擾動(dòng)示意圖Fig.9 Schematic diagram of the new solution perturbation

(1)單點(diǎn)插入:在等待點(diǎn)序列中隨機(jī)抽取一個(gè)點(diǎn)插入另外一個(gè)隨機(jī)位置。

(2)兩點(diǎn)交換:在等待點(diǎn)序列中隨機(jī)抽取兩個(gè)點(diǎn),相互交換位置。

(3)兩點(diǎn)間倒置:在等待點(diǎn)序列中隨機(jī)抽取兩個(gè)點(diǎn),完全顛倒兩點(diǎn)及其之間的序列

(4)片段倒置移位:在等待點(diǎn)序列中隨機(jī)抽取3個(gè)點(diǎn),將前兩點(diǎn)及其之間的序列顛倒后插入第3個(gè)隨機(jī)點(diǎn)后。

(5)片段重組:在等待點(diǎn)序列中隨機(jī)抽?N/2」個(gè)點(diǎn),將等待點(diǎn)序列分成?N/2」個(gè)片段再將片段隨機(jī)重組。

(6)多點(diǎn)聚合:在等待點(diǎn)序列中隨機(jī)抽?N/2」個(gè)點(diǎn),將其按順序排列前置,其于按順序排列后置。

步驟3重升溫操作。對于上層算法的步驟4,當(dāng)溫度低于一定值時(shí),根據(jù)Mtropolis準(zhǔn)則特征可知,算法對新解的接受概率接近于0,此時(shí)算法跳出局部最優(yōu)概率接近于0,為了使算法保持跳出局部最優(yōu)能力,設(shè)計(jì)變降溫系數(shù)的重升溫環(huán)節(jié)。重升溫公式如式(10)所示。

(10)

式(10)中:T為當(dāng)前溫度;T0為初始溫度;maxgen為外循環(huán)迭代次數(shù);iter為該溫度下對應(yīng)的迭代次數(shù);c、c1均為常數(shù);α為降溫系數(shù)。圖10為改進(jìn)降溫函數(shù)的降溫曲線與相同參數(shù)下的傳統(tǒng)降溫曲線。

圖10 降溫曲線Fig.10 Cooling curve

步驟4結(jié)果輸出。上層算法迭代結(jié)束即整體算法迭代結(jié)束,輸出最優(yōu)等待點(diǎn)組合、與航班最優(yōu)匹配、和對應(yīng)滑出U型區(qū)總耗時(shí),即得出航班計(jì)劃中每架航班的優(yōu)化等待點(diǎn)位置與對應(yīng)的滑出U型區(qū)總時(shí)間。

3 算例驗(yàn)證

3.1 算例設(shè)計(jì)

以某大型機(jī)場B、C指廊之間的U型區(qū)為背景,選取U型區(qū)早高峰時(shí)段8:00—9:00的離場航班數(shù)據(jù),如表1所示。該區(qū)域有8個(gè)停機(jī)位,滑行通道總長度260 m,簡圖如圖11所示,以滑行通道為x軸,與滑行通道停止線交點(diǎn)為坐標(biāo)原點(diǎn),滑行通道停止線延長線為y軸建立平面直角坐標(biāo)系。根據(jù)A320的機(jī)型數(shù)據(jù),結(jié)合文獻(xiàn)[4]的計(jì)算方式,L2為60 m。飛機(jī)后推距離L1為135 m,后推速度設(shè)70 m/min,前滑速度120 m/min。兩等待點(diǎn)間最小間距60 m, 設(shè)置每架飛機(jī)到達(dá)優(yōu)化等待點(diǎn)后等待開車的時(shí)長Tw為2 min。設(shè)置等待點(diǎn)精度為1 m。

表1 航班計(jì)劃表

圖11 雙流機(jī)場單通道U型區(qū)構(gòu)型圖Fig.11 Shuangliu Airport single-aisle U-shaped area configuration

經(jīng)反復(fù)試驗(yàn),對算法的各參數(shù)設(shè)置如下:對于下層算法,初始溫度T0=100,最大迭代次數(shù)maxgen=200,Markov鏈長lk=10,降溫速率α=0.9;對于上層算法,初始溫度T0=1 000,最大迭代次數(shù)maxgen=100,Markov鏈長lk=5,降溫速率α=0.9,升溫閾值c=1,變降溫速率參數(shù)c1=1.02。

所得結(jié)果為,滑出U型區(qū)總耗時(shí)93.2 min,對應(yīng)航班計(jì)劃中各航班最優(yōu)等待點(diǎn)位置如表2所示。迭代過程如圖12所示,可見算法在后期陷入局部最優(yōu),通過回溫操作搜索到更優(yōu)值。

表2 優(yōu)化等待點(diǎn)位計(jì)算結(jié)果

圖12 迭代過程Fig.12 Iterative process

3.2 優(yōu)化效果分析

與優(yōu)化前的推出方式進(jìn)行對比。優(yōu)化前,航班計(jì)劃中各飛機(jī)滑出U型區(qū)總耗時(shí)為132.1 min。使用表2所示優(yōu)化點(diǎn)位,15架航班總出港時(shí)間從132.1 min 降低到93.2 min,減少了29.4%。機(jī)位延誤總時(shí)間從51.55 min降低到10.35 min,降低了79.9%。計(jì)耗時(shí)34 s,滿足決策需要。即使航班計(jì)劃臨時(shí)調(diào)整,也能在允許的時(shí)間范圍內(nèi)重新計(jì)算優(yōu)化等待點(diǎn)位置。若不設(shè)計(jì)雙層算法結(jié)構(gòu),使用單層算法對組合空間K進(jìn)行遍歷計(jì)算,所得解為92.5 min,雖然結(jié)果較優(yōu),但其耗時(shí)為52 887.24 s,可見雙層改進(jìn)模擬退火算法的設(shè)計(jì)在保證解質(zhì)量的前提下使得計(jì)算時(shí)間大幅縮短。為了直觀體現(xiàn)優(yōu)化效果,將優(yōu)化對比結(jié)果繪制如圖13所示,各航班機(jī)位延誤時(shí)間如圖14所示。

圖13 機(jī)位總延誤與滑出U型區(qū)總耗時(shí)Fig.13 Total delay time for parking space and total time for taxiing out of U-shaped area

圖14 各航班機(jī)位延誤Fig.14 Length of delay in parking space per flight

3.3 雙層改進(jìn)模擬退火算法有效性分析

根據(jù)所設(shè)計(jì)算法的結(jié)構(gòu)特征,驗(yàn)證順序從下層至上層,使用算例中的U型區(qū),分別輸入15架次航班數(shù)據(jù)和某時(shí)段30架次航班數(shù)據(jù)并進(jìn)行多次計(jì)算。

首先進(jìn)行下層算法有效性驗(yàn)證,從組合空間K中隨機(jī)抽取一個(gè)序號作為下層算法的輸入,所抽編號解譯的等待點(diǎn)組合為(29,89,149,210),將下層設(shè)計(jì)的改進(jìn)模擬退火算法(improved simulated annealing algorithm,ISA)與模擬退火算法(SA),遺傳算法(genetic algorithm,GA)進(jìn)行對比。ISA與SA所設(shè)參數(shù)與上述算例相同,GA與ISA運(yùn)行時(shí)間相同。每種算法獨(dú)立運(yùn)行100次,運(yùn)行結(jié)果如圖15所示。

圖15 下層算法穩(wěn)定性對比Fig.15 Comparison of the stability of lower-level algorithms

模擬退火算法是一種隨機(jī)搜索算法,在同一初始解的情況下,所得解具有隨機(jī)性。由于下層算法需頻繁調(diào)用,因此下層算法求解穩(wěn)定性和求解質(zhì)量與整體算法的性能直接相關(guān)。如圖15所示,通過多鄰域搜索產(chǎn)生新解,使ISA算法解的穩(wěn)定性和質(zhì)量均高于其他兩種算法。

其次進(jìn)行上層算法有效性驗(yàn)證,將上層設(shè)計(jì)的改進(jìn)模擬退火算法(ISA)與模擬退火算法(SA),差分進(jìn)化算法(differential evolution,DE)進(jìn)行對比。3種上層算法所調(diào)用的下層算法均為改進(jìn)的模擬退火算法,下層算法參數(shù)設(shè)置與上述算例相同。上層ISA與SA所用參數(shù)與上述算例中參數(shù)相同,DE運(yùn)行時(shí)間與ISA相同。每種算法獨(dú)立運(yùn)行100次,每種上層算法在不同數(shù)據(jù)量輸入下,100次運(yùn)行的平均值、最小值、最大值如圖16所示。

圖16 上層算法結(jié)果對比Fig.16 Comparison of upper-layer algorithm results

下層算法與上層算法構(gòu)成所設(shè)計(jì)的雙層改進(jìn)模擬退火算法結(jié)構(gòu),驗(yàn)證上層算法性能即為驗(yàn)證整體算法性能。由圖15可知,通過對上層算法增加回溫操作,使求解的平均值、最小值、最大值均優(yōu)于其他兩種算法。最大值與最小值反映算法尋優(yōu)能力,平均值反映算法尋優(yōu)平均狀態(tài)[17]。與優(yōu)化前相比,30架次航班滑出U型區(qū)總耗時(shí)仍可以節(jié)約14.8%,且100次計(jì)算的平均時(shí)間為40 s,滿足決策需要。因此,雙層改進(jìn)模擬退火算法比其他兩種算法性能更優(yōu),且能滿足U型區(qū)高峰時(shí)段不同規(guī)模出港航班的計(jì)算需求。

4 結(jié)論

(1)改變了大型機(jī)場單通道U型區(qū)原有的推出方式,設(shè)計(jì)了基于高峰時(shí)段航班計(jì)劃的動(dòng)態(tài)等待點(diǎn),使航班計(jì)劃內(nèi)飛機(jī)滑出U型區(qū)總耗時(shí)降低29.4%,機(jī)位延誤總時(shí)間降低了79.9%。

(2)設(shè)計(jì)了一種雙層模擬退火算法結(jié)構(gòu),并分別對上下層算法進(jìn)行改進(jìn),對于上層算法,設(shè)計(jì)了基于溫度閾值的變降溫系數(shù)重升溫操作;對于下層算法,改進(jìn)了新解擾動(dòng)方式。相比于其他算法,解的質(zhì)量和求解穩(wěn)定性更優(yōu),且求解時(shí)間滿足決策要求。

(3)下一步工作是加入進(jìn)港航班對出港的影響,制定等待點(diǎn)精度選擇標(biāo)準(zhǔn),做多通道U型區(qū)推出等待點(diǎn)研究。