Relatório Seminário Tese 03 - IT-300

A META-HEURISTIC TOOL TO SUPPORT DECISION-MAKING IN THE RECOVERY OF AIRPORT OPERATIONS AFTER UNEXPECTED EVENTS

Marcus Vinicius Ramalho de Oliveira
Supervisor: Professor Carlos Müller
Co-supervisor: João Pita, PhD
Technological Institute of Aeronautics (ITA) – Civil Engineering Division
IT-300 – Seminário de Tese
Apresentação 01 – 10/04/2015


ABSTRACT
In a scenario with growth of air transport demand, is necessary increase the efficiency of the airports. However, increased efficiency also brings a reduction in the capability to absorb unexpected events in the airport operation. There are few studies aiming the recovery of an operation after an unexpected event. Besides this, these existing works are oriented to the airlines or to the specific airport systems. Thus, this paper aims to create a model of the integrated systems of airport operations and, analyzing the solution provided by this model and comparing it with the solution brought by the optimization of each subsystem of the airport already treated by literature. With this model, the author also intends to create a tool that supports decision making in operational recovery in case of unexpected events in an airport. It will use a meta-heuristic approach for obtaining a near-optimal solution, while the computational effort is maintained at an appropriate level. The tool will, then, be validated through a case study the major international gateway of Brazil.


