Relatório Seminário Tese 01 - IT-310 (Rev 01)

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-310 – Seminário de Tese
Apresentação 01 – 10/04/2015


ABSTRACT
In a scenario 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 aimed 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 bring 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 for a big airport of São Paulo state.


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. 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 aerodrome [1], [2]. 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 [3]. 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 between Brazilian airports, with more than 10% of the total departures, is only the 20th airport in efficiency according to the Brazilian aviation agency [4]. Actually, Bazargan and Vasigh [5] 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. Therefore, a big effort has been applied to improve the level of efficiency of different systems in the airport system.
Bazargan et al. [6] described a method to evaluate airport runway layouts through the TAAM (Total Airspace and Airport Modeller) method, which estimates the efficiency of a proposed model and permits comparison between several designs for a specific airport, acting as a base for decision making to choose the optimal runway configuration.
Abdelghany et al. [7] 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. [8], 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. [9] 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. [10] 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 should be considered that, 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.
It is important to point out that, to increase the efficiency of any system assuming that the same energy is used, an increase in the work done in the amount of time is required. Therefore, "more efficient" means an airport system with less downtime.
A possible parallel to challenges observed at airports is the case of airlines. 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 [11]. In this context, studies have been conducted aiming to provide a new schedule to recover the airline operation plan after a disruption, reducing impacts to the existing schedule and minimizing the costs, delays and cancellations [11], [12]. To airport operation, no studies were found to evaluate recovery after a disruption.
Some studies consider in their models some flexibility of the final solution in order to accomodate these disruptions [7], [10], [13]. However, this approach can bring solutions even further from the optimal solution.
Besides the absence of studies of the recovery of airport operations, there is another aspect which should be considered. The airports are a sum of local system which contributes to the overall performance of the global system. As was seen above, there are several works to improve the efficiency of these systems, but, at this moment, no papers were found that evaluate the airport as an integrated system. 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.
Therefore, the present work has the following hypothesis:
For airport recovery after irregularities, the sum of the optimum solutions in local system is not the global optimum.
The objective of the study is, in this way, to evaluate the relationship between the global solution and the local solutions related by the literature, with the focus on the quality, cost and effectiveness of both approaches.
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 method

As described by Bennell et al. [14], 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 heuristic and meta-heuristic methods [11], [13], [14], [15]. Such methods, in particular meta-heuristic, which seeks a near optimal solution, usually deliver satisfactory results with considerable reduction of computational time [13].
Among the above mentioned methods, the Genetic Algorithm (GA) has shown great potential [13], [15], [16], [17]. 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 [15].
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 [16], [18]. 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 [16], [18], [19].
Other important aspect of this method is the structure of chromosome utilized. In the major part of the literature, the chromosome has a vector form, which allows to record two information in each gene: one for the position and other for the value in that position. The Fig. 1 shows a common chromosome structure used in gate assignment problem. However, in their paper about a multi-objective gate assignment problem [19], Hu and Di Paolo bring another structure to the chromosome which allows to record more information through a two dimensional binary matrix (one row is dedicated to gate number), as shown in the example of the Fig. 2. These chromosome, used by the authors to record the relative position between aircraft in a queue at each gate, also permits to identify and to protect the common genes present in fittest members during the crossover [19]. This approach could be useful for the present work and will be object of further analysis.

Fig. 1 – Common chromosome structure

Fig. 2 – Example of Chromosome Structure used by Hu and Di Paolo [19]
One of the advantages of the use of the genetic algorithm approach is the inherent parallelism of the method [16], [18]. 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. [20], 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. Therefore, in the gate assignment problem addressed by the authors, they proposed to use 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).
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 [20].
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 [21], [22].
The study of the methods will be made separately and the authors will seek to publish the results of this comparison.
The project will be developed through Object Oriented Programming (OOP). This kind of language, based in objects and classes, has several advantages over non-oriented languages [17], [23].
Among these advantages, we highlight the possibility of finding errors more easily, since the action takes place inside the objects [17], [23] , 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 [17] 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.


References

