The Airport Gate Assignment Problem: A Survey
---
paper_title: Flight gate scheduling with respect to a reference schedule

paper_content:

This paper considers the problem of assigning flights to airport gates. We examine the general case in which an aircraft serving a flight may be assigned to different gates for arrival and departure processing and for optional intermediate parking. Restrictions to this assignment include gate closures and shadow restrictions, i.e., the situation where certain gate assignments may cause blocking of neighboring gates. The objectives include maximization of the total assignment preference score, a minimal number of unassigned flights during overload periods, minimization of the number of tows, maximization of a robustness measure as well as a minimal deviation from a given reference schedule. We show that in case of a one period time horizon this objective can easily be integrated into our existing model based on the Clique Partitioning Problem. Furthermore we present a heuristic algorithm to solve the problem for multiple periods. Copyright Springer Science+Business Media, LLC 2012
---
paper_title: Airport Gate Assignment A Hybrid Model and Implementation

paper_content:

With the rapid development of airlines, airports today become much busier and more complicated than previous days. During airlines daily operations, assigning the available gates to the arriving aircrafts based on the fixed schedule is a very important issue, which motivates researchers to study and solve Airport Gate Assignment Problems (AGAP) with all kinds of state-of-the-art combinatorial optimization techniques. In this paper, we study the AGAP and propose a novel hybrid mathematical model based on the method of constraint programming and 0 - 1 mixed-integer programming. With the objective to minimize the number of gate conflicts of any two adjacent aircrafts assigned to the same gate, we build a mathematical model with logical constraints and the binary constraints. For practical considerations, the potential objective of the model is also to minimize the number of gates that airlines must lease or purchase in order to run their business smoothly. We implement the model in the Optimization Programming Language (OPL) and carry out empirical studies with the data obtained from online timetable of Continental Airlines, Houston Gorge Bush Intercontinental Airport IAH, which demonstrate that our model can provide an efficient evaluation criteria for the airline companies to estimate the efficiency of their current gate assignments.
---
paper_title: Optimization of multiple objective gate assignments

paper_content:

This paper proposes a multiple objective model to help airport authorities to efficiently and effectively solve gate assignment problems. The model is formulated as a multiple objective zero-one integer program. To efficiently solve large-scale problems in practice, we used the weighting method, the column generation approach, the simplex method and the branch-and-bound technique to develop a solution algorithm. To test how well the model may be applied in actual operations, a case study regarding the operation of Chiang Kai-Shek (CKS) Airport was performed. The results show that the model could be useful for actual operations.
---
paper_title: DEVELOPMENT OF AN INTELLIGENT AGENT FOR AIRPORT GATE ASSIGNMENT

paper_content:

The Aircraft-Gate Assignment Problem (AGAP) is a well-known Non-deterministic Polynomialtime (NP)-hard problem for optimization. During daily airport operations the arrival and departure times of flights may vary compared to their original schedules. This may require reassignment of gates to capture the dynamics of flights and gate status to enhance the level of services provided to passengers. For busy airports with high numbers of arrivals/departures, the assignment decisions must be made within a short time to capture all the changes. To satisfy this requirement, an intelligent agent for airport gate assignment (InGates) is being developed for this purpose for the management and assignment of gates at an airport for daily operations. The agent is aimed at performing the gate assignment for every flight, taking into consideration gate and flight dynamics, transfers, requirements of the airlines, aircraft types, airport operation rules, etc. A knowledge-based expert system forms the cores of the system and is connected to external databases for flight and passenger information. Real-time changes on airport gates and flights can be made through a graphical user interface, with the capabilities of performing real-time updating of the results and information. Data obtained at Singapore’s Changi Airport is used to examine the performance of the system. Results obtained from the scenario analysis have shown that the system provides an enhanced way to assign gates at an airport. In the development of the next stage, InGates will be integrated with an optimization model to provide an integrated solution for planning and assignment of gates at an airport.
---
paper_title: A conceptual solution to the aircraft gate assignment problem using 0,1 linear programming

paper_content:

Abstract The U.S. commercial airline movement to “hub” operations has increased rapidly over the past several years. This trend will grow with the introduction of the Wayport concept. These giant “people exchange” facilities will feature multiple runways and massive concourses. While the Wayport developers may automate the ground movement of passengers, the sheer size of the facilities and the anticipated close scheduling of flights will confront the passenger with a problem of new dimension in getting from arrival gate to departure gate. One thing that could help alleviate the situation would be “sensible” assignment of flights to gates - sensible in that the assignment would take into account the communion of interest of the passengers. Other things being equal, the positioning of incoming flights should take into account the distribution of passengers among connecting flights. The larger the number of passengers arriving on flight X for destination A, the closer flight X should be positioned to the flight departing for A. This inquiry looks conceptually at this problem, reducing the distance passengers must walk from gate to gate. The criterion selected is minimization of the total passenger-distance travel for a given arrival-departure cycle. The problem can be conveniently cast as a 0,1 Linear Programming (LP) problem. The author discusses derivation of problem parameters and then solves several representative problems. A unique feature of the LP approach is the availability with the optimal solution of cost factors and assignments for suboptimal solutions. Minor changes in the input data do not require reworking the problem. Although the solution is characterized as conceptual, some ideas are given for practical use of the solution methodology in a dynamic airport environment.
---
paper_title: Flight gate scheduling: State-of-the-art and recent developments☆

paper_content:

This paper surveys a large variety of mathematical models and up-to-date solution techniques developed for solving a general flight gate scheduling problem that deals with assigning different aircraft activities (arrival, departure and intermediate parking) to distinct aircraft stands or gates. The aim of the work is both to present various models and solution techniques which are available in nowadays literature and to give a general idea about new open problems that arise in practise. We restrict the scope of the paper to flight gate management without touching scheduling of ground handling operations.
---
paper_title: Stochastic optimization models for the airport gate assignment problem

paper_content:

Uncertainties inherent in the airport traffic may lead to the unavailability of gates for accommodating scheduled flights. Incorporating random disruptions is crucial in constructing effective flight-gate assignments. We consider the gate assignment problem under uncertainty in flight arrival and departure times and develop stochastic programming models incorporating robustness measures based on the number of conflicting flights, idle and buffer times. The proposed models are formulated as large-scale mixed-integer programming problems and tabu search algorithms are implemented to obtain assignments of reasonable quality. We conduct a computational study to analyze the proposed alternate models and show the effectiveness of the solution methods.
---
paper_title: Optimizing gate assignments at airport terminals

paper_content:

The assignment of aircraft arriving on schedule to available gates is a major issue during the daily airline operations. The Gate Assignment Problem (GAP) is an easily-understood but difficult to solve problem. An important issue in GAP is to minimize the distance a passenger is required to walk inside the terminal to reach his or her departure gate. The total passenger walking distance is based on the passenger transfer volume between every pair of aircrafts and the distance between every pair of gates. Therefore, the problem of assigning gates to arriving and departing flights at an airport is a Quadratic Assignment Problem (QAP), which is a difficult problem to solve. Recently, integer programming (IP), simulation, and expert systems have been applied to the GAP. A new integer programming formulation of the gate assignment problem is presented. An efficient heuristic solution procedure for solving the problem is also proposed. The performance of this solution approach is evaluated in a variety of test problems, and is compared to the optimal solutions obtained using CPLEX in certain test problems. The proposed heuristic solution approach proves to be an efficient method for obtaining good solutions for large scale gate assignment problems in a very reasonable computation time.
---
paper_title: Gate Position Requirements at Metropolitan Airports

paper_content:

The number of gate positions required at an airport, or the number of flights that can be accommodated at a given number of gate positions, depends on how efficiently each gate position is used. The airlines' schedule and the airport's operating policies influence the efficient use of the gate positions. A simple stochastic model describing the behavior of flights relative to their schedule was developed based on empirical information. The model was then used to study the influence of a common scheduling practice of bank operation on the requirements for gate positions. It was found that a completely uniform schedule generates the minimum requirement. A procedure is presented to estimate the number of gate positions required at an airport.
---
paper_title: The airport gate assignment problem: mathematical model and a tabu search algorithm

paper_content:

Considers an airport gate assignment problem that dynamically assigns airport gates to scheduled flights based on passengers' daily origin and destination flow data. The objective of the problem is to minimize the overall connection times during which passengers walk to catch their connection flights. We formulate this problem as a mixed 0-1 quadratic integer programming problem and then reformulate it as a mixed 0-1 integer problem with a linear objective function and constraints. We design a simple tabu search meta-heuristic to solve the problem. The algorithm exploits the special properties of different types of neighborhood moves, and create highly effective candidate list strategies. We also address issues of tabu short-term memory, dynamic tabu tenure, aspiration rules, and various intensification and diversification strategies. Preliminary computational experiments are conducted, and the results are presented and analyzed.
---
paper_title: Optimizing Gate Assignments at Airport Terminals

paper_content:

The airport flight-to-gate assignment problem is solved using two methods: (1) a linear programming relaxation of an integer program formulation and (2) a heuristic. The objective is to minimize passenger walking distances within the airport terminal area through a judicious gate assignment policy. An actual flight schedule for an average day at Toronto International Airport is used to compare existing walking distances, obtained from the original assignment, with results from the two methods. The results indicated that the original assignment had a 32% higher average per passenger walking distance than the minimum possible distance given by the LP solution. The heuristic’s performance was near optimal; it gave an average walking distance which was only 3.9% greater than the minimum. Computation times for the heuristic are 3.4 CPU seconds per run, while the linear program consumes 386 seconds per run on an IBM 370/168. In addition, if the heuristic is solved first and its solution is used as an initial feasible basis for the LP relaxation of the IP, the total CPU used to obtain optimality is reduced to 42 seconds.
---
paper_title: A heuristic approach for airport gate assignments for stochastic flight delays

paper_content:

To make good flight to gate assignments, not only do all the relevant constraints have to be considered, but stochastic flight delays that occur in actual operations also have to be taken into account. In past research, airport gate assignments and stochastic disturbances have often been handled in the planning and the real-time stages separately, meaning that the interrelationship between these stages, as affected by such delays, has been neglected. In this research, we develop a heuristic approach embedded in a framework designed to help the airport authorities make airport gate assignments that are sensitive to stochastic flight delays. The framework includes three components, a stochastic gate assignment model, a real-time assignment rule, and two penalty adjustment methods. The test results are based on data supplied by a Taiwan international airport, and show that the proposed framework performs better than the current manual assignment process and the traditional deterministic model.
---
paper_title: Fuzzy model and optimization for airport gate assignment problem

paper_content:

Gate assignment is an important decision making problem which involves multiple and conflict objectives in airport. In this paper, fuzzy model is proposed to handle two main objectives, minimizing the total walking distance for passengers and maximizing the robustness of assignment. The idle times of flight-to-gate are regarded as fuzzy variables, and whose membership degrees are used to express influence on robustness of assignment. Adjustment function on membership degree is introduced to transfer two objectives into one. Modified genetic algorithm is adopted to optimize the NP-hard problem. Finally, illustrative example is given to evaluate the performance of fuzzy model. Three distribution functions are tested?? and comparison with the method of fixed buffer time is given. Simulation results demonstrate the feasibility and effectiveness of proposed fuzzy method.
---
paper_title: Multi-objective airport gate assignment problem in planning and operations

paper_content:

We consider the assignment of gates to arriving and departing flights at a large hub airport. This problem is highly complex even in planning stage when all flight arrivals and departures are assumed to be known precisely in advance. There are various considerations that are involved while assigning gates to incoming and outgoing flights (such a flight pair for the same aircraft is called a turn) at an airport. Different gates have restrictions, such as adjacency, last-in first-out gates and towing requirements, which are known from the structure and layout of the airport. Some of the cost components in the objective function of the basic assignment model include notional penalty for not being able to assign a gate to an aircraft, penalty for the cost of towing an aircraft with a long layover, and penalty for not assigning preferred gates to certain turns. One of the major contributions of this paper is to provide mathematical model for all these complex constraints that are observed at a real airport. Further, we study the problem in both planning and operations modes simultaneously, and such an attempt is, perhaps, unique and unprecedented. For planning mode, we sequentially introduce new additional objectives to our gate assignment problem that have not been studied in the literature so far(i) maximization of passenger connection revenues, (ii) minimization of zone usage costs, and (iii) maximization of gate plan robustnessand include them to the model along with the relevant constraints. For operations mode, the main objectives studied in this paper are recovery of schedule by minimizing schedule variations and maintaining feasibility by minimal retiming in the event of major disruptions. Additionally, the operations mode models must have very, very short run times of the order of a few seconds. These models are then applied to a functional airline at one of its most congested hubs. Implementation is carried out using Optimization Programming Language, and computational results for actual data sets are reported. For the planning mode, analyst perception of weights for the different objectives in the multi-objective model is used wherever actual dollar value of the objective coefficient is not available. The results are also reported for large, reasonable changes in objective function coefficients. For the operations mode, flight delays are simulated, and the performance of the model is studied. The final results indicate that it is possible to apply this model to even large real-life problems instances to optimality within short run times with clever formulation of conventional continuous time assignment model. Copyright (c) 2013 John Wiley & Sons, Ltd.
---
paper_title: New heuristics for over-constrained flight to gate assignments

paper_content:

We consider the over-constrained Airport Gate Assignment Problem where the number of flights exceed the number of gates available, and where the objectives are to minimize the number of ungated flights and the total walking distances. The problem is formulated as a binary quadratic programming problem. We design a greedy algorithm and use a Tabu Search meta-heuristic to solve the problem. The greedy algorithm minimizes ungated flights while we devise a new neighbourhood search technique, the Interval Exchange Move, which allows us flexibility in seeking good solutions, especially when flight schedules are dense in time. Experiments conducted give good results.
---
paper_title: Multicriteria airport gate assignment and Pareto simulated annealing

paper_content:

This paper addresses an airport gate assignment problem with multiple objectives. The objectives are to minimize the number of ungated flights and the total passenger walking distances or connection times as well as to maximize the total gate assignment preferences. The problem examined is an integer program with multiple objectives (one of them being quadratic) and quadratic constraints. Of course, such a problem is inherently difficult to solve. We tackle the problem by Pareto simulated annealing in order to get a representative approximation for the Pareto front. Results of computational experiments are presented. To the best of our knowledge, this is the first attempt to consider the airport gate assignment problem with multiple objectives.
---
paper_title: Optimization of multiple objective gate assignments

paper_content:

This paper proposes a multiple objective model to help airport authorities to efficiently and effectively solve gate assignment problems. The model is formulated as a multiple objective zero-one integer program. To efficiently solve large-scale problems in practice, we used the weighting method, the column generation approach, the simplex method and the branch-and-bound technique to develop a solution algorithm. To test how well the model may be applied in actual operations, a case study regarding the operation of Chiang Kai-Shek (CKS) Airport was performed. The results show that the model could be useful for actual operations.
---
paper_title: Disruption management in flight gate scheduling

paper_content:

This paper introduces models of robustness in flight gate assignments at airports. We briefly repeat the general flight gate assignment problem and disruptions occurring in airline scheduling. Recovery strategies and robust scheduling are surveyed as the main methods in disruption management. We present a non-robust flight gate assignment model and incorporate two approaches of robustness.
---
paper_title: Flight gate scheduling: State-of-the-art and recent developments☆

paper_content:

This paper surveys a large variety of mathematical models and up-to-date solution techniques developed for solving a general flight gate scheduling problem that deals with assigning different aircraft activities (arrival, departure and intermediate parking) to distinct aircraft stands or gates. The aim of the work is both to present various models and solution techniques which are available in nowadays literature and to give a general idea about new open problems that arise in practise. We restrict the scope of the paper to flight gate management without touching scheduling of ground handling operations.
---
paper_title: Flight gate scheduling with respect to a reference schedule

paper_content:

This paper considers the problem of assigning flights to airport gates. We examine the general case in which an aircraft serving a flight may be assigned to different gates for arrival and departure processing and for optional intermediate parking. Restrictions to this assignment include gate closures and shadow restrictions, i.e., the situation where certain gate assignments may cause blocking of neighboring gates. The objectives include maximization of the total assignment preference score, a minimal number of unassigned flights during overload periods, minimization of the number of tows, maximization of a robustness measure as well as a minimal deviation from a given reference schedule. We show that in case of a one period time horizon this objective can easily be integrated into our existing model based on the Clique Partitioning Problem. Furthermore we present a heuristic algorithm to solve the problem for multiple periods. Copyright Springer Science+Business Media, LLC 2012
---
paper_title: DEVELOPMENT OF AN INTELLIGENT AGENT FOR AIRPORT GATE ASSIGNMENT

paper_content:

The Aircraft-Gate Assignment Problem (AGAP) is a well-known Non-deterministic Polynomialtime (NP)-hard problem for optimization. During daily airport operations the arrival and departure times of flights may vary compared to their original schedules. This may require reassignment of gates to capture the dynamics of flights and gate status to enhance the level of services provided to passengers. For busy airports with high numbers of arrivals/departures, the assignment decisions must be made within a short time to capture all the changes. To satisfy this requirement, an intelligent agent for airport gate assignment (InGates) is being developed for this purpose for the management and assignment of gates at an airport for daily operations. The agent is aimed at performing the gate assignment for every flight, taking into consideration gate and flight dynamics, transfers, requirements of the airlines, aircraft types, airport operation rules, etc. A knowledge-based expert system forms the cores of the system and is connected to external databases for flight and passenger information. Real-time changes on airport gates and flights can be made through a graphical user interface, with the capabilities of performing real-time updating of the results and information. Data obtained at Singapore’s Changi Airport is used to examine the performance of the system. Results obtained from the scenario analysis have shown that the system provides an enhanced way to assign gates at an airport. In the development of the next stage, InGates will be integrated with an optimization model to provide an integrated solution for planning and assignment of gates at an airport.
---
paper_title: Airport Gate Scheduling with Time Windows

