面向航班延誤的停機(jī)位實(shí)時(shí)指派優(yōu)化模型

姜 雨，胡志韜，童 楚，劉振宇，陳麗麗，張洪海

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

0 引 言

民航航班量的快速增長與機(jī)場資源的瓶頸使航班延誤現(xiàn)象成為常態(tài)，對機(jī)場場面資源的正常運(yùn)行造成不利影響，其中，停機(jī)位資源對延誤尤為敏感.延誤發(fā)生后，停機(jī)位預(yù)指派方案受到擾動(dòng)，若不能及時(shí)調(diào)整方案，會(huì)使延誤進(jìn)一步傳播和擴(kuò)散.因此，面向航班延誤的停機(jī)位實(shí)時(shí)指派對提升機(jī)場場面資源的運(yùn)行效率，降低航空公司航班延誤成本，優(yōu)化旅客出行體驗(yàn)，具有重要的實(shí)際意義.

停機(jī)位實(shí)時(shí)指派方案是在預(yù)指派方案的基礎(chǔ)上，針對停機(jī)位實(shí)時(shí)使用需求與原計(jì)劃的偏差進(jìn)行合理調(diào)整而得到的.Tang[1]以航班歷史數(shù)據(jù)作為延誤時(shí)間的參考，通過允許違反一些機(jī)位使用約束為航班重新指派停機(jī)位.Maharjan 等[2]在對航班延誤日特性研究的基礎(chǔ)上，構(gòu)建停機(jī)位實(shí)時(shí)指派模型.Guépet 等[3]構(gòu)建了停機(jī)位指派方案的混合整數(shù)規(guī)劃優(yōu)化模型，采用兩種啟發(fā)式算法對模型進(jìn)行求解.近年，國內(nèi)外學(xué)者在建模過程中考慮更多實(shí)際因素，在求解過程中應(yīng)用智能算法，以提高求解效率[4-5].也有學(xué)者從航班延誤的分布規(guī)律出發(fā)，針對旅客出行[6]，機(jī)位使用魯棒性[7]，相鄰航班之間的沖突概率[8]等，建立停機(jī)位實(shí)時(shí)指派模型.

已有研究成果考慮到航班延誤對機(jī)場停機(jī)位調(diào)度的影響，但未考慮延誤等級的劃分.單一化的機(jī)位調(diào)整策略難以適用于所有情境，且無法體現(xiàn)決策的公平性.因此，本文從對航班延誤等級的界定出發(fā)，在保證機(jī)坪安全運(yùn)行的前提下，針對輕度航班延誤狀態(tài)和中/重度航班延誤狀態(tài)，提出一種面向航班延誤的停機(jī)位實(shí)時(shí)指派多目標(biāo)優(yōu)化模型，為繁忙機(jī)場停機(jī)位調(diào)度提供決策依據(jù).

1 問題與建模

1.1 問題描述

航班延誤會(huì)對機(jī)場停機(jī)位資源的正常運(yùn)行造成擾動(dòng).主要體現(xiàn)在：同一機(jī)位的前一架航空器占用超時(shí)，后續(xù)航空器無法在預(yù)定時(shí)間正常使用機(jī)位.停機(jī)位實(shí)時(shí)指派任務(wù)是在停機(jī)位預(yù)指派的基礎(chǔ)上，對部分航班的使用機(jī)位進(jìn)行空間(機(jī)位)或時(shí)間(占用時(shí)段)上的合理調(diào)整，以化解機(jī)位占用沖突.

1.2 模型假設(shè)

(1)研究時(shí)段設(shè)為2 h，指派對象為時(shí)段內(nèi)的進(jìn)港航空器(包括進(jìn)港后又離港的航空器)；

(2)不考慮航空器拖曳，即航空器在停場過程中不可更換機(jī)位；

(3)為防止發(fā)生航空器無可用機(jī)位的情況，假設(shè)存在一個(gè)容量無限且滿足各類約束的虛擬遠(yuǎn)機(jī)位.

