大型樞紐機場停場過夜航班機位分配

鄧松武 王鵬 衛(wèi)東選

摘要：停場過夜航班機位分配問題是當前困擾我國大型樞紐機場機坪運行管理的一個主要問題。一是機位資源供給難以滿足停場過夜航班需求的快速增長，導致部分航班溢出，機位分配管理難度極大增加；二是我國大型機場近機位比例普遍較低，導致分配至遠機位的停場過夜航班比例較高，航班靠橋率明顯偏低。目前，針對機位分配問題的研究成果較豐富，但對于停場過夜航班研究鮮有涉及。本文以停場過夜航班機位分配為研究對象，采用虛擬航班與航班拖曳方式，建立了航班靠橋率和旅客過橋率最大化的0-1整數(shù)多目標規(guī)劃模型，通過簡化約束條件和縮緊約束界限，有效解決模型變量多、計算時間長等問題。最后，以白云機場運行數(shù)據(jù)進行試驗。結(jié)果表明，本文的模型算法使得航班靠橋率提升了31.25%，旅客過橋率提升了28.84%，驗證了本文所提模型與算法的顯著效果。

關鍵詞：大型樞紐機場；停場過夜航班；機位分配；虛擬航班；拖曳；0-1整數(shù)規(guī)劃

中圖分類號：V351文獻標識碼：ADOI：10.19452/j.issn1007-5453.2022.02.007

“十三五”時期，我國民航運輸產(chǎn)業(yè)發(fā)展迅速，運輸總量持續(xù)增長，主要航空公司機隊規(guī)模不斷擴大，但我國民航運輸運力主要分布在大型樞紐機場，集中特點明顯，導致了我國大型樞紐機場停場過夜航班總量大、過夜機位不足。為解決此問題，機場一般通過大規(guī)模擴建遠機位方式來滿足停場過夜航班停放需求。該方式增加了機位總數(shù)，但近機位數(shù)量并未增加，導致大量停場過夜航班需分配至遠機位，航班運行保障壓力陡增，旅客服務水平顯著降低。

目前，我國大型樞紐機場的機位總數(shù)雖多，但近機位比例較低。以白云機場為例，2020年該機場擁有的各類機位共275個，但近機位僅128個，占比46.55%。由于白云機場每晚停場過夜航班數(shù)處于270～280班之間，機位總保持滿負荷甚至超負荷運行狀態(tài)，即每晚有142～152個航班停需要停放在遠機位，部分超容航班甚至不得不停放在機坪滑行通道臨時機位。這種情況導致夜間進港航班和次日早上始發(fā)航班的保障面臨極大壓力，大量旅客需要靠擺渡車轉(zhuǎn)運實現(xiàn)登下機，便捷性、舒適性與效率均大打折扣。

為了提高停場過夜航班靠橋率，很多機場嘗試采用將部分遠機位停場過夜航班拖曳至近機位上客的運行方式。但是由于缺乏科學的模型與算法支持，在制訂每日的航班拖曳計劃時，工作人員很難快速合理地選定拖曳目標航班、目標機位、時間窗和間隔標準，運行效果較差。隨著民航業(yè)的不斷發(fā)展，航班量迅速增加，智能規(guī)劃技術[1]、排序優(yōu)化算法[2]等已列入復雜繁忙環(huán)境下的機場及航路飛機運行控制與調(diào)度問題研究中，因此，機位分配問題也是多年研究熱點。本文針對大型樞紐機場停場過夜航班機位分配問題展開研究，建立數(shù)學規(guī)劃模型并設計優(yōu)化算法進行求解，最后通過實例驗證其有效性。

1研究現(xiàn)狀

