Solving aircraft sequencing problem by using genetic algorithms

Abstract

In typical cases, air traffic controllers make the schedule for arrivals and departures of aircraft on a runway based on the pre prepared schedule, where aircraft that are scheduled first are served first (a.k.a. First Come First Served – FCFS rule). In practice, it often happens that two or more aircraft are scheduled at the same time, and since only one can be served at a time, the others have to be shifted from service at a later time. Hence, the main issue stands at selecting the aircraft that have to be shifted, as, in general, their delay is correlated to excessive expense based on various factors, such as number of passengers, type of aircraft, precedence, ambient pollution, etc. For schedules with a large number of aircraft, deciding manually – which aircraft should be shifted based on FCFS sequence becomes quite complex. Consequently, in this paper, we present a genetic based algorithm to solve the problem of aircraft sequencing in a runway within a computation time of dozens of seconds by using a computing device with standard processing and memory capabilities. The results of the proposed algorithm are compared against three state of the art algorithms on existing test sets that in total consist of 527 instances. For 49.34% of instances, the proposed algorithm finds the optimal solutions, while its results are also quite competitive for difficult instances when compared against a state of the art solution based on the tabu search meta-heuristic. The computational results show that the proposed approach can be easily adapted and fine-tuned for application in practice.

Keywords

Air transport aircraft sequencing genetic algorithms

1. Introduction

In the airports, the air traffic controller has to communicate with the pilots, in order to direct them in their process of landing or taking off. The communication between them is done through a voice or data communication channel, where the exchange of intentions, directives and other important information takes place. In the perspective of the cognitive info-communication field [1], the mode of the communication can be classified as an intra-cognitive info-communication schema, as, in both ends of the communication channel, the human actors (i.e. a pilot and an air traffic controller) are utilized. More in depth, their type of information transfer can be classified as a sensor sharing communication, since the information, obtained or experienced by the envisioned actors, is merely transferred to the other end of the communication channel. Among the others, the shared information, can be used for improving the schedule of aircraft departure/arrival in a congested runway. For example, the pilot knows the actual weight of the aircraft (including its load), which can be used by the air traffic controller as one of the factors to determine the level of importance of the aircraft, and with that an eventual priority could be granted. In addition, the pilot can inform the air traffic controller about the time he/she estimates to land or depart, or even further important information such as the state of the flight: ambulance, state flight, military flight, etc. All such information can be useful in the process of preparation of the schedule for runway usage for a certain period of time.

In general, the airport slot coordination office receives requests, for allocating time slots for arrivals or departures, from aircraft operators. Often, the time slots required by some particular aircraft operator overlap with the time slot wanted by some other operators, as depicted in Fig. 1. Consequently, it is expected that two or more requests from aircraft operators are scheduled to arrive or depart at the same time slot. In cases of airports with only one runway, it is impossible to serve two aircraft at the same slot. Furthermore, for safety reasons, the International Civil Aviation Organization (ICAO) has put in place separation rules, which require that two different aircraft, being served consecutively, need to be separated from each other by some marginal time (see Fig. 2), which, in aviation domain terms, is known as separation minima. Depending on the type of succeeding and preceding aircraft, the separation minima can have different values, e.g., in situations where two consecutive aircraft include a light and medium or a medium and heavy aircraft, then the separation minima is 2 minutes, while in situations where a light aircraft is serviced after a heavy aircraft, the separation time is increased to 3 minutes.

Figure 1.

Aircraft sequence as per operator preferences.

In order to comply with ICOAs rules for separation minima, the initial proposed schedule from the operators need to be adjusted. One of the most trivial methods used by the air traffic control is the First Come First Served (FCFS) sequence, where the operator that is first registered for a given time slot is the first to be served, while the others are scheduled for latter available time slots. Nonetheless, such an approach is fairly naive, as it ignores important factors, denoted as delay cost, about individual aircraft, such as number of passengers, weight, air pollution and other influencing factors. Hence, the aim is to find an optimized sequence that reschedules some of the aircraft in a way that those aircraft with smaller delay cost are shifted at later time slots for service.

Furthermore, depending on the possibility to add new aircraft into the sequence, the ASP problem is labeled as static or dynamic one. In the static case, the sequence of aircraft is generated for a longer period (usually for a whole day), where no new aircraft can be added, whereas, in the dynamic case, new aircraft can be added into the sequence at any time.

In this paper, the static case of ASP problem is considered, where the corresponding aircraft sequence includes landings as well as departures. The envisioned problem is solved with a genetic algorithm approach, where four different variants are presented. In order to test the performance of proposed variants, the computational experiments are conducted on an extended data set from the literature.

The remainder of this paper is organized as it follows: Section 2 presents the related work regarding the different algorithms existing in the literature for the aircraft sequencing problem; Section 3 depicts the mathematical formulation of the problem; Section 4 describes the proposed genetic algorithm approach; Section 5 presents the computational experiments on the state of the art test set; and finally Section 6 concludes the paper.

2. Literature review

An early proposed formal specification of the aircraft sequencing problem (ASP), considering only arriving aircraft, is the mixed integer linear programming (MILP) model [2], which is solved by using two distinct approaches. The first approach is a deterministic one that is based on the branch and bound algorithm, whereas the second approach is non deterministic one based on genetic algorithms, which uses a neighborhood exploration mechanism consisting of a one point random crossover and a mutation operator that randomly changes a gene (aircraft landing time) within the chromosome that represents the aircraft sequence. Further, Stevens [3] designed an approach that is also based on genetic algorithms, whilst imposing constraints and conditions arising from practical situations in regard to constantly changing conditions of aircraft landings.

Figure 2.

Aircraft sequence when considering separation minima.

Ciesielski and Scerri [4] developed a genetic algorithm for the ASP problem that employed specialized crossover and mutation operators for favoring selected members of the population. The proposed approach was evaluated against a real data sets originating from Sydney Airport.

Beasley et al. [5] formulated the static case of an ASP problem for single and multiple runways by using a MILP model, which employs constraints that arise as limitations from real life (e.g. precedence, restricting the number of landings, etc.) [6]. Further, authors solve the problem to optimality by using a tree search approach based on linear programming, and present a heuristic algorithm for speeding up the search process.

Caprì and Ignaccolo [7] are the first to combine arrivals and departures into a single aircraft sequence within ASP, where they propose a genetic algorithm solution that utilizes two specialized crossover operators and a modified mutation mechanism. One of the crossover operators operates only on some genes, which are chosen randomly, while the other operator does the opposite procedure, by fixing some genes and operating with the others. The mutation mechanism, instead of producing a random change in a chromosome, produces a random swap between two genes on a chromosome.