(4)不考慮航班取消和臨時(shí)更換航空器.

1.3 模型建立

首先對延誤等級進(jìn)行界定，設(shè)定差異化的指派目標(biāo).輕度延誤狀態(tài)下，為保證指派計(jì)劃的一致性，減少管制等工作人員的額外負(fù)擔(dān)，在化解沖突的前提下，盡可能減少對原指派計(jì)劃的變動(dòng)，即最小化因變更機(jī)位而增加旅客步行距離；中/重度延誤狀態(tài)下，需要在化解沖突的同時(shí)提升機(jī)坪運(yùn)行效率.機(jī)坪運(yùn)行效率可通過近機(jī)位的利用率衡量，即盡可能將航空器指派至近機(jī)位，故該目標(biāo)可抽象為最小化指派至遠(yuǎn)機(jī)位的旅客數(shù).面向航班延誤的停機(jī)位實(shí)時(shí)指派模型框架如圖1所示.

(1)目標(biāo)函數(shù).

(2)約束條件.

式中：A為運(yùn)行航空器集合；G為所有可用機(jī)位集合；P為機(jī)坪集合；pt為P中元素，代表第t個(gè)機(jī)坪，共有l(wèi)個(gè)機(jī)坪；i，j為航空器；k，m為機(jī)位；ci為航空器i執(zhí)行的離港航班的旅客數(shù)量；dk,m為旅客從停機(jī)位k更換至停機(jī)位m的步行距離；si、sk分別表示航空器i和機(jī)位k的大小等級；分別為航空器i的預(yù)計(jì)開始和預(yù)計(jì)結(jié)束占用機(jī)位時(shí)間；yk、zk,m、ui,m為0-1變量，分別描述機(jī)位是否為遠(yuǎn)機(jī)位、兩機(jī)位是否為相鄰機(jī)位、航空器i是否被預(yù)指派至機(jī)位m；xi,k為模型的決策變量，描述航空器i是否被指派至機(jī)位k；M為一個(gè)足夠大的值；Tb為最小時(shí)間間隔；vi,j表示航空器i與j發(fā)生沖突的概率，其值與兩航空器間的機(jī)位占用時(shí)間間隔Ti,j有關(guān)，λ為沖突概率系數(shù)，即

式(1)針對所有航班延誤狀態(tài)，表示最小化機(jī)坪沖突概率，機(jī)位沖突分為同一機(jī)位的先后航空器沖突和同一時(shí)刻相鄰機(jī)位的航空器沖突；式(2)針對輕度航班延誤狀態(tài)，表示最小化旅客變更登機(jī)口步行距離；式(3)針對中/重度航班延誤狀態(tài)，表示最小化指派至遠(yuǎn)機(jī)位的旅客數(shù)；式(4)為航班指派的唯一性約束，即一架航空器能且僅能被指派至一個(gè)停機(jī)位：式(5)為機(jī)位占用的唯一性約束，即同一個(gè)停機(jī)位在同一時(shí)刻只能被一架航空器占用；式(6)為類型匹配約束，即航空器的機(jī)型大小應(yīng)與停機(jī)位的大小相匹配；式(7)為同一機(jī)位的占用時(shí)間間隔約束.

2 算法設(shè)計(jì)

停機(jī)位實(shí)時(shí)指派問題是大規(guī)模整數(shù)規(guī)劃問題，存在多種可行性約束，求解難度較大.帶精英策略的非支配排序遺傳算法(NSGA-Ⅱ)在處理多目標(biāo)優(yōu)化問題時(shí)生成Pareto前沿，能為決策者提供良好的決策空間，因此，采用NSGA-Ⅱ進(jìn)行求解.具體步驟如下.

Step 1編碼.采用十進(jìn)制整數(shù)編碼方式，每個(gè)基因位置代表航空器被指派至的停機(jī)位編號(hào)，染色體長度等于研究時(shí)段內(nèi)進(jìn)港航空器數(shù)目.

