The Steady State Evolutionary Algorithm (SSEA) used in the Airport Baggage Sorting Station Assignment Problem (ABSSAP) is potentially important for a wider variety of problems other than the ABSSAP. By way of illustration, here we look at applying the SSEA to the more widely studied AGAP.
Some of the metaheuristics and constructive algorithms previously used in the ABSSAP are modified, modifications which are required to be able to apply these metaheuristics to the AGAP, and the constructive algorithms are used as initial solutions in the SSEA presented here for the AGAP. The SSEA is studied, and compared with other metaheuristics approaches, which performance is studied in regard to the different objectives used at London Heathrow airport.
Keywords: Airport Gate Assignment Problem; Scheduling; Heuristics; Evolutionary Algorithms
According to [10] whereas only 16% of the air traffic delays are attributable to the point at which the aircraft is airborne with 26% from taxiout and 8% from taxiin, the remaining delays may be derived from delays where the aircraft are at a gate (50%), which reveals the gates to be of considerable importance in reducing overall airport delays.
The objective most used in the current AGAP literature corresponds to the improvement in service satisfaction, assured to be achieved by reducing passenger walking distance inside the terminal building. When considering the passengers walking distance the AGAP can be modeled by analogy with the NPhard quadratic assignment problem, as shown by [11], [12] and [13], which is a facility location problem where the cost of assigning a flight to a gate depends on the assignment of other resources and the transport volume between two resources (see also [14]).
Also with the increase in passenger traffic volumes and number of flights, the complexity of this task and the number of factors to be considered have increased significantly, and efficient gate utilisation has received considerable attention in past years, e.g. [18], [6], [15] and [16], [17], [18], and [19]. Given that a gate may be required for up to three different operations, namely arrival, parking and departure, the number of assignments required may have increased significantly in comparison with those for the ABSSAP. These also increase the problem complexity and provide more reasons for investigating some metaheuristic approaches, such as the Steady State Evolutionary Algorithm (SSEA) initially presented in [20] and used in [21] and [22] for the ABSSAP.
The similarities between the AGAP and the ABSSAP makes particularly interesting to determine whether the SSEA is also appropriate for the AGAP. However, the SSEA needs first to be adapted to the AGAP.
The model used in the ABSSAP, which it is presented in [25], is modified and extended to represent the remote stand, where i = 0 equates to the dummy stand as used in the ABSSAP, and i = N + 1 represents the remote stand, and where N represents the number of real stands at gates. Where the term remote stand is used, it refers to the dummy remote stand. The dummy remote stand may also be used solely for parking operations where arrivals and departures are not permitted by this resource. This means that when a solution is obtained and the dummy remote stand has been assigned to certain aircraft, then these aircraft must be assigned to real physical stands whether remote or otherwise.
The main reason for this procedure is to speed up the generation of solutions, as the algorithm should already be endeavoring to reduce the number of tows (objective ‘Minimize Number of Towing Operations’ presented in Section 5.3), which includes the reduction of the number of remote assignments. In this representation, those which are commonly regarded as two different flights, namely the arrival and departure flights, are considered here to be only one group composed of three operations: arrival, parking and departure, as shown in Figure 3. The relationship between these operations relates to the same aircraft, but may differ in the use of other resources such as the crew.
In the following sections the only case under consideration is that where the parking of an arriving and/or departing flight may be assigned to the same stand as the arrival or departure activity, or to the remote dummy stand, Figure 4.
It is assumed that aircraft j may be used for three assignments, such that the model may be expressed as follows: the assignment of aircraft j to stands i, l, and q is expressed as ${y}_{ij}{}^{a}=1,{y}_{lj}{}^{p}=1$ and ${\text{y}}_{\text{qj}}{}^{\text{d}}\text{=1}$ respectively. There are now two new base service duration constants, one for the flight arriving, ${\text{T}}_{\text{j}}{}^{\text{a}}$ , and the other which corresponds to the parking base service duration, ${\text{T}}_{\text{j}}{}^{\text{p}}$ , if the corresponding aircraft were to be assigned to a remote stand. The commencement and completion times of a parking operation are fixed, based on the values of the departure time ${\text{e}}_{\text{j}}{}^{\text{d}}$ and arrival time ${\text{\tau}}_{\text{j}}{}^{\text{a}}$ , given that ${\text{e}}_{\text{j}}{}^{\text{a}}{\text{=\tau}}_{\text{j}}{}^{\text{a}}{\text{+T}}_{\text{j}}{}^{\text{a}}$ and ${\text{\tau}}_{\text{j}}{}^{\text{d}}{\text{=e}}_{\text{j}}{}^{\text{d}}{\text{T}}_{\text{j}}{}^{\text{d}}$ then ${\text{\tau}}_{\text{j}}{}^{\text{p}}{\text{=e}}_{\text{j}}{}^{\text{a}}{\text{,e}}_{\text{j}}{}^{\text{p}}{\text{=\tau}}_{\text{j}}{}^{\text{d}}$ and ${\text{T}}_{\text{j}}{}^{\text{p}}{\text{=\tau}}_{\text{j}}{}^{\text{d}}{\text{e}}_{\text{j}}{}^{\text{a}}$ . The list of constants for this model is shown in Table 1 and the list of decision variables is shown in Table 2.
In the AGAP the activity k of group j may take the values a, p or d (P_{j} = 3) whereas in the ABSSAP activity p was represented as an integer (1 ≤ p ≤ P_{j}). However in the AGAP y refers to aircraft, and there are extra constraints which do not allow parking activities to be assigned to stands other than the dummy parking stand (also called the dummy remote stand), or their corresponding arrival and departure stands. The operations represented by ‘a’, ‘p’ and ‘d’ refer to the arrival, parking and departure operations respectively of the same aircraft.
Name 
Description 
N 
The total number of gates under consideration. 
M 
The total number of aircraft to which gates should be allocated. 
k 
The type of operation, arrival, parking or departure, k ∈ {a, p, d}. 
P_{j} 
The total number of activities associated with aircraft 
k 
j in a full cycle, 1 ≤ P_{j} ≤ 3. 
T_{j} 
The base service duration for aircraft j and activity k. 
B_{j}^{k} 
The desired buffer time for aircraft j and activity k. The parking operation does not have any buffer time associated with it, i.e. B_{P}^{j} = 0. 
e_{j}^{k} 
The end service time for aircraft j and activity k. 
τ_{j}^{k} 
The base starting service time for aircraft j and activity 
k 
k, τjk = ejk − T_{j}^{k}. 
t_{j} 
The target starting service time for aircraft j and activity k, T_{j}^{k} = ejk − T_{j}^{k} − B_{j}^{k}, assuming the full buffer time is available. Whereas T_{j}p = t_{j}^{d} − eja and ejp = t_{j}^{d}. 
xij 
Expresses to which stand (i) aircraft j can be assigned, 
Name 
Description 
y_{ij}^{k} 
Specifies the assignment of aircraft to stands. y^{i}_{jk} = 1, if gate i ∈ [1 . . . N] is allocated to aircraft j ∈ [1 . . . M] for activity k ∈ {a, p, b}, and 0 otherwise. 
r_{j}^{k} 
Specifies the necessary reduction in service time for activity k of aircraft j ∈ [1 . . . M], given the allocated starting service time, s^{k}_{j} . 
s_{j}^{k} 
The allocated starting service time for activity k{a, p, d} of aircraft j [1. . . M] and given that a gate can only service one aircraft at a time then sjk can be determined from r_{j}^{k} since s^{k}_{j} = t^{k}_{j} − r^{k}_{j} and t^{j}_{p} = e^{a}_{j}. 
$$\sum _{i=1}^{N}\text{}\sum _{k\in \{a,p,d\}}{\text{y}}_{ij}^{k}={P}_{j}\text{}\forall \text{}j\in [\mathrm{1.......}M]\text{[1]}$$
$$\sum _{i=0}^{N+1}{\text{y}}_{ij}^{k}=1\text{}\forall \text{j}\in \text{[1}\mathrm{.....}\text{M][2]}$$
$${y}_{(N+1)j}^{a}={y}_{(N+1)j}^{d}=\forall \text{}j\in [\mathrm{1.....}M]\text{[3]}$$
The dummy stand (i = 0) cannot be assigned to parking activities. The remote dummy (i = N + 1) allows overlapping activities and always has the capacity to be assigned to a parking activity, Equation 4.
$${y}_{0j}^{p}=0\text{}\forall \text{}j\in [\mathrm{1.....}M]\text{[4]}$$
The parking activity may be assigned to the same stand as its associated arrival or departure activities, Inequality 5.
$${y}_{ij}^{p}\le ({y}_{ij}^{a}\text{+}{y}_{ij}^{d})\text{}\forall \text{}i\in [\mathrm{1.....}N],j\in [\mathrm{1.....}M]\text{[5]}$$
$${y}_{ij}^{k}\le {x}_{ij}\forall i\in [\mathrm{1.....}N],j\in [\mathrm{1.....}M]\text{andk}\in \text{{a,p,d}[6]}$$
$$\sum _{q,u,v\in oj\cup j}\sum _{k\in \{a,p,d\}}({y}_{rq}^{k}+{y}_{lu}^{k}+(2*{y}_{iv}^{k}))\le 2\text{[7]}$$
Based on Inequality6, example in Figure6 pro vides the following restrictions. This means that stand 3 occupies the combined space of stands 1 and 2, and aircraft 3 cannot be assigned to either stands 1 or 2 $\left({x}_{13}={x}_{23}=\text{}0\right)$, whereas aircraft 1 and 2 cannot be assigned to stand 3 $\left({x}_{31}={x}_{32}=\text{}0\right)$ as shown in Table 3
y_{11}k ≤ x_{11} = 1 y_{12}k ≤ x_{12} = 1 y_{13} k ≤ x_{13} = 0 
y_{21}k ≤ x_{21} = 1 y_{22}k ≤ x_{22} = 1 y_{23} k ≤ x_{23} = 0 
y_{31}k ≤ x_{31} = 0 y_{32}k ≤ x_{32} = 0 y_{33}k ≤ x_{33}= 1 
k$$\in $$ {a, p, d} 
$$\mathrm{max}\sum _{i=1}^{N}\text{}\sum _{j=1}^{M}\text{}\sum _{k\in \{a,p,d\}}{\text{y}}_{ij}^{k}\text{[8]}$$
Given that parking is always assured since the parking activity can always be assigned to the dummy remote stand, then Formula 8 is equivalent to Formula 9.
$$\mathrm{max}\sum _{i=1}^{N}\text{}\sum _{j=1}^{M}\text{}\sum _{k\in \{a,d\}}{\text{y}}_{ij}^{k}\text{[9]}$$
The preference for assigning the parking activities to the same stand as one of the associated arrival or departure flights, is taken account of in the objective ‘Minimize Number of Towing Operations’ presented in Section 5.3.
To take account of the different airline preferences a list of gates and a weight, representing the level of preference for the gate, is used. This list could be compiled based on past historical data of gates assigned to the airline, such that the constant θ_{αj} is 1 when aircraft j belongs to airline α and zero otherwise and there is a set of historical flights represented by H. The preference of airline i for stand i may then be expressed by Equation 10, and the objective by Formula 11.
$${\delta}_{\alpha i}=\frac{{\sum}_{j}^{H}{\sum}_{k\in \{a,d\}}{\theta}_{\alpha j}*{y}_{ij}^{k}}{{\sum}_{i=1}^{N}{\sum}_{j}^{H}{\sum}_{k\in \{a,d\}}{\theta}_{\alpha j}*{y}_{ij}^{k}}\text{[10]}$$
$$\mathrm{max}\sum _{i=1}^{N}\text{}\sum _{j=1}^{M}\text{}\sum _{k\in \{a,d\}}\sum _{\alpha}{\delta}_{\alpha i}{\text{*y}}_{ij}^{k}\text{[11]}$$
$$\mathrm{min}\sum _{i=1}^{N}\text{}\sum _{j=1}^{M}{\text{(y}}_{ij}^{a}{\text{y}}_{ij}^{p}{\text{+y}}_{ij}^{d}{\text{y}}_{ij}^{p}\text{)[12]}$$
If ${n}_{gj}$ is the number of assignments to stands in pier $j\in [1.\text{}.\text{}.J]$ for agent $g\in [1.\text{}.\text{}.G]$ , and ng corresponds to the total number of flights serviced by agent g the fitness may be calculated by Formula 13
$$\mathrm{max}\sum _{g=1}^{G}\sum _{j=1}^{J}\frac{{n}_{gj}}{{n}_{g}}\text{[13]}$$
If an aircraft j does not have an arrival activity $\left({T}^{a}={B}^{a}=0\right)$ then no parking is considered in the model, which means the base and target service times for the parking operation are both zero: ${T}_{jp}=0$ (note that ${B}_{j}^{p}$ is already zero). The approach already considers the case where a flight arriving does not have a departing flight associated with it, i.e. after the aircraft has completed the arrival procedure the aircraft is required to follow maintenance procedures for which it will be taken to the appropriate installation to perform any of these necessary maintenance operations.
Some of the robustness approaches are: ‘Distribute Idle Time’, ‘Reduce Reassignment on Disruption’, ‘Area Reduction in Service’, ‘Subarea Reduction in Service’, ‘Unsupervised Estimated Stochastic Reduction in Service’, ‘Reduction in the Number of Conflicts’ and ‘Probability of Conflicts Based on the Gap’ which are similar to those presented in [22] for the ABSSAP. The ‘Minimize Reduction in Service’ is used here and requires some changes in order to be applicable to the AGAP, which is described below.
$$\mathrm{min}\sum _{j=1}^{M}\text{}\sum _{k\in \{a,d\}}\text{}{r}_{j}^{k}\text{[14]}$$
The unassigned flights may also be penalized by a cost proportionally higher than the buffer time. In order to treat all unassigned flights equally, and not discriminate between them, this extra cost may involve a multiple of the maximum buffer time for all flights, Formula 15. In this case, given that the number of assignments is the most important objective, the factor used to multiply the maximum buffer time should be higher than two, given that this would represent the buffer time taken by the reduced service incurred when a new assignment is placed between two consecutive flights. In this case, the buffer times at each end are removed from Figure 7.
$$\mathrm{min}\left(\sum _{j=1}^{M}\sum _{k\in \{a,d\}}{r}_{j}^{k}+\beta *\underset{j=1,k\in \{a,d\}}{\overset{M}{\mathrm{max}}}({B}_{j}^{k})*\underset{\text{numberofunassignedflights}}{\underbrace{\sum _{j=1}^{M}\sum _{k\in \{a,d\}}\left(1\sum _{i=1}^{N}\underset{ij}{\overset{k}{y}}\right)}}\right)\text{[15]}$$
New operators are required to allow the reassignment of parking activities from the dummy remote stand to a gate. This is not required if the Multi Exchange Mutation Operators (MEMOs) described in Section 7 for the ABSSAP are modified, such that their recovery stage also considers the parking activities assigned to the dummy remote stand. This removes the need to use tailored mutation operators to assign parking activities from the dummy remote stand to gates. These tailored operators are presented in Section 7.
All flights which have not been assigned to a stand are assigned to the ‘dummy’ stand. Some operators can switch flights between the real and dummy stands.
When a stand is to be selected, the roulette wheel selection method is used where every stand has the same probability of being selected.
When a time has to be determined (for instance for the start or end of a time range) a uniform random variable is used so that any time within the time range of the flights under consideration has an equal probability of being chosen.
This operator may increase the number of assignments where the operation does not move a flight back onto the ‘dummy’ stand. It is necessary that some flights be unassigned in the parent solution. So when full assignment has been attained for the given number of stands this operator clearly will not provide a new solution.
The DSMMO described in 7.1.2 originally presented for the ABSSAPs at [21, 20] and [21], which here moves assignments from the dummy stand to a gate, is preferred to the DSEMO, which exchanges assignments between the dummy stand and a gate, where N is greater than or equal to the Lower Maximum Assignment Point (LMAP), given that full assignment is achievable, and this operator helps to achieve it. The DSEMO may also need to execute an exchange, which will not improve the number of assignments. Nevertheless, in the early iterations, where there may be many solutions lacking full assignment, these may be forced into assignment by the use of the DSMMO (N ≥ LMAP). When N < LMAP it is impossible to reach full assignment, so the DSEMO is preferable to the DSMMO.
2. Multi Exchange between a Random Number of Resources (MERNRn): The number of stands between which flights are exchanged is randomly chosen each time, between 2 and n, where 2 < n ≤ N.
3. Multi Exchange between a Range Random Number of Resources (MERRNRxy): The number of stands between which flights are exchanged is randomly chosen each time, between x and y, where 2 ≤ x < y ≤ N.
1. Multi Exchange by Pier between a Fixed Number of Resources (MEBPFNRn): The number of stands to exchange flights between is fixed at n, where 2 ≤ n ≤ N.
2. Multi Exchange by Pier between a Random Number of Resources (MEBPRNRn): The number of stands between which the flights are exchanged is randomly chosen each time, between 2 and n, where 2 < n ≤ N.
3. Multi Exchange by Pier between a Range Random Number of Resources (MEBPRRNRxy): The number of stands between which the flights are exchanged is randomly chosen each time, between x and y, where 2 ≤ x < y ≤ N.
1. Range Multi Exchange between Fixed Number of Resources (RMEFNRn): The number of stands between which to exchange flights is fixed at n, where 2 ≤ n ≤ N.
2. Range Multi Exchange between Random Number of Resources (RMERNRn): The number of stands between which to exchange flights is randomly chosen each time, between 2 and n, where 2 < n ≤ N.
3. Range Multi Exchange between Range Random Number of Resources (RMERRNRxy): The number of stands between which to exchange flights is randomly chosen each time, between x and y, where 2 ≤ x < y ≤ N.
The Multi Exchange Mutation Operators may also be extended by using multiple points in time instead of two points in time (a time range). However, this will also increase the complexity and time required to execute the operations, and equates to several executions of the current implementation and was not therefore investigated.
In order to allow these parking activities to be unassigned from the remote dummy stand, it is necessary to add another operator. The Remote Dummy Single Exchange Mutation Operator (RDSEMO) selects only one of the parking activities assigned to the remote dummy for exchange, namely the RDSEMO, described in Algorithm 1. The parking activity for reassignment may be randomly selected when there is more than one assignment to the remote dummy stand. The RDSEMO will be seen in Section 9 to perform poorly given that it is restricted to solutions with parking activities assigned to the remote dummy, together with the extra constraint of assigning them to the gate already assigned to either the arrival or departure flight of the same aircraft as the parking activity.
An example of the RDMAMO operator is shown in Figure 11, where the problem is composed of three gates and four groups. A parking activity is randomly selected from those assigned to the remote dummy, e.g. a parking activity of group 3. A gate is next randomly selected, e.g. gate 1, from which the search to assign the parking activity begins. As the parking activity must be assigned to the same gate as either its arrival or departure flight this remote activity cannot be assigned to gate 1. So the search moves to the next gate, gate 3, but this assignment is not possible either, as otherwise it would overlap with the activity for group 4. Finally, the next gate, 2, which has not yet been looked at, is now checked and the parking activity for group 3 can be assigned to it, given that this parking activity does not overlap with any of the activities already assigned to that gate, and the arrival flight for this parking activity is also assigned to the gate. The process is repeated for each of the other parking activities assigned to the remote dummy which has not yet been considered, for example parking activity 2. However this parking activity cannot be assigned to any of the gates as it would overlap other assigned activities.
When only one or many of the mutation operators introduced in Section 7 are used it may be advantageous to include at least one of the remote dummy mutation operators, as the other mutation operators do not have the capability of reassigning parking activities to gates. The crossover operators may be able to reassign parking activities to gates, but only where at least one of both parents have not assigned the same parking activity to the remote dummy gate. This applies similarly to the dummy operators DSEMO and DSMMO in respect of unassigned flight arrivals and departures.
Whereas in the classic crossover a chromosome is divided into 3 sections, here the chromosome is divided into 3 * N sections which correspond to 3 sections per stand.
As an example, consider the operators C1P with a selection probability of 1 and the MEFNR3 with a probability of selection of 0.01, which may be represented as SO(C1P:100,MEFNR3:1), where a 1point crossover is always applied to generate the intermediate children for which there is a small probability of 0.01 for application of the MEFNR3 operator in order to generate the final children solutions.
Not every aircraft can be parked at all stands, and a stand code identifies the type of aircraft which can be parked at a stand. Each code identifies the largest aircraft which may be parked at the stand. The stand codes at London Heathrow airport are shown in Table 4 and stand codes per gate are presented in Table 5.
Code 
Comment 
F 