機場機位分配問題研究最早始于20世紀70年代，國內(nèi)外學者從機位利用不同階段、不同利益相關者視角等，研究了機位分配問題的建模及求解等問題，如機場機位需求問題[3]、經(jīng)典的靜態(tài)機位分配問題[4]等。隨著民航業(yè)的不斷發(fā)展，航班量迅速增加，機場運行復雜化，部分機場尤其是繁忙機場機位資源難以應付高峰時段航班需求，Ding等[5]較早地研究了資源受限的機位分配模型及啟發(fā)式算法。由于航空運輸業(yè)特點，航班易受天氣、容量等因素影響而需要復雜氣象下航班簽派[6]等，機位分配方式的魯棒性[7]，即抗干擾能力也得到了較多的研究。近年來，機位實時動態(tài)分配[8]相關研究得到重視，如參考文獻[9]研究了航班時刻發(fā)生擾動時的機位再分配問題。航班機位分配與機場、航空公司的運營效益、效率，以及旅客方便性息息相關，如參考文獻[5]等以最小化旅客行走距離為目標，以提升旅客體驗滿意度，參考文獻[10]考慮了機位分配時航空公司利益，參考文獻[11]則從機場運營角度出發(fā)進行研究。

機場停機位分配的研究對象是航班與機位，該問題是典型的NP難問題，研究者們設計了數(shù)學規(guī)劃法[11]、啟發(fā)式算法[5]、禁忌搜索算法[9]、模擬退火算法[12]、遺傳算法[4，13]等，對相關模型進行優(yōu)化求解。

國內(nèi)外專家學者對機位分配問題進行了大量的研究，研究成果豐富，但仍然存在一些問題，如優(yōu)化目標單一，沒有考慮到機位分配過程要考慮運行效率、旅客服務和資源管理等方面需求；約束條件考慮不夠周全，沒有考慮機場運行環(huán)境限制；理論研究成果無法應用于實際，機位分配模型算法的研究成果雖多，但機場實際工作應用中實現(xiàn)較少，我國機場機位分配系統(tǒng)大多數(shù)仍然停留在半人工操作狀態(tài)。研究者們對于機場中航班推出與拖曳等已有相關研究，如拖曳操作的效率[14]、減少碳排放的航班動態(tài)推出[15]等，但對拖曳操作下的停場過夜航班機位分配問題，目前鮮有相關研究涉及。事實上，樞紐機場的停場過夜航班機位分配是一天中機位分配的結(jié)束狀態(tài)和初始狀態(tài)，并與機場出發(fā)早高峰直接相關，是機位分配問題的重要組成部分。尤其在當前我國大型樞紐機場運行中，近機位數(shù)量偏低、大量旅客需要擺渡車運轉(zhuǎn)、航班地面保障壓力大的情況下，研究航班拖曳操作下的過夜航班機位分配顯得尤為重要。

2問題描述

停場過夜航班機位分配問題研究需考慮兩方面，一是如何對前一日的停場過夜航班機位進行優(yōu)化分配，二是如何通過航班拖曳方式令其靠橋來提高航班靠橋率和旅客過橋率。事實上，兩方面相互關聯(lián)，即在前一日停場過夜航班機位配置合理優(yōu)化，是航班拖曳靠橋配對的前提條件。

在實際機位運行管理中，有三種航班拖曳方式。方式1：航班抵達后，先停放在近機位，進港保障作業(yè)結(jié)束后（例如作業(yè)時間為60min）再拖曳至遠機位；方式2：航班抵達后，分配至遠機位完成進港作業(yè)，第二天早上離港前（120min）拖曳至近機位完成離港作業(yè)；方式3：航班抵達后，先在近機位完成進港保障，然后拖曳至遠機位過夜，離港前120min拖曳至近機位進行離港作業(yè)。拖曳方式選擇與機位占用情況、航班經(jīng)停時間、航空公司運營區(qū)域以及場面飛機流量有關。

旅客過橋率是指旅客通過廊橋上下飛機的百分比，是體現(xiàn)旅客服務水平的關鍵指標。旅客過橋率雖然與航班靠橋率有較大關聯(lián)，但也有明顯的區(qū)別，主要在于不同航班座位數(shù)以及實際載客人數(shù)的差異。航班靠橋率相同時，大型機和旅客人數(shù)多的航班靠橋越多，旅客過橋率越高，服務水平越高。

3.2約束條件

3.2.1時間間隔約束

4求解方法