paper_content:

In contrast to the existing airport gate assignment studies where flight have fixed schedules, we consider the more realistic situation where flight arrival and departure times can change. Although we minimize walking distances (or travel time) in our objective function, the model is easily adapted for other material handling costs including baggage and cargo costs. Our objectives are achieved through gate assignments, where time slots alloted to aircraft at gates deviate from scheduled slots minimally. Further, the model can be applied to cross-docking optimization in areas other than airports, such as freight terminals where material arrival times (via trucks, ships) can fluctuate. The solution approach uses insert and interval exchange moves together with a time shift algorithm. We then use these neighborhood moves in Tabu Search and Memetic Algorithms. Computational results are provided and verify that our heuristics work well in small cases and much better in large cases when compared with CPLEX solver.
---
paper_title: Flight gate scheduling: State-of-the-art and recent developments☆

paper_content:

This paper surveys a large variety of mathematical models and up-to-date solution techniques developed for solving a general flight gate scheduling problem that deals with assigning different aircraft activities (arrival, departure and intermediate parking) to distinct aircraft stands or gates. The aim of the work is both to present various models and solution techniques which are available in nowadays literature and to give a general idea about new open problems that arise in practise. We restrict the scope of the paper to flight gate management without touching scheduling of ground handling operations.
---
paper_title: Stochastic optimization models for the airport gate assignment problem

paper_content:

Uncertainties inherent in the airport traffic may lead to the unavailability of gates for accommodating scheduled flights. Incorporating random disruptions is crucial in constructing effective flight-gate assignments. We consider the gate assignment problem under uncertainty in flight arrival and departure times and develop stochastic programming models incorporating robustness measures based on the number of conflicting flights, idle and buffer times. The proposed models are formulated as large-scale mixed-integer programming problems and tabu search algorithms are implemented to obtain assignments of reasonable quality. We conduct a computational study to analyze the proposed alternate models and show the effectiveness of the solution methods.
---
paper_title: A gate reassignment framework for real time flight delays

paper_content:

Flight delays (such as early or late arrivals and late departures) are a frequent occurrence in actual day to day airport operations and it is often not possible to assign such flights to their original gates. Flight delay information may also vary with time. As a consequence, the airport authority needs to reassign flights to different gates in real-time. The traditional manual flight reassignment method is neither efficient nor effective in cases with variable flight delay information, and the reassignment is frequently time constrained. Consequently, in this study the goal is to develop a gate reassignment framework, and a systematic computerized tool, for repeatedly handling gate reassignments given varied flight delay information. The results of a test case related to Taiwan international airport operations, show that the proposed framework performs well.
---
paper_title: Optimizing Gate Assignments at Airport Terminals

paper_content:

The airport flight-to-gate assignment problem is solved using two methods: (1) a linear programming relaxation of an integer program formulation and (2) a heuristic. The objective is to minimize passenger walking distances within the airport terminal area through a judicious gate assignment policy. An actual flight schedule for an average day at Toronto International Airport is used to compare existing walking distances, obtained from the original assignment, with results from the two methods. The results indicated that the original assignment had a 32% higher average per passenger walking distance than the minimum possible distance given by the LP solution. The heuristic’s performance was near optimal; it gave an average walking distance which was only 3.9% greater than the minimum. Computation times for the heuristic are 3.4 CPU seconds per run, while the linear program consumes 386 seconds per run on an IBM 370/168. In addition, if the heuristic is solved first and its solution is used as an initial feasible basis for the LP relaxation of the IP, the total CPU used to obtain optimality is reduced to 42 seconds.
---
paper_title: A heuristic approach for airport gate assignments for stochastic flight delays

paper_content:

To make good flight to gate assignments, not only do all the relevant constraints have to be considered, but stochastic flight delays that occur in actual operations also have to be taken into account. In past research, airport gate assignments and stochastic disturbances have often been handled in the planning and the real-time stages separately, meaning that the interrelationship between these stages, as affected by such delays, has been neglected. In this research, we develop a heuristic approach embedded in a framework designed to help the airport authorities make airport gate assignments that are sensitive to stochastic flight delays. The framework includes three components, a stochastic gate assignment model, a real-time assignment rule, and two penalty adjustment methods. The test results are based on data supplied by a Taiwan international airport, and show that the proposed framework performs better than the current manual assignment process and the traditional deterministic model.
---
paper_title: Fuzzy model and optimization for airport gate assignment problem

paper_content:

Gate assignment is an important decision making problem which involves multiple and conflict objectives in airport. In this paper, fuzzy model is proposed to handle two main objectives, minimizing the total walking distance for passengers and maximizing the robustness of assignment. The idle times of flight-to-gate are regarded as fuzzy variables, and whose membership degrees are used to express influence on robustness of assignment. Adjustment function on membership degree is introduced to transfer two objectives into one. Modified genetic algorithm is adopted to optimize the NP-hard problem. Finally, illustrative example is given to evaluate the performance of fuzzy model. Three distribution functions are tested?? and comparison with the method of fixed buffer time is given. Simulation results demonstrate the feasibility and effectiveness of proposed fuzzy method.
---
paper_title: Automatic assignment of aircraft to gates at a terminal

paper_content:

Abstract The assignment of airplanes to terminal gates should take into account not only the physical constraints of the terminal, but also the incoveniences suffered by the transporter and the travellers when a craft has to be serviced away from the terminal. With this in mind, it is preferable that the number of airplanes assigned to a service area away from the terminal, rather than directly placed at a terminal gate, be minimized. Once this problem has been formulated in the form of a linear programming model with binary variables, a heuristic method is applied to find the best solution.
---
paper_title: A simulation framework for evaluating airport gate assignments

paper_content:

There are many factors that affect gate assignments in an airport's operations. These factors include static gate assignments, stochastic flight delays and real-time gate assignments. Most research on gate assignments in the past has laid stress on improving the performance of static gate assignments. None has analyzed the interrelationship between static gate assignments and real-time gate assignments as affected by the stochastic flight delays that occur in real operations. In addition, none has designed flexible buffer times for static gate assignments to effectively absorb stochastic delays in real-time gate assignments. This research proposes a simulation framework, that is not only able to analyze the effects of stochastic flight delays on static gate assignments, but can also evaluate flexible buffer times and real-time gate assignment rules. Finally, a simulation based on Chiang Kai-Shek airport operations is performed to evaluate the simulation framework.
---
paper_title: Aircraft and gate scheduling optimization at airports

paper_content:

In this paper, we consider the over-constrained airport gate assignment problem where the number of flights exceeds the number of gates available, and where the objectives are to minimize the number of ungated flights and the total walking distances or connection. We design a greedy algorithm and use a tabu search meta-heuristic to solve the problem. The greedy algorithm minimizes ungated flights while providing initial feasible solutions while we devise a new neighborhood search technique, the interval exchange move, which allows us flexibility in seeking good solutions, especially in case when flight schedules are dense in time. Experiment conducted give good results.
---
paper_title: DEVELOPMENT AND APPLICATION OF HYPERHEURISTICS TO PERSONNEL SCHEDULING

paper_content:

This thesis is concerned with the investigation of hyperheuristic techniques. Hyperheuristics are heuristics which choose heuristics in order to solve a given optimisation problem. In this thesis we investigate and develop a number of hyperheuristic techniques including a hyperheuristic which uses a choice function in order to select which low-level heuristic to apply at each decision point. We demonstrate the effectiveness of our hyperheuristics by means of three personnel scheduling problems taken from the real world. For each application problem, we apply our hyperheuristics to several instances and compare our results with those of other heuristic methods. For all problems, the choice function hyperheuristic appears to be superior to other hyperheuristics considered. It also produces results competitive with those obtained using other sophisticated means. It is hoped that ::: - hyperheuristics can produce solutions of good quality, often competitive with those of modern heuristic techniques, within a short amount of implementation and development time, using only simple and easy-to-implement low-level heuristics. ::: ::: - hyperheuristics are easily re-usable methods as opposed to some metaheuristic methods which tend to use extensive problem-specific information in order to arrive at good solutions. ::: ::: ::: These two latter points constitute the main contributions of this thesis.
---
paper_title: A conceptual solution to the aircraft gate assignment problem using 0,1 linear programming

paper_content:

Abstract The U.S. commercial airline movement to “hub” operations has increased rapidly over the past several years. This trend will grow with the introduction of the Wayport concept. These giant “people exchange” facilities will feature multiple runways and massive concourses. While the Wayport developers may automate the ground movement of passengers, the sheer size of the facilities and the anticipated close scheduling of flights will confront the passenger with a problem of new dimension in getting from arrival gate to departure gate. One thing that could help alleviate the situation would be “sensible” assignment of flights to gates - sensible in that the assignment would take into account the communion of interest of the passengers. Other things being equal, the positioning of incoming flights should take into account the distribution of passengers among connecting flights. The larger the number of passengers arriving on flight X for destination A, the closer flight X should be positioned to the flight departing for A. This inquiry looks conceptually at this problem, reducing the distance passengers must walk from gate to gate. The criterion selected is minimization of the total passenger-distance travel for a given arrival-departure cycle. The problem can be conveniently cast as a 0,1 Linear Programming (LP) problem. The author discusses derivation of problem parameters and then solves several representative problems. A unique feature of the LP approach is the availability with the optimal solution of cost factors and assignments for suboptimal solutions. Minor changes in the input data do not require reworking the problem. Although the solution is characterized as conceptual, some ideas are given for practical use of the solution methodology in a dynamic airport environment.
---
paper_title: An efficient Genetic Algorithm with uniform crossover for the multi-objective Airport Gate Assignment Problem

paper_content:

Genetic Algorithms (GAs) have a good potential of solving the Gate Assignment Problem (GAP) at airport terminals, and the design of feasible and efficient evolutionary operators, particularly, the crossover operator, is crucial to successful implementations. This paper reports an application of GAs to the multi-objective GAP. The relative positions between aircraft rather than their absolute positions in the queues to gates is used to construct chromosomes in a novel encoding scheme, and a new uniform crossover operator, free of feasibility problems, is then proposed, which is effective and efficient to identify, inherit and protect useful common sub-queues to gates during evolution. Extensive simulation studies illustrate the advantages of the proposed GA scheme with uniform crossover operator.
---
paper_title: GENETIC ALGORITHM APPROACH TO AIRCRAFT GATE REASSIGNMENT PROBLEM

paper_content:

The aircraft gate reassignment problem occurs when the departure of an incoming aircraft is delayed or a delay occurs in flight. If the delay is significant enough to delay the arrival of subsequent incoming aircraft at the assigned gate, the airline must revise the gate assignments to minimize extra delay times. This paper describes a genetic algorithm approach to solving the gate reassignment problem. By using a global search technique on quantified information, this genetic algorithm approach can efficiently find minimum extra delayed time solutions that are as effective or more effective than solutions generated by experienced gate managers.
---
paper_title: Models and a genetic algorithm for static aircraft-gate assignment problem

paper_content:

Assigning aircraft to available gates at an airport can have a major impact on the efficiency of flight schedules and on the level of passenger satisfaction with the service. Unexpected changes, due to air traffic delays, severe weather conditions, or equipment failures, may disrupt the initial assignments and compound the difficulty of maintaining smooth station operations. Recently, mathematical models and procedures (optimal and heuristic) have been proposed to provide solutions with minimum dispersion of idle time periods for static aircraft-gate assignment problems. This paper introduces a unified framework to specifically treat the objective functions of the previous models. It also provides linear representations of these models and identifies the conditions under which the optimal solutions can be obtained in polynomial time. Furthermore, a genetic algorithm utilizing problem specific knowledge is proposed to provide effective alternative solutions.
---
paper_title: A Bundle Algorithm Approach for the Aircraft Schedule Recovery Problem During Hub Closures

paper_content:

A bundle algorithm is presented to solve a multicommodity network model for determining a recoveryplan for a single carrier with multiple fleets following a hub closure. The algorithm is shown to provide feasible near-optimal solutions much more quickly than can be obtained using a standard commercial mixed-integer programming code (CPLEX). In this application, a bundle method is used to solve a Lagrangian relaxation of the integer programming formulation. The full algorithm includes heuristic techniques for finding feasible solutions from the solutions to the relaxed problems. Extensive computations were performed using data from Continental Airlines. The results show that the proposed approach provides faster times to optimality in some cases and always obtains feasible, near-optimal solutions for larger problems much more quickly than can be found using CPLEX. In addition, while a standard commercial code will provide only one solution, this approach provides multiple high-quality solutions.
---
paper_title: Optimized Assignment of Civil Airport Gate

paper_content:

Airport gate assignment is to appoint a gate for the arrival or leave flight to ensure that the flight is on schedule. Assigning the airport gate with high efficiency and reason is a key task among the airport ground busy works. A model of airport gate assignment based on the embedded analysis of the actual airport gate assignment for a busy domestic civil airport is proposed. The objective of the problem is to maximize the sum of the all products of the flight eigenvalue and the gate eigenvalue which the flight assigned. The flight type and the flight downtime and the number of airline passengers are considered in the flight eigenvalue and the ease of the gate is considered in the gate eigenvalue. The solution space of the problem based on the dynamic scheduling parallel machines and a directed graph model are given. The solving method based on the branch and bound algorithm is designed. Simulation result shows the validity of this model and algorithm.
---
paper_title: Optimizing Gate Assignments at Airport Terminals

paper_content:

The airport flight-to-gate assignment problem is solved using two methods: (1) a linear programming relaxation of an integer program formulation and (2) a heuristic. The objective is to minimize passenger walking distances within the airport terminal area through a judicious gate assignment policy. An actual flight schedule for an average day at Toronto International Airport is used to compare existing walking distances, obtained from the original assignment, with results from the two methods. The results indicated that the original assignment had a 32% higher average per passenger walking distance than the minimum possible distance given by the LP solution. The heuristic’s performance was near optimal; it gave an average walking distance which was only 3.9% greater than the minimum. Computation times for the heuristic are 3.4 CPU seconds per run, while the linear program consumes 386 seconds per run on an IBM 370/168. In addition, if the heuristic is solved first and its solution is used as an initial feasible basis for the LP relaxation of the IP, the total CPU used to obtain optimality is reduced to 42 seconds.
---
paper_title: Models and a genetic algorithm for static aircraft-gate assignment problem

paper_content:

Assigning aircraft to available gates at an airport can have a major impact on the efficiency of flight schedules and on the level of passenger satisfaction with the service. Unexpected changes, due to air traffic delays, severe weather conditions, or equipment failures, may disrupt the initial assignments and compound the difficulty of maintaining smooth station operations. Recently, mathematical models and procedures (optimal and heuristic) have been proposed to provide solutions with minimum dispersion of idle time periods for static aircraft-gate assignment problems. This paper introduces a unified framework to specifically treat the objective functions of the previous models. It also provides linear representations of these models and identifies the conditions under which the optimal solutions can be obtained in polynomial time. Furthermore, a genetic algorithm utilizing problem specific knowledge is proposed to provide effective alternative solutions.
---
paper_title: Assigning arriving flights at an airport to the available gates

paper_content:

Unexpected changes in the flight schedules may disrupt the initial aircraft-gate assignments, and result in congestions and delays in getting aircraft onto gates. A mathematical model is developed to assign the flights with the minimum range of unutilised time periods of gates, subject to the level of service offered to passengers and other physical and managerial considerations. (The assignments are expected to be flexible enough to absorb the minor modifications in the flight schedules.) Interactive optimum and heuristic procedures, both utilising lower bounds on the ranges of future solutions, are proposed to cope with the major changes in disrupting the initial gate-assignments. Over randomly generated schedules, 74 flights can be optimally assigned to seven gates within 17 seconds when the gates are re-utilised within 30 minutes after each departure. The heuristic reaches the optimal solution after evaluating at most 20 partial solutions at one level. Over data obtained from Riyadh’s International Airport, the heuristic outperforms the existing practice: On average, 72.03% and 54.28% improvements are obtained on the number of remote served aircraft and towed aircraft, respectively.
---
paper_title: Stochastic optimization models for the airport gate assignment problem

paper_content:

Uncertainties inherent in the airport traffic may lead to the unavailability of gates for accommodating scheduled flights. Incorporating random disruptions is crucial in constructing effective flight-gate assignments. We consider the gate assignment problem under uncertainty in flight arrival and departure times and develop stochastic programming models incorporating robustness measures based on the number of conflicting flights, idle and buffer times. The proposed models are formulated as large-scale mixed-integer programming problems and tabu search algorithms are implemented to obtain assignments of reasonable quality. We conduct a computational study to analyze the proposed alternate models and show the effectiveness of the solution methods.
---
paper_title: Airport Gate Assignment A Hybrid Model and Implementation

paper_content:

With the rapid development of airlines, airports today become much busier and more complicated than previous days. During airlines daily operations, assigning the available gates to the arriving aircrafts based on the fixed schedule is a very important issue, which motivates researchers to study and solve Airport Gate Assignment Problems (AGAP) with all kinds of state-of-the-art combinatorial optimization techniques. In this paper, we study the AGAP and propose a novel hybrid mathematical model based on the method of constraint programming and 0 - 1 mixed-integer programming. With the objective to minimize the number of gate conflicts of any two adjacent aircrafts assigned to the same gate, we build a mathematical model with logical constraints and the binary constraints. For practical considerations, the potential objective of the model is also to minimize the number of gates that airlines must lease or purchase in order to run their business smoothly. We implement the model in the Optimization Programming Language (OPL) and carry out empirical studies with the data obtained from online timetable of Continental Airlines, Houston Gorge Bush Intercontinental Airport IAH, which demonstrate that our model can provide an efficient evaluation criteria for the airline companies to estimate the efficiency of their current gate assignments.
---
paper_title: Models and a genetic algorithm for static aircraft-gate assignment problem