The problem and hypothesis
As thoroughly demonstrated by literature, air transportation plays an important role in the economic growth and development of a nation. In this context, the infrastructure is a key aspect, since all the operations depend on its operational performance, which is shared by the major part of the other stakeholders, such as airlines and passengers (Dorndorf, Drexl, et al. 2007). Although the infrastructure has, itself, several components, for the present study, the focus will be the airport systems.
In Brazil, there are about 680 public aerodromes and 1700 private aerodromes (ANAC - Brazil 2015). Notwithstanding the high quantity of aerodromes, from a total of 964,684 departures from 147 public airports in 2013, more than 80% were performed at only 17% of the total airports (ANAC - Brazil 2014). Therefore, we can observe a high concentration in the use of these aerodromes, which leads to a saturated system and, consequently, to a less efficient operation.
As an example, Guarulhos airport (IATA: GRU; ICAO: SBGR), the aerodrome with the highest number of departures among Brazilian airports, with more than 10% of the total departures, is only the 20th airport in efficiency according to the Brazilian aviation agency (ANAC - Brazil 2013). Actually, Bazargan and Vasigh (2003) concluded, through a data envelopment analysis, that small airports are more efficient than big hubs such Guarulhos airport.
Although the data above are applied only to Brazil, it is easy to find the same conjunction in other countries. Besides the efficiency issues found by theses major airports, as stated by Barnhart et al. (2012), the construction of new runways or new airports near of congested major hubs is highly unlikely due to several factors, as such cost, environmental and social impact, and political reasons.
Therefore, a big effort has been applied to improve the level of efficiency of different systems of the airport (Dorndorf, Drexl, et al. 2007). As described below, several researches has focused their work in the improvement of the airport systems, as a solution to the growing demand in already congested airports.
Bazargan et al. (A simulation study to investigate runway capacity using TAAM 2002) described a method to evaluate airport runway layouts through the TAAM (Total Airspace and Airport Modeller), which estimates the efficiency of a proposed model and permits comparisons between several designs for a specific airport, acting as a base for decision making to choose the optimal runway configuration. The runway evaluation is one of the most studied areas, because the runways are the scarcest resources in the airports and with a high cost to build (Barnhart, Belobaba and Odoni 2003).
Abdelghany et al. (2006) used an algorithm model to allocate the piers in baggage-handling facility for departure flights from a congested airport, considering different operational restrictions. Through this model, an airport operator could compare several operational restrictions which can be imposed to the baggage-handling facilities to produce a more efficient system.
In Zorografos et al. (2012), the authors described a slot allocation model which utilizes the same rule as IATA models, as well as any additional requirements imposed by European legislation applicable to European airports. Through this model, the authors proposed improvements to the current system that increases efficiency while keeping compliance with the original assumptions.
In Diepen et al. (2013) study, the authors created a computational model to schedule buses used to carry passengers to aircraft which are parked at a remote position. The proposed model provides route planning for the day considering several limitations, such as labor constraints.
Finally, Reinhardt et al. (2013) discussed a model to reduce the route distance and waiting time of disabled passenger, through the creation of optimized routes and schedules to the transport of these passengers in the airport area.
Given the above, it is important to point out that, to increase the efficiency of any system, assuming that the same energy is used, it is necessary to increase the work done in that amount of time. Therefore, despite the effort of the scientific community to increase the aerodrome efficiency to accommodate a growing demand and reduce costs, various barriers may arise from this increased efficiency. One of these barriers came from the fact that "more efficient" means an airport system with less downtime.
Barnhart et al. (2012) states that in several important airports around the world (e.g. New York's JFK and LaGuardia, Newark, London's Heathrow and Gatwick, Frankfurt, and Hong Kong) the demand is near or even exceed the airport capacity, even in good weather.
A possible parallel to the challenges observed at airports is the case of airlines. To address the growing demand, in recent decades, a great effort has also been made to make the flight scheduling of a company be near to the optimum, leaving little room for any changes (Barnhart, Belobaba and Odoni 2003), (Clarke 1997).
Therefore, any disruption in the normal operation of the airline could not be easily absorbed. For the term "disruption", the authors of the present work considered any event which affect the normal operation, due to a delay introduced in the original schedule or due to a system which is not available anymore (e.g. a malfunction of an equipment or an incident in the runway which became unavailable). Dorndorf et al. (2007) also discuss some examples of disruption that can introduce delays in the planned gate schedule of an airport.
For airlines, studies have been conducted aiming to provide a new schedule to recover their operation plan after a disruption, reducing impacts to the existing schedule and minimizing the costs, delays and cancellations (Clarke 1997), (Abdelghany, Abdelghany and Ekollu 2008). To airport operation, few studies were found to evaluate recovery after a disruption.
Gu and Chung (1999) evaluated a method to reassign gates after a disruption. In this study, after a delay in schedule of some flights, the authors proposed a Genetic Algorithm which creates a new assignment that reduces the additional delay caused by solution and also reduces the walking distances for the passengers of these flights.
Wang et al. (Wang, Luo and Shi 2013) also created a method to reassign gates to delayed flights. In their work, the authors divided the flights into two groups based on certainty of the delay time. The objective of the model was to minimize the disturbance (delay) led by the gate reassignment. The ant colony algorithm was used in this paper.
It is important to notice that, in both papers, the approach only reassign the delayed flights, without alterations to previous scheduled flights.
Some studies consider in their models some flexibility of the final solution in order to accommodate these disruptions (Abdelghany, Abdelghany and Narasimhan 2006), (Reinhardt, Clausen e Pisinger 2013), (Cheng, Ho and Kwan 2012). However, this approach can bring solutions even further from the optimal solution, since their solution introduces margins into the schedule.
Besides the absence of more studies of the recovery of airport operations, there is another aspect which should be considered. As stated by Dorndorf et al. (2007), the resources of an airport are highly interdependent, setting up the basis of a complex resources management system. If we consider each resource as a subsystem of the airport system, it is possible to say that airports are a sum of local system which contributes to the overall performance of the global system.
As exposed above, there are several works to improve the efficiency of these systems, but the evaluation of the airport as an integrated system was much less explored. Behrends and Usher (2014) studied the integration of freight movement and aircraft taxiing to reduces the time to move the freight to the aircraft and also reduces the taxi time of the aircraft.
In our understanding, because of the interdependence of the local systems, to disregard the associated effects of each environment to the overall efficiency can generate inadequate results, considering, for example, the overall cost of the airport.
For instance, several studies in gate assignment problem use the reduction of the passenger walking distance as the objective function or part of it (Gu and Chung 1999), (Cheng, Ho and Kwan 2012), (Hu and Di Paolo 2007), (Drexl and Nikulin 2008). The walking distance has an important role to the passenger satisfaction (Cheng, Ho and Kwan 2012), (Prem Kumar and Bierlaire 2014) and it is considered, usually, the distance between the gate and the baggage recovery area to arriving flights and between the check-in and the gate to departure flights (Liu, Chen and Liu 2014). Therefore, alterations in the check-in positions distribution could affect the distance walked by the passenger and, consequently, the solutions found by gate assignment methods.
Besides, from the business point of view, the cost minimization and revenue maximization are the priority for the airports operators (Prem Kumar and Bierlaire 2014). Therefore, a solution to the baggage handling system which reduce the movement of the baggage but increase the distance of the passenger, or a gate assignment which increase the bus traffic and the baggage movement, could result in a reduction of the revenue and/or the increase of the costs of airport operators.
Therefore, the present work has the following hypothesis:
Considering the high integration in airport systems, the sum of the optimum solutions in local systems is not the global optimum for airport recovery after irregularities.
The objective of the study is, in this way, to evaluate the relationship between the optimal solution to the a system created with a set of subsystems (thereafter, named global solution) and the optimal local solutions of each isolated system related by the literature, with the focus on the quality (i.e. how far is the answer from those obtained by non-heuristics methods), cost to the airport and effectiveness of both approaches to the objectives of airport operator.
The main hypothesis, therefore, could be written in a simpler way, by dividing it into n hypothesis, where n is the number of subsystems treated by this paper.
Hn: The local system n optimum is significantly different (in an airport cost point of view) from that obtained by the global model of the airport in that system.
As a secondary objective, the study will evaluate if it is possible to find an optimal global solution with a computational time adequate for use in a real case. Therefore, the authors will work together with GRU Airport, the operator of Guarulhos airport, to evaluate the results of this study in a real scenario.


The scope

