邓松武 王鹏 卫东选

摘要：停场过夜航班机位分配问题是当前困扰我国大型枢纽机场机坪运行管理的一个主要问题。一是机位资源供给难以满足停场过夜航班需求的快速增长，导致部分航班溢出，机位分配管理难度极大增加；二是我国大型机场近机位比例普遍较低，导致分配至远机位的停场过夜航班比例较高，航班靠桥率明显偏低。目前，针对机位分配问题的研究成果较丰富，但对于停场过夜航班研究鲜有涉及。本文以停场过夜航班机位分配为研究对象，采用虚拟航班与航班拖曳方式，建立了航班靠桥率和旅客过桥率最大化的0-1整数多目标规划模型，通过简化约束条件和缩紧约束界限，有效解决模型变量多、计算时间长等问题。最后，以白云机场运行数据进行试验。结果表明，本文的模型算法使得航班靠桥率提升了31.25%，旅客过桥率提升了28.84%，验证了本文所提模型与算法的显著效果。

关键词：大型枢纽机场；停场过夜航班；机位分配；虚拟航班；拖曳；0-1整数规划

中图分类号：V351文献标识码：ADOI：10.19452/j.issn1007-5453.2022.02.007

“十三五”时期，我国民航运输产业发展迅速，运输总量持续增长，主要航空公司机队规模不断扩大，但我国民航运输运力主要分布在大型枢纽机场，集中特点明显，导致了我国大型樞纽机场停场过夜航班总量大、过夜机位不足。为解决此问题，机场一般通过大规模扩建远机位方式来满足停场过夜航班停放需求。该方式增加了机位总数，但近机位数量并未增加，导致大量停场过夜航班需分配至远机位，航班运行保障压力陡增，旅客服务水平显著降低。

目前，我国大型枢纽机场的机位总数虽多，但近机位比例较低。以白云机场为例，2020年该机场拥有的各类机位共275个，但近机位仅128个，占比46.55%。由于白云机场每晚停场过夜航班数处于270～280班之间，机位总保持满负荷甚至超负荷运行状态，即每晚有142～152个航班停需要停放在远机位，部分超容航班甚至不得不停放在机坪滑行通道临时机位。这种情况导致夜间进港航班和次日早上始发航班的保障面临极大压力，大量旅客需要靠摆渡车转运实现登下机，便捷性、舒适性与效率均大打折扣。

为了提高停场过夜航班靠桥率，很多机场尝试采用将部分远机位停场过夜航班拖曳至近机位上客的运行方式。但是由于缺乏科学的模型与算法支持，在制订每日的航班拖曳计划时，工作人员很难快速合理地选定拖曳目标航班、目标机位、时间窗和间隔标准，运行效果较差。随着民航业的不断发展，航班量迅速增加，智能规划技术[1]、排序优化算法[2]等已列入复杂繁忙环境下的机场及航路飞机运行控制与调度问题研究中，因此，机位分配问题也是多年研究热点。本文针对大型枢纽机场停场过夜航班机位分配问题展开研究，建立数学规划模型并设计优化算法进行求解，最后通过实例验证其有效性。

1研究现状

机场机位分配问题研究最早始于20世纪70年代，国内外学者从机位利用不同阶段、不同利益相关者视角等，研究了机位分配问题的建模及求解等问题，如机场机位需求问题[3]、经典的静态机位分配问题[4]等。随着民航业的不断发展，航班量迅速增加，机场运行复杂化，部分机场尤其是繁忙机场机位资源难以应付高峰时段航班需求，Ding等[5]较早地研究了资源受限的机位分配模型及启发式算法。由于航空运输业特点，航班易受天气、容量等因素影响而需要复杂气象下航班签派[6]等，机位分配方式的鲁棒性[7]，即抗干扰能力也得到了较多的研究。近年来，机位实时动态分配[8]相关研究得到重视，如参考文献[9]研究了航班时刻发生扰动时的机位再分配问题。航班机位分配与机场、航空公司的运营效益、效率，以及旅客方便性息息相关，如参考文献[5]等以最小化旅客行走距离为目标，以提升旅客体验满意度，参考文献[10]考虑了机位分配时航空公司利益，参考文献[11]则从机场运营角度出发进行研究。