paper_content:

Assigning aircraft to available gates at an airport can have a major impact on the efficiency of flight schedules and on the level of passenger satisfaction with the service. Unexpected changes, due to air traffic delays, severe weather conditions, or equipment failures, may disrupt the initial assignments and compound the difficulty of maintaining smooth station operations. Recently, mathematical models and procedures (optimal and heuristic) have been proposed to provide solutions with minimum dispersion of idle time periods for static aircraft-gate assignment problems. This paper introduces a unified framework to specifically treat the objective functions of the previous models. It also provides linear representations of these models and identifies the conditions under which the optimal solutions can be obtained in polynomial time. Furthermore, a genetic algorithm utilizing problem specific knowledge is proposed to provide effective alternative solutions.
---
paper_title: Aircraft and gate scheduling optimization at airports

paper_content:

In this paper, we consider the over-constrained airport gate assignment problem where the number of flights exceeds the number of gates available, and where the objectives are to minimize the number of ungated flights and the total walking distances or connection. We design a greedy algorithm and use a tabu search meta-heuristic to solve the problem. The greedy algorithm minimizes ungated flights while providing initial feasible solutions while we devise a new neighborhood search technique, the interval exchange move, which allows us flexibility in seeking good solutions, especially in case when flight schedules are dense in time. Experiment conducted give good results.
---
paper_title: Procedures for providing robust gate assignments for arriving aircrafts

paper_content:

Abstract Assigning commercial service aircrafts to the available gates at an airport depends on flights scheduled, their actual behavior relative to those schedules, aircraft servicing requirements and capacities of ramp facilities. Flight delays, severe weather, or equipment failures can disrupt the planned schedules, and compound the difficulty of maintaining smooth station operations. A mixed-binary mathematical model with a quadratic function for minimizing the variance of idle times at the gates is proposed to make the initial assignments insensitive to variations in flight schedules. Experimental results with a branch and bound algorithm indicate that more computational effort is required to assign flights optimally over low utilized gates. Furthermore, a heuristic employing the priority function which considers additionally the possible idle times from the future assignments outperforms the others, significantly. Over the real data obtained from the Saudi Arabian Airlines, average 87.4% and 76.2% of improvements can be obtained on the number of aircrafts assigned initially to remote area and that towed from their assigned gates during the real-time implementation, respectively.
---
paper_title: The airport gate assignment problem: mathematical model and a tabu search algorithm

paper_content:

Considers an airport gate assignment problem that dynamically assigns airport gates to scheduled flights based on passengers' daily origin and destination flow data. The objective of the problem is to minimize the overall connection times during which passengers walk to catch their connection flights. We formulate this problem as a mixed 0-1 quadratic integer programming problem and then reformulate it as a mixed 0-1 integer problem with a linear objective function and constraints. We design a simple tabu search meta-heuristic to solve the problem. The algorithm exploits the special properties of different types of neighborhood moves, and create highly effective candidate list strategies. We also address issues of tabu short-term memory, dynamic tabu tenure, aspiration rules, and various intensification and diversification strategies. Preliminary computational experiments are conducted, and the results are presented and analyzed.
---
paper_title: New heuristics for over-constrained flight to gate assignments

paper_content:

We consider the over-constrained Airport Gate Assignment Problem where the number of flights exceed the number of gates available, and where the objectives are to minimize the number of ungated flights and the total walking distances. The problem is formulated as a binary quadratic programming problem. We design a greedy algorithm and use a Tabu Search meta-heuristic to solve the problem. The greedy algorithm minimizes ungated flights while we devise a new neighbourhood search technique, the Interval Exchange Move, which allows us flexibility in seeking good solutions, especially when flight schedules are dense in time. Experiments conducted give good results.
---
paper_title: Optimization of multiple objective gate assignments

paper_content:

This paper proposes a multiple objective model to help airport authorities to efficiently and effectively solve gate assignment problems. The model is formulated as a multiple objective zero-one integer program. To efficiently solve large-scale problems in practice, we used the weighting method, the column generation approach, the simplex method and the branch-and-bound technique to develop a solution algorithm. To test how well the model may be applied in actual operations, a case study regarding the operation of Chiang Kai-Shek (CKS) Airport was performed. The results show that the model could be useful for actual operations.
---
paper_title: An efficient Genetic Algorithm with uniform crossover for the multi-objective Airport Gate Assignment Problem

paper_content:

Genetic Algorithms (GAs) have a good potential of solving the Gate Assignment Problem (GAP) at airport terminals, and the design of feasible and efficient evolutionary operators, particularly, the crossover operator, is crucial to successful implementations. This paper reports an application of GAs to the multi-objective GAP. The relative positions between aircraft rather than their absolute positions in the queues to gates is used to construct chromosomes in a novel encoding scheme, and a new uniform crossover operator, free of feasibility problems, is then proposed, which is effective and efficient to identify, inherit and protect useful common sub-queues to gates during evolution. Extensive simulation studies illustrate the advantages of the proposed GA scheme with uniform crossover operator.
---
paper_title: On interfacing multiobjective optimisation models: the case of the airport gate assignment problem

paper_content:

We present a method to capture decision maker's preferences in multiobjective problems and we discuss its use as a base for a decision maker -- multiobjective optimization model interface. We illustrate the idea on a small but illustrative numerical example of the airport gate assignment problem.
---
paper_title: A heuristic approach for airport gate assignments for stochastic flight delays

paper_content:

To make good flight to gate assignments, not only do all the relevant constraints have to be considered, but stochastic flight delays that occur in actual operations also have to be taken into account. In past research, airport gate assignments and stochastic disturbances have often been handled in the planning and the real-time stages separately, meaning that the interrelationship between these stages, as affected by such delays, has been neglected. In this research, we develop a heuristic approach embedded in a framework designed to help the airport authorities make airport gate assignments that are sensitive to stochastic flight delays. The framework includes three components, a stochastic gate assignment model, a real-time assignment rule, and two penalty adjustment methods. The test results are based on data supplied by a Taiwan international airport, and show that the proposed framework performs better than the current manual assignment process and the traditional deterministic model.
---
paper_title: Fuzzy model and optimization for airport gate assignment problem

paper_content:

Gate assignment is an important decision making problem which involves multiple and conflict objectives in airport. In this paper, fuzzy model is proposed to handle two main objectives, minimizing the total walking distance for passengers and maximizing the robustness of assignment. The idle times of flight-to-gate are regarded as fuzzy variables, and whose membership degrees are used to express influence on robustness of assignment. Adjustment function on membership degree is introduced to transfer two objectives into one. Modified genetic algorithm is adopted to optimize the NP-hard problem. Finally, illustrative example is given to evaluate the performance of fuzzy model. Three distribution functions are tested?? and comparison with the method of fixed buffer time is given. Simulation results demonstrate the feasibility and effectiveness of proposed fuzzy method.
---
paper_title: A stochastic neighborhood search approach for airport gate assignment problem

paper_content:

An appropriate and efficient gate assignment is of great importance in airports since it plays a major role in the revenue obtained from the airport operations. In this study, we have focused mainly on maximum gate employment, or in other words minimize the total duration of un-gated flights. Here, we propose a method that combines the benefits of heuristic approaches with some stochastic approach instead of using a purely probabilistic approach to top-down solution of the problem. The heuristic approaches are usually used in order to provide a fast solution of the problem and later stochastic searches are used in order to ameliorate the previous results of the heuristic approach whenever possible. The proposed method generates an assignment order for the whole planes that corresponds to assignment priority. The ordering process is followed by the allocation step. Since, in practice, each airport has its own physical architecture, there have been arisen many constraints mainly concerning airplane types and parking lots in this step. Sequentially handling the plane ordering and allocation phases provides us great modularity in handling the constraints. The effectiveness of the proposed methodology has been tried to be illustrated firstly on fictively generated flight schedule data and secondly on the real world data obtained from a real world application developed for Istanbul Ataturk Airport.
---
paper_title: Stochastic optimization models for the airport gate assignment problem

paper_content:

Uncertainties inherent in the airport traffic may lead to the unavailability of gates for accommodating scheduled flights. Incorporating random disruptions is crucial in constructing effective flight-gate assignments. We consider the gate assignment problem under uncertainty in flight arrival and departure times and develop stochastic programming models incorporating robustness measures based on the number of conflicting flights, idle and buffer times. The proposed models are formulated as large-scale mixed-integer programming problems and tabu search algorithms are implemented to obtain assignments of reasonable quality. We conduct a computational study to analyze the proposed alternate models and show the effectiveness of the solution methods.
---
paper_title: Optimizing gate assignments at airport terminals

paper_content:

The assignment of aircraft arriving on schedule to available gates is a major issue during the daily airline operations. The Gate Assignment Problem (GAP) is an easily-understood but difficult to solve problem. An important issue in GAP is to minimize the distance a passenger is required to walk inside the terminal to reach his or her departure gate. The total passenger walking distance is based on the passenger transfer volume between every pair of aircrafts and the distance between every pair of gates. Therefore, the problem of assigning gates to arriving and departing flights at an airport is a Quadratic Assignment Problem (QAP), which is a difficult problem to solve. Recently, integer programming (IP), simulation, and expert systems have been applied to the GAP. A new integer programming formulation of the gate assignment problem is presented. An efficient heuristic solution procedure for solving the problem is also proposed. The performance of this solution approach is evaluated in a variety of test problems, and is compared to the optimal solutions obtained using CPLEX in certain test problems. The proposed heuristic solution approach proves to be an efficient method for obtaining good solutions for large scale gate assignment problems in a very reasonable computation time.
---
paper_title: Multicriteria airport gate assignment and Pareto simulated annealing

paper_content:

This paper addresses an airport gate assignment problem with multiple objectives. The objectives are to minimize the number of ungated flights and the total passenger walking distances or connection times as well as to maximize the total gate assignment preferences. The problem examined is an integer program with multiple objectives (one of them being quadratic) and quadratic constraints. Of course, such a problem is inherently difficult to solve. We tackle the problem by Pareto simulated annealing in order to get a representative approximation for the Pareto front. Results of computational experiments are presented. To the best of our knowledge, this is the first attempt to consider the airport gate assignment problem with multiple objectives.
---
paper_title: Optimized Assignment of Civil Airport Gate

paper_content:

Airport gate assignment is to appoint a gate for the arrival or leave flight to ensure that the flight is on schedule. Assigning the airport gate with high efficiency and reason is a key task among the airport ground busy works. A model of airport gate assignment based on the embedded analysis of the actual airport gate assignment for a busy domestic civil airport is proposed. The objective of the problem is to maximize the sum of the all products of the flight eigenvalue and the gate eigenvalue which the flight assigned. The flight type and the flight downtime and the number of airline passengers are considered in the flight eigenvalue and the ease of the gate is considered in the gate eigenvalue. The solution space of the problem based on the dynamic scheduling parallel machines and a directed graph model are given. The solving method based on the branch and bound algorithm is designed. Simulation result shows the validity of this model and algorithm.
---
paper_title: Flight gate scheduling with respect to a reference schedule

paper_content:

This paper considers the problem of assigning flights to airport gates. We examine the general case in which an aircraft serving a flight may be assigned to different gates for arrival and departure processing and for optional intermediate parking. Restrictions to this assignment include gate closures and shadow restrictions, i.e., the situation where certain gate assignments may cause blocking of neighboring gates. The objectives include maximization of the total assignment preference score, a minimal number of unassigned flights during overload periods, minimization of the number of tows, maximization of a robustness measure as well as a minimal deviation from a given reference schedule. We show that in case of a one period time horizon this objective can easily be integrated into our existing model based on the Clique Partitioning Problem. Furthermore we present a heuristic algorithm to solve the problem for multiple periods. Copyright Springer Science+Business Media, LLC 2012
---
paper_title: Multi-commodity flow network model of the flight gate assignment problem

paper_content:

The flight gate assignment problem is encountered by gate managers at an airport on a periodic basis. This assignment should be made so as to balance carrier efficiency and passenger comfort, while providing buffers for unexpected events that cause assignment disruptions. In this paper, a binary integer multi-commodity gate flow network model is presented with the objective of minimizing the fuel burn cost of aircraft taxi by type and expected passenger discomfort for ''tight'' connections as a function of inter-gate distance and connection time. This approach is shown to be computationally efficient within a decomposition approach for large problem instances. A numerical application of this approach is given for the gating of Continental Airlines at George W. Bush Intercontinental Airport in Houston (IAH).
---
paper_title: Finding a robust assignment of flights to gates at Amsterdam Airport Schiphol

paper_content:

In this paper we investigate the gate assignment problem as it appears at Amsterdam Airport Schiphol (AAS). Currently, the gate planners spend many hours on adjusting the automatically generated planning during the day of operation to make it proof against small deviations from the schedule. To alleviate this problem, we aim at finding a robust solution, given the planned arrivals and departures for the next day.
---
paper_title: A stochastic neighborhood search approach for airport gate assignment problem

paper_content:

An appropriate and efficient gate assignment is of great importance in airports since it plays a major role in the revenue obtained from the airport operations. In this study, we have focused mainly on maximum gate employment, or in other words minimize the total duration of un-gated flights. Here, we propose a method that combines the benefits of heuristic approaches with some stochastic approach instead of using a purely probabilistic approach to top-down solution of the problem. The heuristic approaches are usually used in order to provide a fast solution of the problem and later stochastic searches are used in order to ameliorate the previous results of the heuristic approach whenever possible. The proposed method generates an assignment order for the whole planes that corresponds to assignment priority. The ordering process is followed by the allocation step. Since, in practice, each airport has its own physical architecture, there have been arisen many constraints mainly concerning airplane types and parking lots in this step. Sequentially handling the plane ordering and allocation phases provides us great modularity in handling the constraints. The effectiveness of the proposed methodology has been tried to be illustrated firstly on fictively generated flight schedule data and secondly on the real world data obtained from a real world application developed for Istanbul Ataturk Airport.
---
paper_title: Stochastic optimization models for the airport gate assignment problem

paper_content:

Uncertainties inherent in the airport traffic may lead to the unavailability of gates for accommodating scheduled flights. Incorporating random disruptions is crucial in constructing effective flight-gate assignments. We consider the gate assignment problem under uncertainty in flight arrival and departure times and develop stochastic programming models incorporating robustness measures based on the number of conflicting flights, idle and buffer times. The proposed models are formulated as large-scale mixed-integer programming problems and tabu search algorithms are implemented to obtain assignments of reasonable quality. We conduct a computational study to analyze the proposed alternate models and show the effectiveness of the solution methods.
---
paper_title: Multicriteria airport gate assignment and Pareto simulated annealing

paper_content:

This paper addresses an airport gate assignment problem with multiple objectives. The objectives are to minimize the number of ungated flights and the total passenger walking distances or connection times as well as to maximize the total gate assignment preferences. The problem examined is an integer program with multiple objectives (one of them being quadratic) and quadratic constraints. Of course, such a problem is inherently difficult to solve. We tackle the problem by Pareto simulated annealing in order to get a representative approximation for the Pareto front. Results of computational experiments are presented. To the best of our knowledge, this is the first attempt to consider the airport gate assignment problem with multiple objectives.
---
paper_title: Optimizing gate assignments at airport terminals

paper_content:

The assignment of aircraft arriving on schedule to available gates is a major issue during the daily airline operations. The Gate Assignment Problem (GAP) is an easily-understood but difficult to solve problem. An important issue in GAP is to minimize the distance a passenger is required to walk inside the terminal to reach his or her departure gate. The total passenger walking distance is based on the passenger transfer volume between every pair of aircrafts and the distance between every pair of gates. Therefore, the problem of assigning gates to arriving and departing flights at an airport is a Quadratic Assignment Problem (QAP), which is a difficult problem to solve. Recently, integer programming (IP), simulation, and expert systems have been applied to the GAP. A new integer programming formulation of the gate assignment problem is presented. An efficient heuristic solution procedure for solving the problem is also proposed. The performance of this solution approach is evaluated in a variety of test problems, and is compared to the optimal solutions obtained using CPLEX in certain test problems. The proposed heuristic solution approach proves to be an efficient method for obtaining good solutions for large scale gate assignment problems in a very reasonable computation time.
---
paper_title: Airport Gate Assignment A Hybrid Model and Implementation

paper_content:

With the rapid development of airlines, airports today become much busier and more complicated than previous days. During airlines daily operations, assigning the available gates to the arriving aircrafts based on the fixed schedule is a very important issue, which motivates researchers to study and solve Airport Gate Assignment Problems (AGAP) with all kinds of state-of-the-art combinatorial optimization techniques. In this paper, we study the AGAP and propose a novel hybrid mathematical model based on the method of constraint programming and 0 - 1 mixed-integer programming. With the objective to minimize the number of gate conflicts of any two adjacent aircrafts assigned to the same gate, we build a mathematical model with logical constraints and the binary constraints. For practical considerations, the potential objective of the model is also to minimize the number of gates that airlines must lease or purchase in order to run their business smoothly. We implement the model in the Optimization Programming Language (OPL) and carry out empirical studies with the data obtained from online timetable of Continental Airlines, Houston Gorge Bush Intercontinental Airport IAH, which demonstrate that our model can provide an efficient evaluation criteria for the airline companies to estimate the efficiency of their current gate assignments.
---
paper_title: Optimization of multiple objective gate assignments

paper_content:

This paper proposes a multiple objective model to help airport authorities to efficiently and effectively solve gate assignment problems. The model is formulated as a multiple objective zero-one integer program. To efficiently solve large-scale problems in practice, we used the weighting method, the column generation approach, the simplex method and the branch-and-bound technique to develop a solution algorithm. To test how well the model may be applied in actual operations, a case study regarding the operation of Chiang Kai-Shek (CKS) Airport was performed. The results show that the model could be useful for actual operations.
---
paper_title: A conceptual solution to the aircraft gate assignment problem using 0,1 linear programming

paper_content:

Abstract The U.S. commercial airline movement to “hub” operations has increased rapidly over the past several years. This trend will grow with the introduction of the Wayport concept. These giant “people exchange” facilities will feature multiple runways and massive concourses. While the Wayport developers may automate the ground movement of passengers, the sheer size of the facilities and the anticipated close scheduling of flights will confront the passenger with a problem of new dimension in getting from arrival gate to departure gate. One thing that could help alleviate the situation would be “sensible” assignment of flights to gates - sensible in that the assignment would take into account the communion of interest of the passengers. Other things being equal, the positioning of incoming flights should take into account the distribution of passengers among connecting flights. The larger the number of passengers arriving on flight X for destination A, the closer flight X should be positioned to the flight departing for A. This inquiry looks conceptually at this problem, reducing the distance passengers must walk from gate to gate. The criterion selected is minimization of the total passenger-distance travel for a given arrival-departure cycle. The problem can be conveniently cast as a 0,1 Linear Programming (LP) problem. The author discusses derivation of problem parameters and then solves several representative problems. A unique feature of the LP approach is the availability with the optimal solution of cost factors and assignments for suboptimal solutions. Minor changes in the input data do not require reworking the problem. Although the solution is characterized as conceptual, some ideas are given for practical use of the solution methodology in a dynamic airport environment.
---
paper_title: Assigning arriving flights at an airport to the available gates

paper_content:

Unexpected changes in the flight schedules may disrupt the initial aircraft-gate assignments, and result in congestions and delays in getting aircraft onto gates. A mathematical model is developed to assign the flights with the minimum range of unutilised time periods of gates, subject to the level of service offered to passengers and other physical and managerial considerations. (The assignments are expected to be flexible enough to absorb the minor modifications in the flight schedules.) Interactive optimum and heuristic procedures, both utilising lower bounds on the ranges of future solutions, are proposed to cope with the major changes in disrupting the initial gate-assignments. Over randomly generated schedules, 74 flights can be optimally assigned to seven gates within 17 seconds when the gates are re-utilised within 30 minutes after each departure. The heuristic reaches the optimal solution after evaluating at most 20 partial solutions at one level. Over data obtained from Riyadh’s International Airport, the heuristic outperforms the existing practice: On average, 72.03% and 54.28% improvements are obtained on the number of remote served aircraft and towed aircraft, respectively.
---
paper_title: Optimized Assignment of Civil Airport Gate

paper_content:

Airport gate assignment is to appoint a gate for the arrival or leave flight to ensure that the flight is on schedule. Assigning the airport gate with high efficiency and reason is a key task among the airport ground busy works. A model of airport gate assignment based on the embedded analysis of the actual airport gate assignment for a busy domestic civil airport is proposed. The objective of the problem is to maximize the sum of the all products of the flight eigenvalue and the gate eigenvalue which the flight assigned. The flight type and the flight downtime and the number of airline passengers are considered in the flight eigenvalue and the ease of the gate is considered in the gate eigenvalue. The solution space of the problem based on the dynamic scheduling parallel machines and a directed graph model are given. The solving method based on the branch and bound algorithm is designed. Simulation result shows the validity of this model and algorithm.
---
paper_title: Procedures for providing robust gate assignments for arriving aircrafts

paper_content:

Abstract Assigning commercial service aircrafts to the available gates at an airport depends on flights scheduled, their actual behavior relative to those schedules, aircraft servicing requirements and capacities of ramp facilities. Flight delays, severe weather, or equipment failures can disrupt the planned schedules, and compound the difficulty of maintaining smooth station operations. A mixed-binary mathematical model with a quadratic function for minimizing the variance of idle times at the gates is proposed to make the initial assignments insensitive to variations in flight schedules. Experimental results with a branch and bound algorithm indicate that more computational effort is required to assign flights optimally over low utilized gates. Furthermore, a heuristic employing the priority function which considers additionally the possible idle times from the future assignments outperforms the others, significantly. Over the real data obtained from the Saudi Arabian Airlines, average 87.4% and 76.2% of improvements can be obtained on the number of aircrafts assigned initially to remote area and that towed from their assigned gates during the real-time implementation, respectively.
---
paper_title: The airport gate assignment problem: mathematical model and a tabu search algorithm

paper_content:

Considers an airport gate assignment problem that dynamically assigns airport gates to scheduled flights based on passengers' daily origin and destination flow data. The objective of the problem is to minimize the overall connection times during which passengers walk to catch their connection flights. We formulate this problem as a mixed 0-1 quadratic integer programming problem and then reformulate it as a mixed 0-1 integer problem with a linear objective function and constraints. We design a simple tabu search meta-heuristic to solve the problem. The algorithm exploits the special properties of different types of neighborhood moves, and create highly effective candidate list strategies. We also address issues of tabu short-term memory, dynamic tabu tenure, aspiration rules, and various intensification and diversification strategies. Preliminary computational experiments are conducted, and the results are presented and analyzed.
---
paper_title: Optimizing Gate Assignments at Airport Terminals

paper_content:

The airport flight-to-gate assignment problem is solved using two methods: (1) a linear programming relaxation of an integer program formulation and (2) a heuristic. The objective is to minimize passenger walking distances within the airport terminal area through a judicious gate assignment policy. An actual flight schedule for an average day at Toronto International Airport is used to compare existing walking distances, obtained from the original assignment, with results from the two methods. The results indicated that the original assignment had a 32% higher average per passenger walking distance than the minimum possible distance given by the LP solution. The heuristic’s performance was near optimal; it gave an average walking distance which was only 3.9% greater than the minimum. Computation times for the heuristic are 3.4 CPU seconds per run, while the linear program consumes 386 seconds per run on an IBM 370/168. In addition, if the heuristic is solved first and its solution is used as an initial feasible basis for the LP relaxation of the IP, the total CPU used to obtain optimality is reduced to 42 seconds.
---
paper_title: A simulation framework for evaluating airport gate assignments

paper_content:

There are many factors that affect gate assignments in an airport's operations. These factors include static gate assignments, stochastic flight delays and real-time gate assignments. Most research on gate assignments in the past has laid stress on improving the performance of static gate assignments. None has analyzed the interrelationship between static gate assignments and real-time gate assignments as affected by the stochastic flight delays that occur in real operations. In addition, none has designed flexible buffer times for static gate assignments to effectively absorb stochastic delays in real-time gate assignments. This research proposes a simulation framework, that is not only able to analyze the effects of stochastic flight delays on static gate assignments, but can also evaluate flexible buffer times and real-time gate assignment rules. Finally, a simulation based on Chiang Kai-Shek airport operations is performed to evaluate the simulation framework.
---
paper_title: Airport Gate Scheduling with Time Windows

paper_content:

In contrast to the existing airport gate assignment studies where flight have fixed schedules, we consider the more realistic situation where flight arrival and departure times can change. Although we minimize walking distances (or travel time) in our objective function, the model is easily adapted for other material handling costs including baggage and cargo costs. Our objectives are achieved through gate assignments, where time slots alloted to aircraft at gates deviate from scheduled slots minimally. Further, the model can be applied to cross-docking optimization in areas other than airports, such as freight terminals where material arrival times (via trucks, ships) can fluctuate. The solution approach uses insert and interval exchange moves together with a time shift algorithm. We then use these neighborhood moves in Tabu Search and Memetic Algorithms. Computational results are provided and verify that our heuristics work well in small cases and much better in large cases when compared with CPLEX solver.
---
paper_title: Aircraft and gate scheduling optimization at airports

paper_content:

In this paper, we consider the over-constrained airport gate assignment problem where the number of flights exceeds the number of gates available, and where the objectives are to minimize the number of ungated flights and the total walking distances or connection. We design a greedy algorithm and use a tabu search meta-heuristic to solve the problem. The greedy algorithm minimizes ungated flights while providing initial feasible solutions while we devise a new neighborhood search technique, the interval exchange move, which allows us flexibility in seeking good solutions, especially in case when flight schedules are dense in time. Experiment conducted give good results.
---
paper_title: A heuristic approach for airport gate assignments for stochastic flight delays

paper_content:

To make good flight to gate assignments, not only do all the relevant constraints have to be considered, but stochastic flight delays that occur in actual operations also have to be taken into account. In past research, airport gate assignments and stochastic disturbances have often been handled in the planning and the real-time stages separately, meaning that the interrelationship between these stages, as affected by such delays, has been neglected. In this research, we develop a heuristic approach embedded in a framework designed to help the airport authorities make airport gate assignments that are sensitive to stochastic flight delays. The framework includes three components, a stochastic gate assignment model, a real-time assignment rule, and two penalty adjustment methods. The test results are based on data supplied by a Taiwan international airport, and show that the proposed framework performs better than the current manual assignment process and the traditional deterministic model.
---
paper_title: New heuristics for over-constrained flight to gate assignments