上文中將過夜航班機位分配建模為多目標的0-1整數(shù)優(yōu)化模型，需要將多目標轉(zhuǎn)化為單目標方可采用數(shù)學規(guī)劃軟件求解。為了縮短求解時間，提高效率，滿足機位分配實際工作要求，本節(jié)基于航班對機位在時間維上的獨占性特點，分析機位沖突的航班集合，對約束條件進行簡化處理。

4.1多目標融合

常用的多目標融合方法有三種：（1）因子分析法和主成分分析法，利用方差解釋率分配目標的權重，未考慮實際的業(yè)務邏輯和重要程度關系；（2）熵值法，利用目標數(shù)據(jù)的熵值信息（即信息的不確定性）來衡量目標的權重大??；（3）層次分析法（AHP），在業(yè)務邏輯上根據(jù)目標重要性對目標項進行專家打分，以確定目標的權重系數(shù)。

本文采用層次分析法進行多目標融合求解。選取三位業(yè)務專家，從機場總體運行效率、旅客服務、運行安全和資源利用率等維度進行綜合評價打分，確定航班靠橋率和旅客過橋率的權重系數(shù)分別為70%和30%，經(jīng)過一致性檢驗后將權重系數(shù)應用在模型的目標融合中。

4.2約束條件簡化

目前，整數(shù)線性規(guī)劃的主流求解方法為分支定界法。該方法的思路在于，先用線性規(guī)劃求解松弛問題，然后在松弛問題解的附近尋找最優(yōu)整數(shù)解。對于實數(shù)線性規(guī)劃問題，內(nèi)點法可以在更短的時間內(nèi)求得最優(yōu)解，并且在實踐中單純形算法也能快速得到最優(yōu)解。模型求解中主要考慮提升線性規(guī)劃速度和降低尋找整數(shù)解難度兩個方面。

4.2.1簡化原理

在機位分配模型求解計算中，由于待分配的航班和機位數(shù)量較大，加上約束條件的限制，求解過程的計算量會變得非常龐大。為了降低計算的復雜性，就需要對約束條件進行簡化處理。簡化原理為：如果約束1與約束2在整數(shù)規(guī)劃模型下等價，但是在線性規(guī)劃模型下約束1可以推導出約束2，而約束2不能推出約束1，則約束2比約束1更緊；例如有a + b≤1， a + c≤1， b + c≤1，當a、b、c都是0-1整數(shù)時，可得到a + b + c≤1，從而約束條件由3條簡化為1條，模型求解時計算量明顯變少，計算效率顯著提升。本文基于以上原理，對約束進行簡化。

4.2.2簡化方法

這個集合其實已經(jīng)覆蓋了9：50的機位沖突集合。因此，在算法中保留9：30的強約束集合，而刪除9：50的弱集合，從而達到約束條件簡化的目的。

5模型驗證

5.1數(shù)據(jù)來源

為了驗證模型的運算效率和求解效果，選取在白云機場東三指廊機坪區(qū)及對應的東航和九元航空2020年12月14—15日的停場過夜和始發(fā)航班為試驗對象。由于機場運營的航空公司采取分區(qū)運作方式，對于其他機坪片區(qū)，研究方法相同。基礎數(shù)據(jù)包括：（1）24對停場過夜航班，其中東航13對，九元航11對；（2）按照航班拖曳方案，本文采用方式3，將24對、48個停場過夜航班轉(zhuǎn)換為72對、144個虛擬航班；（3）在東航和九元航運行區(qū)域內(nèi)，擁有24個可分配停機位，其中，近機位10個，組合方式為：2個C類、6個D類、1個E類和1個F類；遠機位14個，方式為：5個C類、5個D類、3個E類和1個F類（機位備注：C類容量最大可以停放A321neo；D類容量最大可以停放波音767-300er；E類容量最大可以停放波音777-300er；F類容量最大可以停放A380-800）。

5.2參數(shù)設定

