A branch-and-price approach for airport gate assignment problem with chance constraints

Junyoung Kim, Byungju Goo, Youngjoo Roh, Chungmok Lee and Kyungsik Lee

Transportation Research Part B: Methodological, 2023, vol. 168, issue C, 1-26

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.

Keywords: Airport gate assignment; Branch-and-price; Chance constraints; Labeling algorithm (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0191261522002077
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:transb:v:168:y:2023:i:c:p:1-26

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

DOI: 10.1016/j.trb.2022.12.005

Access Statistics for this article

Transportation Research Part B: Methodological is currently edited by Fred Mannering

More articles in Transportation Research Part B: Methodological from Elsevier
Bibliographic data for series maintained by Catherine Liu ().