Gate Assignment Problem Heuristics Examples

Industrial Engineering Department, College of Engineering, King Saud University, P.O. Box 800, Riyadh 11421, Saudi Arabia

Copyright © 2014 Abdelghani Bouras et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

The airport gate assignment problem (AGAP) is one of the most important problems operations managers face daily. Many researches have been done to solve this problem and tackle its complexity. The objective of the task is assigning each flight (aircraft) to an available gate while maximizing both conveniences to passengers and the operational efficiency of airport. This objective requires a solution that provides the ability to change and update the gate assignment data on a real time basis. In this paper, we survey the state of the art of these problems and the various methods to obtain the solution. Our survey covers both theoretical and real AGAP with the description of mathematical formulations and resolution methods such as exact algorithms, heuristic algorithms, and metaheuristic algorithms. We also provide a research trend that can inspire researchers about new problems in this area.

1. Introduction

The complexity of airport management has increased significantly. Flight delays or accidents might happen if operations were not handled well, and domino effect might happen to influence the whole operations of airport. In airports, the tasks related to gate assignment problem (AGAP) are one of the most important daily operations many researches have been published on with the aim of solving the problem in spite of its complexity. The objective of the task is assigning each flight (aircraft) to an available gate while maximizing both conveniences to passengers and the operational efficiency of airport. Large airlines typically need to manage different gates across an airport in the most efficient way in a dynamic operational environment. This requires a solution that provides the ability to change and update the gate assignment data on a real time basis. It should also provide robust and efficient disruption management, while maintaining safety, security, and cost efficiency.

Numerous methods have been developed to solve this problem since 1974. Steuart [1] proposed simple stochastic model to find the efficiency use of the gate positions. The research interest in this field was slow in development because there were less than 15 publications within 25 years. However, after 2000, the interest to develop solutions for this problem increased, until nowadays, though with small growth. The objective of this problem varied and depended on the point of view. The first is as an airport owner, which is the government. The objectives are to maximize the utilization of the available gates and terminal [1–4], minimize the number of gate conflicts [5], minimize the number of ungated flights [3, 6–9], and minimize the flights delay [10]. Another point of view is as an airlines owner. Their goals were to increase the customer satisfaction with minimizing the passenger walking distance between gates [3, 6, 7, 11–18] and minimizing the travelling distance from runway to the gate [19].

Dorndorf et al. [20] divided the objectives into five parts, which are reducing the number of the procedures for the costly aircraft towing, minimizing the passengers total walking distance, minimizing the deviations in the schedules, minimizing the number of ungated aircrafts, and maximizing the preferences (i.e., certain aircrafts should go for particular gates). They also defined three usually used constraints, which are the fact that only one aircraft can be gated in a defined amount of time, the fulfillment of the space restriction and service requirements, and the assurance of getting a minimum time between sequent aircrafts and a minimum ground time.

The solution approaches and the solving techniques are varied with no methods, until nowadays, that provide a robust technique for such problem. This study focuses on assessing the trend of solving gate assignment problem in light of the preceding four points. Specifically, this study will address the following research questions. Is this problem NP-hard? What formulation can be defined for such problem? How effective are the recent methods and techniques to solve the problem? What recommendation can be made based on the current findings with regard to research trends?

From a mathematical view, AGAP has been formulated as integer, binary, or mixed integer, general linear or nonlinear models. Specific formulation as binary or mixed binary quadratic models has also been suggested. Other well-known related problems in combinatorial optimization such as quadratic assignment problem (QAP), clique partitioning problem (CPP), and scheduling problem have been used to formulate AGAP. However, few publications on AGAP tackled stochastic or robust optimization.

While the goal of combinatorial optimization research is to find an algorithm that guarantees an optimal solution in polynomial time with respect to the problem size, the main interest in practice is to find a nearly optimal or at least good-quality solution in a reasonable amount of time. Many approaches to solve the GAP have been proposed, varying from Brand and Bound (B&B) to highly esoteric optimization methods. The majority of these methods can be broadly classified as either “exact” algorithms or “heuristic” algorithms. Exact algorithms are those that yield an optimal solution. As discussed in Section 3.1 different exact solution techniques have been used to solve the GAP and in some research, the authors used some optimization programming languages like CPLEX and AMPL.