机场停机位分配的研究对象是航班与机位，该问题是典型的NP难问题，研究者们设计了数学规划法[11]、启发式算法[5]、禁忌搜索算法[9]、模拟退火算法[12]、遗传算法[4，13]等，对相关模型进行优化求解。

国内外专家学者对机位分配问题进行了大量的研究，研究成果丰富，但仍然存在一些问题，如优化目标单一，没有考虑到机位分配过程要考虑运行效率、旅客服务和资源管理等方面需求；约束条件考虑不够周全，没有考虑机场运行环境限制；理论研究成果无法应用于实际，机位分配模型算法的研究成果虽多，但机场实际工作应用中实现较少，我国机场机位分配系统大多数仍然停留在半人工操作状态。研究者们对于机场中航班推出与拖曳等已有相关研究，如拖曳操作的效率[14]、减少碳排放的航班动态推出[15]等，但对拖曳操作下的停场过夜航班机位分配问题，目前鲜有相关研究涉及。事实上，枢纽机场的停场过夜航班机位分配是一天中机位分配的结束状态和初始状态，并与机场出发早高峰直接相关，是机位分配问题的重要组成部分。尤其在当前我国大型枢纽机场运行中，近机位数量偏低、大量旅客需要摆渡车运转、航班地面保障压力大的情况下，研究航班拖曳操作下的过夜航班机位分配显得尤为重要。

2问题描述

停场过夜航班机位分配问题研究需考虑两方面，一是如何对前一日的停场过夜航班机位进行优化分配，二是如何通过航班拖曳方式令其靠桥来提高航班靠桥率和旅客过桥率。事实上，两方面相互关联，即在前一日停场过夜航班机位配置合理优化，是航班拖曳靠桥配对的前提条件。

在实际机位运行管理中，有三种航班拖曳方式。方式1：航班抵达后，先停放在近机位，进港保障作业结束后（例如作业时间为60min）再拖曳至远机位；方式2：航班抵达后，分配至远机位完成进港作业，第二天早上离港前（120min）拖曳至近机位完成离港作业；方式3：航班抵达后，先在近机位完成进港保障，然后拖曳至远机位过夜，离港前120min拖曳至近机位进行离港作业。拖曳方式选择与机位占用情况、航班经停时间、航空公司运营区域以及场面飞机流量有关。

旅客过桥率是指旅客通过廊桥上下飞机的百分比，是体现旅客服务水平的关键指标。旅客过桥率虽然与航班靠桥率有较大关联，但也有明显的区别，主要在于不同航班座位数以及实际载客人数的差异。航班靠桥率相同时，大型机和旅客人数多的航班靠桥越多，旅客过桥率越高，服务水平越高。

3.2约束条件

3.2.1时间间隔约束

4求解方法

上文中将过夜航班机位分配建模为多目标的0-1整数优化模型，需要将多目标转化为单目标方可采用数学规划软件求解。为了缩短求解时间，提高效率，满足机位分配实际工作要求，本节基于航班对机位在时间维上的独占性特点，分析机位冲突的航班集合，對约束条件进行简化处理。

4.1多目标融合

常用的多目标融合方法有三种：（1）因子分析法和主成分分析法，利用方差解释率分配目标的权重，未考虑实际的业务逻辑和重要程度关系；（2）熵值法，利用目标数据的熵值信息（即信息的不确定性）来衡量目标的权重大小；（3）层次分析法（AHP），在业务逻辑上根据目标重要性对目标项进行专家打分，以确定目标的权重系数。

本文采用层次分析法进行多目标融合求解。选取三位业务专家，从机场总体运行效率、旅客服务、运行安全和资源利用率等维度进行综合评价打分，确定航班靠桥率和旅客过桥率的权重系数分别为70%和30%，经过一致性检验后将权重系数应用在模型的目标融合中。

4.2约束条件简化

目前，整数线性规划的主流求解方法为分支定界法。该方法的思路在于，先用线性规划求解松弛问题，然后在松弛问题解的附近寻找最优整数解。对于实数线性规划问题，内点法可以在更短的时间内求得最优解，并且在实践中单纯形算法也能快速得到最优解。模型求解中主要考虑提升线性规划速度和降低寻找整数解难度两个方面。

4.2.1简化原理