Step 2初始化.依據(jù)停機(jī)位使用的約束條件，在可行范圍內(nèi)隨機(jī)生成規(guī)模為N的初始種群，作為第一代父代種群.

Step 3初代個(gè)體適應(yīng)度產(chǎn)生.對于生成的初始父代種群，計(jì)算每個(gè)個(gè)體在各個(gè)目標(biāo)函數(shù)上的值，并依據(jù)其間是否存在支配關(guān)系對所有個(gè)體進(jìn)行非支配分層與擁擠距離排序.擁擠距離計(jì)算方法為

式中：DC為解C的擁擠距離；r為問題中目標(biāo)函數(shù)的個(gè)數(shù)；分別表示解(C+1)與解(C-1)在第n個(gè)目標(biāo)函數(shù)On上的值.

擁擠距離可以比較各個(gè)解之間的相對優(yōu)劣，擁擠距離小的解易被其他解代替，故在進(jìn)行解的選擇時(shí)，優(yōu)先選擇擁擠距離較大的解.

Step 4交叉和變異操作.采用二元錦標(biāo)賽法從父代種群中選取N個(gè)個(gè)體，記為Wt，分別以概率pc、pm進(jìn)行兩點(diǎn)交叉、單點(diǎn)變異操作，產(chǎn)生N個(gè)新個(gè)體.生成新個(gè)體的過程中需要對個(gè)體按照式(4)～式(7)進(jìn)行可行性檢驗(yàn)，對于不滿足約束條件的個(gè)體，隨機(jī)產(chǎn)生新的可行方案進(jìn)行替換，新個(gè)體記為Qt.

Step 5選擇運(yùn)算和精英策略.對合并后規(guī)模為2N的種群Rt，計(jì)算每個(gè)個(gè)體的適應(yīng)度，并依據(jù)其間是否存在支配關(guān)系對所有個(gè)體進(jìn)行非支配分層，從高到低記為F1、F2、F3，以此類推.在層次內(nèi)部進(jìn)行擁擠距離排序，如圖2 所示.從第一層開始選取N個(gè)個(gè)體組成新的子代種群，記為Wt+1.

圖2 NSGA-Ⅱ的選擇運(yùn)算和精英策略Fig.2 Selection and elitist strategy in NSGA-Ⅱ

Step 6重復(fù)Step 3～Step 5，直到達(dá)到最大迭代次數(shù)MGEN.程序終止后，處于個(gè)體分層中第一層個(gè)體，即為所求解問題的非支配解.

3 仿真驗(yàn)證

3.1 仿真數(shù)據(jù)

機(jī)場運(yùn)行過程中國內(nèi)/國際航班機(jī)位相互獨(dú)立，選取其一研究即可.以北京首都機(jī)場T3航站樓的國內(nèi)停機(jī)位系統(tǒng)為研究對象，進(jìn)行仿真驗(yàn)證.選取停機(jī)坪P3、P4、P5，系統(tǒng)共85個(gè)近機(jī)位和42個(gè)遠(yuǎn)機(jī)位，如圖3所示.2018年3月4日的國內(nèi)航班運(yùn)行數(shù)據(jù)如表1所示，停機(jī)位信息如表2所示，其中，B為近機(jī)位，R為遠(yuǎn)機(jī)位.參考該機(jī)場航班延誤程度劃分規(guī)則，如表3 所示，該日07:00-09:00 時(shí)段航班延誤率17.8%，處于輕度航班延誤狀態(tài)；14:00-16:00 時(shí)段航班延誤率44.9%，處于重度航班延誤狀態(tài).取N=200 、MGEN=200 、pc=0.8 、pm=0.08 、λ=0.23，分別對兩種狀態(tài)下的停機(jī)位實(shí)時(shí)指派仿真結(jié)果進(jìn)行分析.

圖3 北京首都國際機(jī)場T3 航站樓停機(jī)位系統(tǒng)Fig.3 PEKT3 terminal gates system

表1 研究時(shí)段運(yùn)行航空器數(shù)據(jù)示例Table 1 Example of operating aircraft datain study period