Pinol and Beasley [8] consider the multiple runway case of the static Aircraft Landing Problem, where they present two population based heuristic approaches namely, Scatter Search and the Bionomic Algorithm.

Atkin et al. [9] propose four metaheuristic approaches for scheduling aircraft departures at London Heathrow airport that consists of two runways. All proposed metaheuristics, which include first descent, simulated annealing, steeper descent and tabu search, have similar neighborhood designed that is made of three operators, namely, swap single aircraft, shift aircraft and randomize a set of aircraft.

Hu and Chen [10] consider only arrivals in the ASP sequence and solve the problem by using a Receding Horizon Control (RHC) genetic algorithm. The introduction of the RHC strategy into the genetic algorithm has the function of speeding up the optimization process, by optimizing the aircraft arrival sequence only for N time slots ahead. At each time slot, the actual information on disposal is evaluated, and based on that, the optimized arrival sequence is generated for N time slots in the near future.

Likewise, Hu and Di Paolo [11] consider only arrivals in the ASP sequence and propose a binary genetic algorithm that is based on a binary representation instead of earlier permutation based solutions. The resulting representation is a binary matrix that enables employing a uniform crossover operator, which wouldn’t be feasible in earlier permutation based representations. Further, the strategy of RHC algorithm is also integrated into the proposed solution with the aim of allowing dynamic sequencing of aircraft arrivals. Later, Hu and Di Paolo [12] extend their genetic algorithm approach, based on the described uniform crossover, to be used for scheduling arriving aircraft in airports with multi runways.

In addition, Hu and Di Paolo [13] further modify their approach for sequencing aircraft arrivals by introducing the phenomenon of ripple-spreading on liquid surfaces into the genetic algorithms. In this approach, the original one dimensional aircraft sequence is projected into a two dimensional space, where aircraft, presented as points, are linked between each other by using a deterministic approach based on the ripple-spreading strategy.

More recently, Furini et al. [14, 15, 16] formulate the ASP problem for real scenario situations, where airports have single runways, which are used for both arrivals and departures. The problem was formalized using the Mixed Integer Linear Programming (MILP) model, and it was initially solved by using a rolling horizon algorithm (RHA) [13], which is then advanced to an iterative rolling horizon algorithm (IRHA) [15] that featured elements from the tabu search algorithm. The results obtained by RHA algorithm were compared against the results of First Come First Served (FCFS) rule, where it was evidenced that, for a data set of 12 realistic scenarios generated instances, an improvement of around 15% can be made over the sequences produced by the FCFS rule.

In the IRHA algorithm [15], the aircraft sequence is divided into smaller parts (chunks), which are then solved individually. Further, different methods are proposed for the chunk generation with a fixed number of aircraft, where individual methods are guided based on a number of predefined algorithm parameters, such as fixed cardinality, time gap and weight gap. The tabu search algorithm is used to enable escaping from local optima, whilst the neighborhood of the running solution is generated by using either the shift operator, which shifts an aircraft into the sequence, or swap operator, which swaps two aircraft in the sequence. The IRHA algorithm obtained much better results in comparison to the previous RHA algorithm, where the average improvement for the same data set is around 14%.

Furini et al. [15] also developed a dynamic programming approach for the ASP problem where they enforce the constraint for aircraft position shifting. This approach uses heuristic based upper bounds and a completion-lower bound mechanism for reducing the state space. The presented experimental results on real traffic data show that the presented algorithm outperforms the prior state of the art approach, which is based on a MILP model.

Just recently, an ongoing work in [17] has presented an Iterated Local Search based algorithm for aircraft sequencing, where, both arrivals and departures are considered. The algorithm uses a neighborhood exploration mechanism based on two operators, where the first one swaps any two fights in the sequence, whereas the second one shifts a given flight in some other position within the same sequence.

By analyzing the existing literature, we conclude that the version of ASP problem that considers both, arrivals and departures, is not intensively explored in terms of application of the genetic algorithm approaches. Nevertheless, Caprì and Ignaccolo [7] tackle the ASP problem with a genetic algorithm approach, but they present a computational study with a limited data set that includes only four instances with a maximum of forty aircrafts. Therefore, in this paper, we propose an extended genetic algorithm solution to the ASP problem, which, based on the technique used for updating the population, is presented in four different variants, namely generational, steady state, elitism and direct reproduction. Compared with the existing literature, this work can be distinguished with three main contributions: (1) presentation of four different variants of solutions to the ASP problem based on genetic algorithms; (2) introduction of a unique two point crossover that can be fine-tuned based on two parameters; (3) an intensive experimentation with the state of the art algorithms that show the effectiveness of the proposed solution on benchmark data sets from the literature.

3. Mathematical formulation

In the variant of aircraft sequencing problem (ASP) that encompasses departures and arrivals, a set of $n$ aircraft is given, where for each aircraft $i$ , the following details are known: the maximum delay $d_{i}$ expressed in time units (e.g. minutes), the cost of delay $w_{i}$ for a single time unit and the scheduled departure/arrival time $t_{i}$ . Furthermore, for each pair of aircraft $i$ and $j$ , the minimal separation time $T_{ij}$ between them is given. The solution to this problem has the goal of sequencing all the aircraft such that the overall cost of the delay (expressed in time unit delays), for the complete aircraft set, is minimized subject to a predefined number of constraints, as given below.

In the literature, there are two different MILP formulations for the ASP problem, where the first one was presented by Beasley et al. [5], and the second one was presented by Furini et al. [14]. These two mathematical formulations differ in the way they use the decision variables. Beasley et al. [5] use a decision variable to model the relative order between any two aircraft, whereas Furini et al. [14] use a decision variable for each aircraft, which models its position in the sequence. In the following, we present a mathematical formulation that is based on the model of Beasley et al. [5], which is defined by using two decision variables, namely $z_{i}$ , which represents the assigned time of departure/arrival of the aircraft, and $x_{ij}$ , which marks the relationship between a pair of aircraft and represents a logical variable that takes one, if aircraft $i$ is scheduled before aircraft $j$ , otherwise it takes a zero. In the following, individual constraints of the problem are outlined.