在机位分配模型求解计算中，由于待分配的航班和机位数量较大，加上约束条件的限制，求解过程的计算量会变得非常庞大。为了降低计算的复杂性，就需要对约束条件进行简化处理。简化原理为：如果约束1与约束2在整数规划模型下等价，但是在线性规划模型下约束1可以推导出约束2，而约束2不能推出约束1，则约束2比约束1更紧；例如有a + b≤1， a + c≤1， b + c≤1，当a、b、c都是0-1整数时，可得到a + b + c≤1，从而约束条件由3条简化为1条，模型求解时计算量明显变少，计算效率显著提升。本文基于以上原理，对约束进行简化。

4.2.2简化方法

这个集合其实已经覆盖了9：50的机位冲突集合。因此，在算法中保留9：30的强约束集合，而删除9：50的弱集合，从而达到约束条件简化的目的。

5模型验证

5.1数据来源

为了验证模型的运算效率和求解效果，选取在白云机场东三指廊机坪区及对应的东航和九元航空2020年12月14—15日的停场过夜和始发航班为试验对象。由于机场运营的航空公司采取分区运作方式，对于其他机坪片区，研究方法相同。基础数据包括：（1）24对停场过夜航班，其中东航13对，九元航11对；（2）按照航班拖曳方案，本文采用方式3，将24对、48个停场过夜航班转换为72对、144个虚拟航班；（3）在东航和九元航运行区域内，拥有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参数设定

基于32G内存的PC电脑、Win10操作系统，使用美国Gurobi Optimization公司开发新一代大规模优化求解器Gurobi9.1.1进行求解。该求解器计算效率高，接口丰富，在生产制造、金融、保险、交通、服务等领域有广泛应用。模型相关参数设置如下：（1）Method=0，表示使用单纯形算法求解线性规划问题。虽然内点法在复杂度上更好，但是在实践中本问题使用单纯形速度更快。根据实际的运行经验，单纯形算法使用的内存少于内点法。（2）Heuristics=1，在线性规划解的附近尽可能多地尝试寻找整数解。（3）MIPFocus=1，主要精力放在提升整数解上，而不是求解更紧的上界。（4）CutPasses=0，不使用割。（5）Cuts=3，该参数使用最强的割算法，有利于确定更精确的上界。

5.3结果与分析

针对以上验证数据，采用本文拖曳优化算法的分配结果如图3所示。

从航班靠桥率、旅客过桥率、计算时间（计算效率）、拖曳次数方面将白云机场现有机位分配系统算法和本文优化算法得到的分配方案进行对比，结果见表1。

从对比分析结果来看，在相同航班和相同机位资源条件下，本文拖曳优化算法采用的航班拖曳优化方式，增加了15个拖曳航班靠桥，航班靠桥率提高了31.25%；旅客过桥率提高了28.84%，摆渡车使用减少25辆。由于采用航班拖曳方式，虽增加了拖曳次数，但航班靠桥率大大提高，旅客摆渡车使用数量明显减少，旅客方便性得以提高，机场其他地面保障作业也更好地得到保障。算法求解中本文采用了简化约束条件方式，计算时间减少115s，计算效率大幅提升。试验效果非常显著。

6结束语

本文提出一种基于虚拟航班与拖曳操作的停场过夜航班机位分配优化模型，将一个真实的航班对转换为两个或三个虚拟航班对，并允许对航班进行拖曳操作，以最大化航班靠桥率和旅客过桥率，提高航班地面作业保障能力和旅客方便性。在模型求解中，采用多目标融合和简化约束条件的处理方式，提高了模型求解效率；最后，通过白云机场的真实数据进行模型验证。验证结果表明，优化模型显著地提升了航班靠桥率和旅客过桥率，有效地减少了场面摆渡车辆，增强了旅客的满意度。因此，该模型可以推广应用到大型枢纽机场机位分配系统中，用于停场过夜航班的机位分配工作中实现系统自动生成可执行的航班拖曳计划功能，有助于机位分配工作人员提高工作效率。

参考文献

[1]池怿，余磊.民用飞机航路智能规划技术研究[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]衛东选，刘长有.机场停机位再分配问题[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]王巖华，朱金福，朱博，等.繁忙机场机位分配的混合集合规划方法[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