Airport Gate Assignment Problem under Uncertainty

Abstract

In this thesis, we study the airport gate assignment problem under uncertainty in arrival and departure times of flights which may cause overlaps between flights assigned to the same gate. In this respect, we establish a gate assignment schedule where overlaps between flights are prevented with probabilistic guarantees, while maximizing the sum of preference values of flights for gates. We propose a network-based integer programming model with chance constraints that limit the probability of an overlap occurrence in each gate less than a given threshold value, for which the probability that a pair of flights overlaps is predicted based on historical data. We also propose a strengthened integer programming model for the problem based on the concept of flight assignment patterns, and devise a branch-and-price algorithm to solve the model. Computational experiments are conducted with real and artificial instances which are based on the real data of Incheon International Airport in 2019. The results show the efficiency of the proposed algorithm as well as the robustness of the derived schedules compared to the existing approaches.

본 논문은 불확실성하의 공항 게이트 할당 문제를 다룬다. 항공기 출/도착 시각의 불확실성은 수립된 공항 게이트 할당 계획 실행 시에 같은 게이트 내의 항공기 스케줄간의 중첩을 야기하며, 이는 항공기의 지연, 게이트 할당 계획 재수립과 같은 차질을 유발한다. 따라서 본 논문은 실제 항공 데이터를 활용하여 두 항공기 간 중첩이 일어날 확률을 예측하는 방법을 제안하고, 이를 이용하여 각 게이트에서 항공기 스케줄 간 중첩이 발생할 확률을 정량적으로 제한하는 수리모형을 제시한다. 또한 항공기 할당 패턴을 이용하여 강화된 정수최적화 모형을 제시하고 분지평가 알고리즘을 해법으로 제안한다. 인천국제공항의 2019년 실제 데이터를 기반으로 한 실험을 통하여 본 논문에서 제시한 알고리즘의 효율성과 도출된 게이트 할당 계획의 효과성을 확인하였다.