$\displaystyle\min\left(\sum\limits_{i=1}^{n}{w_{i}(z_{i}-t_{i})}\right)$ (1) $\displaystyle t_{i}\leqslant z_{i}\leqslant t_{i}+d_{i},\forall i=1,\ldots,n$ (2) $\displaystyle\sum\limits_{i=1}^{n}{x_{ij}=1,}\forall j=1,\ldots,n$ (3) $\displaystyle\sum\limits_{i=1}^{n-1}{x_{ij}=1,}\forall j=2,\ldots,n$ (4) $\displaystyle\sum\limits_{i=2}^{n}{x_{ij}=1,}\forall j=1,\ldots,n-1$ (5) $\displaystyle z_{i}\geqslant z_{j}+T_{ij}-M\left(1-x_{ij}\right),\forall i=1,% \ldots,n$ $\displaystyle\quad∼{}\forall j=1,\ldots,n$ (6) $\displaystyle x_{ij}\in\left\{0,1\right\},ij\in N,i\neq j$ (7)

where: $M$ is a large constant, and $N$ represent a natural number.

The objective function of the problem is represented by Eq. (1), which aims at minimizing the overall time unit delay of the complete sequence of the scheduled aircraft that include both, the departing and the arriving ones. Constraint (2) sets the time frame limits for rescheduling individual aircraft, which should be obeyed when they get reassigned in a particular time slot either for departure or arrival. Constraint (3) ensures that all aircraft are assigned a time slot for departure/arrival in the sequence. Constraints (4) and (5) together ensure that individual aircraft are assigned only once throughout the sequence. Constraint (6) defines the minimum separation time between consecutive aircraft that should be maintained, in order to avoid any interference between them. Finally, constraint (7) defines the scope of the values for the decision variable $x_{ij}$ and the indexes $i$ and $j$ of aircraft.

4. Solution approach

In air traffic control industry, the process of sequencing the arrivals and departures of the aircraft should be done in a matter of few seconds. Therefore, local search based metaheuristic techniques are utilized for solving the ASP problem. In this paper, the approach to solve the ASP problem is based on the framework of the Genetic Algorithm (GA), which is invented by Holland [18] and it is inspired by the genetics of living beings. The GA algorithm, at the beginning, constructs an initial random population, which then undergoes three generic procedures that are repeated for a number of times (generations). In the first procedure, each individual of the population is evaluated, whereas, in the second procedure, based on this evaluation, a number of individuals (parents) from the current generation are selected to form a group of children that are candidates to join the new generation of the population. The third procedure joins the parents and the newly formed children to create a new generation of the population, and then the GA algorithm restarts a new cycle from the first procedure.

4.1 Representation and initialization

An individual member (candidate solution) $I$ of the population to the ASP problem is represented as an array $I=\{a_{1},a_{2},\ldots,a_{i},\ldots,a_{n}\}$ of $n$ members (aircraft), where the value $a_{i}$ of member at position $i$ indicates that aircraft $a_{i}$ will be served at position $i$ in the sequence.

In a typical instance of an ASP problem, all aircraft are sorted, in ascending order, based on their departure/arrival time, where some of the aircraft might happen to have the same scheduled departure/arrival time. In this approach, the initialization of an individual member $I$ of the population is done based on the original order of aircraft in the input instance by following the First Come First Served (FCFS) rule, where flights with the same departure/arrival time are randomly selected to be shifted one after the other, in order to meet the minimum separation time requirement (a.k.a. Constraint (6) in Section 3).

Figure 3.

Crossover operator.

4.2 Evaluation and selection

Within the first procedure of GA algorithm, the members of the population get evaluated using only the “sum part” of Constraint [1] (i.e. without the objective of minimization). Whereas, the second procedure makes the process of the selection of some of the members from the population, who would take part in breeding new population for the next generation. The selection process is based on the tournament selection procedure, as shown in the following pseudo-code, which is quite straightforward and self-descriptive [19].

Algorithm 1: Tournament selection
1:	$P$ $\leftarrow$ Population
2:	$t$ $\leftarrow$ Tournament size
3:	Best $\leftarrow$ an individual selected at random from $P$
4:	For $i$ from 2 to $t$ do
5:	Current $\leftarrow$ an individual selected at random from $P$ that is not selected so far
6:	If Fitness (Current) $>$ Fitness (Best) then
7:	Best $\leftarrow$ Current
8:	Return Best

4.3 Genetic operators

The genetic operators comprise a unique crossover operator that is applied between two selected population members, and a mutation operator that mutates the children that are generated by the crossover operator.

4.3.1 Crossover

The proposed crossover operator (see Fig. 1) makes a recombination between any two selected members (parents) $A=\{a_{1},a_{2},\ldots,a_{i},\ldots,a_{n}\}$ and $B=\{b_{1},$ $b_{2},\ldots,b_{j},\ldots,b_{n}\}$ of the population by using Algorithm 2, which generates two new feasible members (children) that will take part in forming the new generation. The algorithm is guided by two parameters, namely crossover maximal difference (cmd) and crossover window width (cww), where the earlier one is used to control the maximal difference that can be tolerated between the interchanging parts in the two selected members of the population, whereas the latter parameter determines the size of the interchanging part (number of flights), which contains the flights that will be swept between the members.

Algorithm 2: Crossover
1:	cmd $\leftarrow$ crossover maximal difference
2:	cww $\leftarrow$ crossover window width
3:	$i\leftarrow$ Select a flight index randomly from parent $I_{p}$
4:	$j\leftarrow$ Select a flight index randomly from parent $I_{q}$ in the range [ $i$ $-$ cmd, $i$ $+$ cmw]
5:	$C_{p}^{\prime}\leftarrow$ Replace flights in $I_{p}$ in the range [ $i$ , $i$ $+$ cww] with flights from $I_{q}$ in the range [ $j$ , $j$ $+$ cww] by placing them in a random order
6:	$C_{q}^{\prime}\leftarrow$ Replace flights in $I_{q}$ in the range [ $j$ , $j$ $+$ cww] with flights from $I_{p}$ in the range [ $i$ , $j$ $+$ cww] by placing them in a random order
7:	$C_{p}\leftarrow$ Replace duplicated flights in $C_{p}^{\prime}$ with missing flights
8:	$C_{q}\leftarrow$ Replace duplicated flights in $C_{q}^{\prime}$ with missing flights
9:	Return $C_{p}$ and $C_{q}$

4.3.2 Mutation

The mutate operator swaps any two randomly selected aircraft in a given sequence that is represented by a population member (child) $A=\{a_{{1}},a_{2},\ldots,a_{i},$ $\ldots,a_{n}\}$ . The distance between the positions in the sequence of the selected aircraft cannot be greater than the value of the parameter denoted as mutate maximal distance (mmd).