Since it is impracticable to develop a model which consider the airport entirely, the scope of subsystems that will be analyzed by this paper must be limited. The definition of the scope was based in an interview with a specialist of the airport operator, considering the most important systems by the point of view of the business. Below, the scope of the work is described. The three first bullets will be evaluated by the authors, and the two last bullets will be evaluated if the deadlines allow an extension:
Gate assignment
Check-in positions distribution
Baggage return (arriving flights)
Baggage handling (departing flights)
Bus routing
The first part of the model treats the most important and most complicated system of the airport through the gate assignment problem (GAP). The purpose of the GAP models is create a feasible scheduling where the flights in a range of time are assigned to each gate, while optimize an objective function, respecting, however, all the constraints of the scenario (Dorndorf, Drexl, et al. 2007).
There are several approaches to the objective function and constraints. Dorndorf et al. (2007) list the most common of them:
Constraints:
One gate can process only one aircraft at the same time;
Service requirements and space restrictions with respect to adjacent gates must be fulfilled; and
Minimum ground time and minimum time between subsequent aircraft have to be assured.
Objectives:
The number of un-gated (open) aircraft activities has to be minimized;
Preferences of certain aircraft for particular gates have to be maximized;
The total walking distance for passengers has to be minimized;
The deviation of the current schedule from a reference schedule has to be minimized in order to increase schedule attractiveness and passenger comfort; and
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.
In this paper, the authors also evaluated the scientific literature produced in the last decades about the subject. Using the Google Academic search mechanism, with specific keywords (GAP, Gate Assignment and Gate Assignment Problem) the first 300 results were analyzed, and the results were tabulated in the figures below. There were 45 papers published between 1985 and 2015, using several models and objective functions.
As demonstrated in Figure 1, in this sample, the major part of the papers (about 32%) uses the minimization of total passenger walking distance as objective function. As well, the Figure 2 shows that the most used methods are Linear Programming, Tabu Search Algorithms and Genetic Algorithms. Also, about 40% of the papers used a multi-objective function.

Figure 1 – Objective Function distribution

Figure 2 – Methods distribution
Notwithstanding the above scenario, it is necessary to describe in more details some of the papers that studied the GAP, to understand the model and the methods proposed by this paper.
Wang et al. (2013) have created a model to increase the robustness of the gate assignment through the minimization of the dispersions of the idle time periods, considering some constraints. The authors used genetic algorithm to solve the problem.
Genç et al. (2012), have proposed to solve the GAP through the use of a stochastic method named Single Leap Big Bang-Big Crunch (SL-BBBC), applying it directly to the order of aircraft assignment, which is an input to an heuristic method used to solve the gate assignment problem named ground time duration maximization algorithm (GTMA).
Hu and Di Paolo (2007) used a Genetic Algorithm with uniform crossover to keep the common genes through each generation in a multi-objective gate assignment problem. The authors also used a two dimensional chromosome to keep the relative position and the gate assignment. The results showed the efficiency of the approach.
Drexl and Nikulin (2008) created a simulated annealing model to solve a GAP with multiple objectives: 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.
As already described, Behrends and Usher (2014) studied the integration of freight movement and aircraft taxiing in a GAP to reduces the time to move the freight to the aircraft and also reduces the taxi time of the aircraft.
Cheng et al. (2012) compared three meta-heuristics (simulated annealing, genetic algorithm and tabu search) as well a hybrid approach based on simulated annealing and tabu search, in an airport gate assignment.
In a different approach, Prem Kumar and Bierlaire (2014), utilizes a binary mixed integer program to solve the gate assignment problem. He also used a different objective function, where the model try to reduce the costs and maximize the revenue. Although the paper does not uses a meta-heuristic method, the largest problem was solved in about 30 minutes. They also have an interesting explanation of different constraints applicable to the gate assignment problem.
The other parts of the scope was not analyzed in detail yet.

The method

