延誤航班機(jī)場場面滑行優(yōu)化調(diào)度策略研究＊

柳 青 李春玲 宋祥波

（南京航空航天大學(xué)民航學(xué)院1） 南京 210016） （中國民航大學(xué)經(jīng)管學(xué)院2） 天津 300300）

樞紐機(jī)場場面控制問題（ASMCP）的核心是航空器路徑規(guī)劃及停機(jī)位分配.目前國外研究關(guān)注較多的是自動場面控制系統(tǒng)［1－2］、啟發(fā)式算法求解航班調(diào)度次序［3］、場面運(yùn)行控制和地面等待著陸［4］，以及對多跑道系統(tǒng)（阿姆斯特丹機(jī)場）的復(fù)雜調(diào)度以及高密度航班（達(dá)拉斯沃斯堡機(jī)場）的實(shí)證分析.國內(nèi)現(xiàn)階段研究主要使用多Agent仿真建模、TDSP動態(tài)算法等解決航空器路徑規(guī)劃和優(yōu)化問題［5］.本文將延誤航班按路徑屬性歸類，依照流水車間作業(yè)調(diào)度方式對其進(jìn)行滑行調(diào)度，是機(jī)場控制區(qū)調(diào)度作業(yè)的最新探索，能豐富處理延誤航班應(yīng)急調(diào)度的策略，有較為重要的實(shí)際意義.

1 延誤航班滑行調(diào)度建模

1.1 問題分析

延誤航班應(yīng)急調(diào)度是指在出現(xiàn)天氣、管制等原因后，高峰小時(shí)內(nèi)大量的進(jìn)港航班不能按計(jì)劃到達(dá)時(shí)間（ETA）降落機(jī)場，滑入目標(biāo)停機(jī)位.在出現(xiàn)航班不正常運(yùn)行的緊急情況時(shí)，制定應(yīng)急調(diào)度預(yù)案，重新分配調(diào)度方案，安排更高效的調(diào)度計(jì)劃是解決地面擁堵的重要途徑.調(diào)度航班滑行必須遵守相關(guān)的安全標(biāo)準(zhǔn)，否則，遇到時(shí)刻變化和各種特殊緊急情況，航空器滑行容易產(chǎn)生三類場面沖突［6］，如圖1所示.

圖1 航班調(diào)度過程及滑行三類沖突

航班調(diào)度除推入推出目標(biāo)停機(jī)位可能不同外，有大量航班具有同樣的滑行路徑.正常情況下，不同航空公司飛往不同目的地的不同航班交錯進(jìn)離港.一旦出現(xiàn)航班延誤，既有航班計(jì)劃將被打亂，機(jī)場在效率和安全壓力下，可以考慮選擇更簡單、更快速的應(yīng)急調(diào)度策略，流水作業(yè)法完全可以模擬車間流水線調(diào)度，將具有相同滑行路徑的航班進(jìn)行聚類，統(tǒng)一安排調(diào)度，解決大面積延誤航班調(diào)度同時(shí)，有效規(guī)避滑行沖突，見圖2.

1.2 假設(shè)條件

延誤航班調(diào)度發(fā)生于特殊情況，模型建立需要滿足一定的假設(shè)前提：（1）在時(shí)間（0，T）內(nèi)有一組待降落的航班｛f1，f2，…，fi｝?Aarr和一組等待 起飛的航班｛f1，f2，…，fj｝?Adep由于特殊原因發(fā)生延誤；（2）受所帶油量限制，進(jìn)港航班在空中等待落地的時(shí)間有限.同樣，離港航班在關(guān)艙門后，發(fā)動機(jī)處于運(yùn)轉(zhuǎn)狀態(tài)，不會無限期等待，離港等待滑行的時(shí)間有限；（3）在一個(gè)固定時(shí)段內(nèi)，滑行邊上任意節(jié)點(diǎn)一次只能通過一架航空器；（4）在一個(gè)固定時(shí)段內(nèi)，一架航空器只能在一條滑行邊上滑行.