In regard to defeating the infeasibility, only the constraint about the time frame limit need to be checked for the aircraft that are involved in the swap operation and the subsequent aircraft in the sequence. Still, the procedure for regulating the separation minima is the same as in the case of crossover operator.

4.4 Genetic algorithm

The implemented genetic algorithm can be qualified as generative in its nature, as the respective population is updated entirely at each generation. As presented in Algorithm 3, the approach at hand, besides the usual GA parameters, such as population size, maximum generations and tournament size, also uses some unique arguments, namely crossover wideness threshold(cwt), mutate distance threshold (mdt), crossover wideness percentage list (cwpl) and mutate distance percentage list (mdpl). All these parameters serve as a means to control the upper bound values for the arguments of the crossover operator (i.e. the parameter of crossover maximal difference and crossover window width) and mutation operator (i.e. the parameter of mutate maximal distance), respectively.

After creating the initial population that consists of ps individuals (solutions), the algorithm enters into a loop, which defines the number of generations that the algorithm will undergo, as specified by the maximum generations parameter. At each generation, the individuals in the population are assessed, and in case a particular individual shows that it is better than the best solution found so far, that individual is accepted as the new best found solution. Further, the values of the crossover maximal difference, crossover window width and mutate maximal distance parameters are reset randomly within the range that is described in Algorithm 3 (see lines 18 to 22). Next, until an entirely new population is created, at each run of the inner loop (see line 24), two individual $I_{p}$ and $I_{q}$ are selected as parents by using the tournament selection procedure. Then, the selected parents are used as input to the genetic operator algorithm, which produces two new individuals (children) that will part of the next population. The algorithm will terminate after the predefined number of generations is exceeded and return the best found solution.

4.5 Exploitative variations

The generative approach of the GA algorithm, described in Subsection 4.4, has more explorative attributes than exploitative ones, as its population is renewed entirely in each generation, hence making the algorithm more explorative in different regions of the search space. In order to create some exploitative variants of the algorithm, we have developed three additional approaches, namely elitism, steady-state and direct reproduction, which, in turn, are discussed more in details in the following.

4.5.1 Elitism

In the elitism version of GA algorithm, an additional parameter, namely the percentage of elite individuals (pei), is used to determine what portion of the elite (best fit) individuals from the current population will go directly into the population of the next generation. These elite individuals will make the algorithm exploit the neighborhood around them more in depth, hence making it more exploitative.

In order to select the portion of best fit individuals, at each generation, after the process of the evaluation of the population members, it is necessary to sort the members of the population based on the quality of the solutions they represent, which, in this implementation, is done by using the quick sort algorithm. Further, at the process of the selection, in case a number of individuals has the same evaluation and in the same time compete to enter the portion of best fit individuals, the resolution is made by randomly selecting individuals of the same quality, until the predefined elite quota is attained.

Algorithm 3: Generational genetic algorithm
1:	$n\leftarrow$ Number of aircraft
2:	ps $\leftarrow$ Population size
3:	mg $\leftarrow$ Maximum generations
4:	$t\leftarrow$ Tournament size
5:	cwt $\leftarrow$ Crossover wideness threshold
6:	mdt $\leftarrow$ Mutate distance threshold
7:	cwpl $\leftarrow$ {0.03, 0.04, 0.05} // Crossover wideness percentage list
8:	mdpl $\leftarrow$ {0.12,0.14,0.16} // Mutate distance percentage list
9:	population $\leftarrow$ {}
10:	For $i$ from 1 to psdo
11:	population $\leftarrow$ population $+$ {initialize a new random individual}
12:	best $\leftarrow$ Best member from population
13:	For $i$ from 1 to mgdo
14:	For $j$ from 1 to psdo
15:	Asses fitness (population ( $j$ ));
16:	If fitness (population ( $j$ )) better than fitness (best) then
17:	Best $\leftarrow$ population ( $j$ )
18:	cwp $\leftarrow$ Select a random member from cwpl
19:	mdp $\leftarrow$ Select a random member from mdpl
20:	cmd $\leftarrow$ Select a random number from 1 to cwt $+$ cwp* $n$
21:	cww $\leftarrow$ Select a random number from 1 to cwt $+$ cwp* $n$
22:	mmd $\leftarrow$ Select a random number from 1 to mdt $+$ mdp* $n$
23:	newpopulation $\leftarrow$ {}
24:	For $j$ from 1 to ps/2 do
25:	$I_{p}\leftarrow$ Select a member from population with tournament selection algorithm by using $t$
26:	$I_{q}\leftarrow$ Select a member from population with tournament selection algorithm by using $t$
27:	$C_{p}^{\prime}$ , $C_{q}^{\prime}\leftarrow$ Apply crossover in $I_{p}$ and $I_{q}$ by using cmd and cww
28:	$C_{p}$ , $C_{q}\leftarrow$ Apply mutate in $C_{p}^{\prime}$ and $C_{q}^{\prime}$ by using mmd
29:	newpopulation $\leftarrow$ newpopulation $+$ ( $C_{p}+C_{q}$ )
30:	population $\leftarrow$ newpopulation
31:	Returnbest

Table 1
Details about the flights in the simulation days

Day	Month/Year	Time (UTC)	Scheduled flights	Arrivals	Departures
1	August/2011	14:00–20:00	100	54	46
2	September/2011	14:00–21:00	121	68	53

4.5.2 The steady-state

In the steady state approach [20], the population of the algorithm is updated in a piecemeal mode, rather than updating it in its entirety. In comparison to generational approach, the steady state approach uses an additional parameter, namely the percentage of individuals to replace (pir), which defines what portion of the population will be renewed in the next population. The lower the value of this parameter is, the steadier the population will be, thus enabling the algorithm to be more exploitative around individuals that remain for longer generations into the population.

At each generation, a percentage of individuals, as specified by the respective parameter, will be randomly removed from the current population, in order to make room for the new individuals, which will be breaded based on the earlier described procedure for the processes of selection and crossover.

4.5.3 The variant with a direct reproduction structure

In this approach, we apply a special breading technique for genetic algorithms, proposed by Koza [21] when developing a tree style based genetic programming approach. The envisioned method uses an additional parameter, named probability of performing direct reproduction (ppdr), to determine the chance that individuals have to go directly into the next generation, without undergoing the regular processes of selection and crossover. This makes the algorithm highly exploitative [19], as several individuals of the current population will again show up in the next population.