As described by Bennell et al. (2013), methods that require a large computational time has no practical applications because, in aeronautical operations, decisions must be taken in a short time. Although the case of irregularities in airports does not require a solution in seconds as in the case above (an air traffic problem), methods that do not deliver a quick solution will not find use with airport operators.
A solution to this question frequently discussed in the literature is the use of meta-heuristic methods (Clarke 1997), (Cheng, Ho and Kwan 2012), (Bennell, Mesgarpour and Potts 2013), (Huang, Sadek and Guo 2013). Such methods, which seeks a near optimal solution, usually deliver satisfactory results with considerable reduction of computational time (Cheng, Ho and Kwan 2012).
Although the advantages of meta-heuristics methods above mentioned, there is a theorem created by David H. Wolpert and William G. Macready named No free lunch theorem (NFL) (Wolpert and Macready 1997), which states that no generic algorithm could be better than an algorithm developed specifically for a problem. Therefore, by consequence of NFL, meta-heuristics methods could not be better than specific methods, once they are considered "off-the-shelf" methods (Wolpert and Macready 1997), (Linden 2012).
However, meta-heuristics methods are not necessarily generic. During the development of a method, all the singular characteristics of the problem must be considered in the model (Linden 2012). Thus, because of NFL, the authors of present work proposes to develop a specific solutions instead of utilize a standard package.
Among the above mentioned methods, the Genetic Algorithm (GA) has shown great potential (Cheng, Ho and Kwan 2012), (Huang, Sadek and Guo 2013), (Gu and Chung 1999), (Linden 2012). As shown in Figure 2, this method is the second most used meta-heuristic method for Gate Assignment Problem models. GAs are a type of stochastic algorithm that seeks the near optimum solution in a set of possible solutions, through methods based on the principle of survival of the fittest. By selecting the most "suitable" solutions, it creates new sequential populations until the algorithm converges to a near optimal solution or solutions (Huang, Sadek and Guo 2013).
The method is based on well-defined phases, starting with the creation of the initial population of solutions, which is our first generation, generally created through a random generation method (Gu and Chung 1999), (Bolat 2001). After this phase, the most suitable elements of that generation are chosen by an analyses of their level of fitness. These elements then undergo through stochastic process to combine characteristics of two elements or to create a random mutation, which grants a level of variability in the population and avoids the convergence to a local optimum. At the end of the process, a new generation of the population is created, containing individuals with combined features of the fittest elements of the previous generation and completely new elements. After some generations, it is expected that the population elements converge to a near optimum solution (Gu and Chung 1999), (Bolat 2001), (Hu and Di Paolo 2007).
One of the advantages of the use of the genetic algorithm approach is the inherent parallelism of the method (Gu and Chung 1999), (Bolat 2001). This characteristic allows the search for best solutions in an efficient way and, in most of the cases, creating a final population with feasible and near optimal solutions, which can be the base for decision making considering the idiosyncrasy of the real scenario.
Genç et al. (2012), however, states that the genetic algorithm is not an efficient method since it works directly in the final answer of the problem, leading to an evaluation of each restriction of each member of the population, which increase significantly the computational effort.
The NFL theorem could explain the perception above, since considers again generic characteristics of the GAs. However, since it is important to base the present work on a method which can find a near optimal solution in a feasible time for real problems, the authors proposed to compare the methods in a smaller problem, evaluating the solutions and the computational time required.
Therefore, a further analysis will be conducted, where the genetic algorithm method, the Big Bang – Big Crunch (BB-BC) method and the Simulated Annealing method will be tested to a Gate Assignment Problem.
The BB- BC method is a population based method of genetic algorithms (GA), where an initial population is created randomly, spreading the candidate solutions over the search space in a uniform manner. After this phase, the Big Crunch phase starts, through the use of a convergence operator that has many inputs but only one output, which can be considered as the 'center of mass', since the only output has been derived by calculating the center of mass. Then, after the calculation of the center of mass, the process of the creation of a new population (Big Bang phase) is carried out by calculating new points around the center of mass using normal distribution function (stochastic nature). The algorithm continues until predefined stopping criterion has been met (Genç, et al. 2012).
As stated above, the authors also propose to compare the GA and BB-BC methods with another search algorithm widely used in optimization problems and, therefore, an excellent means of comparing the results obtained: The Simulated Annealing method. In this method, the algorithm first finds a good approximation of the global optimal solution to the objective function in a large search space. In each iteration, the algorithm selects a set of nearby solutions to the current solution, by means of a probability function that decreases each cycle. Thus, the problem tends to a solution that approaches an optimal solution. Typically, the iterations are repeated until a suitable solution is found or a time limit is reached (Drexl and Nikulin 2008), (Erol and Eksin 2006).
The study of the methods will be made separately and the authors will seek to publish the results of this comparison. It will be used a non-heuristic method, as proposed by Prem Kumar and Bierlaire (2014), to evaluate the quality of each method.
The project will be developed through Object Oriented Programming (OOP). This kind of language, based on objects and classes, has several advantages over non-oriented languages (Linden 2012), (Drozdek 2000).
Among these advantages, we highlight the possibility of finding errors more easily, since the action takes place inside the objects (Linden 2012), (Drozdek 2000) , which will be extremely important in the implementation of a model as complex as what is being suggested by this work.
Therefore, it is considered that OOP is the best paradigm to be used in performing this work. While the OOP is selected as the programming scheme, it is still necessary choose a programming language that complies with the requirements of this project. In his book about genetic algorithm, Linden (Linden 2012) decided to utilize Java programming language. The main reasons were:
Java was, since the beginning, a language developed for OOP, instead only adapted as C++ or Ada95. Therefore, the concepts and logic present in this paradigm is the base of Java, allowing an extensive use of the tools.
The language has a neutral architecture, which means that it could be used in any operational system.
Java is safe, since it is based in the use of Java Virtual Machine. The code only talks with the JVM and has no permission to run any operation which could cause damage to the computer.
JVM is stable and, therefore, the program is more reliable.
Thus, the present study will use the Java programming language to develop the model.
For validation, we intend to study the models at a large airport: the International Airport of Guarulhos / São Paulo - Governador André Franco Montoro (IATA: GRU, ICAO: SBGR), where collection of data from various systems at this airport should be performed in order to create an input database, which will be inserted in the developed model, and a set of data output to be compared with the results obtained by the model.

The Model

The model to be used will be a simplified GAP based on the one proposed by Hu and Di Paolo (An efficient genetic algorithm with uniform crossover for the multi-objective airport gate assignment problem 2007), described below with all modifications applied.

Objective function (O.F.)