表2 研究時(shí)段停機(jī)位數(shù)據(jù)示例Table 2 Example of gates data in study period

表3 機(jī)場航班延誤等級劃分規(guī)則Table 3 Airport flight delay classification rules

3.2 輕度航班延誤狀態(tài)下的實(shí)時(shí)指派結(jié)果分析

07:00-09:00進(jìn)港航空器共7架，仿真結(jié)果共得到8組Pareto解，如表4所示.由于受到輕度航班延誤影響，預(yù)指派方案中有兩處停機(jī)位(304、328)發(fā)生占用時(shí)間沖突，8組實(shí)時(shí)指派方案均將這兩架航空器的使用機(jī)位調(diào)整到鄰近的近機(jī)位，雖然增加了旅客步行距離，卻有效避免了機(jī)位占用沖突.

機(jī)坪沖突概率及旅客更換登機(jī)口需要步行距離如圖4 所示.可以發(fā)現(xiàn)，各組實(shí)時(shí)指派方案均互不支配，同一個(gè)停機(jī)位指派方案在兩個(gè)目標(biāo)上呈現(xiàn)相反的趨勢，較小的機(jī)坪沖突概率同時(shí)意味著旅客更換登機(jī)口步行距離的增加.方案中機(jī)坪沖突概率最低降至2.4×10-4(機(jī)位占用時(shí)間平均間隔36.2 min)，旅客更換登機(jī)口總步行距離最小為111 330 m，即平均每位旅客需多步行102.9 m到達(dá)調(diào)整后的登機(jī)口.

表4 07:00-09:00 輕度航班延誤狀態(tài)下的停機(jī)位實(shí)時(shí)指派方案Table 4 07:00-09:00 gate assignment scheme under slight flight delays

圖4 07:00-09:00 停機(jī)位實(shí)時(shí)指派方案的Pareto 解分布Fig.4 07:00-09:00 Pareto front distribution in gate reassignment scheme

3.3 重度航班延誤狀態(tài)下的實(shí)時(shí)指派結(jié)果分析

14:00-16:00 進(jìn)港航空器共38 架.算法終止后得到4 組Pareto 解，指派方案如表5 所示.觀察發(fā)現(xiàn)，38 架待指派航空器中，有5 架航空器的預(yù)指派方案在4 種方案中均未被改變，僅占13.2%，表明重度延誤狀態(tài)下的停機(jī)位實(shí)時(shí)指派策略傾向于調(diào)整大多數(shù)航空器的預(yù)設(shè)停機(jī)位，以旅客步行距離的增加換取近機(jī)位資源的高效利用，從而盡快化解航班延誤.研究時(shí)段內(nèi)共有6個(gè)停機(jī)位發(fā)生了不同程度的占用時(shí)間沖突，即302、309、313、314、402、520.在優(yōu)化結(jié)果中，4 種方案下停機(jī)位302、313、314 及520 均沒有被分配給任何航空器，避免了沖突發(fā)生，從側(cè)面反映預(yù)指派計(jì)劃缺乏魯棒性，易受延誤干擾.

表6 為停機(jī)位實(shí)時(shí)指派方案對比結(jié)果.由表6可知：預(yù)指派方案中有3 架航空器被指派至遠(yuǎn)機(jī)位，而4組方案均將它們調(diào)整至近機(jī)位，這是因?yàn)?架航空器執(zhí)行的進(jìn)港航班旅客人數(shù)相對較多；方案2同樣有3架航空器被指派至遠(yuǎn)機(jī)位，但旅客數(shù)從528人下降至421人，減少了20.3%，體現(xiàn)了本文算法的有效性.在避免機(jī)位沖突的前提下，方案1中沒有航空器被調(diào)整至遠(yuǎn)機(jī)位，機(jī)坪運(yùn)行效率最高，同時(shí)機(jī)坪沖突概率被控制在10.7×10-5(機(jī)位占用時(shí)間平均間隔39.6 min)；方案4的機(jī)坪沖突概率最低，為4.9×10-5(機(jī)位占用時(shí)間平均間隔43 min)，安全運(yùn)行水平最高，但有725名旅客被安排至遠(yuǎn)機(jī)位.停機(jī)位實(shí)時(shí)指派問題作為多目標(biāo)優(yōu)化問題，求解結(jié)果在目標(biāo)上存在差異，決策者可根據(jù)實(shí)際需求在選擇范圍內(nèi)做出合適的決策.

