The airport gate assignment problem: A Branch-and-Price Approach for improving utilization of jetways. (February 2022)

• Record Type: Journal Article
• Authors: Bi, Jun; Wang, Fujun; Ding, Cong; Xie, Dongfan; Zhao, Xiaomei
• Is Part Of: Computers & industrial engineering. Volume 164(2022)
• Publication Date: 2022-02
• Subjects: Gate assignment -- Operation research -- Branch and price -- Airport operation; Engineering -- Data processing -- Periodicals; Industrial engineering -- Periodicals; 620.00285
• DOI: 10.1016/j.cie.2021.107878
• Languages: English
• ISSNs: 0360-8352

Abstract

Highlights: The modelling method based on gate planning can reduce the number of constraints. Column generation algorithm effectively reduces the scale of variables. Tabu search algorithm was used to accelerate the speed of branch and bound. Satisfactory solutions can still be given to bigger problems in a faster time. Abstract: With the development of the civil aviation industry, airports' parking space resources, especially those with jetways, become increasingly scarce. The airport gate assignment problem (AGAP) is a critical issue in airport operation management. When the number of flights is large, solving this situation is challenging. Therefore, designing an efficient gate assignment methodology is very important. This paper considers several significant constraints and aims to maximize the number of passengers using jetways, which is not fully considered in the existing research. A model with gate plans (possible scheme combinations) as decision variables is established, which effectively reduces the number of constraints. However, considering that the scale of this problem is still quite large, the Branch- and-Price algorithm (BAPA) is used to solve the model. The solving speed is improved by adding a heuristic search with a certain probability in each search node. The model's performance is verified by using the actual flight data of Kunming Changshui International Airport, China. The experimental results show that the method of this paper can achieve a 12.71 % increase in the optimization goal compared to the current computer-assisted manual allocation. In terms of finding the optimal and satisfactory solution, the feasibility and effectiveness of this method are verified by comparing with the commercial solver CPLEX, Tabu Search (TS) algorithm, improved Adaptive Parallel Genetic (APGA) algorithm, and Greedy algorithm (GA).