The model will be a weighted multi-objective gate assignment problem (MOGAP), formulated as a minimization problem, that consider the passenger walking distance and the aircraft waiting time in the apron. The minimization of aircraft waiting time on the apron will permit the reduction of the number of constraints, since the model will not assign all the aircrafts to the gate with the lower distance to avoid the increase of this variable. Hu and Di Paolo (2007) also used the baggage transfer distance as part of the O.F., which will be not considered in this simpler model.
Now, supposing that NAC aircrafts need to be assigned to NG gate in a period of time. Considering Pi the planned entering time to gate of ith aircraft and Gi the ground time of this aircraft. Di denotes the departure time of the same aircraft.
Now, Pi could be write as a function of Di and Gi, as in the:
Pi=Di-Gi
(1)
Considering Qg(j) the jth aircraft in the queue g, with g = 1 to NG, EQg(j) the entering time calculated by the model to the jth aircraft in the queue g, and Hg the number of aircrafts in the queue g, then we have:
EQgj=PQgj, if j=1maxPQgj,EQgj-1+GQgj-1, if j>1, j=1 to Hg and g=1 to NG
(2)
Considering the Qg(j) = i, i.e. the ith aircraft is the jth aircraft in the queue g, the waiting time is calculated as described in the Equation (3).
Wi=Ei-Pi i=1 to NAC
(3)
Now, considering that we have two data matrix: MP, which is the matrix with passenger transferred between aircrafts (or leaving/arriving the airport), and MPWD, the matrix with the walking distances between each gate (or exit/entrance of the airport), the total distance walked by all the passengers in a given solution is:
TPWD= g=1NG+1J=1Hgi=1NAC+1MPQgj, iMPWD(g, vi)
(4)
Where vi is the vector indicating the ith aircraft was assigned to vi gate.
In a similar manner, the total waiting time is shown in the Equation (5):
TWT= i=1NACWij=1NAC+1(MPi,j+MPj,i)
(5)
Therefore, the F.O. of the MOGAP can be calculated as follow:
minTMOGAP=αTPWD+(1-α)φTWT
(6)
Where α is a tuneable weight to adjust the contribution of factor of O.F., and φ is a parameter to convert time into distance. We use the same considerations used by Hu and Di Paolo (2007) to estimate the value of φ, setting it as 25.

The GENETIC ALGORITHM METHOD

As described above, a GA will be applied to a simplified Gate Assignment Problem. The model to be used will be based on the one proposed by Hu and Di Paolo (An efficient genetic algorithm with uniform crossover for the multi-objective airport gate assignment problem 2007), described below with all modifications applied.
The most important aspect of the model is the use of a new chromosome structure, which allows to identify and protect the common genes during crossover operations. The new structure also permit to record, in a unique chromosome, the gate assignment and the relative positions of the aircrafts, which is not possible with the usual chromosomes structures proposed in GAs.
To better understand how the new chromosome work, we will use the hypothetic scenario presented by Figure 3, with three gates (all available).

Figure 3 – Hypothetic airport scenario
As an example, we create a scenario with 10 aircrafts assigned to each queue/gate available, as shown in Figure 4.

Figure 4 – Scenario with filled queues
The chromosome C which represents this scenario is shown in the Figure 5.
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
1
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
3
3
1
2
1
1
1
2
2
3

Figure 5 – An example
In above matrix, if C(i,i) = 1, with i = 1,…, NAC, it means that the ith aircraft is assigned for the first position in the queue of the gate C(NAC+1, i). In the other hand, if C(i,j) = 1, with i = 1,…, NAC, it means that jth aircraft follows ith aircraft in the queue assigned in C(NAC+1, j).
As said before, this structure allows to easily identify the common genes. For example, consider the two chromosome presented below, with the common genes highlighted.
0
1
0
0
0
0
0
0
0
0


0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0


0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0


0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0


0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0


1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0


0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
0
0
0
0


0
0
1
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
1
0


0
0
0
0
0
0
0
1
0
1
0
0
0
1
0
0
0
0
0
0


0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1


0
0
0
0
0
0
0
0
0
0
3
3
1
2
1
1
1
2
2
3


2
2
1
1
2
2
1
3
2
3

Figure 6 – Common genes
The common genes are the non-zero values or identical gates values in the same positions in both chromosomes, i.e. C1(i,j) = C2(i,j) for all common genes, with i = 1,…, NAC+1 and j = 1,…, NAC+1.
There are also some constraints to the construction of the chromosomes, as described below (Hu and Di Paolo 2007).
The sum of all aircrafts assigned must be equal to the number of aircrafts available:
i=1NACj=1NACCi,j=NAC
(7)
The sum of each line must be less than or equal 1 for any row, or less than or equal 2 for the main diagonal (only the main diagonal has aircrafts in the first position, therefore, only lines with non-zero values in main diagonal could have another non-zero values in the same row).
j=1NACC(i,j) 2, C(i,i)>0, 1, Ci,i=0
(8)
The aircraft must be assigned for a unique gate.
i=1NACC(i,j)=1
(9)
All gates assigned must have a value in the first position and must be at least one gate assigned.
1 i=1NACCi,i=NG NG
(10)
Where NG is the quantity of assigned gates (lower than NG).
Finally, only one aircraft must be in the first position of an assigned gate.
CNAC+1=g,j=1,…,NACCj,j=1, g ΦG
(11)
Where ΦG is the vector with the assigned gates.
The initialization operation will create an entire population with n members. The algorithm guarantee that each member will obey all the constraints above described. This population will be the Generation 0.
After this step, new generations will be created through Mutation and Crossover operators. Both operators create a feasible chromosome, avoiding the check of each result in all interactions. The feasibility check is one of the problems stated by Genç et al. (2012) to GAs, because it could increase the computational time. Therefore, this approach will, theoretically, reduce the computational time of the model.
The mutation operator is important because creates the random variability in each generation, avoiding that the results converge to a local optimum. This parallel search is one of the most important characteristics of GAs (Linden 2012).
The probability of a mutation must be low (only 0.5%) of the population, because, while the variability is important, the good characteristics observed in fittest members must be kept to guarantee a convergence (Linden 2012).
The model uses two mutation operators, which could be used together or separately. The first operator shifts randomly the positions of two genes, while the second one swaps randomly two aircrafts in two different queues (Linden 2012).
The crossover operator will create a new chromosome with characteristics of two parents from previous generation. As described above, the operator used in this model will keep any common genes (Hu and Di Paolo 2007).
To choose the parents of the new chromosome, the authors will use a method named roulette wheel selection, largely used in GAs. Basically, the method assigns a proportional value based on the fitness of a chromosome compared to the sum of the fitness of all members (Linden 2012). After the evaluation of each member, a raffle is conducted based on this values (the fittest is more probable to be chosen).
As observed in the nature, it is important to permit that even the member with lowest fitness should be considered to cross (with a small probability) with another member, because it could be the only one with a part of the optimal solution (Linden 2012).
For example, if we apply a GA to maximize the function f(x) = x2, between the range 0 and 15, the obvious result is 15, or 1111. Consider that our initial population has four members: 0010, 1100, 0110 and 0001. Although the last member has the worse fitness result, only it has the non-zero value in the last gene. Therefore, if there is a possibility, even small, that this member is chosen, this characteristic could be present in the last generations (Linden 2012).
The both operators will be applied over the population, creating new generations. Each generation will be evaluated for fitness of the population and for the fittest member. A predefined quantity of generations will be established, as well as a stop criteria based on the evolution of the results of the population and of the fittest member between generations.
After all the steps presented above, a near-optimal solution is expected to be found with a small amount of computational time.