In individual generations, after selection of the parents and before applying the crossover procedure, a particular number is generated randomly. If the generated number is smaller than the value of the parameter for performing direct reproduction, then the first selected parent is passed directly to the next population, otherwise the regular procedure for the crossover (using both parents) is applied to bread two new children that will get into the next population.

5. Computational experiments

In this section, the experimental results that are completed using the state of the art instances are presented. At first, a description of the different sets of instances that are used for experimentation is given, and then, the computational results are given for each set of instances, as well as the results for the best case scenario for some difficult instances.

The algorithm is developed by using the C# programming language through the developing environment of MS Visual Studio 2012. The experiments are completed by using an Intel i3 3.3 GHz processor with 1 GB of RAM memory in Windows Server 2008 operating system.

Table 2
Test set details

Instance set	Number of	Number of	Period of
	instances	flights	schedule (minutes)
A	12	60	14–210
B	500	15–24	20–66
C	15	70–150	110–306

5.1 Test set

In order to make an empirical study against the state of the art solutions, in the following experiments, we use the test set for the ASP problem that was created by Furini et al. [14, 16], with the purpose of testing RHA and IRHA approaches. The test set originates from the commercial air traffic schedule at Milano Linate Airport, which is the largest airport in Italy, consisting of two runways, although only one of them is used for commercial traffic. The test instances are created based on two simulation days, as shown in Table 1.

With the aim of making more congested air traffic schedules, Furini et al. [16] merged both simulation days into one. Since the 48 flights operating in both simulation days are not duplicated, the resulting congested schedule has a total of 173 flights, with 94 and 79 arrivals and departures, respectively.

A particular instance contains information about a number of scheduled flights within a period of time, where each flight is described with information such as: name, type of aircraft (e.g. Airbus A321, Boeing B737-800, etc.), size of aircraft (Light-L, Medium-M or Heavy-H), type of flight (Departure-D or Arrival-A), scheduled time, and weight of flight, which corresponds to the cost of time unit delay $w_{i}$ that was described in Section 3.

The calculation of the minimum separation distance $T_{ij}$ , expressed in units of time minutes, between any two consecutive aircraft, $i$ and $j$ , needs to consider the attributes of the size of aircraft and type of flight for both aircraft. In the following experiments, the minimum separation distance is calculated by using Expression (8), which is also used by Furini et al. [16].

$\displaystyle T_{ij}=\begin{cases}3,&(i_{\textit{type}}=j_{\textit{type}}=A)% \wedge\\ &(i_{\textit{size}}=M\wedge{j}_{\textit{size}}=L)\\ 4,&(i_{\textit{type}}=j_{\textit{type}}=A)\wedge\\ &(i_{\textit{size}}=H\wedge{j}_{\textit{size}}=L)\\ 2,&\text{otherwise}\end{cases}$ (8)

As specified in Table 2, the test set consist of three subsets, named A, B and C, which are all generated by combining the instances from the two simulation days taken from Milan Linate Airport. Set A consists of instances with 60 flights that are scheduled within a period of about 2.5 hours until 3.5 hours, whereas Set B consists of instances with a smaller number of flights (15–24) that are scheduled to be served in period that varies from 20 minutes to approximately one hour. Set C consist of instances with larger number of flights (70–150), with a scheduling period that varies from about 2 hours until 5 hours. Due to the smaller number of flights, Set B is considered to be more easily solvable, whereas because of the large number of flights, Set A and Set C are more difficult to be solved, and this is especially the case with Set C. A more detailed description of the Set A can be found in [14], whereas Set B and Set C are described more in depth in the other paper of Furini et al. [16].

Table 3

Results for Set A – score gap (%)

Instance	RHA	IRHA	E	G	SS	DR
FPT01	11.67	0.00	0.00	0.00	0.53	0.30
FPT02	14.83	7.57	0.00	0.46	0.00	0.27
FPT03	19.81	0.00	0.62	0.00	0.31	0.62
FPT04	24.93	0.00	0.00	0.04	0.00	1.47
FPT05	24.77	7.09	0.00	0.00	0.00	0.00
FPT06	30.13	1.76	0.00	0.00	0.00	0.00
FPT07	20.48	1.49	1.49	1.37	1.42	1.49
FPT08	13.47	1.76	1.68	1.74	1.68	1.76
FPT09	13.27	1.61	1.61	1.11	1.61	1.61
FPT10	9.05	1.40	1.40	1.36	1.40	1.40
FPT11	11.58	1.29	1.29	1.17	1.10	1.29
FPT12	2.36	0.00	0.00	0.05	0.00	0.00
Average	16.36	2.00	0.68	0.61	0.67	0.85

Table 4

Results for Set A – computation time (seconds)

Instance	E	G	SS	DR
FPT01	15.19	6.73	8.34	9.34
FPT02	11.18	9.10	11.98	11.04
FPT03	12.60	7.94	10.23	11.00
FPT04	17.08	7.21	7.28	10.13
FPT05	2.52	3.12	1.79	1.43
FPT06	3.09	5.55	3.00	1.80
FPT07	3.16	7.38	4.32	1.76
FPT08	2.41	5.68	3.75	1.31
FPT09	2.17	25.25	5.14	1.27
FPT10	2.47	7.36	5.28	1.29
FPT11	2.76	14.06	9.84	1.43
FPT12	1.46	5.11	2.42	0.76
Average	6.3	8.7	6.1	4.4

5.2 Experimental results

The results are computed for each of the four variants of the genetic algorithm presented in the previous section, which, in the following, will be referred using the subsequent abbreviations: E (Elitism genetic algorithm), G (Generational genetic algorithm), SS (Steady State genetic algorithm), and DR (the variant with Direct Reproduction). The presented results will be compared against the results of three state of the art methods, as in the following:

•
The Mixed Integer Linear Programming (MILP) model, which was presented by Beasley et al. [5], but it was solved by Furini et al. [16] using CPLEX 12.5 (with default parameter settings), hereinafter referred as Model A,
•
The Rolling Horizon Algorithm [14] (tested only using Set A), which is executed on an Pentium 4 processor with 3.00 GHz and 1 GB RAM under Linux operating system, hereinafter referred as RHA,
•
The Iterative Rolling Horizon Algorithm [16], which is executed on an Intel(R) Core(TM) 2 Duo processor with 3.2 GHz and 2 GB RAM under Linux operating system, hereinafter referred as IRHA.

The results of the Model A are used as benchmarks when calculating the average gap of the four variants of GA presented in this paper.

