Improper assignment of gates may result in flight delays, inefficient use of the resource, customer’s dissatisfaction. A typical metropolitan airport handles hundreds of flights a day. Solving the gate assignment problem (GAP) to optimality is often impractical. Meta-heuristics have recently been proposed to generate good solutions within a reasonable timeframe. In this work, we attempt to assess the performance of three meta-heuristics, namely, genetic algorithm (GA), tabu search (TS), simulated annealing (SA) and a hybrid approach based on SA and TS. Flight data from Incheon International Airport are collected to carry out the computational comparison. Although the literature has documented these algorithms, this work may be a first attempt to evaluate their performance using a set of realistic flight data.
A metropolitan airport has more than fifty gates and handles hundreds of flights a day for thousands of passengers. Gate assignment is a complicated problem as it deals with a wide range of interdependent resources including aircrafts, gates, gate facilities, and crews (Dorndorf, Jaehn, & Pesch, 2008). Improper assignment may result in flight delays, poor customer services, and inefficient use of gate facilities. Typically gates are first pre-assigned to the scheduled arriving and departing aircrafts ahead of time to ensure a smooth operation. This is commonly known as the gate assignment problem (GAP). Although GAP produces only a static schedule, it provides a basis for making last-minute changes to handle operational uncertainty caused by unexpected events such as flight delays, machine failures, and severe weather conditions.
Many GAP models and solution methods have been developed in the literature. Static and stochastic models are formulated. Exact and heuristic solution methods are proposed. The use of exact solution methods is certainly preferable. However, Obata (1979) argues that these exact methods are unable to solve realistic problems. Hence, heuristic methods have been extensively studied. Recent research focuses on meta-heuristics.
In this research, we adopt a GAP model commonly used in the literature and examine the use of meta-heuristics. Specifically, we consider genetic algorithm (GA), simulated annealing (SA), tabu search (TS), and a hybrid approach based on SA and TS. To assess the performance of these meta-heuristics, we collect flight data from Incheon International Airport (ICN). ICN is a busy hub in East Asia and provides a practical case for our computational comparison.
Although these meta-heuristics have been well documented in the literature, they have not been comprehensively compared to one another in terms of solution quality and computational efficiency. Also, all the previous studies use generated data to test their algorithms. In this work, we compare the three well-known meta-heuristics and a hybrid approach together using a common set of realistic flight data. To the best of our knowledge, this is a first attempt.
This manuscript is organized in this way. We will provide a literature review in the next section. Section 3 discusses a common GAP model. Section 4 presents the three GAP meta-heuristics, namely GA, SA, TS and a hybrid approach. In Section 5, we describe our flight data collected from ICN. One week data is used to evaluate these algorithms. Section 6 provides concluding remarks.
An airport in a major city may have over 50 gates and handle hundreds of flights. It is very critical to assign gates to flights to avoid any delays, make efficient use of the facility, and maintain a smooth and uninterrupted service. This is referred to as the gate assignment problem. Although optimal solution methods are available, they are unable to handle realistic applications. Recent research effort focuses more on heuristic methods. In this work, we examine three classic meta-heuristics and a hybrid approach. We collect one week flight data from Incheon International airport (ICN) to test these algorithms. Tabu search (TS) is the best among all three classic meta-heuristics. However, it is clear that the hybrid approach is better in terms of solution quality and computational time. This work may be a first attempt to evaluate all these algorithms together with a realistic data. The findings of the computational evaluation will be interesting to researchers and practitioners for airport operations.