E3 
744 & 773/346 
E2 
744 but not 773/A346 
E1 
772 
D (767300) 

D (757) 

C (A321) 

C (A319) 
Stand 
Code 
Pier 
Full gate ID 
1 
D(767300) 
1 
4101 
2 
E2 
1 
4102 
3 
E2 
1 
4103 
5 
F 
1 
4105 
6 
F 
1 
4106 
7 
E3 
2 
4207 
8 
E2 
2 
4208 
9 
E2 
2 
4209 
10 
E3 
2 
4210 
11 
E3 
2 
4211 
12 
E2 
2 
4212 
14 
E1 
2 
4214 
15 
C(A321) 
2 
4215 
16 
D(767300) 
2 
4216 
17 
C(A319) 
2 
4217 
19 
C(A321) 
2 
4219 
20 
C(A321) 
2 
4220 
21 
D(767300) 
2 
4221 
22 
E2 
3 
4322 
23 
E2 
3 
4323 
24 
E2 
3 
4324 
25 
E2 
3 
4325 
29 
E2 
3 
4029 
The topology used for Terminal 4 at London Heathrow airport is shown in Figure 16, which is composed of 23 gates and three piers.
The consecutive arrival and departure flights which make use of the same aircraft are considered a group, and if the times between the consecutive flight arrival and flight departure for the same aircraft are less than 3 hours then they are considered as one activity, stretching from the arrival to the departure times, otherwise the service of each individual flight is considered to be an activity, and a parking activity links them both (for the time between the completion of the arrival activity and the commencement of the departure activity).
Real schedules for London Heathrow airport Terminal 4 were used, which were obtained from BAA. The numbers of flights are lower than for Terminal 1, however, data for terminals 1, 3 and 5, was not available. Schedules were generated based on the density of the schedules provided for Terminal 4, to investigate the effect on busier terminals as described below.
The consecutive flights serviced by the same aircraft are herein called a group, such that any flight always belongs to a group, although it may be the only flight in its group. For an original schedule of G_{o} groups, ordered in ascending base starting time (τ_{j}), a set of group lists is generated, each containing all of the groups where the base starting time is within the same time range (n_{i}). Algorithm 5 was then used to generate the new schedule.
ID 
Date 
LMAP 
UMAP 
LMAPp 
UMAPp 
No. of Activities 
No. of Parking Activities 
H4T100906 
6Sep10 
8 
10 
17 
19 
118 
15 
H4T100907 
7Sep10 
11 
14 
18 
20 
120 
15 
H4T100908 
8Sep10 
7 
10 
16 
18 
119 
16 
H4T100909 
9Sep10 
8 
10 
18 
20 
119 
15 
H4T100910 
10Sep10 
9 
12 
15 
18 
120 
15 
H4T100911 
11Sep10 
9 
10 
16 
16 
110 
11 
H4T100912 
12Sep10 
11 
11 
18 
19 
117 
15 
ID 
Date 
LMAP 
UMAP 
LMAPp 
UMAPp 
No. of Activities 
No. of Parking Activities 
N4T100906 
6Sep10 
17 
20 
23 
26 
164 
21 
N4T100907 
7Sep10 
21 
23 
25 
28 
160 
19 
N4T100908 
8Sep10 
18 
20 
23 
25 
169 
24 
N4T100909 
9Sep10 
21 
21 
28 
28 
168 
22 
N4T100910 
10Sep10 
19 
20 
20 
21 
164 
21 
N4T100911 
11Sep10 
19 
21 
21 
21 
154 
15 
N4T100912 
12Sep10 
19 
21 
23 
24 
167 
22 
The data sets used in the experiments conducted are presented in Section 8, and a summary is presented in Table 8 for convenience. Multiple combinations of the parameters used in both the SSEA and the CGA were used, the values for which are summarized in Table 9.
The following section looks at the performance of the SSEA for all combinations of the parameters presented in Tables 8 and 9, when only one operator is used in each execution. Experiments were next conducted with various combinations of the same operators and parameters, which are compared and studied, and a single operator is used to establish their performance, Section 9.2. The results from the experiments conducted for the SSEA are compared to those obtained from the application of other metaheuristics, which are then studied in Section 9.3. Some experiments were next conducted to determine the effects of the parking restriction, where a parking activity may only be assigned to a gate if such a gate is already assigned to either the flight arrival or departure associated with it, the results of which are presented in Section 9.4. Finally in Section 9.5 experiments are conducted to study the effect on the performance of the different operators when the number of flights increases.
Given that the MEMOs lack the ability to assign activities from the dummies, thus keeping fitness low, removal of this disadvantage improves the Multi Exchange Mutation Operator by introducing a recovery stage after the child solution has been generated whereby unassigned activities (those assigned to one of either dummy) are randomly assigned to a gate where possible. This is very important as it is a constraint on the static problem achieving full assignment, N ≥ LMAP, as presented in Section 5.1. As a solution reaches full assignment this extra step may not be needed, therefore having no detrimental effect on the speed of the operator. The word ‘Improved’ is added at the beginning of the name of the original base operators to identify the new operators. This explains the poor fitness results obtained when the MEMO were used when compared with those obtained by their ‘Improved’ version, as shown in Table 10. The Improved MEMOs do not need to be combined with any of the Dummy operators to allow them to increase the number of assignments to gates.
Name 
Values 
Terminal 
4 
Topology 
3pier 
Data sets 
London Heathrow airport schedules for Terminal 4 shown in Table 6 
Fitness weights 
W1 = 0.75193, W2 = 0.6, W3 = 0.00025, W4 = 0.11 and W5 = 0.25 
Name 
Values 
Total number of iterations 
800,000 
Population sizes 
5, 10, 15, 30, 50, 100, 200, 500, 1000 and 2000 
Iterations in a generation (`, only for SSEA) 
1, 5, 10 and 20 
Replacement Strategies 
ES, SUMS, IS1ES and IS1SUMS (later IS1fES and IS1fSUMS are used too) 
Member Selectors 
Tournament Selection 
Operators 
C1P, C2P, MEFNR2, MEFNR3, MEFNR4, MEFNR5, IMEFNR2, IMEFNR3, IMEFNR4, IMEFNR5, RMEFNR2, RMEFNR3, RMEFNR4, RMEFNR5, IRMEFNR2, IRMEFNR3, IRMEFNR4, IRMEFNR5 
A summary of all of the experiments conducted for the SSEA using different combinations of l operators, selectors and population sizes (Section 8) is presented in Table 10, which only shows those combinations which best solution obtained cannot be said to be significantly statistically less fit than the best solutions obtained for any of the other combinations. Table 10 clearly shows that the Index Selection with Elitist Selection and a group size of 1 (IS1ES) replacement strategy provides significantly statistically better solutions overall, which is similar to the result obtained for the ABSSAP at [21]. The only operators covering all of the data sets studied, where a fitness solution cannot be said to be significantly statistically worse than the solutions obtained when using any of the other combinations, are:
1. $\ell $ = 1, IRMEFNR2 and IS1ES and population size of 5
2. $\ell $ = 5, IRMEFNR2 and IS1ES
Similarly, the good performance of the operator IRMEFRN2 was also seen for the ABSSAP at [21] for operator RMEFRN2, particularly where the number of BSSs is greater than the UMAP, which also equates here to the data set cases considered for Terminal 4 at London Heathrow airport.
The ‘Index Selector’ operators remove all solutions having the same fitness, but which do not have interesting parts useful in future generations. Furthermore, this also reduces the fitness pressure, since there are fewer solutions with duplicates. This approach may be too strong so a new version of the Index Selection with Elitist Selection (ISxES) and Index Selection with Stochastic Universal Modified Sampling (ISxSUMS) is proposed, whereby duplicates are removed only if the population is greater than expected. The results, which include the new ‘Index Selector’, are shown in Table 11, where an ‘f’ is inserted in the selector’s name to represent the new ‘Index Selector’. The performance of both versions of the ‘Index Selector’, with and without full removal of duplicates, generally appears to be close. The overall approaches achieving solutions where fitness is no worse than in the other operators in all the data sets considered are:
1. $\ell $ = 1, IMEFNR2 and IS1fES
2. $\ell $ = 5, IRMEFNR2, IS1ES and population size of 5
When the new ‘Index Selector’ is used these empirical results show an improvement by the IMEFNR2 over previous results using a lower number of iterations per generation ($\ell $ ), which also corresponds to a small increase in search pressure as less fit solutions in the population have less chance of being selected (the diversity is retained for longer at a higher $\ell $ ). Whereas, the removal of duplicate solutions by the replacement strategy equates to an increase in diversity. The new ‘Index Selectors’ were not applied to the ABSSAP. These results show that the solutions obtained may potentially be improved when using this selection enhancement in other resource assignment problems, such as the ABSSAP, especially for data sets where a slight extra increase in the search pressure may be advantageous. Furthermore, the ability to activate or deactivate this characteristic may be beneficial as the search advances, based on the particular circumstances at each time, such as switching it off later in the search when diversity has sufficiently decreased in order to slightly reduce the search pressure.
ℓ 
Operator 
Selector 
Population sizes 

H4T0100906 
H4T100907 
H4T100908 
H4T100909 

1 
IMEFNR2 
IS1ES 
5, 10, 15, 30 
5 
5 
5, 10, 15, 30 
IS1SUMS 
5 

SUMS 
5, 10, 15, 50, 500 
15, 50, 200, 1000 

IRMEFNR2 
IS1ES 
5, 15 
5 
5 
5, 10 

RMEFNR2 
IS1ES 
10 

5 
IMEFNR2 
IS1ES 
10 
5 
5, 15 
5, 10 
IRMEFNR2 
IS1ES 
5, 10, 15 
5 
5, 15 
5, 10 

MEFNR2 
IS1ES 
5 

SUMS 
200 

10 
IMEFNR2 
IS1ES 
5, 10, 15 
5 
5 
5, 10 
IRMEFNR2 
IS1ES 
5, 10, 30 
10 
5, 10 
5, 10 

MEFNR2 
IS1ES 
5 

20 
IMEFNR2 
IS1ES 
5, 10, 15 
10 
5, 10 

IRMEFNR2 
IS1ES 
5, 10 
10 
5, 10 
5 

MEFNR2 
IS1ES 
15 
10 
ℓ 
Operator 
Selector 
Population sizes 

H4T100910 
H4T100911 
H4T100912 

1 
IMEFNR2 
IS1ES 
5 
5, 10 

SUMS 
15, 30, 100, 2000 
10, 50, 100, 500, 2000 

IRMEFNR2 
IS1ES 
5, 15 
5, 15 
5, 10 

5 
IMEFNR2 
IS1ES 
5 
5 

IRMEFNR2 
IS1ES 
15 
5 
10 

10 
IRMEFNR2 
IS1ES 
5 
5, 10 

MEFNR2 
IS1ES 
5 

20 
IMEFNR2 
IS1ES 
15 

IRMEFNR2 
IS1ES 
5 
5 

MEFNR2 
IS1ES 
10 
ℓ 
Operator 
Selector 
Population sizes 

1 
H4T100906 
H4T100907 
H4T100908 
H4T100909 

IMEFNR2 
IS1ES 
5 
5, 10, 15 
5 
5, 10, 15 

IS1fES 
10 
10 
10 
10 

SUMS 
15, 50 
15, 50, 200, 1000 

IRMEFNR2 
IS1ES 
5 
5, 10 
5 
5, 15 

IS1fES 
10 
10, 15 

IMEFNR2 
IS1ES 
5 
5, 15 

5 
IS1fES 
5 
5, 10 
5 
5 

IRMEFNR2 
IS1ES 
5 
5 
5, 15 
5 

IS1fES 
5 
5 
5 

MEFNR2 
SUMS 
200 

IMEFNR2 
IS1ES 
5 
10 
5 

10 
IS1fES 
5 
10 
5, 10 
5 

IRMEFNR2 
IS1ES 
5, 10 
5, 10 

IS1fES 
5 
5, 10 
5 

IMEFNR2 
IS1ES 
10, 15 
10 
5, 10 

20 
IS1fES 
5 
5, 10 
5, 10, 15 

IRMEFNR2 
IS1ES 
10 
5, 10 
5 

IS1fES 
5 

MEFNR2 
IS1ES 
15 
ℓ 
Operator 
Selector 
Population sizes 

H4T100910 
H4T100911 
H4T100912 

1 
IMEFNR2 
IS1ES 
5 
5, 10 

IS1fES 
5 
5, 15, 30 
5, 10 

SUMS 
15, 30, 100, 2000 
10, 50, 100, 500, 2000 

IRMEFNR2 
IS1ES 
5, 15 
5, 10 

5 
IS1fES 
5 
5 

IS1fSUMS 
5 

IMEFNR2 
IS1ES 
5, 10 
5 
5 

IS1fES 
5, 10, 15 
5, 10, 15 

IRMEFNR2 
IS1ES 
15 
5 
10 

IS1fES 
5, 10 
5, 15 
5 

IMEFNR2 
IS1ES 

10 
IS1fES 
5 
5, 10, 15 

IRMEFNR2 
IS1ES 
5 
5, 10 

MEFNR2 
IS1ES 
5 

IMEFNR2 
IS1ES 
15 

20 
IS1fES 
5 

IRMEFNR2 
IS1ES 
5 
5 

MEFNR2 
IS1ES 
10 
Several experiments were designed and executed to examine the performance of the CGA when using the same operators as previously described, so this implementation of the CGA does not correspond to the standard definition of the CGA since it does not make use of a binary representation, and does not use binary or random mutation operators as classically presented in [30]. Both 1point and 2point crossover operators together with one of the previously described mutation operators were used, with a probability of 0.99 for the crossover operators and 0.01 for the mutation operators with population sizes of 500, 1000 and 2000. Also based on the good performance of the mutation operators, some experiments with a probability of 0.9 crossovers and 0.1 mutations were executed to establish whether a higher percentage of mutation operators were desirable for the data sets used. These were later extended to include a population size of 400, given that a number of the experiments provided good results for a population size of 500.
Algorithm 
Walk Size 
Operator 
Tabu List Sizes 

H4T1009dd 

Mon 6 
Tue 7 
Wed 8 
Thur 9 

TS 
10 
IMEFNR3 
5 
5, 10 
5, 15 
15 
IRMEFNR3 
5, 30 
15 
30 
15 

30 
IRMEFNR3 
5, 15 
10 
5, 15 
5, 10, 15, 30 

Algorithm 
Walk Size 
Operator 
Tabu List Sizes 

H4T1009dd 

Fri 10 
Sat 11 
Sun 12 

TS 
10 
IMEFNR3 
10, 30 
10 
5, 30 

IRMEFNR3 
5, 10, 15, 30 
10, 15 
5, 10, 15, 30 

30 
IRMEFNR3 
5, 10, 15, 30 
30 
5, 10, 15 
The 1point crossover did perform better than the 2point crossover, which may partly be attributable to the fact that some service periods are very long and the extra hard constraints, i.e. assignment of parking activities, may reduce the efficiency when using time regions. In these cases, it is more probable that the time limits of the region fall within those long services, thus reducing the number of assigned activities for use in the children. Table 13 only shows combinations of operators with the replacement strategy Elitist Selection (ES) which indicates that the tendency of the ES in reducing the diversity, which is normally maintained for longer by the larger population sizes typically used by crossover operators when used alone, is a beneficial one for the data sets considered.
Operator 
Selector 
Population Sizes 

H4T1009xx 

Crossover 0.9 
Mutation 0.1 
6 
7 
8 
9 
10 
11 
12 

C1P 
IMEFNR3 
ES 
400 and 500 
400, 500 and 2000 
400 and 500 
400, 1000 and 2000 
400 and 500 
400, 500 and 1000 
400, 500, 1000 and 2000 
IRMEFNR2 
ES 
400 and 500 
500 and 1000 
400 
400, 500 and 1000 
400, 500 and 2000 
400 and 2000 
2000 

MEFNR2 
ES 
500 
400, 500, 1000 and 2000 
400, 500 and 2000 
400, 500, 1000 and 2000 
400, 1000 and 2000 
500 and 1000 
2000 

RMEFNR2 
ES 
400 
400 and 500 
400 
1000 and 2000 
400, 1000 and 2000 
1000 
400 and 2000 

Algorithm 
Operator 
Selector 
Population Sizes 

H4T1009xx 

6 
7 
8 
9 
10 
11 
12 

CGA 
C1P 0.9 
IRMEFNR2 0.1 
ES 
500, 1000 
400, 500, 1000 
400 
400, 500 
400, 500, 2000 
400, 2000 
400, 500, 1000, 2000 
MEFNR2 
400, 500, 1000, 2000 
400, 500, 1000, 2000 
400, 500, 2000 
500 
1000, 2000 
500, 1000 
1000, 2000 

RMEFNR2 0.1 
400, 500 
400, 1000, 2000 
400 
400 
400, 1000, 2000 
1000 
400, 500, 2000 

CGA+ 
C1P 0.9 
IMEFNR3 
SUMS 
400, 500 
400 
400 
400, 500 
400, 500 
400 
400, 500 
IMEFNR3 0.1 
400 
400 
400 
400 
400, 500 
400 
400, 500 

SSEA 
1 
IMEFNR2 
IS1fES 
10 
10 
10 
10 
5 
5, 15, 30 
5, 10 
5 
IRMEFNR2 
IS1ES 
5 
5 
5,15 
5 
15 
5 
10 

SSEA+ 
1 
IMEFNR2 
IS1ES 
5, 10, 15 
5, 10, 15, 30 
5, 10, 15, 30 
10, 15 
10, 15 
5, 10 
5, 10, 15, 30 
IRMEFNR2 
5, 10, 15, 30 
5, 10, 15, 30 
5, 10, 15, 30 
30 
30 
5, 10 
5, 10, 15, 30 

5 
IMEFNR2 
5, 10, 15 
5, 10, 15, 30 
5, 10, 15, 30 
30 
30 
5, 10, 30 
5, 10, 15, 30 

IRMEFNR2 
5, 10, 15, 30 
5, 10, 15 
5, 10, 15, 30 
5, 10, 15, 30 
10, 15, 30 
30 
5, 10, 15, 30 

10 
IMEFNR2 
10, 15, 30 
5, 10, 15, 30 
5, 10, 15, 30 
15, 30 
15, 30 
5, 10, 15, 30 
5, 10, 15, 30 

IRMEFNR2 
5, 10, 15, 30 
5, 10, 15 
5, 10, 15 
10,15,30 
10, 15, 30 
15 
5, 10, 15, 30 

20 
IMEFNR2 
5, 10, 15, 30 
5, 10, 15, 30 
5, 10, 15, 30 
10, 15 
10, 15 
5, 15 
5, 10, 15, 30 

IRMEFNR2 
5, 10, 15 
5, 10, 15 
5, 10, 15 
30 
30 
5, 10 
5, 10, 15, 30 
Algorithm 
Walk Size 
Operator 
Tabu List Size 

H4T1009xx 

6 
7 
8 
9 
10 
11 
12 

TS 
10 
IMEFNR3 
5, 10 
15 
5, 15 
5 
10, 30 
10 
15 
IRMEFNR3 
15 
15 
30 
5, 30 
5, 10, 15, 30 
10, 15 
5 

30 
IRMEFNR3 
10 
5, 10, 15, 30 
5, 15 
5, 15 
5, 10, 15, 30 
30 
5, 15 

50 
IRMEFNR3 
5, 30 
5, 15, 30 
10 
5, 30 
5, 10, 15, 30 
10, 15 
5, 10, 30 

TS+ 
10 
IRMEFNR3 
5, 10, 15, 30 
5, 10 
5, 30 
5, 10, 15 
10, 30 
5, 10, 15, 30 
5, 10, 15, 30 
IRMEFNR4 
5, 10, 15, 30 
5, 30 
10, 15 
5, 15 
5, 10, 15 
10 
5, 15, 30 

30 
IMEFNR3 
5, 10, 15, 30 
5, 10, 15, 30 
10, 15 
30 
15, 30 
5, 10, 15, 30 
5, 10, 15, 30 

IRMEFNR4 
10, 15, 30 
10, 15 
5, 30 
5, 10, 15, 30 
5, 15, 30 
10, 15 
5, 15, 30 

50 
IMEFNR3 
10, 15, 30 
10, 15, 30 
5, 10, 15, 30 
10, 15 
15 
10, 15 
5, 10, 15, 30 

IRMEFNR4 
5, 30 
5, 10, 15, 30 
10, 30 
5, 15 
5, 15 
5, 15, 30 
5, 10, 15, 30 
The new data sets all have a number of gates (N=23) larger or equal to the UMAP, so it should be possible to assign all the flights to gates. However on reviewing the parking activities there was found to be an insufficient number of gates to which to assign all of the activities (N < LMAPp), with the exception of the first and last data sets. The most difficult data sets to solve were for H4T100907 with UMAP equal to 23 BSSs, which is also the number of gates, followed by the H4T100909, which has the highest LMAPp and UMAPp as well. Thus all flights from the sets generated can be assigned to a gate as N ≤ UMAP, which meets one of the conditions for a real static airport problem.
Experiments using the SSEA were executed for the new base schedules, and a summary of the results is shown in Table 16. The results show an improvement on the solution obtained by the IMEFRN2, IMEFRN3 and IRMEFRN3 as it is similarly seen at [21] for MEFRN2, MEFRN3 and RMEFRN3 when fewer resources (BSSs and gates) are available.
ℓ 
Operator 
Population Sizes 

N4T100906 
N4T100907 
N4T100908 
N4T100909 

1 
IMEFNR2 
5 
10, 15, 30 
5, 10 

IRMEFNR2 
3 
5, 10 

IMEFNR3 
5, 10, 30 

IRMEFNR3 
10, 30 

5 
IMEFNR2 
5, 10, 15 
15, 30 
5 

IRMEFNR2 
10, 15 
5, 10, 30 
5, 10 

IMEFNR3 
15 

IRMEFNR3 
5 
5, 10 

10 
IMEFNR2 
10, 15 
5, 10, 30 

IRMEFNR2 
10, 15, 30 

IMEFNR3 
5, 15 

IRMEFNR3 
5 

20 
IMEFNR2 
5, 10, 15 
5, 10 
5, 10 

IRMEFNR2 
5, 10 
15 

IMEFNR3 
5, 15 

IRMEFNR3 
5 
ℓ 
Operator 
Population Sizes 

N4T100910 
N4T100911 
N4T100912 

1 
IMEFNR2 
5 
5, 10 
5, 15 
IRMEFNR2 
5 
5 
5 

5 
IMEFNR2 
10 

IRMEFNR2 
5 
10 
5 

10 
IMEFNR2 
5, 10 
10, 15 

IRMEFNR2 
5 

20 
IMEFNR2 
5 

IRMEFNR2 
5, 10 
5, 15 
Operator 
Selector 
N4T1009xx 

Crossover 0.9 
Mutation 0.1 
6 
7 
8 
9 
10 
11 
12 

C1P 
IMEFNR2 
IS1ES 
400, 500, 1000 
400, 500 
400, 500 
400, 500 
400, 500 
400, 500 
400, 500 
SUMS 
400 

IRMEFNR2 
IS1ES 
400, 500 
400, 500, 1000 
400 
400, 500 
400, 500 
400, 500 

SUMS 
400, 500 
400, 500 

IMEFNR3 
IS1ES 
400 
400 
400, 500 

SUMS 
500 

IRMEFNR3 
IS1ES 
400 
500 
400, 500 
400, 500 

C2P 
IMEFNR2 
IS1ES 
400, 500 
400 

IMEFNR3 
IS1ES 
500 

IRMEFNR3 
IS1ES 
400 
Different algorithms and their parameters were studied to find characteristics which could be used to identify the algorithm and parameters most appropriate to the AGAP. Both the model and algorithms are derived by modifying those presented in previous work, and are based on the specific characteristics of the problem. These approaches were tested on real data from London Heathrow airport, using a fitness function composed of the weighted sum of the different real world objectives currently used in London Heathrow airport. When there were plentiful gates to which the flights could be assigned, there was little difference between the algorithms studied (SSEA, CGA and TS) when the same operators were used. Nevertheless, the mutation operators used are potentially faster than the crossover operators and have been able to cover more search space. There is also potential for combining these algorithms to generate new ones, which may improve the solutions still further. This potential may also be better fulfilled by combining algorithms with significant differences in their underlying approach, e.g. SSEA which is a population based approach, and TS which is an individual approach (local search).
The SSEA has been shown to provide fitter solutions for the Improved Range Multi Exchange with Fixed Number of Resources with two gates between which to exchange assignments (IRMEFNR2), and a sufficient number of gates to which all flights and parking activities can be assigned (N ≥ UMAPp, Upper Maximum Assignment Point with Parking) with a preference for the IS1ES, and in some cases also its modified version (Index Selection with Elitist Selection and a group size of 1 (IS1fES)). As the number of gates in the problem decreases, both the original and improved Multi Exchange between Fixed Number of Resources (MEFNRn and Improved Multi Exchange with Fixed Number of Resources (IMEFNRn)) with a higher ‘n‘ (number of gates between which to exchange assignments), are preferable, as it was also seen for the ABSSAP.
The TS with Multiple Exchange Mutation operators has been seen to perform better for a higher number of gates between which to exchange assignments than the same operators for the SSEA. This is believed to be a consequence of the higher number of gates between which to exchange assignments, extending the search to a wider area of the search space. This would help to find a better solution, but only where the extra search space covered is not too wide, since this may also reduce the effectiveness of the iterations as there is more danger of straying into disinterested areas of the search space. The SSEA achieves the same, however, partly as a result of the differences within its population of solutions, so it does not necessarily need to extend the search further as this may well increase the number of iterations used to investigate uninteresting areas of the search space. This effect depends on both the problem under study and the model used in the two algorithms, which have a direct impact on the shape of the search space, as can be seen when comparing these results with those obtained for the ABSSAP ([22]). The good performance of the Multiple Exchange Mutation operators was also seen to extend to the CGA, where a higher probability of mutation was preferred, which I attribute to the good results provided by these mutation operators. Nevertheless too high an intervention by the mutation operators has been seen to be detrimental, perhaps in part due to the potential disruptive effect of the mutation operators.
It is envisaged that use of the serial crossover presented might be better suited to this problem than the 1point and 2point crossover operators studied here, given the longer service time required for the combined arrival/departure flights and parking. In the case of the serial crossover, since cut(s) in the time delimiting the areas of assignments for copying only affects gates, they are less likely to have activities between the two intersection sites than in the case of the other crossover operators used here, which clearly affects activities which are copied from each parent. The time an aircraft expends parked at a gate has a considerable effect on the operations which take place upstream in the overall airport operation, especially when some of the resources required, such as gates, are limited. Delays in starting the departure sequencing may have important effects on the departure itself, which in turn may also require other aircraft to extend the time during which they are held at the gates. This could well affect other flights arriving which have had the same gates assigned to them. It would be therefore advisable to account for the effect of potential disturbances in the assignment plan.
To establish the validity of the model (original model) a different model was also considered (new model) where the extra constraint for the parking activity does not exist. The empirical results for the new model when compared with the original model show that both models find good solutions and it cannot be said that either is better. Nevertheless the new model performs well in a wider range of parameter values, making it preferable.
However, as the number of parking activities increases, so the search space also increases. This will increase the time required by the new model to find good solutions, so the use of the extra constraint (original model) should reduce the time taken to find good solutions, making it preferable.