A branch-and-price approach for airport gate assignment problem with chance constraints. (February 2023)

• Record Type: Journal Article
• Authors: Kim, Junyoung; Goo, Byungju; Roh, Youngjoo; Lee, Chungmok; Lee, Kyungsik
• Is Part Of: Transportation research. Volume 168(2023)
• Page Start: 1
• Page End: 26
• Publication Date: 2023-02
• Subjects: Airport gate assignment -- Branch-and-price -- Chance constraints -- Labeling algorithm; Transportation -- Research -- Periodicals; Transportation -- Mathematical models -- Periodicals
• DOI: 10.1016/j.trb.2022.12.005
• Languages: English
• ISSNs: 0191-2615

Abstract

Abstract: At an airport, the flights should be attached to the gates to embark or disembark the passengers. The airport gate assignment problem concerns the efficient utilization of gates by assigning flights to the gates according to the flights' planned schedules. However, due to ever-increasing air traffic demands and unpredictable weather conditions, it is hard to expect that the flights strictly follow the planned schedules. Therefore, establishing a robust gate assignment plan against uncertain flight schedule deviations is crucial for airport operators. However, ensuring the robustness of the plan by imposing too long idle times of gates may deteriorate the efficiency of gate usage. To address the trade-off between two goals, we introduce an overlap chance-constrained airport gate assignment problem that limits the probability of an overlap occurrence of flight schedules for each gate to given thresholds while maximizing the sum of preference values of flights for gates. We propose a network-based integer programming model for this problem, estimating the probability distribution using the historical flight arrival/departure deviation data. Then, we strengthen the model using the concept of gate assignment patterns, and a branch-and-price algorithm is devised to solve the model. A labeling algorithm-based efficient column generation algorithm is developed, further accelerated by clustering gates with similar characteristics. Through computational experiments, we demonstrate the efficiency of the proposed algorithm, and the trade-off between the overlap occurrence probability and the preference is analyzed using real-life instances. Highlights: Studies the airport gate assignment problem under uncertain flight schedules. Proposes a chance-constrained MIP model to establish a robust assignment plan. Proposes an estimation method for the probability of overlap of flight schedules. Devises an efficient branch-and-price algorithm to solve the MIP model. Demonstrates the effectiveness and efficiency of the proposed methods.