Abstract:

To address the challenge that the existing methods struggle to balance solution efficiency， assignment quality， and generalization in airport gate pre-assignment at large hub airports under dynamic changes in flight number， gate layout， and assignment rules， an airport gate assignment algorithm based on node prediction in conflict graph of assigned activities was proposed. Firstly， an airport gate assignment model was established with the objectives of maximizing gate assignment rate and cumulative soft preference. Secondly， the feasible airport gate assignment activities were screened through an airfield zoning strategy， the corresponding conflict graph of assignment activities was constructed， the Node-Edge Collaborative Updating Graph Neural Network （NECU-GNN） was designed， and the NECU-GNN for Node Prediction model （NECU-GNN4NP） was developed. Finally， the NECU-GNN4NP-guided ranking-based Max Weighted Independent Set Algorithm （MWISA） was proposed on the basis of NECU-GNN4NP， so as to solve the optimal set of assignment activities for the conflict graph of assignment activities and obtain the airport gate assignment scheme. Experimental results based on Shenzhen Bao’an International Airport data show that compared with the current optimal assignment scheme at Shenzhen Bao’an International Airport， the proposed algorithm increases the gate assignment rate by 4.2， 4.3， and 3.1 percentage points， respectively， improves the cumulative soft preference by 38.1%， 30.3%， and 42.8%， respectively， and reduces the solution time by 65.3%， 39.1%， and 41.4%， respectively， in low-peak， normal， and high-peak scenarios. In addition， migration experimental results based on Yinchuan Hedong International Airport data demonstrate that the proposed algorithm can be adapted and applied to other airports rapidly. It can be seen that the proposed algorithm not only has good generalization but also enables efficient and high-quality airport gate assignment.

Key words: aviation transportation engineering, airport gate assignment, Graph Neural Network (GNN), max weighted independent set, gate assignment rate, soft preference

摘要：

针对大型枢纽机场停机位预分配问题在航班数量、机位布局和分配规则动态变化背景下，现有方法难以兼顾求解效率、分配质量和泛化性的挑战，提出一种基于指派活动冲突图节点预测的机场停机位分配算法。首先，建立以最大化靠桥率与最大化累计软偏好为优化目标的停机位分配模型；其次，采用场面分区策略筛选可行的机位指派活动，构建相应的指派活动冲突图，设计基于节点-边协同更新的图神经网络（NECU-GNN），并设计基于NECU-GNN的节点预测模型（NECU-GNN4NP）；最后，设计基于NECU-GNN4NP引导排序的最大加权独立集算法（MWISA）以求解指派活动冲突图的最优指派活动集合，得到停机位分配解方案。基于深圳宝安国际机场数据的实验结果表明，在低峰期、普通和高峰期这3种场景下，与深圳宝安国际机场的目前最优分配方案相比，所提算法的靠桥率分别提升了4.2、4.3和3.1个百分点，累计软偏好分别提高了38.1%、30.3%和42.8%，求解时间分别减少了65.3%、39.1%和41.4%。此外，基于银川河东国际机场数据的迁移实验结果表明，所提算法能够快速迁移应用到其他机场。可见，所提算法不仅能高效与高质量地进行停机位分配，而且具有良好的泛化性。

关键词: 航空运输工程, 机场停机位分配, 图神经网络, 最大加权独立集, 靠桥率, 软偏好