N. E. H. Sayah Ben Aissa, A. N. Medakene, K. Bouanane, M. L. Kherfi
In this study, we tackle the problem of assigning n flights to m gates, called Airport Gate Assignment Problem (AGAP). We study the case in which flights can be assigned to gates such that constraints on flight and gate sizes as well as conditions on flights’ arrival and departure times are considered. The maximization of the robustness and the total preference for flight-gate assignment are taken into account. We define a novel graph formulation for AGAP as a weighted m-coloring problem and equivalently as a graph clustering task. This allows to apply a clustering based Graph Neural Network (GNN) method as a powerful tool that addresses graph representations with deep learning algorithms. The proposed algorithm aims to find an efficient clustering of vertices in the constructed graph and thus an optimal assignment of flights under the aforementioned constraints. To reach our goal, some modifications on the GNN algorithm are performed, where the total weight in the graph formulation is integrated in the loss function of the original algorithm. This permits to enhance the learning process of the model and obtain an acceptable solution with regard to our objectives.
Keywords: Airport Gate Assignment Problem, Graph Coloring, Graph Neural Network, Graph ClusteringScheduled
FC3 Logistics, Transportation and Distribution Planning 1
June 11, 2021 12:15 PM
3 - TC Koopmans