Aircraft Landing

Algorithms for Scheduling Aircraft Landings Andreas T Ernst and Mohan Krishnamoorthy August 15, 2001 CSIRO Mathematical and Information Sciences Private Bag 10, Clayton South MDC, Clayton VIC 3169, Australia. [email protected], [email protected] Abstract The problem of scheduling aircraft landings on one or more runways is an interesting problem that is similar to a machine job scheduling problem with sequence dependent processing times and with earliness and tardiness penalties. The aim is to optimally land a set of planes on one or several runways in such a way that separation criteria between all pairs of planes (not just successive ones) are satisfied. Each plane has an allowable time window as well as a target time. There are penalties associated with landing either earlier or later than this target landing time. In this paper, we consider both the static and the dynamic version of the problem. The latter occurs where decisions about the landing times for planes (and the runways they land on) must be taken in a dynamic fashion as time passes and as the operational environment changes. A number of possible solution algorithms, both heuristic and exact, are discussed. Keywords: runway operations, landing, takeoff, scheduling, reactive scheduling, displacement problem

1 Introduction In this paper we introduce the problem of scheduling aircraft (plane) landings at an airport. This problem is one of deciding a landing time on a runway for each plane in a given set of planes such that: each plane lands at some time within a predetermined time window; and separation criteria between the landing of a plane, and the landing of all successive planes, are respected. The objective is to minimise the total (weighted) deviation from a desired target landing time for each plane. This type of problem occurs at busy airports where making optimal use of the bottleneck resource (the runways) is crucial to keep the whole airport operating smoothly. Given a set of planes in the radar horizon of an air traffic controller (ATC), the problem is one of determining a landing time for each plane such that each plane in this ATC horizon lands within a pre-specified landing time window and such that landing separation criteria specified for each 1




pair of planes in this horizon are adhered to. This problem is a slightly unusual application that fits into the general category of machine scheduling problems. This problem was presented first by Beasley, Krishnamoorthy, Sharaiha & Abramson [5]. As in [5], we are only concerned with modeling and solving the problem of scheduling aircraft landings in this paper. However, the approach presented in this paper is easily adaptable to a problem featuring only takeoffs or, indeed, a problem involving a mix of takeoffs and landings on the same (or on different) runways. In addition, in this paper, we are concerned with the static case of scheduling aircraft landings. The dynamic case of scheduling aircraft landings has been dealt with by Beasley, Krishnamoorthy, Sharaiha & Abramson [4]. Consider the planes within the radar range (or horizon) of an air traffic controller (ATC) at an airport. Typically, the ATC will be in charge of determining approach paths, runway allocation and landing times of several planes in the radar horizon. Each of these planes has a preferred landing time as well as earliest and latest possible landing times. In addition, there are aerodynamic considerations that arise because of the turbulence created by landing aircraft. These considerations impose a constraint that the landing time between any two aircraft pairs in the horizon must be greater than some minimum interval. This minimum separation is dependent on the aircraft types and could be different for different pairs of aircraft in the horizon. It is important to note here that whilst throughout this paper we shall only refer to planes landing, the model presented in this paper is applicable without change to problems involving just takeoffs only and to problems involving a mix of landings and takeoffs on the same runway. We start by describing algorithms for the static case. In other words, we are dealing with the off-line case where we have complete knowledge of the set of planes that are going to land. We then show how the methods for the static case can be adapted to deal with the dynamic, or on-line, case, where decisions about the landing times for planes must be made as time passes and the situation changes (planes land, new planes appear, etc). The problem of assigning to each plane, a landing time such that all planes land as close as possible to their preferred landing time will be called the Aircraft Landing Problem (ALP). There are many variants of the ALP and many approaches for solving it. Most previous work in this area present simulation models (see Andreussi [2]), queueing models (see Milan [12]), or heuristics (see Dear [9], Dear & Sherif [10], Venkatakrishnan, Barnett & Odoni [17]). A dynamic programming based approach was considered by Psaraftis [14]. Beasley, Krishnamoorthy, Sharaiha & Abramson [5] provide a detailed review of the literature in this area. The work in [5] was based on an earlier mixed integer linear programming formulation and a genetic algorithm approach by Abela, Abramson, Krishnamoorthy, De Silva & Mills [1]. There are, however, many (optimisation) problems of interest in the area of air-space management and in air traffic control. Some of these are discussed in, for example, Bianco & Odoni [6], Odoni, Rousseau & Wilson [13], and Winter & Nuber [18]. Bianco, Rinaldi & Sassano [8] and Bianco, Ricciardelli, Rinaldi & Sassano [7] adopt a job-shop scheduling view of the ALP. They solve the single runway problem using a mixed integer linear program. They provide a tree-search procedure with embedded Lagrangean lower bounds and also develop a heuristic approach for the problem. Their paper also presents a set of ALP data and provides computational results for all of the approaches. The results provided in [7] are perhaps the most complete set for the ALP apart from [5]. Most approaches for solving the job-shop scheduling problem with sequence dependent processing times are heuristic in nature, although there exist some formulations, complexity results, worst case performance bounds and also some exact approaches.

2

1.1

Problem context

Upon entering within air traffic control’s radar range (or horizon) at an airport, a plane requires air traffic control to assign it a landing time, sometimes known as the broadcast time. This time must lie within a specified time window, bounded by an earliest time and a latest time, these times being different for different planes. The earliest time represents the earliest a plane can land if it flies at its maximum airspeed. The latest time represents the latest a plane can land if it slows to its slowest possible airspeed while also holding (circling) for the maximum allowable time. Each plane has a most economical, preferred speed referred to as the cruise speed. A plane is said to be assigned its preferred time, or target time, if it is required to fly in to land at its cruise speed. If air traffic control requires the plane to either slow down, hold or speed up, a cost will be incurred. This cost will grow as the difference between the assigned landing time and the target landing time grows. In this paper we shall assume that this cost is linearly related to deviation from target. Figure 1 illustrates the variation in cost within the time window of a particular plane. The time between a particular plane landing, and the landing of any successive plane, must be greater than a specified minimum (the separation time) which is dependent upon the size of the planes involved. A Boeing 747 generates a great deal of turbulence and therefore imposes a (relatively) large time delay before other planes can land. A light plane, by contrast, generates little turbulence and therefore imposes only a (relatively) small time delay before other planes can land. Planes taking off impose similar restrictions on successive operations. Note that these minimum separations due to turbulence apply to all subsequent planes and not just the immediate successive one. Thus the landing time of a plane can influence the possible landing times of two or three subsequent planes.

1.2

Dynamic scheduling