表6 14:00-16:00 停機(jī)位實(shí)時(shí)指派方案對比Table 6 14:00-16:00 contrast of gate assignment scheme

目標(biāo)函數(shù)平均值變化趨勢如圖5 所示.由圖5可知：初始條件下兩目標(biāo)均值都較高，隨著迭代的進(jìn)行，出現(xiàn)比較明顯的下降趨勢；第80 次迭代后，指派至遠(yuǎn)機(jī)位旅客數(shù)均值有小幅上升趨勢，這是因?yàn)楫?dāng)幾乎所有航班都被指派到近機(jī)位時(shí)，僅在近機(jī)位范圍內(nèi)調(diào)整難以使機(jī)坪沖突概率進(jìn)一步下降，此時(shí)需要將少數(shù)航空器指派至遠(yuǎn)機(jī)位以減小沖突；兩目標(biāo)函數(shù)均值在第130 次迭代后收斂，收斂狀態(tài)下，機(jī)坪沖突概率均值小于1×10-4，即機(jī)位占用時(shí)間平均間隔超過40 min.

表5 14:00-16:00 重度航班延誤狀態(tài)下的停機(jī)位實(shí)時(shí)指派方案(部分)Table 5 14:00-16:00 part of gate assignment scheme under severe flight delays

圖5 14:00-16:00 目標(biāo)函數(shù)平均值迭代曲線Fig.5 14:00-16:00 evolution of mean value of objective function

旅客更換登機(jī)口步行距離并非重度延誤狀態(tài)下的優(yōu)化目標(biāo)，相反地，為實(shí)現(xiàn)機(jī)坪運(yùn)行的整體優(yōu)化，需調(diào)整大量航空器的機(jī)位使用計(jì)劃，故旅客步行距離顯著增加.以方案1 為例，從機(jī)位分配公平性角度分析航空器機(jī)位變更距離的分布規(guī)律(僅針對近機(jī)位范圍)，如圖6(a)、(b)所示.航空器機(jī)位變更距離的均值為261.4 m，均值以下的分布較為密集，55%的航空器的機(jī)位變更距離小于200 m；均值以上的分布則較為均勻，僅有兩架航空器的變更機(jī)位距離超過800 m.整體分布趨勢表明，重度延誤狀態(tài)下的停機(jī)位實(shí)時(shí)指派方案具有較好的公平性.

圖6 14:00-16:00 航空器機(jī)位變更距離的分布規(guī)律Fig.6 14:00-16:00 distribution of gate shifting distance for aircraft

4 結(jié) 論

本文研究了航班延誤情境下的機(jī)場停機(jī)位實(shí)時(shí)指派問題.在對機(jī)場航班延誤等級進(jìn)行界定并考慮差異化指派目標(biāo)的基礎(chǔ)上，構(gòu)建了面向航班延誤的停機(jī)位實(shí)時(shí)指派多目標(biāo)優(yōu)化模型，并給出求解方法.結(jié)果表明：多目標(biāo)優(yōu)化中各目標(biāo)不會(huì)同時(shí)達(dá)到最優(yōu)，可根據(jù)實(shí)際情況選取指派方案；所提模型可成功化解延誤導(dǎo)致的機(jī)位占用沖突，并有效優(yōu)化旅客乘機(jī)體驗(yàn)和提升機(jī)坪運(yùn)行效率.下一步研究可考慮航班取消、航空器拖曳等機(jī)坪運(yùn)行過程中的實(shí)際情況，使模型更加細(xì)化.