圖2 航空器滑行調(diào)度轉(zhuǎn)化為流水車間調(diào)度過程

1.3 相關(guān)符號及模型建立

將經(jīng)典車間流水線作業(yè)的思想應(yīng)用于應(yīng)急航班調(diào)度建模，具體過程可描述為：在應(yīng)急高峰時(shí)段內(nèi)有n個(gè)需要調(diào)度航班fi（i＝1，2，…，n）在m 條滑行道邊Rj（j＝1，2，…，m）上滑行，這n個(gè)航班依據(jù)路徑屬性可以歸類成l組航班簇.在一個(gè)航班簇內(nèi)，航班fi的滑行路徑Ri，j（j＝1，2，…，ml），航班滑行路徑Ri，j必須通過滑行邊Rj，滑行時(shí)間記為pi，j.調(diào)度目標(biāo)是在滿足路徑的要求下，為每架航空器尋找到一條有時(shí)間限制的路線，最終使所有航空器總調(diào)度滑行時(shí)間最小，由此建立延誤航班流水調(diào)度模型：

模型中，決策變量ti，k為航班i在滑行道Rk上完成滑行的時(shí)間；pi，k為航空器i在Rk邊上的滑行時(shí)間；xijk為二進(jìn)制決策變量，表示指示變量.如果航班fi在航班fj之前在Rk上滑行，則xijk＝1，否則，xijk＝0；aihk為二進(jìn)制決策變量，表示指示系數(shù)，若航空器i在滑行邊h上滑行的次序先于滑行邊k，那么aihk＝1，否則記為0；M 為一充分大的正整數(shù)；Tsep為不同機(jī)型之間按照規(guī)定要求的滑行間隔時(shí)間，根據(jù)不同重量機(jī)型選取不同的間隔距離值，用公式Tsep＝dsep／ˉv來計(jì)算兩架飛機(jī)最小時(shí)間間隔，ˉv取值飛機(jī)的平均速度.ATAi為到達(dá)航班fi的實(shí)際降落時(shí)間；OBTi為起飛航班撤輪檔時(shí)間，TTDi為離港航空器的結(jié)束滑行的起飛時(shí)間.

目標(biāo)函數(shù)（7）指調(diào)度優(yōu)化的總目標(biāo)是所有進(jìn)離港航空器調(diào)度滑行時(shí)間最少；約束（8）為航空器通過滑行邊的次序，除了滿足滑行時(shí)間外，還需要符合民航局規(guī)定的最小安全間隔；約束（9）為航空器在不同滑行邊上的滑行順序；約束（10）為降落航班的實(shí)際到達(dá)時(shí)間，也即起始滑行時(shí)間；約束（11）為離港航班的實(shí)際起飛時(shí)間；約束（12）為每架航空器必須降落到地面或者撤開輪檔才能開始滑行；約束（13）為對滑行完成時(shí)間的正數(shù)約束.航班預(yù)計(jì)降落時(shí)間ATAi和撤輪檔時(shí)間OBTi由空管調(diào)度給出時(shí)間表；約束（14）為對二進(jìn)制變量的描述.

2 多粒子群求解算法設(shè)計(jì)

2.1 粒子群算法求解滑行調(diào)度

粒子群算法（particle swarm optimization，PSO）是Kennedy和Eberhart在1995年提出的群智能優(yōu)化算法，針對NP復(fù)雜問題求解，粒子群算法有時(shí)間和效率的優(yōu)勢［7－8］，粒子群算法求解調(diào)度問題的主要步驟包括：