The above assumes that we have perfect information about all planes that are going to land (or take off). However in practice the operational environment changes as time passes, new information becomes available making it necessary to revise the previous decisions that have been made. Whilst it is sufficient to assume a static environment for planning purposes, reallife applications require the study of tactical decisionmaking in operational environments. In scheduling aircraft landings, as a new plane appears we may have to revise the landing times of planes that have already been scheduled for landing. This problem is dynamic in the sense that planned decisions are continually having to be revisited as the operational environment changes. However it is clear that, from an operational viewpoint, it may be undesirable to perturb the previous decision ‘too much’ in making a new decision. Placing a new plane at the front of the landing queue may change the previous scheduled landing time for all planes already in the queue. Typically therefore in making a new decision we have to explicitly consider the previous decision (solution) as we have some degree of commitment to it and are reluctant to change it too much. Hence we have a displacement problem, the problem of making a decision but with an explicit link back to the previous decision that was made. The remainder of the paper is structured as follows. In Section 2 we provide a mathematical formulation of the ALP. Section 3 we present a specialised simplex method for finding optimal values of broadcast landing times given a determination of some or all off the sequencing variables. This algorithm can be used to quickly calculate lower bounds in a branch and bound scheme or to evaluate solutions in a heuristic for the plane landing sequence variables. We develop a heuristic approach based on problem space search. This is described in Section 4. The heuristic upper bound and the lower 3



bounds that are obtained from the simplex algorithm are then combined in a branch and bound method together with several types of pre-processing steps, to yield an effective exact solution algorithm. In Section 5, we then show how to extend the exact algorithm to the case of multiple runways. Finally we present some numerical results in Section 6.

2 Formulation of ALP As in [5] we are only interested in modeling the Decision problem here. In other words, we are only interested in deriving, for each plane, a broadcast landing time. Along with this, the ATC must also determine solutions to the Control problem of how to land the planes. For example, a set of broadcast times may require some planes to overtake other planes in the static horizon, while some of the determined broadcast times may require the allocation of different trajectories and flight paths to various planes. We do not incorporate, into our decision model, any considerations that arise from these control problems.



 

   ,

A precise formulation of the ALP requires the following parameters:

 the earliest landing time of plane   ,  the latest landing time of plane   ,  the target (preferred) landing time of plane   ,    the required separation time between planes  and ! if  lands before ! ,   #"%$#&  '!   (  the penalty cost for plane  landing ahead of the target time, )  the penalty cost for plane  landing after the target time. the set of planes

,

We require the following decision variables in our decision model. We note that we deviate slightly from the variable notations that are used in [5]:

*  the landing time of plane  , +   a binary variable indicating that plane  lands before ! .

A mathematical formulation of ALP can now be stated as follows: Problem ALP min Subject to:

;

. , -0/ (  max 1$2 43 * 576 )  max 1$2 * 4385 * 26   #9 * :6<; + = & ? > !@ A

+ =B6 +  ? & C > !@ A

D9 * D9%: & E A

+    1$2 ?F

(1) (2) (3) (4) (5)

Here, is a sufficiently large number. Needless to say, the formulation as it stands would not be of much use for calculating solutions to ALP. It is only provided as a compact and precise mathematical definition of the problem. Note that this formulation can easily be transformed to a Mixed Integer Linear Programming (MILP) formulation through the use of additional variables to model the maximum operators in the objective. 4

2.1

Incorporating takeoffs

We said before that the model presented in this paper is applicable without change to problems involving just takeoffs only and to problems involving a mix of landings and takeoffs on the same runway. To see that this is so reflect that all we have really done is build a model to decide times for planes so as to respect time window constraints and separation time constraints. This is precisely the situation we have both for takeoffs and for a mix of landings and takeoffs just a set of of planes with time windows and separation times, where we know for any particular pair planes whether is landing or taking off and whether is landing or taking off and so can set the separation time accordingly.

 

2.2

HG  !JI

!

!

Multiple runway MILP

A slight variation to this problem is the multiple runway case. Here the planes can be assigned to one of two or more runways. In most applications involving multiple runways, the separation constraints need only be satisfied for planes landing on the same runway. This may not be the case if there are multiple runways that are very close together or even intersecting.

K

 M









L

Let be the time before that plane lands (or zero if plane lands after ) and let be defined similarly as the time after that plane lands. In this formulation we also re-interpret the variables : the variable is one if plane lands before plane on the same runway. In order to count and limit the number of runways we also introduce binary variables which are zero unless plane is the last plane to land on a runway. Now the multiple runway MILP can be defined as follows:

+ 



* " * R + =B6 +   9 N V" ., -0/ N V9 ?9 K 55 + L   " N 

!

N

,  G (  K 26 )  L  I * 26   E3 G 3OEP6    IQG 3 +   I & C  > !' A

M3 K B6 L  & :   & ST!@ U

?3 W- ,/X Y  +   &  A

[\ Z * ]9 : &  U

$ & ^ A

1$2 ?F



min

Subject to:

+ 

(6) (7) (8) (9) (10) (11) (12) (13)

Note that the multiple runway formulation is significantly weaker than the single runway version mainly due to the fact that the variables are only constrained by an inequality constraint in (8) rather than the equality constraint (3). Equation (10) limits the number of runways to . The formulation can be tightened slightly as follows:

[

#_ ` it may be possible to tighten the time windows for planes: ?ba max 1?5 M43 _#`dceK f :ba min 1g B6 _#`dc1L f +   variables can be fixed to zero a priori: if ? D6   #hi:j then obviously plane 2. Some of the argument based  cannot land before plane ! on the same runway so +  k$ . An analogous +   on the upper bound and costs can be used to attempt fixing of further variables. 1. By using any upper bound

5

+   to take on non-zero values the following constraint may be HZY , W- / +  l"% G0m  c [#nl3o Icp 6 m  c [#n G rqtsBut[ I The right hand side value of this constraint is simply based on the minimum number of  planes are to land on [ runways. More planes that must land on the same runway if kyzh{[ then generally if v is any set of planes with w vxw |ZY , W-~} +  l"%y Gm y c [#n€3i IcFp 6 m y c [#n G ykq'sJut[ I y  p [ then we must have at least two planes on each runway given a For example if [ right hand side value of . Alternatively we could have more on some runway and less on +   values as the sum of +   for others but this would give an even larger number of non-zero % 3   planes on the same runways is given by  G  I‚cp . Naturally there are a large number of

3. In order to force some of the useful:

constraints of this type that could be added. In practice it is only sensible to include these constraints for sets of planes that have their target landing times close together, or by adding them as cuts during the branch and bound process when they are violated.

+ „ƒU" + j6 + …ƒ†3‡

4. Implication constraints of the form are not likely to be useful at the root node of the LP, but may be used to strengthen the LP after branching.

[

[<6‰ ˆ ŒŠ ‹  Hmin ZY W- ‹ 0 MB6   x382"%$2

5. A more complicated tightening constraint can be constructed based on minimum deviations required to land planes on runways. Let be a set of planes such that:

then the following constraint holds:

Ž , - ‹ G|K P6 L  I " ŠŒ‹ [ [O6i planes can land on separate runways, at least one In other words, since only of the pair of planes needs to land on the same runway, and in this case the amount that either of the planes needs to move from its preferred landing time is at least enough to put either  before ! or ! before  as given by ŠŒ‹ . This type of approach is shown in [5] to be able to solve problems for two or three runways with up to fifty planes. However the computational times are still slightly two large for use in practice. In the next section a different approach is described for obtaining results more quickly.

3 A simplex algorithm to determine landing times We first observe that the ALP involves two decision problems: (1) a sequencing problem (that determines the sequence of plane landings), (2) a scheduling decision problem (that determines the precise landing times for each plane in the sequence, subject to the separation constraints). We observe that if we are given the sequence in which planes land, then, we can develop an algorithm for resolving the scheduling decisions. In this section we show how the simplex algorithm can be specialised to the problem of finding the optimal landing times of all planes given a partial ordering of the planes. The algorithm described in this section is used later in a heuristic approach. It is 6



also used to calculate lower bounds that are then embedded in a branch and bound algorithm to find an optimal solution.





 “•‘’ ! ”z!  _ G| !BI7–‘—!

Consider the problem of determining the landing times of planes to land. Let represent an ordering of planes. Note that can either be a partial ordering or a total ordering. Additionally, we define if plane appears before in the sequence. In other words, if and . Thus, a partial ordering of the planes defines a set of ordered pairs .

C  > !

‘’!





!

*  for each plane  such that

*  O˜ f Žš™ , * B6   #9 *  if :‘ _ . 2.  )  3. The cost ( ( ) for landing before (after) is minimised.   We define variables K and L as before. Now the primal landing time problem can be written as: / / Problem PLT: Min , ZMœ (  K R6 , ZMœ )  L  43 K 6 L E3 L " B6   x3T2 & GH !JIx_ Subject to: K (14) 43TM9 L 43 K  &  

~ Ž (15) L 43 K 9 38M &  F

 Ž (16) ž ‚Ÿ "   We now want to find landing times 1.

(17)

This is a linear program which could be solved by any standard LP algorithm. However this would not exploit the special structure of this type of problem.

¡   ¢0£ ¢e¤ / / Problem DLT: ¥§¦1¨   4  T 3    6  , ZMœ ¢0£ G I , ZMœ ¢e¤ G M3© I 6 ,«ªe ¡   G ¬E3TM43    I ­B®¬¯J°‚±²³^³ s – Ž, ´  ¡  ^3 ,ƒ~ª  ¡ ƒµ9 ( B6 ¢£ 3 ¢e¤ &  

  Ž (18) (19) Ž, ´  ¡  ^3 ,ƒ~ª  ¡ ƒµ9 3 ) 26 ¢0£ 3 ¢e¤ &  ¶

 Ž · £ · ¤ ¸ "   (20)   It is obvious that at most one of K and L will be non-zero in the optimal solution of PLT, hence at most one of the constraints (18) and (19) can be active for any  . Also note that the left hand side of equations (18) and (19) are just the network flow equations for a network in which directed arcs join  to ! if ‘—! . Define dual variables , and corresponding to (14), (15) and (16), respectively, the three sets of inequality constraints in PLT. Now the dual of PLT can be written as:

We will now proceed to construct a simplex algorithm, analogous to the network simplex algorithm, which solves DLT. The first step is to consider the structure of basic feasible solutions of this problem.

¹

A basic solution consists of a set of active arcs forming a forest which spans the set of nodes (a single node implies a trivial tree). Each tree in the forest has a root node . This node may be in one of three states: early , late or target. Each non-root node can be in one of two states early or late. Hence a basic solution is characterised by a forest of arcs and a state for each node. These have the following meaning:



7

HG  !JI



!

¡ 

If an arc is active then planes and land with the minimum separation distance carries some flow. between them. Correspondingly the dual variable



K L

(





)

If a non-root node is early (late) then the plane lands before (after) . In other words, ( ) is basic in PLT. In the dual it means that has a supply of (demand of ). The divergence equation holds for all non-root nodes.

¹

¢ º£ ( º

The root node of any tree is used to make up the net difference between supply and demand over the whole tree. If it is in the early state then makes up the difference (for feasible solutions the amount of flow leaving is greater than ). Similarly if it is in the late state then makes up the difference (the amount of flow entering should be greater than ). Finally if it is in its third state (target) then the divergence equations are not applied to this node (the net difference between supply and demand should be between and ). In terms of the primal solution the three states correspond to plane landing at times , or respectively.

¹

¢ º¤

)º

¹

( º  3 ) º º º

¹

º

K

L

¡

Given a basis, the and variables can be calculated for each tree by starting with the root node and working down to the leaves using equation (14). Similarly the flows can be calculated or for each tree by starting at the leaf nodes and working back to the root node, where the variable is determined. Based on this representation of basic feasible solutions we can now develop a simplex algorithm for DLT.

¢¤

¢£

Initialisation: Start with a basic feasible solution for the dual problem. The easiest way to find such a solution is to land each plane at its target time. In other words the basis consists of trees each having only a root node with status target.



as described above. For any plane  if it ˜  fK Žand .™ thenL variables   the corresponding ¢0£ or ¢F¤ has a positive reduced U‘µ! the separation constraint is not satisfied then ¡   has a

Reduced Costs: We calculate the lands outside of the interval cost. Similarly if for some positive reduced cost.

Selection of Incoming Variable: Pick any variable with a positive reduced cost. In practice it makes sense to choose variables with a large reduced cost and to try to cycle through all other planes rather than repeatedly selecting variables relating to the same small set of planes.

¡ 

!



is picked to enter the basis and and Pivoting: There are two types of pivot operations: If are in the same tree then the pivot operation is identical to that of the network simplex algorithm. We simply push flow around the cycle in the direction until the flow in one of the arcs in the cycle becomes zero. This arc is then deactivated to give a new tree.

¡  ! ¼ ¼ ¹ ¼



!

E» !

¹ ¼ GH !JI

In all other cases we push flow along a path with two different end nodes, say and . Assume that is entering the basis and that and are in different trees, with root nodes and respectively. The path from to is made up of the path from to , arc and the path from to . If is in the same tree as , and if is entering the basis, then the path is from to . Similarly, if is entering the basis, then we use the same path in the opposite direction. In each case, the aim is to push flow along the new path (by changing the flows in the path as well as the supply at the end nodes), until one of the flows becomes zero or one of the end nodes changes status. Hence this type of pivot can result in several different changes to the structure of the basis: (1) a tree breaking in two if arc becomes non-basic and and were originally in the same tree; (2) the root node of the tree changes, where becomes the root node instead of ; (3) two trees being joined.

¹

¼

¼

¹

¼

¢ ½¤

¹ ¼

¹

8

¹

¢ ½£

¹ 

HG  !JI

¾

The simplex algorithm then consists simply of repeated iterations of the above steps until an optimal solution is found. Note that apart from a speed advantage over a general simplex algorithm, it also has the benefit that no matrix storage is required, hence memory usage is significantly reduced.

4 A problem space search heuristic Based on the above algorithm it is now possible to construct a number of different heuristic. The heuristics would all follow the following basic pattern: Algorithm 1 repeat Pick a complete ordering of the planes (or a suitable partial order if there are multiple runways) Solve the simplex landing problem as shown in Section 3. if Problem is feasible and has a lower cost than any previously found then Store the ordering and landing times as the best solution endif until termination criterion reached end algorithm 1. Different heuristics can be developed based on the way in which planes are ordered in the first step of the loop. Usually the termination criterion would be a maximum iteration limit, though other methods could be envisaged. A very simple heuristic would be to go through the loop just once, or maybe a small number of times, with the planes sorted according to target landing times (with maybe some small randomzation) and each successive plane allocated to a different runway, looping back to the beginning when the last runway is reached. A more heuristic can be developed under the above scheme using the Problem Space Search (PSS) is meta-heuristic approach. It attempts to combine a (usually) simple constructive heuristic with a genetic algorithm (or, perhaps some other heuristic search algorithm). The main idea of PSS is that we do not attempt to search through the space of feasible solutions directly. Instead, we use a base heuristic as a mapping function between a space of perturbations and the solution space. Thus it is sufficient to use the base heuristic and some method of searching through the perturbation space (in this current application, through a genetic algorithm), to find a good solution to the original problem. For more details and some variations on this basic idea of PSS, see Storer, Wu & Vaccari [16]. The implementation of the PSS heuristic for the aircraft landing problem uses a constructive heuristic to order the planes and a genetic algorithm to search through the space of all orderings of planes. These two parts of the PSS algorithm are described below.

4.1

The constructive base heuristic

¿

A sequence for landing the planes is constructed using a greedy approach based on a set of priorities. In each iteration of the algorithm the plane with the lowest priority is picked to be 9

À

¼ ƒ ‰Á2:6<ÂÄà  ƒ 6 K 1 (21) ƒ Á   à  is defined Here and are two arbitrary positive weights and K is a perturbation of the priority. as the earliest time that plane ! can land given the previous sequence of planes. That is if the

 ¢ ƒ œ of planes has been constructed already then partial sequence ¢ Å ¤ ƒ à   max Æ ^0 max «ÇJƒ  à È| É 6  ÈÊÉšË  ¬Ì ƒ C ƒ  

 0 Y Í We then define the next plane to land as: ¢ arg min ÈÊ΂ËjÏ jÏ Ë È5ЅÑeÒÊÓ ¼ ƒ ƒ Note that the earliest possible landing time for plane ¢ is given by ÈÊÐ . Ã ƒ hi È5Ð for This heuristic will not necessarily find a feasible landing sequence (it is possible that ÈÊÐ some ¿ ). This heuristic could be modified to reduce the likelihood that an infeasible sequence will be generated. However in practice the algorithm only rarely fails to provide a feasible solution as long as the perturbations ž are not too large. landed next, where the priority for each of the remaining planes is calculated as

The rational behind this heuristic is that the natural way for the planes to land is in order of their target times, however if their earliest possible landing time is quite late then it may be better to use a plane which can land earlier even if its target time is a little later. Obviously we use . In fact for the results presented below, and . The perturbations for each plane are an input to this heuristic.

ÁÔkÕ

4.2

ÂE’

K

ÁŒh¶Â !

The PSS meta–heuristic

ž

The problem space search heuristic uses a genetic algorithm to search through the space of perturbation vectors . We only use a simple GA scheme to search the perturbation space. Several sophisticated GA variations exist in the literature (see for example, [15]). The basic algorithm that we implement is as follows:

ž œ   €ž ÖW× ž†Ù ž Ø žlÚ

½

Algorithm 2 with random individuals Initialise population size for to do repeat Choose 2 members of the population as parents Perform a single point crossover with mutation to obtain until produces a feasible landing sequence Evaluate using the simplex algorithm Replace the worst member of the population with next Report the best solution found end algorithm 2.

 ¶ bØ žlÚ



žlÚ

ž†Ú

The following parameter settings are used for the results in this paper:

K

The genes of the initial population as well as the mutations are generated using an exponential distribution for positive and negative with an even chance of positive or negative values.

10

Û

Û   Ü Ý max 1Á2:6<Â4^ #3 min 1Á¬P6<Â4^0Þ@ This ensures that the perturbations K are of a similar size as the differences in priority values. $2 ßà . The probability of a gene being mutated at birth is  $$ and the number of births bØ:¶0$$$F$ . The population size ½ is p The parameter

4.3

used for the exponential distribution is

PSS for Multiple Runways

The PSS heuristic described (as described in this section so far) can be extended quite easily to take multiple runways into account. An initial attempt was to employ the constructive heuristic for assigning planes to runways. This did not provide promising results. Hence the task of deciding on runways for each plane was added to the genetic algorithm.

G|K 5 ¹  I

K

¹

For each gene of the population of multiple runway solutions consists of a list of ordered pairs where is the perturbation used by the constructive heuristic as before and is the runway index for plane . For the initial population and mutations the runway is chosen at random using a uniform probability distribution.



5 A branch and bound method for multiple runway problems Based on the simplex method described in Section 3 we can also construct a branch and bound method that solves the ALP for single and multiple runways. It uses the simplex method to derive lower bounds for a given partial order and progressively orders more planes until a complete sequence of planes for each runway is found.

_

_

|G  !JI

Denote by the set of all the pairs of planes which have to land in that order on the same runway. That is only contains pairs of planes which we have constrained a priori to land on the same runway. Let be the set of runways, indexed by . At any point in the branch and bound algorithm we have some set (which might be empty at the root node) and a set of landing times corresponding to this set determined by the simplex algorithm.

5.1

ˆ á  p

~ Ž[“

_

Assigning planes to runways

Assume that we are given the landing times for each plane as well as a set tries to allocate the planes to runways has to do the following: 1. For any

HG  !JIx_



, planes and

!

¹

_

_

. Any algorithm that

have to be assigned to the same runway.

2. All runways must be used, unless it is possible to land all of the planes on fewer runways than are available without violating the separation constraints. 3. If no feasible solution can be found, the algorithm has to indicate which planes conflict with each other, thus preventing a solution from being found.

11

¾ _

The set defines groups of planes that have to land on the same runway. For each of these groups containing more than two planes we need to check that the separation constraint is satisfied. For example it is possible that and are in , so that and have to land on the same runway, but and have been assigned the same landing time. If an infeasible pair of planes is found then we return the pair with maximum conflict. The branch and bound algorithm can then branch on the two possible orderings of the pair. (In the above example the we would branch by including or in ).



!

G| ¿¬I

G.! ¿¬I

 !

_

¿

G| !BI G.! gI _

Next we order the planes according to the landing times assigned to them by the simplex algorithm. We then go through the list of planes in chronological order and try to assign to each plane a runway on which it will not conflict with previous planes. If there are several runways on which plane could land then we choose the runway for which the gap to the previous planes is smallest (breaking ties arbitrarily). More precisely we choose a runway which minimises



¹ â º  *  3 max   :  6 …  5  

Ž - ãBÉä * (22)  º * where å is the set of planes already assigned to runway ¹ and the landing time of plane ! . On â º is negative for each runway ¹ , then we can not find a feasible solution. Let yx the other hand if o [ % 6  º be a set of planes consisting of  and one plane ! in each å which attains the maximum in yx (22). In order to land all of the planes on the available runways, at least two of the planes in must land on the same runway.



â º

¹



º - ‹d( º

Rather than stopping as soon as we find the first plane that can not be landed, we assign to the runway with the largest (least negative) and continue assigning planes to runways. Once all planes have been assigned to runways we choose the set for which max is smallest (most negative) to continue the branch and bound process. Note that the above process is a heuristic assignment method. Even if this method produces sub-optimal assignments in some cases, the branch and bound will ensure that the optimal solution is found eventually as described below.

5.2

yx

Preprocessing

Some use can be made of the preprocessing techniques that we developed for the single runway problems. The method of tightening landing intervals based on the upper bound described for the such that if and land on the MILP formulation still applies. We define a set of planes same runway then must land after . There are several ways in which we can add elements to this set as described below.

æ

!



æ

5.2.1 Upper Bound based Fixing



!

¬6  = S 

HG  !JI



!

!



Consider two planes and . What would be the cost of landing plane before plane if there are no other planes to be landed? Obviously if the cost is zero. Otherwise we have to displace at least one of the planes from its target time. Assume that (the case where is similar), then it is cheaper to move back than to bring the landing time of forwards. Hence the minimum cost is achieved by

) E" ( 



) S (

!

* R min 026  …5 Ž5

*   * 43  …Ê )  * 23] I 6 (  G 23 *  I . If this cost exceeds the upper bound, or The cost of landing the planes is G *  S E then plane ! can not land before plane  , hence ‘
ç

G.! fI

A second pass of this type of fixing can be made once some of the other pre-processing methods have given the ordering of some of the planes. In the second pass, we simply fix and solve the lower bound problem using the simplex method to see if this lower bound exceeds the upper bound. The advantage of this method is that it gives better lower bounds using information from the other pre-processing steps. The disadvantage is that it is relatively expensive. 5.2.2 Fixing Based on Data

! ”èE ”èé  :’2 (  (  )  )   êƒ\  …ƒe  ƒ  ƒg‚& ¿ 

! GH J! I _ More generally  can be assumed to land before ! in the (an) optimal solution if all of the following conditions are satisfied: D9%E , 9i2 and D9%é . 1. Plane  is earlier than plane ! . More precisely   #9  = . 2. Landing  before ! does not require more time, ie 3. It is no more expensive (in terms of displacement of  and ! ) to land  before ! than vice ) #" )  or €9ë¬ ) and (( €9 (  or €9á^ ). This eliminates the versa. Mathematically: ( possibility that it may be much cheaper to, say, delay  for a very long time so as to land ! on time (or even early). 4. Reversing the order and landing ! before  would not reduce the separation to other planes.



If some third plane ¿ is comparable to both  and ! (ie ¿ì‘{ ! or  !t‘k¿ ) then we only need to check the separation in one direction otherwise we check both. More precisely: ¦eï u && ¿í–4GH ¿¬I†> _ ssîî G.! ¿¬I†> _

 ‚ƒgƒ†#"9  „ƒƒ  ¿ì–GÊ¿ gI†> _ G5¿ !BI†> _

If all of the four conditions above are satisfied then GH !JI can be inserted into _ . There are a

Consider two planes assigned to the same runway with identical data ( , , , , and ). In this case it is irrelevant in which order and land so we can insert into arbitrarily.

lot of conditions that need to be satisfied, making it unlikely that a randomly generated problem would satisfy all of them for very many pairs. However these pairs, if identified have the potential to reduce processing times significantly. Assume for example that planes and have identical data. Then they satisfy the above condition and would be fixed to land in some arbitrary order. However if they were not included in then the branch and bound algorithm may branch on and at the root node producing two identical subtrees, thereby doubling the number of nodes that have to be searched.

_

G.! gI

5.3



Branch and Bound

_

æ

!

G| !BI

We start the search for an optimal solution with an empty set and with given by the preprocessing. The branch and bound method for the multiple runway problem differs from that for the single runway case in that a node may have either 2 descendants or . The first case occurs when two planes in the same group are found to violate the separation constraint. In this case the pairs and are added to (and ) to produce two new nodes of the branch and bound tree. The second scenario is where we have a set of planes that clash produced by the heuristic method of assigning planes to runways. In this case we generate a descendant node for each pair with and .

HG  !JI

 !

G.! fI G.! ¿2I

! ¿ì yx

_

!A > ¿

æ

yx [i6ò

13

[lðñ6§[

Gß! ¿¬I 

ó

Note that it is possible that one or more of these pairs could be allocated to the same runway without changing the landing times (in other words the heuristic may have made a poor choice in allocating planes to runways before coming to plane ). In this case we may choose to run the heuristic again but try to put and on the same runway to see if this will lead to a feasible solution. However experimental experience suggests that this is hardly worth doing. Hence we only run the heuristic once for each node.

!

¿

HG  !JI _

We use a simple depth first method for processing the branch and bound tree. There are several ways to reduce the size of the tree. For each new node, created by adding the pair to we can do the following: Cutting based on upper bound: This is the standard way of cutting the branch and bound tree. Whenever the lower bound calculated by simplex is greater than the upper bound (or the subproblem is infeasible) we can abandon the current node and backtrack.

æ

æ GH !JI _ G.! fI]æ

Inference: This can be applied not only to the set _ but also to æ for conclusions based on GH !JI .

For any pair GH !JI€O_ , if ! and ¿ land on the same runway then so do  and ¿ . Hence from

GH !JIx_ô‰æ and Gß! ¿¬I7õæ we can conclude GH ¿¬Ix]æ . Cutting using : We can make use of to cut branches at which pairs of planes have been placed on the same runway in an order that can not lead to an optimal solution. Whenever is to be added to and we can immediately cut of that branch.

6 Results This section contains some computational results of the algorithms presented in this paper. The algorithms for multiple runways was tested on the aircraft landing problem test data sets provided by the OR problem library maintained by Beasley [3] (problems number 1 – 8) as well as two new problems (problems 9 & 10). All programs were run on a DEC 3000/700 (200MHz Alpha CPU). The exact algorithms were programmed in C and compiled with maximum compiler optimisation. The problem space search heuristic was tested on both single and multiple runway problems. For each problem the heuristic was run 20 times to give a good indication of the average behaviour of the heuristic. Table 1 shows the results for the single runway problems. The upper gap from the optimal solution (denoted as Gap), defined as , is given in Table 1. We provide the worst upper Gap, the best upper Gap as well as the average upper Gap over 20 trials. The

G5ö^÷ 3 öø W½ ù I c ö:ø ½Žù

Prob No. of Min Avg Max No. Planes Gap (%) Gap (%) Gap (%) 1 10 0.00 0.00 0.00 2 15 0.00 0.00 0.00 3 20 0.00 0.00 0.00 4 20 0.00 0.00 0.00 5 20 0.00 0.00 0.00 6 30 0.00 0.00 0.00 7 44 0.00 0.00 0.00 8 50 0.00 0.99 10.51 9 30 0.00 0.00 0.00 10 44 0.00 2.57 7.42

No of CPU Births (sec) 5075 0.71 6339 1.24 5463 1.63 5226 2.14 5466 2.32 5230 5.67 6304 9.87 11160 20.54 6215 7.95 15636 34.42

Table 1: Heuristic results for a single runway 14

ú

last two columns in the table give the average number of births (individuals evaluated) and the average running time over all trials. As can be seen the heuristic manages to produce solutions in a reasonable amount of CPU time. In most cases the solution is consistently optimal. In the two problems where this is not the case (problems 8 & 10), it nevertheless manages to produce a reasonable solution with only occasional outliers where the heuristic gets stuck in an local minimum. Table 2 shows the results of the upper bounding heuristic for the multiple runway problems. For each data set we start with two runways and solve with an increasing number of runways until it is possible to land all planes without delay. In most cases this requires 3 or 4 runways, the exception being problem 7 where 2 runways are sufficient. Instead of showing the upper gaps, we show the actual minimum, average and maximum objectives. This is because the percentage gap as defined above is meaningless when the objective is zero, as is the case in many of the examples. For each of the problems the minimum objective value found is optimal. The running time is similar to that required by the single runway problems. However the solution quality is less consistent. In many of the dual runway examples the heuristic occasionally fails to find the optimal solution. This is presumably because the perturbations are used in the base heuristic only to determine the order. The assignments of planes to runways is affected only indirectly by the perturbations. It would be possible to modify the base heuristic to add perturbations for the construction of assignments of planes to runways. However such an approach would require not only additional coding but also a greater effort by the genetic algorithm since the parameter space would be significantly increased in this manner. Given that the average solution quality is still reasonable, the extra effort seems unjustified. Prob No. of No. Planes 1 10 1 10 2 15 2 15 3 20 3 20 4 20 4 20 4 20 5 20 5 20 5 20 6 30 6 30 7 44 8 50 8 50 9 30 9 30 10 44 10 44 10 44

No. of Runways 2 3 2 3 2 3 2 3 4 2 3 4 2 3 2 2 3 2 3 2 3 4

Min Cost 90.00 0.00 210.00 0.00 60.00 0.00 640.00 130.00 0.00 650.00 170.00 0.00 554.00 0.00 0.00 135.00 0.00 219.00 0.00 660.00 63.00 0.00

Avg Max Cost Cost 90.00 90.00 0.00 0.00 210.00 210.00 0.00 0.00 74.00 100.00 0.00 0.00 640.00 640.00 130.00 130.00 0.00 0.00 650.00 650.00 170.00 170.00 0.00 0.00 569.45 758.00 3.45 39.00 0.00 0.00 184.25 255.00 3.00 15.00 219.05 220.00 0.00 0.00 864.00 1080.00 94.30 178.00 1.90 20.00

No of CPU Births (sec) 4075 0.62 4079 0.57 4080 1.16 4085 1.06 4470 2.04 3482 1.49 4237 2.22 4176 1.95 2696 1.14 4478 2.40 4512 2.09 973 0.42 5984 6.60 750 0.76 1235 2.57 8361 23.08 2613 7.02 5331 6.37 486 0.54 8577 26.26 7742 16.73 2676 5.55

Table 2: Heuristic results for a multiple runways 15

The results of the exact algorithm for multiple runway problems are summarised in Table 3. The column headings have the following meaning: For each problem (Prob No.) we give the number of planes and runways involved and the optimal objective value (Opt Cost). Next we list how many were added to in the pre-processing and during the branch & bound based on pairs

G| !BI

_

Cost: cost based arguments (see Section 5.2.1), Data: problem data (see Section 5.2.2), and Inference: deduced from the transitive nature of

_

(see page 14).

Finally we show how many branch and bound nodes were required to find an optimal solution and how much CPU time. Prob No. of No. of Opt. Pre-processing B&B fixed per node No. of CPU No. Planes Runways Cost Cost Data Cost Inference Nodes (sec.) 1 10 2 90 48 0 0.00 0.00 1 0.00 2 15 2 210 104 1 0.00 0.00 2 0.00 3 20 2 60 192 2 0.00 0.00 1 0.00 4 20 2 640 158 24 0.75 0.53 533 0.36 4 20 3 130 196 2 3.33 0.18 6 0.01 5 20 2 650 155 27 0.78 0.62 669 0.44 5 20 3 170 194 1 2.54 0.00 24 0.02 6 30 2 554 422 4 3.67 0.49 154 0.22 8 50 2 135 1215 0 9.45 0.09 11 0.06 9 30 2 219 410 11 4.42 0.43 137 0.21 10 44 2 660 668 139 7.29 0.92 94614 292.05 10 44 3 63 967 0 10.14 0.07 14 0.05 Table 3: Exact solutions for multiple runways The results for the exact algorithm for multiple runways is given in Table 3. Here we only report the results for all runway numbers which lead to a non-trivial solution. In other cases the solution was found ‘instantaneously’. In other words, Problem 7 is not represented in Table 3 because, all 44 planes in Problem 7 would land on target (thereby producing an optimal solution value of 0) if we present it with two runway options to land on. The algorithm generally has no difficulties solving these problems, the only one which requires a bit of effort is problem 10 with 2 runways. In Problem 10 (and also Problem 9) the aircraft are essentially of 2 types (A and B) with separation requirements between any pair of planes only depending on their type. Furthermore all of the planes have , and . Hence, for these problems, the objective is to minimise the sum of the delays (with no early landings allowed). Each of the planes has only a marginally different target landing time . Thus there is little to distinguish one solution from another, forcing the branch and bound algorithm to search a large number of nodes with almost identical costs.

(  ) 7V 7ûM

Rü M

These results compare favourably those obtained exact algorithm described by in [5]. They only provide results for Problem 1 – Problem 8. Their MILP based algorithm was tested on the same computer that we used for our tests. The MILP approach of [5] solves Problem 5 with 2 runways and Problem 8 with 2 runways in 11510.4 seconds and 3450.6 seconds respectively. The above approach based on the specialised simplex method is able to solve these problems in 2.84 seconds and 23.14 seconds respectively.

16

7 Conclusions In this paper we have developed a specialised lower bounding method for the aircraft landing problem. This method is based on the simplex algorithm, but makes use of the specific problem structure of the LP relaxation of the aircraft landing problem to produce a much faster algorithm. This yields a fast method for finding the landing times of planes in the static horizon of an air traffic controller, given a partial ordering of the aircraft. This fast method for finding landing schedules is used both in a heuristic as well as a branch and bound method. We develop a heuristic based on problem space search. This heuristic is extremely effective for all of the test problems. The branch and bound method depends heavily on the success of several pre-processing methods that are described in this paper. In all but two (artificially derived difficult) problems, the exact method is very efficient in solving both the single and multiple runway problems in a reasonable amount of computational time. Our methods are also an improvement on a comparable method that exists in the literature for such problems. It is of interest to see if the results that we describe in this paper can be transferred to yield good algorithms for a similar problem in the machine scheduling literature – the problem of scheduling jobs on machines with sequence-dependent processing times. This is a topic of current research. Moreover, it is of interest to see if some of the results that we have described in this paper can be used to solve the practical problem of scheduling planes in a ’dynamic’ ATC horizon, in which some planes land (and hence depart from the ATC horizon) and new planes appear (into the ATC horizon) at a steady rate.

8 The Displacement Problem 8.1

Problem context

In many decisionmaking problems we assume a static operational environment. However often in applications the operational environment changes, typically as time passes new information makes it necessary to revise the previous decisions that have been made. Whilst it is sufficient to assume a static environment for planning purposes, reallife applications require the study of tactical decisionmaking in operational environments. In scheduling aircraft landings, as a new plane appears we may have to revise the landing times of planes that have already been scheduled for landing. This problem is dynamic in the sense that planned decisions are continually having to be revisited as the operational environment changes. However it is clear that, from an operational viewpoint, it may be undesirable to perturb (change, displace) the previous decision ”too much” in making a new decision. Placing a new plane at the front of the landing queue may change the previous scheduled landing time for all planes already in the queue. Typically therefore in making a new decision we have to explicitly consider the previous decision (solution) as we have some degree of commitment to it and are reluctant to change it too much. Hence we have a displacement problem, the problem of making a decision but with an explicit link back to the previous decision that was made. Whilst we have discussed this problem in words above the problem can be formulated mathematically as below.

17

8.2

Displacement formulation

Dynamic aircraft landing problem is a particular case of the generic displacement problem discussed in [4]. As such we need to define an appropriate displacement function for the problem. In the aircraft landing problem each plane has a target landing time and we assign it a scheduled landing time. This scheduled landing time could be less than, equal to, or greater than, the target landing time. It seems reasonable to assume however that, after each plane is told of its scheduled landing time, then that time becomes its new target time. Moreover, as we have cost information for each plane in regard to deviation from the original target time (for plane , per unit of time for landing before target and per unit of time for landing after target) we consider that an appropriate displacement function is:

) ýÔ Gÿþ 1  I  ()   G  þ  I if þ €€ 9h “ ! ’¶

   Ž Ž GHþ I if þ !


!





! (

 



(23)

In other words the displacement function reflects the cost of deviating from the scheduled landing time ( ) assigned in the preceding solution. This function has the desirable property that it penalises any deviation from the previous solution with a cost of zero if the new solution ( ) is the same as the old solution ( ). We have made an implicit assumption here, namely that each plane is told of its new ( ) scheduled landing time after the solution of each displacement problem, i.e. that each time we solve the displacement problem we communicate (broadcast) the solution to each plane.

þ

þ



It is clear that our choice of displacement function is somewhat arbitrary. For example, the displacement function defined above (23) only takes into account changes in scheduled landing times. There could well be, between displacement problem solutions, changes in the runway assigned for landing. There is a case therefore for including in the displacement function a term relating to changes in the runway assigned to each plane. For the purposes of the computational results presented in this paper, however, we did not include such a term in the displacement function. Also it seems unlikely that a change in runway would be considered as undesirable as a change in landing time. Different displacement functions could be defined for the dynamic aircraft landing problem. However the above definition is likely to be a reasonable first approximation to any more complicated displacement function. Also this definition has the highly desirable property that it creates a displacement problem which has the same structure as the original static ALP, allowing the same algorithms to be used to solve the problem.

9 Discussion There are a number of issues that arise from the above formulation of the displacement problem. These are discussed below. Decision process We would envisage that the displacement problem would be applicable in any situation where we have to continually revise the decisions made previously while not wanting to unnecessarily deviated from a plan arrived at previously in order to minimise the inconvenience to all parties concerned in the landing of the planes. Hence we make successive decisions as the operational environment changes, each time formulating and solving an appropriate displacement problem that incorporates the previous decision ( ) that was made. To illustrate this, the decision process we envisage following is:



18

1. Let

 be the initial decisions.

2. Wait until a change which necessitates a new set of decisions occurs. Most likely this is in the form of a new aircraft arriving as well as some of the aircraft already having landed. However changes could also occur to the time windows with updates to the estimated earliest and latest arrival times due to unforeseen circumstances.

*

“  equal to the solution value for *  as obtained from step (3) above. 4. Set 5. Go to step (2) above.  and the formuVariables Any variables ”removed” from the problem between the old solution 3. Formulate and solve the displacement problem involving new (unknown) decisions and the previous (known) decisions .

lation of the displacement problem (ie. planes that have landed) are probably best dealt with via a constraint (set the variable equal to the value it took in reality) so that, without loss of generality, we can assume that the number of variables is increasing. Though obviously it is desirable to periodically clean out all of the old unused variables that no longer have any effect on the solution (ie once the landing times of planes no longer affect the possible landing times for planes still in the air).



Constraints Similarly any constraints ”removed” from the problem (e.g. constraints that have become inactive between the old solution ( ) and the formulation of the displacement problem) could be dealt with by setting the righthand side of the constraint appropriately. However in here it is likely that better efficiency is gained by deleting any constraints as soon as they have become redundant.

* “  ! µF

~ Ž þ 

!  r6‡

 

Solutions In the displacement problem setting variable values equal to their previous solution  values (i.e. for ; to be decided for all new planes ) may not be feasible, and even if feasible may not be optimal (of minimum cost). This applies was the optimal solution of the previous problem. even if



Variations There are a number of variations to the basic displacement function described above that could be incorporated very straightforwardly into the MILP formulation of the displacement problem, and with some work also into the specialised simplex algorithm described above. For example one could charge no penalty for any landing time between the original target landing time and the most recently broadcast one . In essence this would replace the concept of a ‘target landing time’ with one of a ‘target landing interval’. This simplest of the variations could easily be incorporated into the specialised simplex algorithm without any major changes. More complex options include having a penalty for both deviation from and a different penalty for deviation from . Thus the objective function would be piecewise linear in with three distinct pieces.

M

*

Ä



t

Another potential source of variation is to adapt the cost coefficients depending on how far out the plane is. Once a plane is close to landing, making last minute changes to scheduled landing times or the sequence of planes is likely to be far more disruptive than when the plane is still some way off from using the runway. The choice of displacement function is (inevitably) somewhat arbitrary. Simply put, there is no one unique displacement function that (logically) dominates all other possible displacement functions for a particular problem. As such different decisionmakers may prefer different displacement functions for the same problem. Linking to all previous solutions As we have formulated it the displacement problem just links the current (unknown) solution to the previous (known) solution. It is a simple matter to extend the formulation to link the current (unknown) solution to all previous solutions. However 19

we believe that the utility of such an approach is dubious. In reality it may be difficult enough to decide an appropriate displacement function to quantify (for each and every variable) displacement from the previous solution, let alone decide a function to quantify displacement from all previous solutions. Frequency of resolving What should be the rule for deciding when new decisions are to be made, i.e. when a displacement problem needs to be solved? For example, we may solve a displacement problem after every change; after a fixed number of changes; after a fixed time interval; after some combination of changes/time; etc. Obviously there may be a choice about whether or not to make new decisions after a change. When a new plane appears it may still be some time away from landing. Hence we could wait and see if any more planes appear before solving the displacement problem and revising the landing times (and runways) of planes that have already been scheduled for landing. In practice it is likely that a simple rule of thumb will be used that depends bot hon the number of changes and minimum/maximum time interval between solutions to the displacement problem. Broadcasting Should we communicate (broadcast) the solution to each displacement problem or not? For example, it is perfectly possible for a plane to have a scheduled landing time of 0930 initially, 0941 after the first displacement problem is solved, but reverting back to 0930 after the second displacement problem is solved. In such a case communicating the new scheduled landing time to the plane after each displacement solution may (in operational terms) be unacceptable and confusing. By contrast we could just communicate the initial scheduled landing time to the plane and then delay communicating new scheduled landing times until (for example) we are reasonably sure that the plane will not be able to land at the time initially communicated. Hence we need to develop rules for deciding whether (and when) to communicate solutions, which may change after further displacement problems are solved, to those affected by such solutions (the pilots and passengers).

ýÔ Gÿþ 1  I

“

With regard to this point note here that we have implicitly assumed in defining the displace
that refers to the last solution communicated. This is because ment function we have assumed that any cost incurred in displacement can only occur in suffering a displacement from something known, i.e. the previously communicated solution. There is little that can be said from a theoretical standpoint on this question, however finding a reasonable answer to this question is vital for the successful implementation of such a system in practice. A good compromise may well involve communicating changes to the solution more frequently to those planes that are close to landing while only infrequently to those that are not scheduled to land for quite some time, unless a very major change to their landing time has occured. Given the nonunique nature of the displacement function, consultation with decisionmakers and affected parties (such as air traffic controllers, airport managers and pilots in the case of scheduling aircraft landings) will be vital.

9.1

Conclusions

In this paper we described the aircraft landing problem (ALP) that describes the scheduling problem arising out of the decisions arising at a busy airport where airplanes need to be assigned runways and landing/takeoff times in order to make best use of the runways which commonly form a bottleneck. A number of algorithms are described that provide good numerical solutions to the static version of the ALP where the number and characteristics of the planes are known and unchanging.

20

¾

In this paper we have also described the displacement problem that occurs when landing planes in a dynamic environment. We have indicated a number of different options that can be used to tailor this approach to a particular environment and the preferences of the organisations and individuals involved. Despite this flexibility and large number of options the same underlying mathematical techniques can be used to provide solutions to the displacement problem as were described for the static problem in this paper.

10

Acknowledgments

Much of the material presented in this paper is drawn from previous work published by the authors with Robert Storer [11] and with Beasley, Sharaiha and Abramson [5, 4].

References [1] J Abela, D Abramson, M Krishnamoorthy, A De Silva, and Graham Mills. Computing optimal schedules for landing aircraft. In Proceedings 12th National ASOR Conference, pages 71– 90, Adelaide, Australia, 1993. [2] A Andreussi, L Bianco, and S Riccardelli. A simulation model for aircraft sequencing in the terminal area. EJOR, 8:345–354, 1981. [3] J E Beasley. Or-library: distributing test problems by electronic mail. Journal of the Operations Research Society, 41:1069–1072, 1990. [4] J E Beasley, M Krishnamoorthy, Y M Sharaiha, and D Abramson. Dynamically scheduling aircraft landings - the displacement problem. Submitted to Transportation Sciences, 1996. [5] J E Beasley, M Krishnamoorthy, Y M Sharaiha, and D Abramson. Scheduling aircraft landings - the static case. Transportation Science (Forthcoming), 34(2):180–197, 2000. [6] L Bianco and A R Odoni (eds.). Large scale computation and information processing in air traffic control. Springer-Verlag, 1993. [7] L Bianco, S Ricciardelli, G Rinaldi, and A Sassano. Scheduling tasks with sequence dependent processing times. Naval Research Logistics, 35:177–184, 1988. [8] L Bianco, G Rinaldi, and A Sassano. A combinatorial optimization approach to aircraft sequencing problem. In L Bianco A R Odoni and G Szego, editors, Flow Control of Congested Networks, volume 38 of NATO ASI Series, Series F: Computer Systems and Systems Science, pages 323–339. Springer-Verlag, 1987. [9] R G Dear. The dynamic scheduling of aircraft in the near terminal area. Research Report R76-9, Flight Transportation Laboratory, MIT, 77 Massachussetts Avenue, 33-412, Cambridge, MA 02139, USA., 1976. [10] R G Dear and Y S Sherif. An algorithm for computer assisted sequencing and scheduling of terminal area operations. Transportation Research Part A – Policy and Practice, 25:129–139, 1991.

21



[11] A T Ernst, M Krishnamoorthy, and R H Storer. Heuristic and exact algorithms for scheduling aircraft landings. Networks, 34(3):229–241, 1999. [12] J Milan. The flow management problem in air traffic control: a model of assigning priorities for landings at a congested airport. Transportation Planning and Technology, 20:131–162, 1997. [13] A R Odoni, J M Rousseau, and N H M Wilson. Models in urban air transportation. In S M Pollock, M H Rothkopf, and A Barnett, editors, Operations Research and the Public Sector: Handbooks in Operations Research and Management Science, volume 6, pages 107–150. Elsevier Science, 1994. [14] H N Psaraftis. A dynamic programming approach for sequencing groups of identical jobs. OR, 28:1347–1359, 1980. [15] C R Reeves. Genetic algoritms for the operations researcher. INFORMS Journal on Computing, 9(3):231–250, 1997. [16] Robert H Storer, S David Wu, and Renzo Vaccari. New search spaces for sequencing problems with application to job shop scheduling. Management Science, 38(10):1495–1509, 1992. [17] C S Venkatakrishnan, A Barnett, and A R Odoni. Landings at logan airport: Describing and increasing airport capacity. Transportation Science, 27:211–227, 1993. [18] H Winter and H G Nuber (eds.). Advanced technologies for air traffic flow. Springer-Verlag, 1994.

22