Omega35(2007)326–
334
www.elsevier/locate/omega
Flight gate scheduling:State-of-the-art and recent developmentsଁ
Ulrich Dorndorf a,Andreas Drexl b,Yury Nikulin b,∗,Erwin Pesch c
a INFORM GmbH,Pascalstr23,52076Aachen,Germany
b Christian-Albrechts-Universita¨t zu Kiel,Institut für Betriebswirtschaftslehre,Olshausenstr40,24118Kiel,Germany
c Universita¨t Siegen,Institut für Wirtschaftswissenschaften,Lehrstuhl für Wirtschaftsinformatik,Hölderlinstr3,57068Siegen,Germany
Received31January2005;accepted7July2005
Available online6September2005
Abstract
This paper surveys a large variety of mathematical models and up-to-date solution techniques developed for solving a generalflight 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 toflight gate management without touching scheduling of ground handling operations.
᭧2005Elsevier Ltd.All rights reserved.
Keywords:Air transport;Flight gate scheduling;Assignment of aircraft;Activities to terminals;Survey of models and algorithms
1.Introduction
Due to the growth of air transport traffic(it has roughly doubled since the early1980s)techniques for managing and allocating airport and airline resources in a dynamic oper-ational environment effectively and efficiently have gained
an ever-increasing interest.Strong competition between air-lines and the demand of passengers for more comfort have lead to complex planning problems that require new mod-
els and methods.The scheduling problems nowadays faced
by airport and air-line managers are even more complicated than most other traditional scheduling problems.This fact
can be easily explained.First of all,a wide range of resource modules apparently have to be considered:flights,terminals,
ଁThis work has been supported by the German Science Foun-dation(DFG)through the grant“Planung der Bodenabfertigung an Flughäfen’’(Dr170/9-1,9-2and Pe514/10-2).
∗Corresponding author.Tel.:+494318805397.
E-mail addresses:ulrich.dorndorf@inform-ac
(U.Dorndorf),andreas.drexl@bwl.uni-kiel.de(A.Drexl),
nkln@lycos(Y.Nikulin),pesch@fb5.uni-siegen.de(E.Pesch). 0305-0483/$-see front matter᭧2005Elsevier Ltd.All rights reserved. doi:10.a.2005.07.001crews,baggage etc.Moreover,decisions about the usage of these resources influence each other,that is,the resources are highly interdependent.As a consequence these modules set up the basis of a complex resource management system for airports and airlines of any size.
This paper surveys a large variety of mathematical models and techniques developed for solving a generalflight gate scheduling problem.In doing so we do not restrict ourself to collecting various models and solution techniques which are available in the open literature.We also intend to give an idea about new open problems arising in practice.In particular, we concentrate on issues concerning robust scheduling and generating stable assignments.
The paper is organized as follows:In Section2we detail the problem setting under consideration.A rough classi-fication offlight gate scheduling problems is proposed in Section3while a brief literature review is presented in Section4.Section5presents two particularly interesting approaches that have recently been proposed,based on quadratic assignment model and multi-mode scheduling for-mulation,respectively.A short description of new research directions is given in Section6,along with some concluding remarks.
U.Dorndorf et al./Omega35(2007)326–334327
2.Problem setting
There are several major classes of decisions for which air-line and airport management is responsible:crew schedul-ing,disruption management,airlinefleet assignment,air-craft scheduling and rotation,ground operations scheduling and some others that can be modeled as traditional ma-chine scheduling problems.Nevertheless,one of the most important and most complicated airport management topics isflight gate scheduling.
The main purpose of gate scheduling is tofind an as-signment offlights,or rather of the aircraft serving aflight, to aircraft stands,as well as start and completion times for processing an aircraft at the position it has been assigned to.Aircraft stands at the terminal and off-pier stands on the apron are often simply referred to as“gates’’.
Of course,a gate assignment must be suitable for airport services and convenient for passengers.
A well-constructed schedule must satisfy a set of strict rules and constraints:
< gate can process only one aircraft at the same time,
2.service requirements and space restrictions with respect
to adjacent gates must be fulfilled,
3.minimum ground time and minimum time between sub-
sequent aircraft have to be assured.
Typical objectives are:
1.the number of un-gated(open)aircraft activities has to
be minimized,
2.preferences of certain aircraft for particular gates have to
be maximized,
3.the total walking distance for passengers has to be min-
imized,
4.the deviation of the current schedule from a reference
schedule has to be minimized in order to increase sched-ule attractiveness and passenger comfort,
5.the number of expensive aircraft towing procedures(that
otherwise decrease the available time for some ground service operations on the ramp as well as in the terminal) has to be minimized.
Some special soft or strict constraints may also be intro-duced([1–4]).For example,the assignment of a large aircraft to a particular gate may imply that neighbor-ing gates can only accept aircraft of a certain size or are even completely blocked.
All these requirements make a gate scheduling problem very complicated both from a theoretical and a practical point of view.In fact,the multiple criteria and multiple con-straints nature of the problem make it very unlikely that an optimal solution can be found and verified.Therefore, one has to determine a solution that provides an appropri-ate compromise between all the different objectives while assuring a set of hard constraints.Moreover,any practical gate scheduling instance of a big international airport usu-ally has to deal with a large number of daily aircraft activ-ities(around1000)which have to be assigned to a pretty large number(around100)of differentflight gates.
The basic input data for gate scheduling is aflight time-table with arrival and departure times and additional speci-fications offlights:the origin and destination of aflight,the type of aircraft,the number of passengers,the cargo vol-ume,the type offlight(domestic or international)as well as gate preferences,required airport services and inspection facilities.
It is worth pointing to—from a practical point of view—one of the most important issues of gate scheduling: a gate schedule should be insensitive to small changes of input data;in other words scheduleflexibility is required. Obviously,the input data of anyflight gate scheduling prob-lem are subject to uncertainty and may change over time. Input data uncertainty in gate scheduling may have a cou-ple of reasons:(1)flight or gate breakdown,(2)flight earli-ness or tardiness,(3)emergencyflights,(4)severe weather conditions,(5)errors made by staff and many others.For example,a tardy arrival of one aircraft may generate a chain of delayed arrivals for other aircraft which have been as-signed to the same gate.In the worst case,this may lead to a“domino effect’’andfinally require a complete reschedul-ing,a fact which is absolutely undesirable.
Obviously,reliability of input data in the complex sys-tem of a modern airport cannot be guaranteed.Hence,new gate scheduling techniques try tofind a schedule(being non-optimal but as close as possible to an optimal one),which has the property offlexibility to changes of input data.Flex-ib
le gate scheduling gives terminal operators the possibil-ity to react quickly and properly to accommodate necessary changes or updates in theflight schedule.Finally,an appro-priateflexible gate assignment is supposed also to have an impact on efficiency of airlines and airports business activ-ities as well as on passenger service satisfaction.
3.Classification
Since the early seventies a large number of papers has been written on different topics which have to be addressed by airport and airline managers.We refer the reader to the survey[5],where one canfind a comprehensive description of the scheduling problems arising in the airline industry (e.g.aircraft rotation,fleet assignment,crew scheduling).In turn,here we focus on a review of the literature concerning gate scheduling issues,a key activity in any airport. Flight gates are scarce and expensive resources.There-fore,it is very important to use the available gates in the best possible way.Flight gates are the major items addressed in the gate assignment problem(GAP).The basic constraints of the GAP are that one gate can only accommodate a sin-gle aircraft at a time and that twoflights must therefore not be assigned to the same gate if they overlap in time.In this
328U.Dorndorf et al./Omega35(2007)326–334
section we roughly classify some of the research directions in this area.
Single or multiple time slot models.Gate assignment opti-mization models can be classified as single or multiple time slot models.Single time slot models consider the assign-ment of a batch offlights that arrive within a single given time period(slot)at gates.In this case only oneflight can be assigned to each gate.In multiple time slot models the entire time interval is divided into afixed number of time slots.The width of the time slots must be carefully selected because it influences the problem size as well as possible gate utilization.
Types of objectives.Gate assignment optimization mod-els can be classified with respect to the main objectives considered.For example,passenger walking distance mini-mization is the most frequently used goal,present not only in gate assignment,but also in the design of airport termi-nals.This objective is easily motivated and clearly under-stood,but it leads to models which can hardly be solved.At the same time,there exists a large variety of different ob-jectives,the consideration of which is at least as important as total walking distance minimization.All these objectives can be divided into two big classes:passenger-oriented and airport-oriented objectives.For example,Teodorovic et al. focus on total passenger delay and the number offlights cancellations in the case of irregularity offlights(see[6,7]). In turn,Chang[8]considers the distance passengers have to carry their baggage as a
n objective in addition to passen-ger walking distance.In contrast to previous ones,airport-oriented objectives like total gate preferences,number of aircraft towing procedures and others can be addressed. Mathematical models.It is well-known,that the single-slot GAP can be modeled in analogy to the NP-hard quadratic assignment problem[9–11]which is a facility location problem where the cost of placing aflight at a gate depends on the placement of other facilities and transport volume between two facilities(see also[12]). Additionally,the single time slot GAP can be stated as a linear integer program[13]with the objective of minimizing the total walking distance for arriving and departing pas-sengers.In[14]an integer program with an extended objec-tive function that takes into account transfer of passengers is proposed.
Haghani and Chen[4]formulate a multiple time slot ver-sion of the GAP with the objective of passenger walking and baggage transport distance minimization as an integer program.They introduce time-indexed binary variables that indicate the assignment of a particularflight to some gate in a given time slot.
4.State-of-the-art algorithms
There are two main research streams actively developed inflight gate scheduling:thefirst is based on m
athematical programming techniques and the second is based on rule based expert systems.We start the review with mathematical programming techniques.
Babic et al.[13]use branch and bound,with some en-hancements to accelerate computation,in order to deter-mine an optimal solution of the GAP.The objective is to reduce the number of passengers who have to walk maxi-mum distances—at the price that more passengers have to walk the minimum distances,compared to random aircraft position assignment.Contrary to[13]Mangoubi and Math-aisel[14]take into account transfer passengers.Moreover, they use the LP relaxation and greedy heuristics to solve the GAP.Bihr[15]uses0–1integer programming to solve the minimum walking distance gate assignment problem for fixed arrivals in a hub using a simplified formulation as an assignment problem.
The aforementioned papers(as well as the approaches of[16,17]),head towards improved passenger satisfaction mainly by reducing passenger walking distance inside the terminal building.Unfortunately,the assignment is very sen-sitive with respect to small changes of theflight schedule. In turn,Wirasinghe and Bandara([18,19])addition-ally integrate the cost of delays to minimize intra-terminal travel in terminal design process.Furthermore,they employ an approximation algorithm in their analysis.
Xu an Bailey[20]propose a tabu search algorithm for a single slot GAP with the objective function of minimizing the overall distances,that passengers have to walk in order to get connectingflights.The problem is formulated as a quadratic assignment problem and reformulated as a mixed 0–1integer linear program.A simple tabu search metaheuris-tic to solve the problem is developed.The algorithm exploits the special properties of different types of neighborhood moves,and creates effective candidate list strategies.Some computational experiments are presented and analyzed. Some models try to improve the performance of static gate assignment by taking into account stochasticflight de-lays(including early or late arrivals and late departures). For example,Hassounah and Steuart[21]show that planned buffer times could improve schedule punctuality.Yan and Chang[22]and Yan and Huo[23]use in their static gate assignment problems afixed buffer time between two con-tinuousflights assigned to the same gate in order to absorb the stochasticflight delays.Yan and Chang[22]develop a multi-commodity networkflow model.Moreover,they use Lagrangian relaxation with sub-gradient optimization and some heuristics to solve the GAP.Yan and Huo[23]formu-late a dual objective0–1integer programming model for the aircraft position allocation.Thefirst objective tries to min-imize passenger walking time while the second objective aims at minimizing passenger waiting times.The authors argue during peak hours,an aircraft might have to wait for an available gate,and hence passengers have to wait on the aircraft until a gate is available.In[24]the authors propose a simulation f
ramework,that is not only able to analyze the effects of stochasticflight delays on static gate assignments(cf.[22,23,25]),but can also evaluateflexible
U.Dorndorf et al./Omega35(2007)326–334329
buffer times and real-time gate assignment rules.
In[26–28]a GAP where the number offlights exceeds the number of available gates is studied.The primary goals are to minimize the number of open(non-assigned)flights and the total connection times.A two-stage algorithm,which exploits both a greedy strategy to minimize the number of openflights and a tabu search metaheuristic improved by a new neighborhood search technique to minimize the total connection times,is proposed to solve the problem.We will consider this model in the next section in more details. Recently,some authors try to take into account the dy-namic character of the GAP.A delayed departure may delay the arrival of another aircraft scheduled to the same gate, or require theflight to be reassigned.When gate idle times are distributed uniformly among the gates,the probability that the delayed departure time will still be earlier than the arrival of the nextflight is maximized.One of thefirst at-tempts to realize an approach aiming at robust schedules is due to[1–3,29]where the authors propose to utilize gates as uniformly as possible to provide schedule robustnes
s to small changes of input data.In[3]mathematical models and (optimal and heuristic)procedures are proposed to provide solutions with minimum dispersion of idle time periods for the GAP.
The aircraft gate reassignment problem occurs when the departure of an incoming aircraft is delayed.If the delay is significant enough to delay the arrival of subsequent incom-ing aircraft at the assigned gate,the management must revise the gate assignment to minimize extra delay times.Two pa-pers describe approaches for solving the gate reassignment problem.In[30]a genetic algorithm is proposed which ef-ficiently calculates minimum extra delayed time schedules that are at least as effective as solutions generated by ex-perienced gate managers.In[31]an integral minimum cost networkflow model is introduced.This model aims at recon-structing airlines schedules in response to delays by trans-forming the routing problem into a time-based network in which the overall time horizon is divided in discrete periods. The transformation is polynomial with respect to the num-ber of airports andflights.An optimum of the new model corresponds to the optimal solution of the original problem under some slight conditions.
The second mainstream research direction concentrates on simulation and rule based expert systems construction. While“traditional approaches utilizing classical operations research techniques have difficulty with uncertain infor-mation and multiple performance criteria and do not adapt well to the nee
ds of real-time operations support’’(see [32]),alternatively,many authors focus on the design of so-called rule-based expert systems([33–40]).Based on the knowledge obtained from ground controllers,an ex-pert system uses production rules to produce assignments. Evidently,the number of factors to be taken into account is large.Therefore,the most crucial task is to identify all the rules,order them by importance and list these rules appropriately.
Hamzwawi[37]introduces a rule based system for sim-ulating the assignment of gates toflights and for evaluating the effects of particular rules on gate utilization.Gosling [32]describes an expert system for gate assignment that has been implemented at a major hub of Denver Stapleton air-port.Srihari and Muthukrishnan[39]use a similar approach for solving the GAP and also describe how to apply sensi-tivity analysis.
From a practical point of view,it is even more important to develop simple expert systems that make use of mathemat-ical programming techniques(branch and bound,dynamic programming,local search).Such an integration would help to create a gate scheduling system with the desiredflexibil-ity property.For example,Cheng[36,41–43]describes the integration of mathematical programming techniques into a knowledge-based gate assignment system to provide par-tial parallel assignments with multiple objectives.Both op-timization and rule based approaches have been combined with simul
ation analysis in[33,37].
5.Recent developments
In this section we outline two new promising optimiza-tion models for gate scheduling.The choice of these two models is not occasional.The main drawback of all previ-ous models is that they do not take into account a real mul-tiple criteria nature of the problem.The models we propose are he proper solving of them provides a trade-off between several objectives which are usually in conflict.Finding such a compromise between several goals may positively influence passenger satisfaction withflight and save extra money for airport and airline companies.The first model we describe addresses two traditional goals of flight gate assignment.Thefirst goal is to assignflights to stand positions located directly at the terminal(and,hence, not to the apron).The second goal is to minimize the total passenger walking or baggage transportation distance.In the past the two goals were not considered together inside one model.Contrary to thefirst model,the second one uses a fairly large number of apron stands for passenger embarking and disembarking because of scarce terminal space.More-over,we suppose that one aircraft can be assigned to dif-ferent gates during its ground time.Such assumption gives more freedom for airport managers.For example,if one flight has a long ground time and the aircraft is assigned to a gate,which has to be used very often,the
n it can be temporally removed to another gate,which is currently can-not be used,or to the apron in order to make the gate free for other assignment.As well as thefirst model,the second one aims to optimize several objectives which are oriented on both passenger comfort and convenience for airport ser-vices.While thefirst model is considered to be classical,the second model can be treated as quite new and contemporary. Additionally,note that thefirst(second)model represents the strategy usually adopted for United States(European) airports.
330U.Dorndorf et al./Omega35(2007)326–334 Model1.This model has been proposed by Ding et al.
[26,27].Generally speaking,the airport gate assignment
problem is modeled as a quadratic assignment problem
where the objectives are to minimize the number of un-
gatedflights and the total passenger walking distance(or
equivalently,connection time).For the sake of shortness
we will sketch the basic ideas of[26].
When an aircraft arrives at the airport,it can be either
assigned to the terminal gates or,if no terminal stand po-
sition is available,it can be assigned to the apron stand
position(the model does not distinguish between distinct
off-pier stands).All the terminal gates are usually equipped
with passenger bridges,whereas passengers fromflights as-
signed to the apron can be transported to the terminal build-
ing by transfer busses.Such bus connection may increase
connection time and can hardly be regarded as desirable if
our goal is to minimize total passenger walking distance and
connection time.
The following parameters are given:
N:set offlights arriving at and/or departing from
the airport,
M:set of available gates at the airport,
n:total number offl=|N|,
m:total number of =|M|,
a i:arrival time offlight i,
d i:departurreact to the recent
e time offlight i,d i>a i∀i,
w k,l:walking distance for passengers from gate k to
gate l,
f i,j:number of passengers transferrin
g fromflight i
toflight j.
Additionally,two dummy gates are introduced.Gate0rep-
resents the passenger entrance/exit of the airport.Gate m+1
represents the apron whereflights arrive when no terminal
gates are available.The binary variable y i,k=1denotes that
flight i is assigned to gate k,0<k m+1,and y i,k=0
otherwise.Then the objectives can be expressed as follows:
Min
n
i=1
y i,m+1
Min
n
i=1
n
j=1
m+1
k=1
m+1
l=1
f i,j w k,l y i,k y j,l
+
n i=1m+1
k=1
f0,i w0,k y i,k+
n
i=1
m+1
k=1
f i,0w k,0y i,k.
Thefirst objective represents the number offlights which are not assigned to any terminal ,they
are as-signed to the apron).The second objective represents the total passenger walking distance.It consists of three terms:the walking distance of transfer passengers,orig-inating departure passengers and disembarking arrival passengers.
The set of restrictions is defined by the following system of constraints.Thefirst constraint
m+1
k=1
y i,k=1,1 i n
assures that everyflight must be assigned to exactly one gate including the apron.
The second constraint
y i,k y j,k(d j−a i)(d i−a j) 0,
1 i,j n,k=m+1
prohibits schedule overlapping of twoflights if they are assigned to the same gate.The last constraint
y i,k∈{0,1},1 i n,1 k m+1
defines the variables to be boolean.
The mathematical model can also be supplemented with several observations.Firstly,it is very natural to put f ii=0. Secondly,in reality,for two distinctflights i and j,f ij and f ji are exclusive.If f ij>0then f ij=0and vice versa.
The problem has been primarily attacked with greedy methods originally proposed by Xu and Bailey[20]to minimize thefirst objective.The basic idea is to sort all theflights according to departure times and then assign flights one by one to the earliest available gate.If no ter-minal gates are available for assignment,then theflight is assigned to dummy gate m+1.Then the second objective is addressed applying different meta heuristic approaches such as simulated annealing and tabu search.The main new contribution are so-called interval exchange moves. These particular moves generalize a technique proposed in [20],where three types of neighborhood moves have been investigated:insertion moves and two types of exchange moves.With this new approach,experimental results are obtained which are quite good in comparison with previous approaches.
Model2.The purpose of the second model is to assign available airportflight gates to three possible airc
raft ac-tivities(arrival;optional intermediate parking activity,the length of which depends on ground time;departure)and to schedule start and completion times of the activities at the positions.A detailed description can be found in[44]. Compared to previous models there are several new con-tributions.Firstly,the three activities are modeled separately and,hence,can potentially be assigned to different posi-tions.The aircraft can be moved to another assigned posi-tion using tow tractors,a procedure which is called tow-ing.Secondly,in contrast to the standard objective function commonly used(which minimizes passenger walking dis-tance)a complex objective function which is a combination of several partial objectives is introduced.
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论