面向航班延誤的停機位實時指派優化模型

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

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

0 引 言

民航航班量的快速增長與機場資源的瓶頸使航班延誤現象成為常態，對機場場面資源的正常運行造成不利影響，其中，停機位資源對延誤尤為敏感.延誤發生后，停機位預指派方案受到擾動，若不能及時調整方案，會使延誤進一步傳播和擴散.因此，面向航班延誤的停機位實時指派對提升機場場面資源的運行效率，降低航空公司航班延誤成本，優化旅客出行體驗，具有重要的實際意義.

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

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

1 問題與建模

1.1 問題描述

航班延誤會對機場停機位資源的正常運行造成擾動.主要體現在：同一機位的前一架航空器占用超時，后續航空器無法在預定時間正常使用機位.停機位實時指派任務是在停機位預指派的基礎上，對部分航班的使用機位進行空間(機位)或時間(占用時段)上的合理調整，以化解機位占用沖突.

1.2 模型假設

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

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

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

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

1.3 模型建立

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

(1)目標函數.

(2)約束條件.

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

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

2 算法設計

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

Step 1編碼.采用十進制整數編碼方式，每個基因位置代表航空器被指派至的停機位編號，染色體長度等于研究時段內進港航空器數目.

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

Step 3初代個體適應度產生.對于生成的初始父代種群，計算每個個體在各個目標函數上的值，并依據其間是否存在支配關系對所有個體進行非支配分層與擁擠距離排序.擁擠距離計算方法為

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

擁擠距離可以比較各個解之間的相對優劣，擁擠距離小的解易被其他解代替，故在進行解的選擇時，優先選擇擁擠距離較大的解.

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

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

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

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

3 仿真驗證

3.1 仿真數據

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

圖3 北京首都國際機場T3 航站樓停機位系統Fig.3 PEKT3 terminal gates system

表1 研究時段運行航空器數據示例Table 1 Example of operating aircraft datain study period

表2 研究時段停機位數據示例Table 2 Example of gates data in study period

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

3.2 輕度航班延誤狀態下的實時指派結果分析

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

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

表4 07:00-09:00 輕度航班延誤狀態下的停機位實時指派方案Table 4 07:00-09:00 gate assignment scheme under slight flight delays

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

3.3 重度航班延誤狀態下的實時指派結果分析

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

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

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

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

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

圖5 14:00-16:00 目標函數平均值迭代曲線Fig.5 14:00-16:00 evolution of mean value of objective function

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

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

4 結 論

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