The status

The milestones of the research could be viewed in the Figure 6 below. The current objective of the authors is establish the best method to be used in the present work. As already explained, there are some discussion about the quality of the solutions found by each meta-heuristic method (Genç, et al. 2012) and even the comparison with non-heuristics (Prem Kumar and Bierlaire 2014).
Therefore, a study will be developed, using a simpler scenario: a GAP using as objective function (O.F.) the minimization of the weighted sum of passenger walking distance and aircraft waiting time on the apron. In this scenario, the authors will evaluate three meta-heuristics methods: Genetic Algorithm, Simulated Annealing and Big Bang – Big Crunch methods. The choice will be based on a comparison with a non-heuristic method proposed by Prem Kumar and Bierlaire (Multi-Objective Airport Gate Assignment Problem in Planning and Operations 2014).
An evaluation between the GA created by the authors in JAVA and a GA created in a commercial software will be performed to study the effect of NFL in the above described scenario.
The models will use real data (distances and flights times) from Guarulhos airport and the model created can be used in the future phases with some adaptation.

Figure 6 – Milestones of the research
After the validation, the method will be applied in the different subsystems, using, preferably, a literature validated approach. The O.F. will be adapted to cost minimization.
Finally, the global model will be created with the subsystems integrated in a multi-objective model. As other multi-objective models in the literature, a weighted sum will be used. However, since the final answer of the model depends strongly of the weights values, a sensibility evaluation will be made by the authors, as well as the analysis of the viability of prediction methods.
The quality of the model will be validated by the comparison with the costs of the solution applied by airport operators in a real scenario.
The Table 1 brings the schedule to delivery each part of the above described plan. Currently, the authors are developing the GA model to the gate assignment in the first scenario (O.F. as passenger walking distance).
Table 1 - Schedule
Delivery
2014.2
2015.1
2015.2
2016.1
2016.2
2017.1
2017.2
2018.1
Literature review








Disciplines




TBD



GAP model GA








GAP model SA








GAP model GA (Matlab)








GAP model BBBC








GAP model NH








GAP model (final)








Check-in Model








Baggage model








Sensibility Evaluation








Integrated Model








Evaluation of the results








Qualification





End of the semester


Articles and thesis










Possible periodics

Only 22% of the papers evaluated during the bibliografic research described in the scope section were published in conferences proceedings. In the other 78%, the most frequent journals were Computers & Industrial Engineering and Transportation Research Part A: Policy and Practice, with Qualis A2 and A1, respectively. The 5-Year Impact Factor of the first one is 2.412 and for the second one is 3.563.
Those will be the target of the present work.