[1]
Agência Nacional de Aviação Civil - ANAC (Brazil), "Lista de Aeródromo Privados," 24 February 2015. [Online]. Available: http://www.anac.gov.br/Area.aspx?ttCD_CHAVE=8. [Acesso em 27 March 2015].
[2]
Agência Nacional de Aviação Civil - ANAC (Brazil), "Lista de Aeródromos Públicos," 24 February 2015. [Online]. Available: http://www.anac.gov.br/Area.aspx?ttCD_CHAVE=8. [Acesso em 27 March 2015].
[3]
Agência Nacional de Aviação Civil - ANAC (Brazil), "Anuário do Transporte Aéreo - Dados estatísiticos e econômicos de 2013," Brasília-DF, 2014.
[4]
Agência Nacional de Aviação Civil - ANAC (Brazil), "Relatório de desempenho operacional dos aeroportos - Ano base 2012," 2013.
[5]
M. Bazargan and B. Vasigh, "Size versus efficiency: a case study of US commercial airports," Journal of Air Transport Management, vol. 9, pp. 187-193, 2003.
[6]
M. Bazargan, K. Fleming and P. Subramanian, "A simulation study to investigate runway capacity using TAAM," in Proceedings of the 2002 Winter Simulation Conference, San Diego, 2002.
[7]
A. Abdelghany, K. Abdelghany and R. Narasimhan, "Scheduling baggage-handling facilities in congested airports," Journal of Air Transport Management, vol. 12, pp. 76-81, 2006.
[8]
K. G. Zorografos, Y. Salouras and M. A. Madas, "Dealing with the efficient allocation of scarce resources," Transportation Research Part C, vol. 21, pp. 244-256, 2012.
[9]
G. Diepen, B. F. I. Pieters, J. M. van den Akker and J. A. Hoogeveen, "Robust planningofairportplatformbuses," Computers & Operations Research, vol. 40, pp. 747-757, 2013.
[10]
L. B. Reinhardt, T. Clausen and D. Pisinger, "Synchronized dial-a-ride transportation of disabled passengers at airports," European Journal of Operational Research, vol. 225, pp. 106-117, 2013.
[11]
M. D. D. Clarke, The airline recovery problem, Boston, MA: MIT International Center for Air Transportation, 1997, p. 26p.
[12]
K. F. Abdelghany, A. F. Abdelghany and G. Ekollu, "An integrated decision support tool for airlines schedule recovery during irregular operations," vol. 185, pp. 825-848, 2008.
[13]
C. H. Cheng, S. C. Ho and C. L. Kwan, "The use of meta-heuristics for airport gate assignment," Expert Systems with Applications, vol. 39, p. 12430–12437, 2012.
[14]
J. A. Bennell, M. Mesgarpour and C. N. Potts, "Airport runway scheduling," Annals of Operations Research, pp. 204: 249-270, 24 January 2013.
[15]
S. Huang, A. W. Sadek and L. Guo, "Computational-Based Approach to Estimating Travel Demand in Large-Scale Microscopic Traffic Simulation Models," Journal of Computing in Civil Engineering, vol. 27, pp. 78-86, January/February 2013.
[16]
Y. Gu and C. A. Chung, "Genetic Algorithm Approach to Aircraft Gate Reasssignment Problem," Journal of Transportation Engineering, vol. 125, pp. 384-389, October 1999.
[17]
R. Linden, Algoritmos Genéticos, Rio de Janeiro: Editora Ciência Moderna Ltda., 2012.
[18]
A. Bolat, "Models and a genetic algorithm for static aircraft-gate assignment problem," The Journal of the Operational Research Society, vol. 52, no. 10, pp. 1107-1120, october 2001.
[19]
X. B. Hu and E. Di Paolo, "An efficient genetic algorithm with uniform crossover for the multi-objective airport gate assignment problem," in IEEE Congress on Evolutionary Computation, Singapore, 2007.
[20]
H. M. Genç, O. K. Erol, I. Eksin, M. F. Berber and B. O. Güleryüz, "A stochastic neighborhood search approach for airport gate assignment problem," Expert Systems with Applications, vol. 39, p. 316–327, 2012.
[21]
A. Drexl and Y. Nikulin, "Multicriteria airport gate assignment and Pareto simulated annealing," IIE Transactions, vol. 40, pp. 385-397, 2008.
[22]
O. K. Erol and I. Eksin, "A new optimization method: Big Bang–Big Crunch," Advances in Engineering Software, vol. 37, pp. 106-111, 2006.
[23]
A. Drozdek, Data Structures and Algorithms in C++, Second Edition ed., Pacific Grove, CA: Brooks/Cole, 2000.


4