1）編碼機(jī)制 首先對模型的參數(shù)進(jìn)行編碼.由于調(diào)度是基于操作為基礎(chǔ)，粒子的順序代表了調(diào)度順序.用d＝n×m表示微粒的位置矢量，一個(gè)粒子可以表示為d維向量，每架航空器均會出現(xiàn)m次.將微粒轉(zhuǎn)化為有序的操作表，再根據(jù)每架航空器滑行時(shí)間進(jìn)行調(diào)度，進(jìn)而產(chǎn)生調(diào)度方案.舉一個(gè)3架進(jìn)場航空器在5條滑行邊上滑行的例子，粒子位置 X＝［1，2，3，4，5，2，3，1，5，4，4，1，5，3，2］，根據(jù)航空器滑行次序（見表1），路徑R1的通過順序是J1－J2－J3，路徑2的調(diào)度次序是J2－J1－J3.

表1 航空器滑行次序

2）適應(yīng)度函數(shù) 適應(yīng)度函數(shù)用來評價(jià)粒子的性能，函數(shù)目標(biāo)是最小化調(diào)度時(shí)間，考慮到航空器的安全間隔因素，也就是約束條件（8）.因此，算法用目標(biāo)函數(shù)

M（1－xijk）×min｛tj，k－ti，k－pj，k－Tsep，0｝作為候選方案的適應(yīng)度函數(shù)，其中M（1－xjk）×min｛tj，k－ti，k－pj，k－Tsep，0｝作為約束條件放入到目標(biāo)函數(shù)的懲罰項(xiàng)，一旦最小安全時(shí)間間隔小于規(guī)定值，則粒子的適應(yīng)度函數(shù)加上無限大的正數(shù)項(xiàng)，可以避免進(jìn)入下一次迭代.

2.2 多粒子群（CPSO）粒子群算法

多粒子群算法步驟如下.

步驟1 根據(jù)初始調(diào)度計(jì)劃，計(jì)算各航空器在各自路徑集Ri上的理想滑行時(shí)間.

步驟2 根據(jù)延誤航班的滑行路徑屬性進(jìn)行聚類，同時(shí)考慮起降時(shí)刻間隔滿足等待時(shí)間約束的一類航班劃分為一組航班簇.

步驟3 設(shè)置2層粒子參數(shù)，全局最優(yōu)粒子種群和5個(gè)子種群，計(jì)算初始子目標(biāo)值.

步驟4 從5個(gè)最優(yōu)子種群中找出最優(yōu)適應(yīng)度函數(shù)值Ztemp與當(dāng)前全局最優(yōu)適應(yīng)度最優(yōu)值進(jìn)行比較，如果優(yōu)于，則用新的適應(yīng)度函數(shù)值代替前一輪的最優(yōu)值.用相應(yīng)新粒子代替原來的粒子，得到此狀態(tài)下的每個(gè)粒子的個(gè)體最優(yōu)解Xpi.

步驟5 在最優(yōu)種群的基礎(chǔ)上重新產(chǎn)生5個(gè)子種群，利用式（8）、（9）移動粒子，產(chǎn)生新的粒子群，重復(fù)步驟5，直至完成設(shè)定的迭代次數(shù).

步驟6 將Ztemp與目前的適應(yīng)度最優(yōu)值進(jìn)行比較，如果優(yōu)于，則用新的適應(yīng)度函數(shù)值代替前一輪的最優(yōu)值.用相應(yīng)新粒子代替原來的粒子，得到此狀態(tài)下的每個(gè)粒子的個(gè)體最優(yōu)解Xpi.

步驟7 計(jì)算調(diào)度時(shí)間，得到調(diào)度方案.

3 算例分析

依算法步驟，首先根據(jù)延誤航班進(jìn)離港調(diào)度路徑和停機(jī)位進(jìn)行屬性聚類，延誤航班滑行路徑可以分為6組待調(diào)度的航班簇，見表2.每組航班簇有相同或者相近的停機(jī)位，再對6組航班簇進(jìn)行滑行調(diào)度優(yōu)化.

表2 聚類航班簇流水車間調(diào)度

圖3 延誤航班流水調(diào)度