基于32G內(nèi)存的PC電腦、Win10操作系統(tǒng)，使用美國Gurobi Optimization公司開發(fā)新一代大規(guī)模優(yōu)化求解器Gurobi9.1.1進行求解。該求解器計算效率高，接口豐富，在生產(chǎn)制造、金融、保險、交通、服務等領域有廣泛應用。模型相關參數(shù)設置如下：（1）Method=0，表示使用單純形算法求解線性規(guī)劃問題。雖然內(nèi)點法在復雜度上更好，但是在實踐中本問題使用單純形速度更快。根據(jù)實際的運行經(jīng)驗，單純形算法使用的內(nèi)存少于內(nèi)點法。（2）Heuristics=1，在線性規(guī)劃解的附近盡可能多地嘗試尋找整數(shù)解。（3）MIPFocus=1，主要精力放在提升整數(shù)解上，而不是求解更緊的上界。（4）CutPasses=0，不使用割。（5）Cuts=3，該參數(shù)使用最強的割算法，有利于確定更精確的上界。

5.3結(jié)果與分析

針對以上驗證數(shù)據(jù)，采用本文拖曳優(yōu)化算法的分配結(jié)果如圖3所示。

從航班靠橋率、旅客過橋率、計算時間（計算效率）、拖曳次數(shù)方面將白云機場現(xiàn)有機位分配系統(tǒng)算法和本文優(yōu)化算法得到的分配方案進行對比，結(jié)果見表1。

從對比分析結(jié)果來看，在相同航班和相同機位資源條件下，本文拖曳優(yōu)化算法采用的航班拖曳優(yōu)化方式，增加了15個拖曳航班靠橋，航班靠橋率提高了31.25%；旅客過橋率提高了28.84%，擺渡車使用減少25輛。由于采用航班拖曳方式，雖增加了拖曳次數(shù)，但航班靠橋率大大提高，旅客擺渡車使用數(shù)量明顯減少，旅客方便性得以提高，機場其他地面保障作業(yè)也更好地得到保障。算法求解中本文采用了簡化約束條件方式，計算時間減少115s，計算效率大幅提升。試驗效果非常顯著。

6結(jié)束語

本文提出一種基于虛擬航班與拖曳操作的停場過夜航班機位分配優(yōu)化模型，將一個真實的航班對轉(zhuǎn)換為兩個或三個虛擬航班對，并允許對航班進行拖曳操作，以最大化航班靠橋率和旅客過橋率，提高航班地面作業(yè)保障能力和旅客方便性。在模型求解中，采用多目標融合和簡化約束條件的處理方式，提高了模型求解效率；最后，通過白云機場的真實數(shù)據(jù)進行模型驗證。驗證結(jié)果表明，優(yōu)化模型顯著地提升了航班靠橋率和旅客過橋率，有效地減少了場面擺渡車輛，增強了旅客的滿意度。因此，該模型可以推廣應用到大型樞紐機場機位分配系統(tǒng)中，用于停場過夜航班的機位分配工作中實現(xiàn)系統(tǒng)自動生成可執(zhí)行的航班拖曳計劃功能，有助于機位分配工作人員提高工作效率。

參考文獻

[1]池懌，余磊.民用飛機航路智能規(guī)劃技術研究[J].航空科學技術， 2020， 31（10）：49-53. Chi Yi， Yu Lei. Research on civil flight intelligent trajectory planning technology[J]. Aeronautical Science & Technology， 2020， 31（10）：49-53.（in Chinese）

[2]徐肖豪，吳青，黃寶軍.多跑道航班排序的改進蛙跳算法研究[J].航空科學技術，2014，25（2）：6-11. Xu Xiaohao， Wu Qing， Huang Baojun. Improved shuffled frog leaping algorithm research for multiple runway flight schedule[J]. Aeronautical Science & Technology， 2014，25（2）：6-11.（in Chinese）

[3]Steuart G N. Gate position requirements at metropolitan airports[J]. Transportation Science，1974，8（2）：169-189.

[4]Bolat A. Models and a genetic algorithm for static aircraft-gate assignment problem[J]. Journal of the Operational Research Society，2001，52（10）：1107-1120.

[5]Ding H，Lim A，Rodrigues B，et al. New heuristics for overconstrained flight to gate assignments[J]. Journal of the Operational Research Society，2004，55（7）：760-768.