Note that in order to be able to compare the results of the proposed approaches versus state of the art approaches [14, 16], the partial constraint about the allowable time unit delay required for a particular flight (see Constraint (2) in Section 3) is not enforced, hence enabling the flights to be assigned at any time that is equal or later than the initial scheduled time.

In each experiment, every instance of a particular set is executed for 20 times, where respective minimal, maximal and average values are outlined for both, the quality of solution and the computation time.

Based on the preliminary experiments with a selected number of instances from different test sets, the values of the algorithm parameter are fine-tuned, and read as it follows: ps $=$ 2000, mg $=$ 200 (except for instance Set C, which it is set to 500), $t=$ 0.01ps, cwt* $=$ 1, mdt $=$ 5, cwpl $=$ {0.03, 0.04, 0.05}, mdpl $=$ {0.12,0.14,0.16}, pir $=$ 0.05ps, pei* $=$ 0.6ps and ppdr* $=$ 0.5.

Table 5
Results for Set B – score gap (%)

No. flights IRHA E G SS DR

15   4.99   5.05   4.99   5.07   5.76

16   7.37   7.41   7.37   7.46   8.18

17   9.44   9.47   9.44   9.47 10.39

18 11.92 11.95 11.92 11.96 12.90

19 14.17 14.18 14.17 14.17 15.27

20 17.30 17.32 17.31 17.33 18.48

21 21.25 21.23 21.22 21.23 22.45

22 24.76 24.77 24.76 24.76 25.99

23 27.80 27.80 27.80 27.81 29.01

24 33.36 33.36 33.36 33.36 34.67

Average 17.24 17.25 17.24 17.26 18.31

Table 6
Results for Set B – computation time (seconds)

No. flights E G SS DR

15 0.73 0.40 0.24 0.32

16 0.97 0.42 0.35 0.43

17 0.99 0.49 0.34 0.40

18 1.27 0.61 0.45 0.49

19 1.12 0.57 0.43 0.52

20 1.41 0.68 0.44 0.59

21 1.59 0.74 0.53 0.63

22 1.56 0.79 0.50 0.72

23 1.79 0.90 0.64 0.70

24 1.95 1.06 0.75 0.68

Average 1.34 0.67 0.47 0.55

5.2.1 Results for Set A

No. flights	IRHA	E	G	SS	DR
15	4.99	5.05	4.99	5.07	5.76
16	7.37	7.41	7.37	7.46	8.18
17	9.44	9.47	9.44	9.47	10.39
18	11.92	11.95	11.92	11.96	12.90
19	14.17	14.18	14.17	14.17	15.27
20	17.30	17.32	17.31	17.33	18.48
21	21.25	21.23	21.22	21.23	22.45
22	24.76	24.77	24.76	24.76	25.99
23	27.80	27.80	27.80	27.81	29.01
24	33.36	33.36	33.36	33.36	34.67
Average	17.24	17.25	17.24	17.26	18.31

No. flights	E	G	SS	DR
15	0.73	0.40	0.24	0.32
16	0.97	0.42	0.35	0.43
17	0.99	0.49	0.34	0.40
18	1.27	0.61	0.45	0.49
19	1.12	0.57	0.43	0.52
20	1.41	0.68	0.44	0.59
21	1.59	0.74	0.53	0.63
22	1.56	0.79	0.50	0.72
23	1.79	0.90	0.64	0.70
24	1.95	1.06	0.75	0.68
Average	1.34	0.67	0.47	0.55

The instances in Set A were solved to optimality by Model A [16], therefore the corresponding results are used as benchmark for compering the results of the different variants of the genetic algorithm proposed in this paper. Further, the optimal results of the IRHA approach for Set A are computed by Furini et al. [16] with a computation time of 120 seconds, expect for instance “FPT12”, whose results are generated only for 40 seconds.

In Table 3, the results, expressed in percentage gap against Model A, of the two state of the art solutions (denoted as RHA and IRHA) are presented, along with the results of the four proposed variants of GA (denoted as E, G, SS and DR). From Table 3, it is evident that, on average, all four variants of the GA algorithm outperform the state of the art algorithms (denoted as RHA and IRHA), as their average margin against the optimal solutions (obtained by Model A) is lower than 1%, as opposed to RHA and IRHA algorithms, whose score gap margin is 16.36% and 2%, respectively. In between the variants of the GA algorithm itself, the generational approach (G), in average, produces better results than the other three approaches with an advantage, in terms of score gap, of slightly more than 0.05%.

Table 7
Results for Set C – score gap (%)

Instance	No.	IRHA	E	G	SS	DR
	flights
FPT_0_69	70	60.33	56.79	56.79	56.79	56.79
FPT_50_119	70	91.44	84.35	84.35	84.35	84.35
FPT_100_169	70	65.12	57.54	57.54	57.54	57.54
FPT_0_89	90	79.77	75.04	74.89	75.17	75.19
FPT_40_129	90	91.65	82.77	82.77	82.77	82.77
FPT_80_169	90	87.64	74.14	74.14	74.27	74.14
FPT_0_109	110	87.54	81.04	80.94	80.96	80.84
FPT_30_139	110	93.02	85.19	85.19	85.27	85.19
FPT_60_169	110	94.73	87.46	87.40	87.63	87.57
FPT_0_129	130	91.33	82.75	82.69	82.75	82.78
FPT_20_149	130	93.23	85.60	85.52	85.45	85.51
FPT_40_169	130	94.09	86.16	86.28	86.23	86.20
FPT_0_149	150	92.64	84.54	84.73	84.61	84.54
FPT_10_159	150	93.85	86.23	86.49	86.26	86.22
FPT_20_169	150	94.12	86.24	86.70	86.36	86.30
Average		87.37	79.72	79.76	79.76	79.73

Table 8

Results for Set C – computation time (seconds)

Instance	No.	E	G	SS	DR
	flights
FPT_0_69	70	15.32	18.98	11.49	20.83
FPT_50_119	70	8.78	7.31	2.73	6.08
FPT_100_169	70	5.20	5.67	2.26	3.19
FPT_0_89	90	29.07	34.66	40.04	38.74
FPT_40_129	90	13.94	13.35	6.00	9.67
FPT_80_169	90	36.79	25.92	18.26	17.78
FPT_0_109	110	77.91	94.68	68.40	52.55
FPT_30_139	110	25.13	31.22	11.60	16.50
FPT_60_169	110	46.85	115.01	39.72	38.57
FPT_0_129	130	71.38	140.24	93.42	59.47
FPT_20_149	130	59.75	130.51	35.74	54.77
FPT_40_169	130	61.65	125.73	92.39	47.34
FPT_0_149	150	137.15	148.76	88.36	115.86
FPT_10_159	150	119.48	170.32	85.95	104.76
FPT_20_169	150	74.58	138.54	87.42	48.12
Average		52.20	80.06	45.58	42.28