Basically the GAP is a QAP and it is an NP-hard problem as shown in Obata [21]. Since the AGAP is NP-hard, researchers have suggested various heuristic and metaheuristics approaches for solving the GAP. With heuristic algorithms, theoretically there is a chance to find an optimal solution. That chance can be remote because heuristics often reach a local optimal solution and get stuck at that point. But metaheuristics or “modern heuristics” introduce systematic rules to deal with this problem. The systematic rules avoid local optima or give the ability of moving out of local optima. The common characteristic of these metaheuristics is the use of some mechanisms to avoid local optima. Metaheuristics succeed in leaving the local optimum by temporarily accepting moves that cause worsening of the objective function value. Sections 3.2 and 3.3 addressed the heuristic and metaheuristics approaches for solving the GAP. Some papers presenting good overviews as well as annotated bibliographies on the topic of GAP and a good literature on the AGAP and the use of metaheuristics for AGAP are Dorndorf et al. [20, 22] and Cheng et al. [23].

This paper surveys a large number of models and techniques developed to deal with GAP. In Section 2, we detail the models formulations of the problem. In Section 3, we addressed the resolution methods used to solve the problem. We conclude in Section 4, and we represent the research trends.

2. Formulations of AGAP and Related Problems

Many researchers formulated the AGAP as an integer, binary, or mixed integer linear or nonlinear model and some of them formulated it as binary or mixed binary quadratic models, whereas some of the researchers have formulated the AGAP as well-known related problems in combinatorial optimization such as quadratic assignment problem (QAP), clique partitioning problem (CPP), and scheduling problem or even as a network representation. However, some of the researchers formulated the AGAP as a robust optimization model. In this section, according to the way of how the researchers deal with the gate assignment problem, a classification for the AGAP has been made as follows.

2.1. Selected AGAP Formulations
2.1.1. Integer Linear Programming Formulations (IP)

Lim et al. [24] formulated the AGAP as an integer programming model and developed two models with time windows. The first model was devoted to minimization of the passenger walking distance (travel time) while the second model optimized the gate assignments with cargo handling costs: Both of these objectives put a penalty function due to a delay. These two objectives used the constraints, as follows: where , , and are binary and  is integer.

Constraint (3) ensures that each flight must be assigned to exactly one gate. Constraints (4)-(5) state that a binary variable can be equal to one if flight is assigned to gate () and flight is assigned to gate (). Constraint (6) further specifies the necessary condition that must be equal to one if and . Constraints (7) and (8) ensure that the flight must land and depart within the specified time window. Constraint (9) indicates that = 1 if , which means when flight departs before or right at the time when some gate opens for flight . Constraint (10) states that if , which means when flight departs after some gate opens for flight . Constraint (11) specifies that one gate cannot be occupied by two different flights simultaneously.

In the first model and according to the linearity of the objective function and constraints, they used a standard IP solver (CPLEX) to find the optimal solution, whereas in the second model authors used several heuristic algorithms, namely, the “Insert Move Algorithm,” the “Interval Exchange Move Algorithm,” and a “Greedy Algorithm” to generate solutions. The generated solutions then have been improved using a tabu search (TS) and memetic algorithm. The results showed that the used heuristics performed better than the IP solver (CPLEX) in both CPU time and solutions quality.

Diepen et al. [25, 26] formulated the AGAP as integer linear programming model with a relaxation for the integrality. After relaxing the integrality, the resulting relaxed LP was exploited to obtain solutions of ILP by using column generation (CG). The problem was divided into two phases, planning and attaching. The first phase was the planning section and it was easier to model and calculate. Their objective is to minimize the cost of a gate plan. They proposed the following model: subject to where

Please, wait while we are validating your browser

0 thoughts on “Gate Assignment Problem Heuristics Examples”


Leave a Comment

Your email address will not be published. Required fields are marked *