[6]張序，羅鳳娥，周川，等.濃霧天氣背景下昆明長水機場簽派放行研究[J].航空科學技術， 2019， 30（10）： 50-55. Zhang Xu， Luo Feng’e， Zhou Chuan， et al. Research on the dispatch work at Kunming Changshui Airport under the heavy fog weather[J]. Aeronautical Science & Technology， 2019， 30（10）： 50-55.（in Chinese）

[7]Narciso M E，Piera M A. Robust gate assignment procedures from an airport management perspective[J]. Omega，2015，50：82-95.

[8]Skorupski J，Arów P. Dynamic management of aircraft stand allocation[J]. Journal of Air Transport Management，2021，90：101964.

[9]衛(wèi)東選，劉長有.機場停機位再分配問題[J].南京航空航天大學學報，2009，41（2）： 257-261. Wei Dongxuan， Liu Changyou. Airport gate reassignment problem[J]. Journal of Nanjing University of Aeronautics & Astronautics，2009，41（2）：257-261.（in Chinese）

[10]Ching H T，Wei C W. Airport gate assignments for airlinespecific gates[J]. Journal of Air Transport Management，2013，30：10-16.

[11]王巖華，朱金福，朱博，等.繁忙機場機位分配的混合集合規(guī)劃方法[J].武漢理工大學學報（信息與管理工程版）， 2015， 37（4）： 427-431. Wang Yanhua，Zhu Jinfu，Zhu Bo， et al. Method of mixed set programming for gate assignment in busy airports[J]. Journal of WUT（Information & Management Engineering）， 2015，37（4）：427-431.（in Chinese）

[12]Drexl A，Nikulin Y. Multicriteria airport gate assignment and Pareto simulated annealing[J]. IIE Transactions，2008，40（4）：385-397.

[13]徐思敏，姜雨，王歡，等.基于NSGA-II的停機位多目標指派建模與仿真[J].南京航空航天大學學報，2018，50（6）：823-828. Xu Simin， Jiang Yu， Wang Huan， et al. Multi-objective gate assignment modeling and simula tion based on NSGA-II[J]. Journal of Nanjing University of Aeronautics & Astronautics， 2018， 50（6）：823-828.（in Chinese）

[14]Du J Y，Brunner J O，Kolisch R. Planning towing processes at airports more efficiently[J]. Transportation Research，Part E. Logistics and Transportation Review，2014，70：293-304.

[15]Lian G，Zhang Y P，Xing Z W，et al. A new dynamic pushback control method for reducing fuel-burn costs：Using predicted taxi-out time[J]. Chinese Journal of Aeronautics，2019，32（3）：660-673.

Gate Assignment for Overnight Flights in Large Hub Airport

Deng Songwu1，Wang Peng1，Wei Dongxuan2

1. Guangzhou Baiyun International Airport Co.，Ltd.，Guangzhou 510470，China 2. Chang’an University，Xi’an 710064，China

Abstract： The gate assignment for overnight flights is a major problem that troubles large hub airports in China. On the one hand， the supply of contact-gates can not meet the rapid growth of parking demand for overnight flights， resulting in gate overload， which greatly increases the difficulty of gate assignment. On the other hand， due to the low proportion of contact-gates in large airports in China， a large number of overnight flights park in the remote-gates. At present， there are a lot of research on the problem of gate assignment in the academic field， but the research on the above issues is rarely involved. In this paper， the optimization problem of allocation for overnight flights is taken as the research object， and using virtual flight and flight towing， this paper establish a zero-one integer multi-objective programming model of ratemaximize for flights parking in the contact-gates and passengers boarding on air bridge. The simplified constrained conditions and the tightening constrained boundary methods are adopted to solve the practical problems of multivariables and calculation time. Finally， Baiyun Airport is taken as a case to verify that the algorithm proposed in this paper has a significant effectiveness， experiments show that the model algorithm of this paper is used to improve the flights parking in the contact-gates rate by 31.25% and passengers boarding on air bridge rate by 28.84%.

Key Words：large hub airport；overnight flights；gate assignment；virtual flight；towing；zero-one integer programming

Received： 2021-08-09；Revised： 2021-09-09；Accepted： 2021-10-16