Table 9

Best results for Set A and Set C

#	Instance	Model A	IRHA	E	G	SS	DR	GA (best fitness)	GA vs.	GA vs.
		(lower bound)							Model A (%)	IRHA (%)
1	FPT01.txt	265	265	265	265	265	265	265	0.00	0.00
2	FPT02.txt	293	293	293	293	293	293	293	0.00	0.00
3	FPT03.txt	255	255	255	255	255	255	255	0.00	0.00
4	FPT04.txt	268	268	268	268	268	268	268	0.00	0.00
5	FPT05.txt	249	249	249	249	249	249	249	0.00	0.00
6	FPT06.txt	167	167	167	167	167	167	167	0.00	0.00
7	FPT07.txt	198	198	201	198	198	201	198	0.00	0.00
8	FPT08.txt	167	167	167	167	167	170	167	0.00	0.00
9	FPT09.txt	183	183	186	183	186	186	183	0.00	0.00
10	FPT10.txt	211	211	214	211	214	214	211	0.00	0.00
11	FPT11.txt	229	229	232	229	229	232	229	0.00	0.00
12	FPT12.txt	207	207	207	207	207	207	207	0.00	0.00
13	FPT_0_69.txt	261	604	604	604	604	604	604	56.79	0.00
14	FPT_50_119.txt	312	2272	1994	1994	1994	1994	1994	84.35	$-$ 12.24
15	FPT_100_169.txt	338	796	796	796	796	796	796	57.54	0.00
16	FPT_0_89.txt	331	1332	1316	1316	1316	1316	1316	74.85	$-$ 1.20
17	FPT_40_129.txt	408	2885	2368	2368	2368	2368	2368	82.77	$-$ 17.92
18	FPT_80_169.txt	390	1800	1508	1508	1508	1508	1508	74.14	$-$ 16.22
19	FPT_0_109.txt	408	2131	2115	2115	2115	2115	2115	80.71	$-$ 0.75
20	FPT_30_139.txt	458	3935	3055	3055	3055	3055	3055	85.01	$-$ 22.36
21	FPT_60_169.txt	451	5019	3577	3577	3577	3577	3577	87.39	$-$ 28.73
22	FPT_0_129.txt	509	3167	2909	2913	2909	2909	2909	82.50	$-$ 8.15
23	FPT_20_149.txt	536	4846	3649	3655	3655	3649	3649	85.31	$-$ 24.70
24	FPT_40_169.txt	511	5159	3691	3702	3691	3691	3691	86.16	$-$ 28.46
25	FPT_0_149.txt	593	4467	3786	3832	3797	3786	3786	84.34	$-$ 15.25
26	FPT_10_159.txt	576	5808	4142	4210	4150	4142	4142	86.09	$-$ 28.68
27	FPT_20_169.txt	577	6434	4171	4283	4183	4171	4171	86.17	$-$ 35.17
	Average								44.23	$-$ 8.88

In terms of computation time, due to differences in the capacities of machines used, no direct comparison can be made against the state of the art algorithms. Nevertheless, when comparing the different variety of GA (see Table 4), the variant with Direct Reproduction (DR) approach is approximately as twice as fast as the Generational (G) approach, and around 50% faster than the remaining two approaches, although this goes at the cost of a slight decrease in the side of the quality of the solutions obtained. The speed of the DR variant can be reasoned when considering the process of the population update, which, in the case of DR variant, occurs much rarely. On the other hand, the generational (E) variation is much slower due to the need for a complete population updated in every single generation.

5.2.2 Results for Set B

Table 5 shows the experimental results of the four variants of the GA algorithm along with the results the IRHA algorithm, which are averaged over the subsets of instances that contain equal number of flights. The benchmark results of Model A and IRHA approach were computed by Furini et al. [16] by imposing a time limit of 15 seconds.

In terms of quality of solutions, the averaged figures in Table 5 show that, for Set B, the generative (G) variant of the proposed algorithm equals the results obtained by IRHA algorithm, while the other three variants of the GA algorithm remain slightly behind the results that are obtained by IRHA algorithm, with the direct reproduction (DR) variant having the largest score gap of 18.31% against the lower bound values obtained by Model A. All GA algorithm variants find the lower bound solutions for 49.6% of instances (i.e. 248 out of 500), except for DR variant, which finds 48.4% of the lower bound solutions in the same instance set (i.e. 242 out of 500). These results prove that the proposed GA algorithm variants are competitive to the IRHA algorithm for the Set B of instances.

Table 6 shows the computation time of the four variants of GA, where results are averaged over the instances that have the same number of flights. As it can be seen in Table 6, the steady state (SS) variant, with an average running time of less than half of the second, is the fastest, whereas the elitism (E) variant, with an average running time of 1.34 s, is the slowest. This longer computation time required by the elitism (E) variant can be reasoned due to the need for sorting the population members in each generation.

5.2.3 Results for Set C

Table 7 presents the results for Set C of all variants of GA algorithm and also the IRHA approach, which are shown in the form of percentage score gap versus the lower bound values obtained by Model A, where the results are computed by Furini et al. [16] using CPLEX by imposing a time limit of 5 hours.

It could be seen that, on average, all four variants of the GA algorithm outperform IRHA approach by a margin of around 7.6%. In this test set, the best performing variants of the GA algorithm are the elitism (E) and direct reproduction (DR) variants, which, in terms of quality of solutions, have an average score gap against the lower bound values of 79.72%, as opposed to other two variants, whose score gap stands at 79.76%.

5.2.4 Results of best case scenario for difficult instances

Since Set A and Set C of instances have many more flights in their schedules than Set B of instances, the level of difficulty in solving an instance from Set A or Set C is much higher than solving an instance from Set B [16].

In Table 9, we present the best results obtained for these two test sets, where the best results for the state of the art approaches (i.e. Model A and IRHA) are presented, along with the results for the respective variants of the GA algorithm and their comparison versus the state of the art algorithms. The results show that the GA algorithm finds the lower bound solutions for 44.44% instances (12 out of 27 instances), whereas for 100% of instances, it is either better (48.15%) or equal (51.85%) than the IRHA algorithm. When the results are averaged over these two difficult sets of instances, the quality of the solutions obtained by the GA algorithm is better than the quality obtained by the IRHA algorithm for 8.88%. If the results of different instances among the different variants of the GA algorithm are compared, it can be noticed that the generational (G) variant has managed to find either the lower bound solution or the best found solution among all variants, for instances with up to 110 aircraft, whereas for instances with 130 and 150 aircraft, there are the elitism (E) and direct reproduction (DR) variants the ones that dominate.

