1、第 55 卷第 2 期2023 年 4 月Vol.55 No.2Apr.2023南 京 航 空 航 天 大 学 学 报Journal of Nanjing University of Aeronautics&Astronautics基于改进 NSGA-的停机位预分配优化刘禹汐1,2，刘继新1,2，田文1,2（1.南京航空航天大学民航学院，南京 211106；2.国家空管飞行流量管理技术重点实验室，南京 211106）摘要：随着民航运输业的发展，航班密度不断增加，大型机场的近机位资源紧张问题日益突出，降低了航班保障效率。为了探索大型枢纽机场停机位预分配问题综合有效的解决方法，从航空公司、机场和旅
2、客的实际情况出发，建立多目标停机位分配优化模型，并设计了改进的带精英策略的非支配排序遗传算法（Nondominated sorting genetic algorithms，NSGA）对模型进行求解，得到一组 Pareto前沿解。在交叉和变异操作阶段，对种群个体以指数形式自适应地调整交叉率和变异率，以此提高算法的收敛速度和优良解的多样性。实例验证结果表明，该模型和改进算法相较于人工分配和传统 NSGA算法对停机位指派的优化结果更为突出，尤其在靠桥率和被使用的停机位数量方面；同时利用性能评价指标对比两种算法，发现改进型 NSGA算法更适合停机位预分配问题的求解。关键词：停机位预分配；多目标优化；
3、改进型 NSGA；Pareto前沿解；性能评价指标中图分类号：V351.11 文献标志码：A 文章编号：10052615（2023）02032910Optimization of Gate Pre-allocation Based on Improved NSGA-LIU Yuxi1，2，LIU Jixin1，2，TIAN Wen1，2（1.College of Civil Aviation，Nanjing University of Aeronautics&Astronautics，Nanjing 211106，China；2.National Key Laboratory of Air T
4、raffic Flow Management，Nanjing 211106，China）Abstract:With the development of the civil aviation transportation industry，the density of flights is increasing，and the shortage of near-airport resources in large airports has become increasingly prominent.The lack of nearairport resources reduces the ef
5、ficiency of flight guarantees.In order to develop a comprehensive and effective solution to the problem of gate preallocation in large hub airports，based on the actual situation of airlines，airports and passengers，a multiobjective parking space allocation optimization model is established，and an imp
6、roved nondominated sorting genetic algorithm（NSGA）with an elite strategy is designed to solve the model.The Pareto frontier solution is obtained.In the crossover and mutation operation stage，the crossover rate and the mutation rate are adaptively adjusted for the population individuals in an exponen
7、tial form，so as to improve the convergence speed of the algorithm and the diversity of excellent solutions.The example verification results show that the optimization results of the model and the improved algorithm are more prominent than the manual allocation and the traditional NSGA algorithm for
8、parking space assignment，especially in terms of the bridge rate and the number of used parking stands.At the same time，the performance evaluation index is used to compare the two algorithms，and found that the improved NSGA algorithm is more suitable for solving the gate preallocation problem.Key wor
9、ds:gate preallocation；multiobjective optimization；improved NSGA；Pareto frontier solution；performance evaluation indicatorsDOI：10.16356/j.10052615.2023.02.019基金项目：国家重点研发计划（2021YFB1600500）；国家自然科学基金（71971112）；南京航空航天大学科研与实践创新计划（xcxjh20220709）。收稿日期：20220729；修订日期：20221220通信作者：刘继新，男，副教授，E-mail：。引用格式：刘禹汐，刘继
10、新，田文.基于改进 NSGA的停机位预分配优化 J.南京航空航天大学学报，2023，55（2）：329338.LIU Yuxi，LIU Jixin，TIAN Wen.Optimization of gate pre-allocation based on improved NSGA-J.Journal of Nanjing University of Aeronautics&Astronautics，2023，55（2）：329338.第 55 卷南 京 航 空 航 天 大 学 学 报对于大型机场而言，机位资源与航班量的增长是彼此促进，又相互制约的两个矛盾体1。其中大型枢纽机场的矛盾尤为突出。
11、停机位分配是一个复杂的问题，因为它涉及广泛的相互依赖的资源，不适当的分配可能会导致航班延误、降低旅客满意度和机场资源的使用效率23。机场停机位分配问题（Airport gate assignment problem，AGAP）最主要的目的就是配置航班到合适的停机位，以便保证旅客能够方便地上下航班、提取行李、转机以及进出航空港，确保机场地面各项作业顺利进行4。其研究涉及到各航空公司进出航班的航线类型、航线距离、机型、航班数量、航班密度、停机时间、中转旅客行走距离和行李搬运距离等多方面的因素，可以归结为具有多项式复杂程 度（Nondeterministic polynomialbounded，NP
12、）的非确定性问题的二次配置问题（Quadratic assignment problem，QAP）56。停机位分配分为预分配阶段和再分配阶段，本文研究的是停机位预分配阶段的优化问题。目前，国内外学者主要从机场和旅客的角度对停机位预分配问题进行研究。从机场运营商的角度出发，Liu 等7考虑操作安全约束，以最小化登机口空闲间隔时间方差为优化目标建立了分配优化模型。马思思等8以航班进离港滑行距离最小为目标函数构建停机位分配模型，在实例仿真验证后对比优化方案和原始方案，发现滑行距离和滑行系统可服务航班量均有提高，提高了机场运行效率。袁媛等9考虑跑道的因素建立了以最小化航班场面滑行时间为优化目标的停机位
13、分配模型，利用 ILOG CPLEX 优化器求解，结果表明所建立模型的可行性，机场运行效率得到提高。赵征等10研究了在资源受限条件下的多目标停机位分配优化问题，以靠桥数最大、航班延误时间最少为优化目标构建停机位分配模型，通过实例验证说明所建立的模型可以有效提高靠桥率、减少航空器延误时间。刘君强等11基于航班延误建立了滑行道停机位一体化分配模型，并采用基因蚁群算法进行求解。从旅客角度出发，Ding 等12以最小化总的旅客在航站楼内的步行时间作为优化目标，研究在过度约束的情况下，当飞机数量超过可用停机位数量时，提出一种新的邻域搜索技术，获得有效的停机位分配方案。Feron 等13以 最 小 化 乘
14、 客 转 机 时 间 和 最 大 化 航班停机位分配偏好得分为目标函数建立多目标机场停机位分配模型。Kim 等14、Ding等15、郑志武等16、王志清等17等在最小化旅客步行距离时间的基础上，同时考虑了最大化停机位设施的使用率。曾琳燕等18、徐思敏等19、文笑雨等20等综合考虑旅客和航空公司公平性，以最小化所有旅客的步行距离和均衡航空公司旅客步行距离为目标建立停机位优化指派模型。纵观国内外对停机位预分配的研究，主要以旅客步行距离、停机位空闲时间和航空器滑行时间/滑行距离等作为优化目标建立单目标或多目标停机位分配优化模型，并使用启发式算法等对模型进行求解，以满足不同需求的停机位分配。已有的研究
15、很少综合考虑大型枢纽机场、航空公司和旅客的协同优化，以及机场主用机坪构型的运行模式。本文从保障航空公司和机场的利益以及提高旅客满意度的角度出发，在确保机场安全运行的前提下，从靠桥率、被使用停机位的数量和旅客步行距离 3个方面建立模型进行停机位预分配优化研究。将指定航空公司的机位分配和机场港湾 U 型区域的运行规则作为约束条件，以最小化分配到远机位的航班数目、最小化被使用的停机位数量和最小化旅客步行距离为优化目标，建立多目标优化模型。为了改进约束较多的复杂优化问题容易存在早熟及稳定性差的缺点，本文设计了一种自适应调整交叉率和变异率的 NSGA算法对所建立的停机位预分配优化模型进行有效求解，最后进
16、行实例分析。1 停机位预分配模型1.1问题描述停机位预分配是指在航班机型、航班时刻表、航空公司和旅客的利益以及机场全局运行顺畅等因素的制约下，由机场运行指挥中心为所有进出港航班分配合适的停机位。为保障航空公司的利益，需要将指定机坪的航空公司的航班分配至优先使用的停机位。而旅客满意度需从旅客步行距离入手，大型枢纽机场的旅客步行距离包括 3 项：进港旅客的步行距离（停机位与行李提取处之间的距离）、离港旅客的步行距离（安检口与出发停机位之间的距离）、中转旅客的步行距离（中转航班分配到的两个停机位之间的距离），即中转航班的旅客从进港停机位到中转柜台和中转柜台到离港停机位之间的距离。1.2假设条件（1）机场的航班量和时间分布保持在机场容量许可范围内，即在任意时刻，总可以为任一航班指派 1个停机位，尽管不是最优但一定是可行的。（2）由同一架飞机执行的进离港个航班称为航班对（以下简称航班），用 1 个航班号表示，且只能分配到 1个停机位上。（3）在研究时段内的航班计划、飞机基本信息、停330第 2 期刘禹汐，等：基于改进 NSGA的停机位预分配优化机位使用情况、停机位到中转柜台之间的距离和订票信息等