paper_content:

We consider the over-constrained Airport Gate Assignment Problem where the number of flights exceed the number of gates available, and where the objectives are to minimize the number of ungated flights and the total walking distances. The problem is formulated as a binary quadratic programming problem. We design a greedy algorithm and use a Tabu Search meta-heuristic to solve the problem. The greedy algorithm minimizes ungated flights while we devise a new neighbourhood search technique, the Interval Exchange Move, which allows us flexibility in seeking good solutions, especially when flight schedules are dense in time. Experiments conducted give good results.
---
paper_title: Optimization of multiple objective gate assignments

paper_content:

This paper proposes a multiple objective model to help airport authorities to efficiently and effectively solve gate assignment problems. The model is formulated as a multiple objective zero-one integer program. To efficiently solve large-scale problems in practice, we used the weighting method, the column generation approach, the simplex method and the branch-and-bound technique to develop a solution algorithm. To test how well the model may be applied in actual operations, a case study regarding the operation of Chiang Kai-Shek (CKS) Airport was performed. The results show that the model could be useful for actual operations.
---
paper_title: DEVELOPMENT AND APPLICATION OF HYPERHEURISTICS TO PERSONNEL SCHEDULING

paper_content:

This thesis is concerned with the investigation of hyperheuristic techniques. Hyperheuristics are heuristics which choose heuristics in order to solve a given optimisation problem. In this thesis we investigate and develop a number of hyperheuristic techniques including a hyperheuristic which uses a choice function in order to select which low-level heuristic to apply at each decision point. We demonstrate the effectiveness of our hyperheuristics by means of three personnel scheduling problems taken from the real world. For each application problem, we apply our hyperheuristics to several instances and compare our results with those of other heuristic methods. For all problems, the choice function hyperheuristic appears to be superior to other hyperheuristics considered. It also produces results competitive with those obtained using other sophisticated means. It is hoped that ::: - hyperheuristics can produce solutions of good quality, often competitive with those of modern heuristic techniques, within a short amount of implementation and development time, using only simple and easy-to-implement low-level heuristics. ::: ::: - hyperheuristics are easily re-usable methods as opposed to some metaheuristic methods which tend to use extensive problem-specific information in order to arrive at good solutions. ::: ::: ::: These two latter points constitute the main contributions of this thesis.
---
paper_title: Assigning arriving flights at an airport to the available gates

paper_content:

Unexpected changes in the flight schedules may disrupt the initial aircraft-gate assignments, and result in congestions and delays in getting aircraft onto gates. A mathematical model is developed to assign the flights with the minimum range of unutilised time periods of gates, subject to the level of service offered to passengers and other physical and managerial considerations. (The assignments are expected to be flexible enough to absorb the minor modifications in the flight schedules.) Interactive optimum and heuristic procedures, both utilising lower bounds on the ranges of future solutions, are proposed to cope with the major changes in disrupting the initial gate-assignments. Over randomly generated schedules, 74 flights can be optimally assigned to seven gates within 17 seconds when the gates are re-utilised within 30 minutes after each departure. The heuristic reaches the optimal solution after evaluating at most 20 partial solutions at one level. Over data obtained from Riyadh’s International Airport, the heuristic outperforms the existing practice: On average, 72.03% and 54.28% improvements are obtained on the number of remote served aircraft and towed aircraft, respectively.
---
paper_title: Hyper-heuristics: A Survey of the State of the Art

paper_content:

Hyper-heuristics comprise a set of approaches that are motivated (at least in part) by the goal of automating the design of heuristic methods to solve hard computational search problems. An underlying strategic research challenge is to develop more generally applicable search methodologies. The term hyper-heuristic is relatively new; it was first used in 2000 to describe heuristics to choose heuristics in the context of combinatorial optimisation. However, the idea of automating the design of heuristics is not new; it can be traced back to the 1960s. The definition of hyper-heuristics has been recently extended to refer to a search method or learning mechanism for selecting or generating heuristics to solve computational search problems. Two main hyper-heuristic categories can be considered: heuristic selection and heuristic generation. The distinguishing feature of hyper-heuristics is that they operate on a search space of heuristics (or heuristic components) rather than directly on the search space of solutions to the underlying problem that is being addressed. This paper presents a critical discussion of the scientific literature on hyper-heuristics including their origin and intellectual roots, a detailed account of the main types of approaches, and an overview of some related areas. Current research trends and directions for future research are also discussed.
---
paper_title: Optimized Assignment of Civil Airport Gate

paper_content:

Airport gate assignment is to appoint a gate for the arrival or leave flight to ensure that the flight is on schedule. Assigning the airport gate with high efficiency and reason is a key task among the airport ground busy works. A model of airport gate assignment based on the embedded analysis of the actual airport gate assignment for a busy domestic civil airport is proposed. The objective of the problem is to maximize the sum of the all products of the flight eigenvalue and the gate eigenvalue which the flight assigned. The flight type and the flight downtime and the number of airline passengers are considered in the flight eigenvalue and the ease of the gate is considered in the gate eigenvalue. The solution space of the problem based on the dynamic scheduling parallel machines and a directed graph model are given. The solving method based on the branch and bound algorithm is designed. Simulation result shows the validity of this model and algorithm.
---
paper_title: Procedures for providing robust gate assignments for arriving aircrafts

paper_content:

Abstract Assigning commercial service aircrafts to the available gates at an airport depends on flights scheduled, their actual behavior relative to those schedules, aircraft servicing requirements and capacities of ramp facilities. Flight delays, severe weather, or equipment failures can disrupt the planned schedules, and compound the difficulty of maintaining smooth station operations. A mixed-binary mathematical model with a quadratic function for minimizing the variance of idle times at the gates is proposed to make the initial assignments insensitive to variations in flight schedules. Experimental results with a branch and bound algorithm indicate that more computational effort is required to assign flights optimally over low utilized gates. Furthermore, a heuristic employing the priority function which considers additionally the possible idle times from the future assignments outperforms the others, significantly. Over the real data obtained from the Saudi Arabian Airlines, average 87.4% and 76.2% of improvements can be obtained on the number of aircrafts assigned initially to remote area and that towed from their assigned gates during the real-time implementation, respectively.
---
paper_title: A gate reassignment framework for real time flight delays

paper_content:

Flight delays (such as early or late arrivals and late departures) are a frequent occurrence in actual day to day airport operations and it is often not possible to assign such flights to their original gates. Flight delay information may also vary with time. As a consequence, the airport authority needs to reassign flights to different gates in real-time. The traditional manual flight reassignment method is neither efficient nor effective in cases with variable flight delay information, and the reassignment is frequently time constrained. Consequently, in this study the goal is to develop a gate reassignment framework, and a systematic computerized tool, for repeatedly handling gate reassignments given varied flight delay information. The results of a test case related to Taiwan international airport operations, show that the proposed framework performs well.
---

Title: The Airport Gate Assignment Problem: A Survey

Section 1: Introduction
Description 1: Introduce the importance and complexity of the airport gate assignment problem (AGAP), historical development, and key objectives from different stakeholders' perspectives.

Section 2: Formulations of AGAP and Related Problems
Description 2: Provide various mathematical formulations of AGAP, including integer and mixed integer programming, nonlinear programming, quadratic programming, multiple objective AGAP formulations, and robust optimization models.

Section 3: Integer Linear Programming Formulations (IP)
Description 3: Detail the integer linear programming models used to solve AGAP.

Section 4: Mixed Integer Linear Programming (MILP)
Description 4: Explain the mixed integer linear programming techniques applied to AGAP.

Section 5: Mixed Integer Nonlinear Programming
Description 5: Describe the mixed integer nonlinear programming methods proposed for AGAP.

Section 6: Quadratic Programming
Description 6: Discuss the quadratic programming approaches and their effectiveness in dealing with AGAP.

Section 7: Multiple Objective AGAP Formulations
Description 7: Present models addressing multiple objectives for AGAP and the methods used to solve them.

Section 8: Stochastic Models
Description 8: Describe stochastic models tackling AGAP under uncertainty conditions such as flight delays.

Section 9: AGAP Related Problems
Description 9: Review the transformation of AGAP into well-known problems like quadratic assignment problem (QAP), clique partitioning problem (CPP), scheduling problems, and network representations.

Section 10: Resolution Methods
Description 10: Explore different resolving techniques, mainly focusing on exact algorithms, heuristic algorithms, and metaheuristic methods.

Section 11: Exact Algorithms
Description 11: Examine exact algorithms that yield optimal solutions and their applications to AGAP.

Section 12: Heuristic Algorithms
Description 12: Delve into heuristic algorithms, discussing their capabilities and limitations in solving AGAP.

Section 13: Conclusion and Research Trends
Description 13: Summarize the findings of the survey, highlighting research trends, the importance of exact methods, and the potential of hyperheuristic approaches for addressing AGAP.