求解航班應(yīng)急調(diào)度模型，設(shè)置種群數(shù)50，最大迭代次數(shù)100，慣性因子0.4.同時(shí)，根據(jù)每組航班簇的航空器數(shù)量不同，設(shè)置多粒子種群個(gè)數(shù)，分別為4，4，2，1，3，4組粒子分別計(jì)算.依照假設(shè)條件中的風(fēng)險(xiǎn)級別規(guī)定，待降航班的調(diào)度優(yōu)先級大于起飛航班，調(diào)度過程如圖3所示.

從圖4的計(jì)算結(jié)果看，多粒子群算法不到80代即收斂得到全局最優(yōu)解.但是，多粒子群算法在計(jì)算局部小規(guī)模的航班簇調(diào)度中，相比FCFS方式總體優(yōu)勢不明顯，每個(gè)局部最優(yōu)的總和2 501s的總體調(diào)度時(shí)間效率僅僅提高98s；當(dāng)將所有延誤航班看成一個(gè)整體進(jìn)行全局流水航班調(diào)度時(shí)，總體調(diào)度時(shí)間為1 745s，較之FCFS提高了854s（14.2min），見表3.調(diào)度結(jié)果，對編排新的調(diào)度計(jì)劃有非常有意義的參考價(jià)值.

圖4 迭代次數(shù)與最優(yōu)解

表3 航班調(diào)度結(jié)果比較 s

5 結(jié) 論

1）延誤航班調(diào)度問題可以轉(zhuǎn)化為車間調(diào)度中特殊的流水線調(diào)度方法，處理延誤航班需要分析和正確歸類有類似屬性的航班計(jì)劃，模擬流水車間處理具有相同工序工件的方式.

2）建立的延誤航班應(yīng)急調(diào)度模型可以用來求解不正常航班調(diào)度計(jì)劃，以此提高機(jī)場場面控制部門的調(diào)度效率和機(jī)場容量.通過適應(yīng)性改進(jìn)后可以應(yīng)用于樞紐機(jī)場單跑道場面的延誤航班調(diào)度，具有一定的實(shí)際參考價(jià)值.

3）多粒子群算法在處理大規(guī)模復(fù)雜優(yōu)化問題方面具有時(shí)間效率和解空間快速收斂的優(yōu)勢，可以作為此類模型可靠的求解算法之一.

［1］趙文智，王化佳.一個(gè)航班備降延誤的成本分析［J］.中國民航大學(xué)學(xué)報(bào)，2009，12（6）：45－47.

［2］CAPOZZI B J，DIFELICI J.Towards automated airport surface traffic control：potential benefits and feasibility［C］／／ AIAA Guidance，Navigation，and Control Conference and Exhibit，2004（8）：1－16.

［3］RATHINAM S，MONTOYA J，JUNG Yoon.An optimization model for reducing aircraft taxi times at the dallas fort worth international airport［C］／／26th International Congress of The Aeronautical Sciences，2008：1－14.

［4］ANAGNOSTAKIS I，CLARKE J P.Runway operations planning：a two－stage solution methodology［C］／／Proc.of the 36th Hawaii International Conference on System Sciences（HICSS′03），2003：1－12.

［5］尤 杰，韓松臣.基于多智能體MAS的智能交通控制系統(tǒng)的研究［J］.交通運(yùn)輸工程學(xué)報(bào)，2009，2（1）：109－113.

［6］王艷軍，胡明華，蘇 煒.基于沖突回避的動態(tài)滑行路徑算法［J］.西南交通大學(xué)學(xué)報(bào)，2009，12（6）：933－940.

［7］王萬良，周 明，徐新黎，等.基于改進(jìn)粒子群算法的離子膜車間調(diào)度問題研究［J］.控制與決策，2010，25（7）：1021－1025.

［8］李愛國.多粒子群協(xié)同優(yōu)化算法［J］.復(fù)旦學(xué)報(bào)：自然科學(xué)版，2004，43（5）：923－925.