References
Abdelghany, Ahmed, Khaled Abdelghany, and Ram Narasimhan. 2006. "Scheduling baggage-handling facilities in congested airports." Journal of Air Transport Management, 76-81.
Abdelghany, Khaled F., Ahmed F. Abdelghany, and Goutham Ekollu. 2008. "An integrated decision support tool for airlines schedule recovery during irregular operations." 825-848.
ANAC - Brazil. 2014. "Anuário do Transporte Aéreo - Dados estatísiticos e econômicos de 2013." Brasília-DF.
ANAC - Brazil. 2015. "Lista de Aeródromo Privados." 24 de February. Acesso em 27 de March de 2016. http://www.anac.gov.br/Area.aspx?ttCD_CHAVE=8.
ANAC - Brazil.. 2015. "Lista de Aeródromos Públicos." 24 de February. Acesso em 27 de March de 2016. http://www.anac.gov.br/Area.aspx?ttCD_CHAVE=8.
ANAC - Brazil. 2013. "Relatório de desempenho operacional dos aeroportos - Ano base 2012."
Barnhart, Cynthia, Fearing Douglas, Amedeo Odoni, and Vikrant Vaze. 2012. "Demand and capacity management in air transportation." EURO Journal on Transportation and Logistics 1: 135-155. doi:0.1007/s13676-012-0006-9.
Barnhart, Cynthia, Natashia L. Boland, Lloyd W. Clarke, Ellis L. Johson, George L. Nemhauser, and Rajesh G. Shenoi. 1993. "Flight String Models for Aircraft Fleeting and Routing." Tranportation Science 32 (3): 208-220.
Barnhart, Cynthia, Peter Belobaba, and Amedeo R. Odoni. 2003. "Applications of Operations Research in the Air Transport Industry." Transportation Science 37 (4): 368-391.
Bazargan, Massoud, and Bijan Vasigh. 2003. "Size versus efficiency: a case study of US commercial airports." Journal of Air Transport Management 9: 187-193.
Bazargan, Massoud, Kenneth Fleming, and Prakash Subramanian. 2002. "A simulation study to investigate runway capacity using TAAM." Proceedings of the 2002 Winter Simulation Conference. San Diego.
Behrends, John A., and John M. Usher. 2014. "Aircraft Gate Assignment: Integrating Freight Movement and Aircraft Taxiing." Industrial and Systems Engineering Research Conference. Montréal, Canada.
Bennell, Julia A., Mohammad Mesgarpour, and Chris N. Potts. 2013. "Airport runway scheduling." Annals of Operations Research (Springer Science) 204: 249-270. doi:10.1007/s10479-012-1268-1.
Bihr, Richard A. 1990. "A conceptual solution to the aircraft gate assignment problem using 0, 1 linear programming." Computers & Industrial Engineering 19 (1-4): 280-284.
Bolat, A. 2001. "Models and a genetic algorithm for static aircraft-gate assignment problem." The Journal of the Operational Research Society 52 (10): 1107-1120.
Cheng, Chun Hung, Sin C. Ho, and Cheuk Lam Kwan. 2012. "The use of meta-heuristics for airport gate assignment." Expert Systems with Applications 39: 12430–12437.
Ching, Chang. 1996. "Flight sequencing and gate assignment at airport hubs." Transportation Research Part A: Policy and Practice 30 (1): 53-54.
Clarke, M. D. D. 1997. "The airline recovery problem." Boston, MA: MIT International Center for Air Transportation. 26p.
Diepen, G., B. F. I. Pieters, J. M. van den Akker, and J. A. Hoogeveen. 2013. "Robust planningofairportplatformbuses." Computers & Operations Research, 747-757.
Ding, H, A Lim, B Rodrigues, and Y Zhu. 2004. "Aircraft and gate scheduling optimization at airports." Proceedings of the 37th Annual Hawaii International Conference on System Sciences. Kauai.
Ding, H, A Lim, B Rodrigues, and Y Zhu. 2004. "New Heuristics for Over-Constrained Flight to Gate Assignments." The Journal of the Operational Research Society 55 (7): 760-768.
Ding, H, A Lim, B Rodrigues, and Y Zhu. 2005. "The over-constrained airport gate assignment problem." Computers & Operations Research 32 (7): 1867–1880.
Dorndorf, Ulrich, Andreas Drexl, Yury Nikulin, and Erwin Pesch. 2007. "Flight gate scheduling: State-of-the-art and recent developments." Omega 35 (3): 326-334.
Dorndorf, Ulrich, Florian Jaehn, and Erwin Pesch. 2012. "Flight gate scheduling with respect to a reference schedule." Annals of Operations Research, April: 177-187.
Dorndorf, Ulrich, Florian Jaehn, and Erwin Pesch. 2008. "Modelling Robust Flight-Gate Scheduling as a Clique Partitioning Problem." Transportation Science 42 (3): 292-301.
Drexl, Andreas, and Yury Nikulin. 2008. "Multicriteria airport gate assignment and Pareto simulated annealing." IIE Transactions 40: 385-397. doi:10.1080/07408170701416673.
Drozdek, Adam. 2000. Data Structures and Algorithms in C++. Second Edition. Pacific Grove, CA: Brooks/Cole.
Erol, Osman K., and Ibrahim Eksin. 2006. "A new optimization method: Big Bang–Big Crunch." Advances in Engineering Software 37: 106-111.
Genç, Hakkı Murat, Osman Kaan Erol, Ibrahim Eksin, Mehmet Fatih Berber, and Binnur Onaran Güleryüz. 2012. "A stochastic neighborhood search approach for airport gate assignment problem." Expert Systems with Applications 39: 316–327.
Gu, Yu, and Christopher A Chung. 1999. "Genetic Algorithm Approach to Aircraft Gate Reasssignment Problem." Journal of Transportation Engineering 125: 384-389.
Hamzawi, Salah G. 1986. "Management and planning of airport gate capacity: a microcomputer based gate assignment simulation model." Transportation Planning and Technology 11 (3): 189-202.
Hu, X. B., and E. Di Paolo. 2007. "An efficient genetic algorithm with uniform crossover for the multi-objective airport gate assignment problem." IEEE Congress on Evolutionary Computation. Singapore. 55-62.
Hu, Xiao -Bing, and Ezequiel Di Paolo. 2009. "A ripple-spreading Genetic Algorithm for the airport Gate Assignment Problem." IEEE Congress on Evolutionary Computation. Trondheim.
Huang, Shan, Adel W. Sadek, and Liya Guo. 2013. "Computational-Based Approach to Estimating Travel Demand in Large-Scale Microscopic Traffic Simulation Models." Journal of Computing in Civil Engineering 27: 78-86.
Jaehn, Florian. 2010. "Solving the flight gate assignment problem using dynamic programming." Zeitschrift für Betriebswirtschaft 80 (10): 1027-1039 .
Jo, Geun -Sik, Jong -Jin Jung, and Chang -Yoon Yang. 1997. "Expert system for scheduling in an airline gate allocation." Expert Systems with Applications 13 (4): 275-282.
Kim, Sang Hyun, Eric Feron, and John -Paul Clarke. 2013. "Gate Assignment to Minimize Passenger Transit Time and Aircraft Taxi Time." Journal of Guidance, Control, and Dynamics 36 (2): 467-475.
Lam, Soi -Hoi, Jia -Meng Cao, and Henry Fan. 2002. "Development of an intelligent agent for airport gate assignment." Journal of Air Transportation 7 (2): 103-114.
Lim, A, and Fan Wang. 2005. "Robust airport gate assignment." 17th IEEE International Conference on Tools with Artificial Intelligence. Hong Kong.
Lim, A, B Rodrigues, and Y Zhu. 2005. "Airport Gate Scheduling with Time Windows." Artificial Intelligence Review 24 (1): 5-31.
Linden, Ricardo. 2012. Algoritmos Genéticos. Rio de Janeiro: Editora Ciência Moderna Ltda.
Linhares, A, H H Yanasse, and J R. A Torreao. 1999. "Linear gate assignment: a fast statistical mechanics approach." IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 18 (12): 1750-1758.
Liu, Shuo, Wenhua Chen, and Jiyin Liu. 2014. "Optimizing Airport Gate Assignment with Operational Safety Constraints." International Conference on Automation & Computing. Bedfordshire, UK.
Maharjan, Binod, and Timothy I Matis. 2012. "Multi-commodity flow network model of the flight gate assignment problem." Computers & Industrial Engineering 63 (4): 1135–1144.
Mangoubi, R S, and Dennis F. X Mathaisel. 1985. "Optimizing Gate Assignments at Airport Terminals." Transportation Science 19 (2): 173 - 188.
Neuman, Urszula M, and Jason D Atkin. 2013. "Airport Gate Assignment Considering Ground Movement." ICCL 4th International Conference. Copenhagen. 184-198.
Prem Kumar, Viswanathan, and Michel Bierlaire. 2014. "Multi-Objective Airport Gate Assignment Problem in Planning and Operations." Journal of Advanced Transportation 48 (7): 902-926.
Reinhardt, Line Blander, Tommy Clausen, and David Pisinger. 2013. "Synchronized dial-a-ride transportation of disabled passengers at airports." European Journal of Operational Research, 106-117.
Wang, Huawei, Yuxiao Luo, and Zhijian Shi. 2013. "Real-Time Gate Reassignment Based on Flight Delay Feature in Hub Airport." Mathematical Problems in Engineering 2013.
Wang, Li. 2010. "Optimized Assignment of Civil Airport Gate." International Conference on Intelligent System Design and Engineering Application. Changsha.
Wei, Dong -Xuan, and Chang -You Liu. 2009. "Fuzzy model and optimization for airport gate assignment problem." IEEE International Conference on Intelligent Computing and Intelligent Systems. Shanghai.
Wei, Dongxuan, and Changyou Liu. 2007. "Optimizing Gate Assignment at Airport Based on Genetic-Tabu Algorithm." IEEE International Conference on Automation and Logistics. Jinan.
Wolpert, David H., and William G. Macready. 1997. "No Free Lunch Theorems for Optimization." IEEE Transactions on Evolutionary Computation 1 (1): 67-82.
Xu, Jiefeng, and G Bailey. 2001. "The airport gate assignment problem: mathematical model and a tabu search algorithm." 34th Annual Hawaii International Conference on System Sciences. Maui: IEEE.
Yan, Shangyao, and Cheun-Ming Huo. 2001. "Optimization of multiple objective gate assignments." Transportation Research Part A: Policy and Practice 35 (5): 413-432.
Yan, Shangyao, and Chia-Ming Chang. 1998. "A network model for gate assignment." Journal of Advanced Transportation 32 (2): 176-189.
Yan, Shangyao, and Ching -Hui Tang. 2007. "A heuristic approach for airport gate assignments for stochastic flight delays." European Journal of Operational Research 180 (2): 547–567.
Yan, Shangyao, Chi-Yuan Shieh, and Miawjane Chen. 2002. "A simulation framework for evaluating airport gate assignments." Transportation Research Part A: Policy and Practice 36 (10): 885–898.
Zhu, Yi, A Lim, and B Rodrigues. 2003. "Aircraft and gate scheduling with time windows." 15th IEEE International Conference on Tools with Artificial Intelligence. Sacramento, CA.
Zorografos, Konstantinos G., Yiannis Salouras, and Michael A. Madas. 2012. "Dealing with the efficient allocation of scarce resources." Transportation Research Part C, 244-256.