6. Conclusion and future work

This paper deals with the aircraft sequencing problem, which has to do with making the sequence of arrivals and departures of the aircraft in a distinct runway of a given airport. An optimized scheduled sequence is aimed at minimizing the delays of individual aircraft in the sequence subject to a predefined number of hard constraints that might be applicable in the domain of aircraft sequencing. The paper at hand, considers hard constraints such as the minimal separation time between aircraft, disallowing aircraft assignments before their scheduled time and allowing no possibility for two particular aircraft to be assigned at the same time.

Being grounded on the procedure for updating the population, four different variants of genetic algorithm, namely elitism, generational, steady state and direct reproduction, are designed to solve the ASP problem efficiently for the state of the art instances. Within a computation time of one minute or less, high quality solutions are found in the three sets of test instances. The comparison results versus the state of the art IRHA algorithm show an average improvement of around 1.3% and 7.6% for the most difficult sets A and C, respectively, whereas an equivalent score gap is achieved for easier instances that are part of Set B. For all three sets, with a total of 527 instances, the lower bound (LB) solutions were found in 49.34% of them.

Based on the presented experimental results, we conclude that on congested airport runways, in situations where all flight information is known beforehand (i.e. the static case of aircraft sequencing), the proposed algorithm can be used to implement practical applications to assist air traffic controllers in making runway operation schedules, for both, arrivals and departures of aircraft. As future work, it might be interesting to investigate the fine tuning of the algorithm parameters, in order to come with a version of the algorithm that has a faster computation time, even though this might lead to a slight reduction in terms of quality of obtained solutions. A faster computation time might be needed in situations where dynamic re-scheduling is required to cope with changes that often arise due to different causes (e.g. weather conditions, emergency landing, congested air traffic, etc.).

The solution to the problem at hand is searched only in the feasible part of the search space, hence, as a future work, it would be worth investigating the possibility to allow the algorithm to also move around the infeasible part of the search space by applying the so called strategic oscillation mechanism proposed by [22].

Footnotes

Acknowledgments

The authors would like to thank prof. Dr. Bujar Krasniqi for proof reading this paper. Further, we would like to thank two anonymous reviewer for their valuable feedback, which helped improve the correctness and readability of the paper.

References

Baranyi

Csapo

Sallai

. Cognitive Infocommunications (CogInfoCom). Springer 2015.

Abela

Abramson

Krishnamoorthy

De Silva

Mills

. Computing optimal schedules for landing aircraft. In Proceeding 12th National ASOR Conference, Adelaide, Australia1993; 71.

Stevens

. An approach to scheduling aircraft landing times using genetic algorithms. Citeseer 1995.

Ciesielski

Scerri

. Real time genetic scheduling of aircraft landing times. In IEEE World Congress on Computational Intelligence1998.

Beasley

Krishnamoorthy

Sharaiha

Abramson

. Scheduling aircraft landings – the static case. Transportation2000; 34: 180-197.

Pallottino

Sciomachen

. Scienze delle decisioni per i trasporti. Milano1999.

Capriì

Ignaccolo

. Genetic algorithms for solving the aircraft-sequencing problem: The introduction of departures into the dynamic model. Journal of Air Transport Management2004; 10(5): 345-351.

Pinol

Beasley

. Scatter search and bionomic algorithms for the aircraft landing problem. European Journal of Operational Research2006; 171(2): 438-462.

Atkin

Burke

Greenwood

Reeson

. A metaheuristic approach to aircraft departure scheduling at London Heathrow airport. Computer-aided Systems in Public Transport2008; (Springer Berlin Heidelberg), 235-252.

10.

Chen

. Genetic algorithm based on receding horizon control for arrival sequencing and scheduling. Engineering Applications of Artificial Intelligence2005; 18(5): 633-642.

11.

Di Paolo

. Binary-representation-based genetic algorithm for aircraft arrival sequencing and scheduling. IEEE Transactions on Intelligent Transportation Systems2008; 9(2): 301-310.

12.

Di Paolo

. An efficient genetic algorithm with uniform crossover for air traffic control. Computers & Operations Research2009; 36(1): 245-259.

13.

Di Paolo

. A ripple-spreading genetic algorithm for the aircraft sequencing problem. Evolutionary Computation2011; 19(1): 77-106.

14.

Furini

Persiani

Toth

. Aircraft sequencing problems via a rolling horizon algorithm. Lecture Notes in Computer Science2012; 7422: 273-284.

15.

Furini

Kidd

Persiani

Toth

. State space reduced dynamic programming for the aircraft sequencing problem with constrained position shifting. Combinatorial Optimization2014; (Springer International Publishing), 267-279.

16.

Furini

Kidd

Persiani

Toth

. Improved rolling horizon approaches to the aircraft sequencing problem. Journal of Scheduling2015; 1-13.

17.

Bytyçi

Sylejmani

Dika

. Iterated local search algorithm for planning the sequence of arrivals and departures at airport runways. In Mipro, 2016.

18.

Holland

. Adaptation in Natural and Artificial Systems, 1975.

19.

Luke

. Essentials of Metaheuristics. Lulu, 2013.

20.

Whitley

Kauth

. Genitor: A different genetic algorithm. 1988.

21.

Koza

. Genetic programming: On the programming of computers by means of natural selection. MIT Press, 1992.

22.

Glover

Laguna

. Tabu Search. Norwell, MA, 1997.

Solving aircraft sequencing problem by using genetic algorithms

Abstract

Keywords

1. Introduction

4.1 Representation and initialization

4.3 Genetic operators

4.3.1 Crossover

4.3.2 Mutation

4.4 Genetic algorithm

4.5 Exploitative variations

4.5.1 Elitism

Table 1 Details about the flights in the simulation days

4.5.3 The variant with a direct reproduction structure

5. Computational experiments

Table 2 Test set details

Table 7 Results for Set C – score gap (%)

5.2.3 Results for Set C

5.2.4 Results of best case scenario for difficult instances

6. Conclusion and future work

Footnotes

Acknowledgments

References

Table 1
Details about the flights in the simulation days

Table 2
Test set details

Table 7
Results for Set C – score gap (%)