# An Efficient Approximation Algorithm for Aircraft Arrival Sequencing and Scheduling Problem

Authors: Weimin Ma; Bo Xu; Ming Liu; Hui Huang
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

The aircraft arrival sequencing and scheduling (ASS) problem is a salient problem in airports' runway scheduling system, which proves to be nondeterministic polynomial (NP) hard. This paper formulates the ASS in the form of a constrained permutation problem and designs a new approximation algorithm to solve it. Then the numerical study is conducted, which validates that this new algorithm has much better performance than ant colony (AC) algorithm and CPLEX, especially when the aircraft types are not too many. In the end, some conclusions are summarized.


---

## Body

## 1.  Introduction

With the rapid development of airline industry, serious congestions and frequent delays have been hitting most major airports in the world, especially in the United States and Europe [1]. How to enhance the air traffic capacity and reduce the delay becomes a severe problem [2, 3].In 1998, runway has been identified as the primary bottleneck in air traffic [4]; that is, even small enhancements to runway throughput will significantly reduce the delay. However, building more runways is often considered not a realistic option because of practical constraints and huge investment costs. Therefore, many researches and technologists resort to a promising approach, which is to more optimally schedule the aircraft arrival sequence so that the runway can land as many aircraft as possible within a period of time. The optimization process is formulated in this paper as the aircraft arrival sequencing and scheduling (ASS) problem (see in Section 2).However, ASS is inherently hard to solve [5]; it is nondeterministic polynomial (NP) hard [6, 7]. To cope with it, two methods are often adopted, which are mixed integer programming (MIP) and ant colony (AC) algorithm [5, 8–10].ASS can be expressed by MIP formulations. In 1992, Brinton [11] has introduced, as far as we know, the first MIP formulations and designed an implicit enumeration (IE) algorithm to optimize it. In 1993, another MIP is presented by Abela et al. [12] for single-runway ASS. A branch and bound (B&B) algorithm is developed to solve it. Back in 1999, the MIP is presented not only in single but also in multiple runway [8]. Beasley et al. [5] give an improved B&B algorithm by employing linear programming (LP) based tree search. Then Bennell et al. [13] provide an extensive literature overview for ASS.Ant colony (AC) algorithm [9, 10, 14] is another effective method for ASS. It is originally proposed by Dorigo in 1992 [15–17]. In 2002, Randall [10] presents its first application in ASS, which shows great advantages. Then AC is used to generate initial solutions and to incorporate local search heuristic for single- and multiple-runway ASS [9, 18]. Back in 2010, AC is developed to tackle the real-time ASS based on the receding horizon control by Zhan et al. [14]. Experimental results validate that AC is robust, effective, and efficient for ASS.In this paper, rather than using the above two methods, we develop a new approximation algorithm for ASS. The core idea is to find the lower bound solution of the ASS problem. Then the algorithm presents solutions infinitely approaching this bound. We compare the performance of this new algorithm with AC and MIP (by CPLEX). Computational results verify that this new algorithm returns much better solution and costs less time than AC and MIP, especially when there are several aircraft types.This paper is organized as follows. In Section2, some constraints for ASS are introduced. The approximation algorithm is proposed in Section 3. In Section 4, ant colony (AC) and MIP are designed for ASS. In Section 5, numerical study is conducted to compare the performance of this new algorithm with AC and MIP (by CPLEX), while some conclusion is summarized in Section 6.


## 2. Basic Concepts

### 2.1. Aircraft Sequencing and Scheduling (ASS) Problem

ASS aims to make the most use of runway, that is, to minimize the makespan of the landing sequence so that to land as many aircraft as possible within a period of time. The objective function is(1)
min
⁡
W
π
=
x
π
end
,
where x
π
end is the landing time of the last aircraft in sequence π. For the ith aircraft in sequence π, its landing time is achieved by
(2)
x
π
i
=
max
⁡
e
π
i
,
current
time
,
if
i
=
1
;
max
⁡
x
π
i
-
1
≤
l
π
i
-
1
e
π
i
,
x
π
i
-
1
+
MS
T
TP
π
i
-
1
,
TP
π
i
,
if
1
<
i
≤
n
,
where e
k and l
k insure the time-window constraint and MST insures the minimum separation time constraint. These two constraints, as well as some other constraints, are described below. If x
π
i
-
1
≤
l
π
i
-
1 is not satisfied, x
π
i equals +
∞.


#### 2.1.1. Minimum Separation Time (MST) Constraints

MST is a hard constraint to insure safety. When an aircraft flies in the air, it generates wake-vortex (WV). However, WV may result in the instability of the following aircraft (to shake or to lift) [19]. To avoid this, a MST is strictly kept between them.Table1 illustrates a typical MST table concerning three main types of aircraft. Generally, a smaller aircraft followed by a larger aircraft requires much shorter MST than the other way around. For example, a small aircraft has to wait for 196 s after the landing of a heavy aircraft. However, when a heavy aircraft lands after a small aircraft, the MST is only 60 s. One reason is that larger aircraft commonly generates and tolerates more turbulent air, while smaller aircraft generates and tolerates less.Table 1
MST (in sec.) between operations on the same runway [22].
Following
1
2
3
1
82
69
60
Leading
2
131
69
60
3
196
157
96
1 = small aircraft, 2 = large aircraft, and 3 = heavy aircraft.The asymmetric nature of MST results in the feasibility and necessity of runway scheduling. Proper scheduling strategies can save a lot of landing time. For example in Figure1, the makespan of sequence 1 equals 288 s; however, for sequence 2, the makespan is only 129 s, which saves more than 50% time.Figure 1
Two ordering methods result in different makespan for the same three aircraft.


#### 2.1.2. Time-Window Constraints

Time-window is a hard constraint to insure that aircraft lands between its earliest and latest possible landing time, which is in the interval time set[
e
i
,
l
i
]. The earliest possible landing time (e
i) depends on the constraints such as maximum airspeed to speed up, runway availability, and possible manoeuvres, while the latest possible landing time (l
i) depends on the fuel limitation, maximum allowed delay, minimum airspeed, and so on [13]. Actually, it is not necessary that the time-window for an aircraft is only one that continues interval set [19]. Though we only discuss the single-interval case in this paper, our approach is also applicable to handle the situation that time-window constraints are disjoint intervals.


#### 2.1.3. Precedence Constraints

Precedence constraints are pairwise requirements to insure whether one aircraft must land before another [19]. There are two reasons for these constraints. One is due to the airline company, which sometimes has strict restriction that one should land first for the reason of priority, banking operations, and so on. Another is due to the jet route, which does not allow two aircraft within the same jet route to overtake each other [20].


## 2.1. Aircraft Sequencing and Scheduling (ASS) Problem

ASS aims to make the most use of runway, that is, to minimize the makespan of the landing sequence so that to land as many aircraft as possible within a period of time. The objective function is(1)
min
⁡
W
π
=
x
π
end
,
where x
π
end is the landing time of the last aircraft in sequence π. For the ith aircraft in sequence π, its landing time is achieved by
(2)
x
π
i
=
max
⁡
e
π
i
,
current
time
,
if
i
=
1
;
max
⁡
x
π
i
-
1
≤
l
π
i
-
1
e
π
i
,
x
π
i
-
1
+
MS
T
TP
π
i
-
1
,
TP
π
i
,
if
1
<
i
≤
n
,
where e
k and l
k insure the time-window constraint and MST insures the minimum separation time constraint. These two constraints, as well as some other constraints, are described below. If x
π
i
-
1
≤
l
π
i
-
1 is not satisfied, x
π
i equals +
∞.


### 2.1.1. Minimum Separation Time (MST) Constraints

MST is a hard constraint to insure safety. When an aircraft flies in the air, it generates wake-vortex (WV). However, WV may result in the instability of the following aircraft (to shake or to lift) [19]. To avoid this, a MST is strictly kept between them.Table1 illustrates a typical MST table concerning three main types of aircraft. Generally, a smaller aircraft followed by a larger aircraft requires much shorter MST than the other way around. For example, a small aircraft has to wait for 196 s after the landing of a heavy aircraft. However, when a heavy aircraft lands after a small aircraft, the MST is only 60 s. One reason is that larger aircraft commonly generates and tolerates more turbulent air, while smaller aircraft generates and tolerates less.Table 1
MST (in sec.) between operations on the same runway [22].
Following
1
2
3
1
82
69
60
Leading
2
131
69
60
3
196
157
96
1 = small aircraft, 2 = large aircraft, and 3 = heavy aircraft.The asymmetric nature of MST results in the feasibility and necessity of runway scheduling. Proper scheduling strategies can save a lot of landing time. For example in Figure1, the makespan of sequence 1 equals 288 s; however, for sequence 2, the makespan is only 129 s, which saves more than 50% time.Figure 1
Two ordering methods result in different makespan for the same three aircraft.


### 2.1.2. Time-Window Constraints

Time-window is a hard constraint to insure that aircraft lands between its earliest and latest possible landing time, which is in the interval time set[
e
i
,
l
i
]. The earliest possible landing time (e
i) depends on the constraints such as maximum airspeed to speed up, runway availability, and possible manoeuvres, while the latest possible landing time (l
i) depends on the fuel limitation, maximum allowed delay, minimum airspeed, and so on [13]. Actually, it is not necessary that the time-window for an aircraft is only one that continues interval set [19]. Though we only discuss the single-interval case in this paper, our approach is also applicable to handle the situation that time-window constraints are disjoint intervals.


### 2.1.3. Precedence Constraints

Precedence constraints are pairwise requirements to insure whether one aircraft must land before another [19]. There are two reasons for these constraints. One is due to the airline company, which sometimes has strict restriction that one should land first for the reason of priority, banking operations, and so on. Another is due to the jet route, which does not allow two aircraft within the same jet route to overtake each other [20].


## 2.1.1. Minimum Separation Time (MST) Constraints

MST is a hard constraint to insure safety. When an aircraft flies in the air, it generates wake-vortex (WV). However, WV may result in the instability of the following aircraft (to shake or to lift) [19]. To avoid this, a MST is strictly kept between them.Table1 illustrates a typical MST table concerning three main types of aircraft. Generally, a smaller aircraft followed by a larger aircraft requires much shorter MST than the other way around. For example, a small aircraft has to wait for 196 s after the landing of a heavy aircraft. However, when a heavy aircraft lands after a small aircraft, the MST is only 60 s. One reason is that larger aircraft commonly generates and tolerates more turbulent air, while smaller aircraft generates and tolerates less.Table 1
MST (in sec.) between operations on the same runway [22].
Following
1
2
3
1
82
69
60
Leading
2
131
69
60
3
196
157
96
1 = small aircraft, 2 = large aircraft, and 3 = heavy aircraft.The asymmetric nature of MST results in the feasibility and necessity of runway scheduling. Proper scheduling strategies can save a lot of landing time. For example in Figure1, the makespan of sequence 1 equals 288 s; however, for sequence 2, the makespan is only 129 s, which saves more than 50% time.Figure 1
Two ordering methods result in different makespan for the same three aircraft.


## 2.1.2. Time-Window Constraints

Time-window is a hard constraint to insure that aircraft lands between its earliest and latest possible landing time, which is in the interval time set[
e
i
,
l
i
]. The earliest possible landing time (e
i) depends on the constraints such as maximum airspeed to speed up, runway availability, and possible manoeuvres, while the latest possible landing time (l
i) depends on the fuel limitation, maximum allowed delay, minimum airspeed, and so on [13]. Actually, it is not necessary that the time-window for an aircraft is only one that continues interval set [19]. Though we only discuss the single-interval case in this paper, our approach is also applicable to handle the situation that time-window constraints are disjoint intervals.


## 2.1.3. Precedence Constraints

Precedence constraints are pairwise requirements to insure whether one aircraft must land before another [19]. There are two reasons for these constraints. One is due to the airline company, which sometimes has strict restriction that one should land first for the reason of priority, banking operations, and so on. Another is due to the jet route, which does not allow two aircraft within the same jet route to overtake each other [20].


## 3. Approximation Algorithm for ASS

In this section, we design an approximation algorithm to solve ASS. The core idea is to find the lower bound solution of ASS. Then the approximation algorithm gives ASS solutions infinitely approaching this bound.


### 3.1. The Lower Bound Solution of ASS-MST

In the following we give the lower bound solution of ASS. This bound relates to a new generated MST (denoted byMST
′), which is an approximation of the actual MST. How to determine MST
′ is shown in L
P
1 (formulas (3)–(6)).The objective function (formula (3)) is to minimize the differences between MST and MST
′ since ΔMST measures their differences (formula (4)).Formula (5) calculates out MST
′. We decompose each element in MST
′ into two parts (see in Figure 2). One is the ability of the leading aircraft to generate the WV (denoted by α
r), and the other is the ability of the following aircraft to bear the disturbance (denoted by β
s).Figure 2
Decomposition of minimum separation time (MST
′).In formula (6), Δ
MS
T
r
s, α
r, and β
s are restricted nonnegative. Δ
MS
T
r
s
≥
0 insures that the elements in MST
′ are not bigger than the corresponding elements in MST, which insures Theorem 1.It is worthy to note that we do not restrictMS
T
r
s
′
≥
0, because it does not affect the result in Theorems 1, 2, and 4 from the perspective of mathematical calculation. In addition, it allows more elements in Δ
MS
T
r
s to be 0:
(3)
L
P
1
:
min
⁡
⁡
∑
r
=
1
m
∑
s
=
1
n
Δ
MS
T
r
s
,
subject to
(4)
MS
T
r
s
-
MS
T
r
s
′
=
Δ
MS
T
r
s
;
∀
r
,
s
∈
Λ
,
(5)
α
r
-
β
s
=
MS
T
r
s
′
;
∀
r
,
s
∈
Λ
,
(6)
Δ
MST
r
s
≥
0
,
α
r
≥
0
,
β
s
≥
0
;
∀
r
,
s
∈
Λ
.Theorem 1.
The makespan of each sequenceπ in ASS-MST′ is the lower bound of π in ASS-MST.Proof.
Referring to formulas (4) and (6), we have MS
T
r
s
-
MS
T
r
s
′
≥
0. So for any sequence π, MS
T
TP
(
π
i
-
1
)
,
TP
(
π
i
)
′
≤
MS
T
TP
(
π
i
-
1
)
,
TP
(
π
i
). It is easy to confirm that W
π
′
≤
W
π (see formulas (1) and (2)).Actually, this lower bound is very close to the optimal solution when the time-window constraint is not in consideration since its optimality only depends on the first and last aircraft in the sequence (Theorem2).Theorem 2.
The optimal solution of minimizing makespan for ASS-MST′ only depends on the first and the last aircraft in the final sequence, if the time-window constraint is not taken into consideration andα
r and β
r are given constant, ∀
r
∈
Λ.Proof.
For the landing sequence (π) with n aircraft, the MST
′ between aircraft π
i and π
i
+
1 is (
α
TP
(
π
i
)
-
β
TP
(
π
i
+
1
)
). So we have
(7)
W
π
′
=
∑
i
=
1
n
-
1
α
TP
π
i
-
β
TP
π
i
+
1
,
which is equivalent to
(8)
W
π
′
=
∑
i
=
1
n
α
TP
π
i
-
β
TP
π
i
+
β
TP
π
1
-
α
TP
π
n
.
In formula (8), ∑
i
=
1
n
‍
(
α
TP
(
π
i
)
-
β
TP
(
π
i
)
) is a constant number since the type of each aircraft in π is known. So the makespan (W
π
′) is determined by (
β
TP
(
π
1
)
-
α
TP
(
π
n
)
), which only concerns the first and last aircraft in π.Definition 3.
A sequence is calledstrongly hypo
o
p
t
i
m
a
l if and only if the change of the first and the last aircraft leads to its optimality.So any sequence in ASS-MST
′ is at least strongly hypooptimal (SHO). Figure 3 lists the relationship between ASS-MST curve and ASS-MST
′ curve when the time-window constraint is not in consideration. (
m
1
-
m
2
) is very small. We wish to minimize Δ
W
π which measures how a solution is close to SHO solution (the lower bound).Figure 3
Makespan of sequences in ASS-MST and ASS-MST
′.


### 3.2. Approximation Algorithm Approaches the Lower Bound

The approximation algorithm gives ASS solutions infinitely approaching the lower bound; that is, it attempts to find a sequenceπ with minimized Δ
W
π (see in Figure 3) since Δ
W
π measures how a solution is close to a SHO solution (the lower bound) when the time-window constraint is not in consideration (Δ
W
π is also a useful measure when considering time-window). The numerical result in Section 5 validates the statement and the efficiency of algorithm.


#### 3.2.1. Contain Time-Window with Aircraft Not Too Many

In ASS, each aircraft is associated with an estimated landing time (ELT), which is used to estimate the time when the aircraft lands. The ELT relates to the earliest and the latest landing time of the time-window. Generally, the earliest landing time (e
i) is one minute less than the ELT, because more than one-minute forward move is often not economical [20]. The latest landing time (l
i) can be 60 minutes after the ELT if aircraft have enough fuel and without any emergency accident.Based on the above discussion, the earliest landing timee
i is the main constraint in time-window, since the latest landing time is often inactive if the number of aircraft is not too many. So we firstly develop an algorithm for ASS without too many aircraft (often less than 30). And then we extend it to solve the case with many aircraft (often more than 30).The core idea is to infinitely approach the lower bound, that is, minimizing additional makespan when comparing ASS-MST and ASS-MST
′. The additional makespan consists of ΔMST and the earliest landing time (e
i). We give the approximation of the additional makespan.For the FSFC sequenceϜ, all aircraft with the same type are put together according to their order in Ϝ to construct subsequences. There are p subsequences, which are Ϝ
1
,
Ϝ
2
,
…
,
Ϝ
p, where TP
(
Ϝ
i
r
)
=
r, r
∈
Λ, and Ϝ
i
r is the ith aircraft in Ϝ
r.For example, a FCFS sequence is of types1,2
,
3,2
,
1,2
,
3,3, Λ
=
{
1,2
,
3
}. Then there are 3 subsequences. Ϝ
1 is constructed by the 1st and 5th aircraft in FCFS according to their order, Ϝ
2 is by the 2nd, 4th, and 6th aircraft, and Ϝ
3 is by the 3rd, 7th, and 8th aircraft. The complete algorithm consists of the following 3 steps to determine the final landing sequence Π.Step 1.
Determine the first aircraft ofΠ. Find the smallest Δ
w
r in formula (9) and transfer the aircraft Ϝ
1
r to the first position in Π; delete Ϝ
1
r from subsequence Ϝ
r. Then set i
∶
=
2:
(9)
Δ
w
r
=
e
Ϝ
1
r
,
r
=
r
*
e
Ϝ
1
r
+
Δ
MS
T
TP
r
,
TP
r
*
,
otherwise
,
where r
*
=
min
⁡
{
s
:
s
∈
Λ
,
Ϝ
s
≠
⌀
}.Step 2.
Determine theith aircraft of Π. Find the aircraft Ϝ
1
r with the smallest Δ
w
r in formula (10). Transfer it to the ith position in Π and delete it from subsequence Ϝ
r. Then set i
∶
=
i
+
1:
(10)
Δ
w
r
=
Δ
MS
T
TP
Π
i
-
1
,
r
+
g
i
,
r
,
r
=
r
*
Δ
MS
T
TP
Π
i
-
1
,
r
+
g
i
,
r
+
Δ
MS
T
r
,
r
*
,
otherwise
,
where g
(
i
,
r
)
=
max
⁡
{
0
,
e
Ϝ
1
r
-
(
x
Π
i
-
1
+
MS
T
TP
(
Π
i
-
1
)
,
r
)
} and r
*
=
min
⁡
{
s
:
s
∈
Λ
,
Ϝ
s
≠
⌀
}.Step 3.
Terminal criteria: if all aircraft in subsequences (Ϝ
r, r
∈
Λ) are transferred into Π, return sequence Π; otherwise, go to Step 2.Theorem 4.
The complexity of the approximation algorithm to generate the final sequence withn aircraft and p aircraft types is O
(
p
n
).Proof.
Step2 costs O
(
p
) to find the smallest Δ
w
r. Since there are n aircraft, Step 2 repeats for n times. So the complexity is O
(
p
n
).


#### 3.2.2. Contain Time-Window with Many Aircraft

If the number of aircraft is too large (often more than 30), the “inactive” assumption of the latest landing time is often broken, since some aircraft may be assigned to land 1 hour later. To avoid this, we firstly reschedule the first 30 aircraft (from the 1st to the 30th) in FCFS by the above algorithm and then reschedule the next 30 aircraft (from the 31st to the 60th) and then the next 30 aircraft (from the 61st to the 90th) and go on until all aircraft have been considered. In the end, we connect all the rescheduled sequences one by one to construct the ultimate sequence. Here the length of 30 aircraft is based on the numerical result in Section5. Of course we can set other lengths for subrescheduling but without such a good solution. These whole processes do not exceed the complexity of Theorem 4.


#### 3.2.3. Contain Precedence

To consider the precedence, we may freeze the subsequence. For example, aircrafti in subsequence Ϝ
s should land before aircraft j in Ϝ
r; we can freeze subsequence Ϝ
r when j is in the first position of Ϝ
r. The only sufficient condition to unfreeze Ϝ
r is that aircraft i has been transferred into the final sequence Π.


## 3.1. The Lower Bound Solution of ASS-MST

In the following we give the lower bound solution of ASS. This bound relates to a new generated MST (denoted byMST
′), which is an approximation of the actual MST. How to determine MST
′ is shown in L
P
1 (formulas (3)–(6)).The objective function (formula (3)) is to minimize the differences between MST and MST
′ since ΔMST measures their differences (formula (4)).Formula (5) calculates out MST
′. We decompose each element in MST
′ into two parts (see in Figure 2). One is the ability of the leading aircraft to generate the WV (denoted by α
r), and the other is the ability of the following aircraft to bear the disturbance (denoted by β
s).Figure 2
Decomposition of minimum separation time (MST
′).In formula (6), Δ
MS
T
r
s, α
r, and β
s are restricted nonnegative. Δ
MS
T
r
s
≥
0 insures that the elements in MST
′ are not bigger than the corresponding elements in MST, which insures Theorem 1.It is worthy to note that we do not restrictMS
T
r
s
′
≥
0, because it does not affect the result in Theorems 1, 2, and 4 from the perspective of mathematical calculation. In addition, it allows more elements in Δ
MS
T
r
s to be 0:
(3)
L
P
1
:
min
⁡
⁡
∑
r
=
1
m
∑
s
=
1
n
Δ
MS
T
r
s
,
subject to
(4)
MS
T
r
s
-
MS
T
r
s
′
=
Δ
MS
T
r
s
;
∀
r
,
s
∈
Λ
,
(5)
α
r
-
β
s
=
MS
T
r
s
′
;
∀
r
,
s
∈
Λ
,
(6)
Δ
MST
r
s
≥
0
,
α
r
≥
0
,
β
s
≥
0
;
∀
r
,
s
∈
Λ
.Theorem 1.
The makespan of each sequenceπ in ASS-MST′ is the lower bound of π in ASS-MST.Proof.
Referring to formulas (4) and (6), we have MS
T
r
s
-
MS
T
r
s
′
≥
0. So for any sequence π, MS
T
TP
(
π
i
-
1
)
,
TP
(
π
i
)
′
≤
MS
T
TP
(
π
i
-
1
)
,
TP
(
π
i
). It is easy to confirm that W
π
′
≤
W
π (see formulas (1) and (2)).Actually, this lower bound is very close to the optimal solution when the time-window constraint is not in consideration since its optimality only depends on the first and last aircraft in the sequence (Theorem2).Theorem 2.
The optimal solution of minimizing makespan for ASS-MST′ only depends on the first and the last aircraft in the final sequence, if the time-window constraint is not taken into consideration andα
r and β
r are given constant, ∀
r
∈
Λ.Proof.
For the landing sequence (π) with n aircraft, the MST
′ between aircraft π
i and π
i
+
1 is (
α
TP
(
π
i
)
-
β
TP
(
π
i
+
1
)
). So we have
(7)
W
π
′
=
∑
i
=
1
n
-
1
α
TP
π
i
-
β
TP
π
i
+
1
,
which is equivalent to
(8)
W
π
′
=
∑
i
=
1
n
α
TP
π
i
-
β
TP
π
i
+
β
TP
π
1
-
α
TP
π
n
.
In formula (8), ∑
i
=
1
n
‍
(
α
TP
(
π
i
)
-
β
TP
(
π
i
)
) is a constant number since the type of each aircraft in π is known. So the makespan (W
π
′) is determined by (
β
TP
(
π
1
)
-
α
TP
(
π
n
)
), which only concerns the first and last aircraft in π.Definition 3.
A sequence is calledstrongly hypo
o
p
t
i
m
a
l if and only if the change of the first and the last aircraft leads to its optimality.So any sequence in ASS-MST
′ is at least strongly hypooptimal (SHO). Figure 3 lists the relationship between ASS-MST curve and ASS-MST
′ curve when the time-window constraint is not in consideration. (
m
1
-
m
2
) is very small. We wish to minimize Δ
W
π which measures how a solution is close to SHO solution (the lower bound).Figure 3
Makespan of sequences in ASS-MST and ASS-MST
′.


## 3.2. Approximation Algorithm Approaches the Lower Bound

The approximation algorithm gives ASS solutions infinitely approaching the lower bound; that is, it attempts to find a sequenceπ with minimized Δ
W
π (see in Figure 3) since Δ
W
π measures how a solution is close to a SHO solution (the lower bound) when the time-window constraint is not in consideration (Δ
W
π is also a useful measure when considering time-window). The numerical result in Section 5 validates the statement and the efficiency of algorithm.


### 3.2.1. Contain Time-Window with Aircraft Not Too Many

In ASS, each aircraft is associated with an estimated landing time (ELT), which is used to estimate the time when the aircraft lands. The ELT relates to the earliest and the latest landing time of the time-window. Generally, the earliest landing time (e
i) is one minute less than the ELT, because more than one-minute forward move is often not economical [20]. The latest landing time (l
i) can be 60 minutes after the ELT if aircraft have enough fuel and without any emergency accident.Based on the above discussion, the earliest landing timee
i is the main constraint in time-window, since the latest landing time is often inactive if the number of aircraft is not too many. So we firstly develop an algorithm for ASS without too many aircraft (often less than 30). And then we extend it to solve the case with many aircraft (often more than 30).The core idea is to infinitely approach the lower bound, that is, minimizing additional makespan when comparing ASS-MST and ASS-MST
′. The additional makespan consists of ΔMST and the earliest landing time (e
i). We give the approximation of the additional makespan.For the FSFC sequenceϜ, all aircraft with the same type are put together according to their order in Ϝ to construct subsequences. There are p subsequences, which are Ϝ
1
,
Ϝ
2
,
…
,
Ϝ
p, where TP
(
Ϝ
i
r
)
=
r, r
∈
Λ, and Ϝ
i
r is the ith aircraft in Ϝ
r.For example, a FCFS sequence is of types1,2
,
3,2
,
1,2
,
3,3, Λ
=
{
1,2
,
3
}. Then there are 3 subsequences. Ϝ
1 is constructed by the 1st and 5th aircraft in FCFS according to their order, Ϝ
2 is by the 2nd, 4th, and 6th aircraft, and Ϝ
3 is by the 3rd, 7th, and 8th aircraft. The complete algorithm consists of the following 3 steps to determine the final landing sequence Π.Step 1.
Determine the first aircraft ofΠ. Find the smallest Δ
w
r in formula (9) and transfer the aircraft Ϝ
1
r to the first position in Π; delete Ϝ
1
r from subsequence Ϝ
r. Then set i
∶
=
2:
(9)
Δ
w
r
=
e
Ϝ
1
r
,
r
=
r
*
e
Ϝ
1
r
+
Δ
MS
T
TP
r
,
TP
r
*
,
otherwise
,
where r
*
=
min
⁡
{
s
:
s
∈
Λ
,
Ϝ
s
≠
⌀
}.Step 2.
Determine theith aircraft of Π. Find the aircraft Ϝ
1
r with the smallest Δ
w
r in formula (10). Transfer it to the ith position in Π and delete it from subsequence Ϝ
r. Then set i
∶
=
i
+
1:
(10)
Δ
w
r
=
Δ
MS
T
TP
Π
i
-
1
,
r
+
g
i
,
r
,
r
=
r
*
Δ
MS
T
TP
Π
i
-
1
,
r
+
g
i
,
r
+
Δ
MS
T
r
,
r
*
,
otherwise
,
where g
(
i
,
r
)
=
max
⁡
{
0
,
e
Ϝ
1
r
-
(
x
Π
i
-
1
+
MS
T
TP
(
Π
i
-
1
)
,
r
)
} and r
*
=
min
⁡
{
s
:
s
∈
Λ
,
Ϝ
s
≠
⌀
}.Step 3.
Terminal criteria: if all aircraft in subsequences (Ϝ
r, r
∈
Λ) are transferred into Π, return sequence Π; otherwise, go to Step 2.Theorem 4.
The complexity of the approximation algorithm to generate the final sequence withn aircraft and p aircraft types is O
(
p
n
).Proof.
Step2 costs O
(
p
) to find the smallest Δ
w
r. Since there are n aircraft, Step 2 repeats for n times. So the complexity is O
(
p
n
).


### 3.2.2. Contain Time-Window with Many Aircraft

If the number of aircraft is too large (often more than 30), the “inactive” assumption of the latest landing time is often broken, since some aircraft may be assigned to land 1 hour later. To avoid this, we firstly reschedule the first 30 aircraft (from the 1st to the 30th) in FCFS by the above algorithm and then reschedule the next 30 aircraft (from the 31st to the 60th) and then the next 30 aircraft (from the 61st to the 90th) and go on until all aircraft have been considered. In the end, we connect all the rescheduled sequences one by one to construct the ultimate sequence. Here the length of 30 aircraft is based on the numerical result in Section5. Of course we can set other lengths for subrescheduling but without such a good solution. These whole processes do not exceed the complexity of Theorem 4.


### 3.2.3. Contain Precedence

To consider the precedence, we may freeze the subsequence. For example, aircrafti in subsequence Ϝ
s should land before aircraft j in Ϝ
r; we can freeze subsequence Ϝ
r when j is in the first position of Ϝ
r. The only sufficient condition to unfreeze Ϝ
r is that aircraft i has been transferred into the final sequence Π.


## 3.2.1. Contain Time-Window with Aircraft Not Too Many

In ASS, each aircraft is associated with an estimated landing time (ELT), which is used to estimate the time when the aircraft lands. The ELT relates to the earliest and the latest landing time of the time-window. Generally, the earliest landing time (e
i) is one minute less than the ELT, because more than one-minute forward move is often not economical [20]. The latest landing time (l
i) can be 60 minutes after the ELT if aircraft have enough fuel and without any emergency accident.Based on the above discussion, the earliest landing timee
i is the main constraint in time-window, since the latest landing time is often inactive if the number of aircraft is not too many. So we firstly develop an algorithm for ASS without too many aircraft (often less than 30). And then we extend it to solve the case with many aircraft (often more than 30).The core idea is to infinitely approach the lower bound, that is, minimizing additional makespan when comparing ASS-MST and ASS-MST
′. The additional makespan consists of ΔMST and the earliest landing time (e
i). We give the approximation of the additional makespan.For the FSFC sequenceϜ, all aircraft with the same type are put together according to their order in Ϝ to construct subsequences. There are p subsequences, which are Ϝ
1
,
Ϝ
2
,
…
,
Ϝ
p, where TP
(
Ϝ
i
r
)
=
r, r
∈
Λ, and Ϝ
i
r is the ith aircraft in Ϝ
r.For example, a FCFS sequence is of types1,2
,
3,2
,
1,2
,
3,3, Λ
=
{
1,2
,
3
}. Then there are 3 subsequences. Ϝ
1 is constructed by the 1st and 5th aircraft in FCFS according to their order, Ϝ
2 is by the 2nd, 4th, and 6th aircraft, and Ϝ
3 is by the 3rd, 7th, and 8th aircraft. The complete algorithm consists of the following 3 steps to determine the final landing sequence Π.Step 1.
Determine the first aircraft ofΠ. Find the smallest Δ
w
r in formula (9) and transfer the aircraft Ϝ
1
r to the first position in Π; delete Ϝ
1
r from subsequence Ϝ
r. Then set i
∶
=
2:
(9)
Δ
w
r
=
e
Ϝ
1
r
,
r
=
r
*
e
Ϝ
1
r
+
Δ
MS
T
TP
r
,
TP
r
*
,
otherwise
,
where r
*
=
min
⁡
{
s
:
s
∈
Λ
,
Ϝ
s
≠
⌀
}.Step 2.
Determine theith aircraft of Π. Find the aircraft Ϝ
1
r with the smallest Δ
w
r in formula (10). Transfer it to the ith position in Π and delete it from subsequence Ϝ
r. Then set i
∶
=
i
+
1:
(10)
Δ
w
r
=
Δ
MS
T
TP
Π
i
-
1
,
r
+
g
i
,
r
,
r
=
r
*
Δ
MS
T
TP
Π
i
-
1
,
r
+
g
i
,
r
+
Δ
MS
T
r
,
r
*
,
otherwise
,
where g
(
i
,
r
)
=
max
⁡
{
0
,
e
Ϝ
1
r
-
(
x
Π
i
-
1
+
MS
T
TP
(
Π
i
-
1
)
,
r
)
} and r
*
=
min
⁡
{
s
:
s
∈
Λ
,
Ϝ
s
≠
⌀
}.Step 3.
Terminal criteria: if all aircraft in subsequences (Ϝ
r, r
∈
Λ) are transferred into Π, return sequence Π; otherwise, go to Step 2.Theorem 4.
The complexity of the approximation algorithm to generate the final sequence withn aircraft and p aircraft types is O
(
p
n
).Proof.
Step2 costs O
(
p
) to find the smallest Δ
w
r. Since there are n aircraft, Step 2 repeats for n times. So the complexity is O
(
p
n
).


## 3.2.2. Contain Time-Window with Many Aircraft

If the number of aircraft is too large (often more than 30), the “inactive” assumption of the latest landing time is often broken, since some aircraft may be assigned to land 1 hour later. To avoid this, we firstly reschedule the first 30 aircraft (from the 1st to the 30th) in FCFS by the above algorithm and then reschedule the next 30 aircraft (from the 31st to the 60th) and then the next 30 aircraft (from the 61st to the 90th) and go on until all aircraft have been considered. In the end, we connect all the rescheduled sequences one by one to construct the ultimate sequence. Here the length of 30 aircraft is based on the numerical result in Section5. Of course we can set other lengths for subrescheduling but without such a good solution. These whole processes do not exceed the complexity of Theorem 4.


## 3.2.3. Contain Precedence

To consider the precedence, we may freeze the subsequence. For example, aircrafti in subsequence Ϝ
s should land before aircraft j in Ϝ
r; we can freeze subsequence Ϝ
r when j is in the first position of Ϝ
r. The only sufficient condition to unfreeze Ϝ
r is that aircraft i has been transferred into the final sequence Π.


## 4. Ant Colony and MIP for ASS

### 4.1. Ant Colony (AC) for ASS

Ant colony (AC) algorithm is an intensively studied method [13]. Many papers adopt it for single-runway scheduling [9, 10, 14]. Here AC is used to find a solution for ASS, which is a valid comparison with the approximation algorithm. The following are some important settings of AC in the computation.


#### 4.1.1. State Transition Check

All aircraft are labeled according to their positions in the FCFS. After finishing visiting an aircrafti, all ants choose the next allowable aircraft j to visit. To make sure most routes returned by ants satisfy the time-window constraints, we restrict the allowable aircraft to the integer set {
max
⁡
{
1
,
i
-
k
}
,
…
,
min
⁡
{
n
,
i
+
k
}
} when an ant does its ith visit. This principle is also called k-CPS [19].Under this principle, an aircrafti should be visited before an ant does its (
i
+
k
+
1
)th visit. So if aircraft i has not been visited when an ant does its (
i
+
k
)th visit, it is forced to be visited by this ant. In the numerical study here, setting the integer number k
=
5 is good to satisfy time-window.


#### 4.1.2. State Transition Rule

After finishing visiting an aircrafti, all ants choose the next allowable aircraft j according to the probability of Pb
(
i
,
j
):
(11)
Pb
i
,
j
=
τ
i
,
j
a
η
i
,
j
b
∑
u
∈
allowe
d
i
τ
i
,
u
a
η
i
,
u
b
,
if
j
∈
allowe
d
i
0
,
otherwise
.


#### 4.1.3. Pheromone Updating Rule

The pheromone updating operation is carried out on each arc in the completed tour as in formulas (12) and (13) for each ant:
(12)
τ
i
j
t
+
1
=
1
-
γ
τ
i
j
t
+
Δ
τ
i
j
,
where (
1
-
γ
)
τ
i
j
(
t
) models the evaporation of the pheromone and Δ
τ
i
j is the lately released pheromone by ants. For an ant u, Δ
τ
i
j
u is defined as
(13)
Δ
τ
i
j
u
=
Q
W
u
,
if
arc
i
,
j
is
visited
by
ant
u
0
,
otherwise
,
where Q is a given constant and W
u is makespan of tour route by ant u.


### 4.2. Mixed Integer Programming (MIP) for ASS

In 2000, Beasley et al. [5] proposed a MIP for the single-runway scheduling problem. Here we extend it to ASS as a solution comparison of the approximation algorithm. The following are some important settings.The objective function (formula (14)) is to minimize the makespan. W
≥
x
i (formula (18)) insures W is the landing time of the last aircraft.In formula (15), δ
i
j is a 0-1 variable. δ
i
j
=
1 (aircraft i lands before j) and δ
i
j
=
0 (i after j). δ
i
j and δ
j
i must not equal 0 (or 1) at the same time. δ
i
j
+
δ
j
i
=
1 ensures this requirement.Formula (16) is the separation constraint. There are two cases.(a)
δ
j
i
=
0. Then x
j
≥
x
i
+
MS
T
TP
(
i
)
,
TP
(
j
), which ensures a time separation.
(b)
δ
j
i
=
1. Then x
j
≥
x
i
+
MS
T
TP
(
i
)
,
TP
(
j
)
-
M, which is effectively inactive if M is large enough.Formula (17) insures the time-window constraint:
(14)
MI
P
1
:
min
⁡
⁡
W
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
(15)
s
.
t
.
δ
i
j
+
δ
j
i
=
1
;
∀
i
,
j
∈
U
h
h
h
(16)
x
j
-
x
i
≥
MS
T
TP
i
,
TP
j
-
δ
j
i
·
M
;
hhhhhhhhhhhhhhhh
∀
i
,
j
∈
U
h
h
(17)
e
i
≤
x
i
≤
l
i
;
i
=
1,2
,
…
,
n
h
h
h
h
h
h
(18)
W
≥
x
i
;
∀
i
=
1,2
,
…
,
n
h
h
h
h
h
h
h
(19)
h
h
h
h
h
h
h
h
x
i
≥
0
,
W
≥
0
,
δ
i
j
=
0,1
;
∀
i
,
j
∈
U
.We use CPLEX Optimization Studio 12.5 to solveMI
P
1, and the traditional Branch and Bound (B&B) search function in CPLEX is used. From the point of view of the LP relaxation, M (in formula (16)) is wished to be as small as possible. Because large M leads (
MS
T
TP
(
i
)
,
TP
(
j
)
-
δ
j
i
·
M
) to be much smaller than MS
T
TP
(
i
)
,
TP
(
j
) even if δ
j
i is very small, the small M is achieved by replacing it with (
l
i
+
MS
T
TP
(
i
)
,
TP
(
j
)
-
e
j
) [5].


## 4.1. Ant Colony (AC) for ASS

Ant colony (AC) algorithm is an intensively studied method [13]. Many papers adopt it for single-runway scheduling [9, 10, 14]. Here AC is used to find a solution for ASS, which is a valid comparison with the approximation algorithm. The following are some important settings of AC in the computation.


### 4.1.1. State Transition Check

All aircraft are labeled according to their positions in the FCFS. After finishing visiting an aircrafti, all ants choose the next allowable aircraft j to visit. To make sure most routes returned by ants satisfy the time-window constraints, we restrict the allowable aircraft to the integer set {
max
⁡
{
1
,
i
-
k
}
,
…
,
min
⁡
{
n
,
i
+
k
}
} when an ant does its ith visit. This principle is also called k-CPS [19].Under this principle, an aircrafti should be visited before an ant does its (
i
+
k
+
1
)th visit. So if aircraft i has not been visited when an ant does its (
i
+
k
)th visit, it is forced to be visited by this ant. In the numerical study here, setting the integer number k
=
5 is good to satisfy time-window.


### 4.1.2. State Transition Rule

After finishing visiting an aircrafti, all ants choose the next allowable aircraft j according to the probability of Pb
(
i
,
j
):
(11)
Pb
i
,
j
=
τ
i
,
j
a
η
i
,
j
b
∑
u
∈
allowe
d
i
τ
i
,
u
a
η
i
,
u
b
,
if
j
∈
allowe
d
i
0
,
otherwise
.


### 4.1.3. Pheromone Updating Rule

The pheromone updating operation is carried out on each arc in the completed tour as in formulas (12) and (13) for each ant:
(12)
τ
i
j
t
+
1
=
1
-
γ
τ
i
j
t
+
Δ
τ
i
j
,
where (
1
-
γ
)
τ
i
j
(
t
) models the evaporation of the pheromone and Δ
τ
i
j is the lately released pheromone by ants. For an ant u, Δ
τ
i
j
u is defined as
(13)
Δ
τ
i
j
u
=
Q
W
u
,
if
arc
i
,
j
is
visited
by
ant
u
0
,
otherwise
,
where Q is a given constant and W
u is makespan of tour route by ant u.


## 4.1.1. State Transition Check

All aircraft are labeled according to their positions in the FCFS. After finishing visiting an aircrafti, all ants choose the next allowable aircraft j to visit. To make sure most routes returned by ants satisfy the time-window constraints, we restrict the allowable aircraft to the integer set {
max
⁡
{
1
,
i
-
k
}
,
…
,
min
⁡
{
n
,
i
+
k
}
} when an ant does its ith visit. This principle is also called k-CPS [19].Under this principle, an aircrafti should be visited before an ant does its (
i
+
k
+
1
)th visit. So if aircraft i has not been visited when an ant does its (
i
+
k
)th visit, it is forced to be visited by this ant. In the numerical study here, setting the integer number k
=
5 is good to satisfy time-window.


## 4.1.2. State Transition Rule

After finishing visiting an aircrafti, all ants choose the next allowable aircraft j according to the probability of Pb
(
i
,
j
):
(11)
Pb
i
,
j
=
τ
i
,
j
a
η
i
,
j
b
∑
u
∈
allowe
d
i
τ
i
,
u
a
η
i
,
u
b
,
if
j
∈
allowe
d
i
0
,
otherwise
.


## 4.1.3. Pheromone Updating Rule

The pheromone updating operation is carried out on each arc in the completed tour as in formulas (12) and (13) for each ant:
(12)
τ
i
j
t
+
1
=
1
-
γ
τ
i
j
t
+
Δ
τ
i
j
,
where (
1
-
γ
)
τ
i
j
(
t
) models the evaporation of the pheromone and Δ
τ
i
j is the lately released pheromone by ants. For an ant u, Δ
τ
i
j
u is defined as
(13)
Δ
τ
i
j
u
=
Q
W
u
,
if
arc
i
,
j
is
visited
by
ant
u
0
,
otherwise
,
where Q is a given constant and W
u is makespan of tour route by ant u.


## 4.2. Mixed Integer Programming (MIP) for ASS

In 2000, Beasley et al. [5] proposed a MIP for the single-runway scheduling problem. Here we extend it to ASS as a solution comparison of the approximation algorithm. The following are some important settings.The objective function (formula (14)) is to minimize the makespan. W
≥
x
i (formula (18)) insures W is the landing time of the last aircraft.In formula (15), δ
i
j is a 0-1 variable. δ
i
j
=
1 (aircraft i lands before j) and δ
i
j
=
0 (i after j). δ
i
j and δ
j
i must not equal 0 (or 1) at the same time. δ
i
j
+
δ
j
i
=
1 ensures this requirement.Formula (16) is the separation constraint. There are two cases.(a)
δ
j
i
=
0. Then x
j
≥
x
i
+
MS
T
TP
(
i
)
,
TP
(
j
), which ensures a time separation.
(b)
δ
j
i
=
1. Then x
j
≥
x
i
+
MS
T
TP
(
i
)
,
TP
(
j
)
-
M, which is effectively inactive if M is large enough.Formula (17) insures the time-window constraint:
(14)
MI
P
1
:
min
⁡
⁡
W
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
(15)
s
.
t
.
δ
i
j
+
δ
j
i
=
1
;
∀
i
,
j
∈
U
h
h
h
(16)
x
j
-
x
i
≥
MS
T
TP
i
,
TP
j
-
δ
j
i
·
M
;
hhhhhhhhhhhhhhhh
∀
i
,
j
∈
U
h
h
(17)
e
i
≤
x
i
≤
l
i
;
i
=
1,2
,
…
,
n
h
h
h
h
h
h
(18)
W
≥
x
i
;
∀
i
=
1,2
,
…
,
n
h
h
h
h
h
h
h
(19)
h
h
h
h
h
h
h
h
x
i
≥
0
,
W
≥
0
,
δ
i
j
=
0,1
;
∀
i
,
j
∈
U
.We use CPLEX Optimization Studio 12.5 to solveMI
P
1, and the traditional Branch and Bound (B&B) search function in CPLEX is used. From the point of view of the LP relaxation, M (in formula (16)) is wished to be as small as possible. Because large M leads (
MS
T
TP
(
i
)
,
TP
(
j
)
-
δ
j
i
·
M
) to be much smaller than MS
T
TP
(
i
)
,
TP
(
j
) even if δ
j
i is very small, the small M is achieved by replacing it with (
l
i
+
MS
T
TP
(
i
)
,
TP
(
j
)
-
e
j
) [5].


## 5. Numerical Study of Three Methods

Here is the numerical result of the approximation algorithm for ASS. The AC and CPLEX are used as a valid comparison of this new algorithm.


### 5.1. Randomly Generate the MST

In ASS, the concerning MST is important. Table1 gives a typical MST table by a classical aircraft types classification. However, there are some other MST tables by other classifying principles. For example, Table 2 illustrates another MST table with more than 3 aircraft types. We believe that our algorithm applies almost all possible MST matrixes. So in the numerical study we randomly generate MST matrixes which have two common properties.Table 2
MST (in sec.) between operations on the same runway [6].
Following
1
2
3
4
Leading
1
90
80
70
72
2
110
80
70
72
3
130
100
70
72
3
228
200
181
96
1 = Mc Donnel Douglas DC9, 2 = Boeing 727, 3 = Boeing 707, and 4 = Boeing 747.For MST matrixes withp aircraft types, their general properties are summarized as follows.(1)
Larger aircraft landing before the same aircraft needs more (at least equal) separation; that is,MS
T
r
,
s
≥
MS
T
r
-
1
,
s, r
=
2,3
,
…
,
p; s
=
1,2
,
…
,
p.
(2)
Larger aircraft landing after the same aircraft needs less (at least equal) separation; that is,MS
T
r
,
s
≥
MS
T
r
,
s
+
1, r
=
1,2
,
…
,
p; s
=
1,2
,
…
,
(
p
-
1
).In numerical study, MST can be generated by(20)
MS
T
r
s
=
k
r
s
MS
T
r
,
s
+
1
,
if
r
=
1
;
s
=
1,2
,
…
,
p
-
1
k
r
s
MS
T
r
-
1
,
s
,
if
r
=
2,3
,
·
·
·
,
p
;
s
=
p
k
r
s
·
max
⁡
MS
T
r
,
s
+
1
,
MS
T
r
-
1
,
s
,
otherwise
,
where MS
T
1
p is a given number and k
r
s
(
≥
1
) is a random number. In the following numerical study, if p
≤
4, k
r
s is in the interval of [
1,2
] satisfying uniform distribution; if p
>
4, k
r
s is in [
1,1
+
1
/
(
p
-
3
)
] satisfying uniform distribution. This setting insures MST
p
1 is not too much bigger than MST
1
p. It is in accord with the actual MST; for example, Tables 1 and 2 are basically satisfied.It is worthy to note that even if a MST does not strictly satisfy the above settings, it can also be well coped with by the approximation algorithm.


### 5.2. Numerical Result

We test the cases ofp
=
3 and p
=
9. In each case, ten groups (aircraft number n
=
20,40,60
,
…
,
200) of aircraft sequences are randomly generated. Each group contains 20 random sequences; the number of all types of aircraft is the same in each sequence. The MST is randomly generated for each sequence (see detailed setting and its parameters explanation in formula (20)).The estimated landing time (ELT) of aircraft is simulated by a Poisson arrival process, which has been validated by Willemain et al. [21]. The expectation of interval time between neighbor aircraft in ELT is set to be 4
/
5
E
(
MST
), where E
(
MST
) is the mean value of all elements in MST. It models how crowded an airport is. The earliest landing time is set to be one minute less than the ELT, because more than a minute forward move is often not economical [20]. The latest possible landing time is set 60 minutes after the earliest landing time.For approximation algorithm, long aircraft sequences (with more than 30 aircraft) are scheduled each time for 30 aircraft (see the explanation in Section3.2.2). For AC algorithm, the termination criteria are the maximal generations of 100. The parameters in formulas (11)–(13) are set as a
=
1, b
=
5, γ
=
0.1, and Q
=
100. The allowable aircraft are restricted in set {
max
⁡
{
1
,
i
-
5
}
,
…
,
min
⁡
{
n
,
i
+
5
}
} when an ant does its ith visit. For MIP, the traditional B&B search in CPLEX is used and the maximal tree nodes of B&B search are set to be 4000. The numerical result is shown in Table 3 with average runtime and average runway enhancement of the tested 20 sequences in each group. For each sequence, the “runway enhancement” is achieved by W
FCFS
-
W
Π
/
W
FCFS
×
100
%. It is comparison of the makespan between the final sequence Π and the FSFC sequence since FCFS is a widely used method in current runway scheduling system.Table 3
WVM, AC, and MIP to minimize makespan in ASS whenp = 3, 9.
Aircraft  types
Number of aircraft
AC
CPLEX
Approx. algo.
Time
Runway
Time
Runway
Time
Runway
(sec.)
enhancement
(sec.)
enhancement
(sec.)
enhancement
p
=
3
20
4.9
1.34%
0.2
4.07%
0.003
4.60%
30
7.7
3.04%
0.2
4.77%
0.002
6.21%
40
10.5
1.63%
0.4
2.58%
0.003
4.39%
60
16.4
2.93%
0.7
2.70%
0.004
5.09%
80
22.0
1.87%
0.9
1.51%
0.006
4.18%
100
27.8
2.94%
1.2
1.80%
0.007
3.39%
120
33.6
3.68%
1.9
1.59%
0.008
3.81%
140
39.1
2.47%
2.2
1.40%
0.010
3.13%
160
45.2
2.38%
2.1
0.87%
0.011
4.55%
180
51.1
2.05%
2.9
1.16%
0.012
3.69%
200
57.5
2.38%
3.7
1.23%
0.014
2.67%
p
=
9
20
4.9
1.69%
0.2
3.82%
0.004
2.81%
30
7.7
1.32%
0.3
2.35%
0.003
2.64%
40
10.5
2.06%
0.4
1.98%
0.004
4.15%
60
16.2
1.07%
0.6
0.98%
0.006
2.41%
80
22.0
1.17%
1.0
0.74%
0.007
2.63%
100
27.8
1.28%
1.3
0.82%
0.009
1.28%
120
33.7
1.21%
1.9
0.48%
0.011
1.08%
140
39.4
1.36%
2.6
0.84%
0.012
1.04%
160
45.5
1.79%
2.9
0.55%
0.015
1.00%
180
51.9
1.55%
3.1
0.90%
0.020
0.80%
200
57.8
0.99%
3.5
0.68%
0.018
1.09%
Bold characters mark the maximum runway enhancement by these methods.When there are fewer aircraft types (3 types), the approximation algorithm enhances the runway throughput more than AC and CPLEX and costs less time. It validates the performance of the algorithm. Actually classifying the aircraft into 3 types is often enough. If there are too many aircraft types, we can classify the aircraft into several big categories and reconstruct the MST table concerning the big categories other than the aircraft types—each big category contains aircraft types with very close properties. So the ASS in this condition can also be well coped with by the approximation algorithm.When there are 9 aircraft types, the approximation algorithm generally has higher runway enhancement when the number of aircraft is not too many (<100 aircraft). For too many aircraft (100–200 aircraft), AC enhances the runway throughput more. However, the approximation algorithm costs less time than the other two methods.By comparing AC and MIP, we find that MIP (by CPLEX) has better performance when both the number of aircraft types and aircraft are small. For a large number of aircraft (or many aircraft types), it is better to use AC for scheduling other than CPLEX. It is also worthy to note that the approximation algorithm has better performance than CPLEX in almost all the enumerated cases in Table3.


## 5.1. Randomly Generate the MST

In ASS, the concerning MST is important. Table1 gives a typical MST table by a classical aircraft types classification. However, there are some other MST tables by other classifying principles. For example, Table 2 illustrates another MST table with more than 3 aircraft types. We believe that our algorithm applies almost all possible MST matrixes. So in the numerical study we randomly generate MST matrixes which have two common properties.Table 2
MST (in sec.) between operations on the same runway [6].
Following
1
2
3
4
Leading
1
90
80
70
72
2
110
80
70
72
3
130
100
70
72
3
228
200
181
96
1 = Mc Donnel Douglas DC9, 2 = Boeing 727, 3 = Boeing 707, and 4 = Boeing 747.For MST matrixes withp aircraft types, their general properties are summarized as follows.(1)
Larger aircraft landing before the same aircraft needs more (at least equal) separation; that is,MS
T
r
,
s
≥
MS
T
r
-
1
,
s, r
=
2,3
,
…
,
p; s
=
1,2
,
…
,
p.
(2)
Larger aircraft landing after the same aircraft needs less (at least equal) separation; that is,MS
T
r
,
s
≥
MS
T
r
,
s
+
1, r
=
1,2
,
…
,
p; s
=
1,2
,
…
,
(
p
-
1
).In numerical study, MST can be generated by(20)
MS
T
r
s
=
k
r
s
MS
T
r
,
s
+
1
,
if
r
=
1
;
s
=
1,2
,
…
,
p
-
1
k
r
s
MS
T
r
-
1
,
s
,
if
r
=
2,3
,
·
·
·
,
p
;
s
=
p
k
r
s
·
max
⁡
MS
T
r
,
s
+
1
,
MS
T
r
-
1
,
s
,
otherwise
,
where MS
T
1
p is a given number and k
r
s
(
≥
1
) is a random number. In the following numerical study, if p
≤
4, k
r
s is in the interval of [
1,2
] satisfying uniform distribution; if p
>
4, k
r
s is in [
1,1
+
1
/
(
p
-
3
)
] satisfying uniform distribution. This setting insures MST
p
1 is not too much bigger than MST
1
p. It is in accord with the actual MST; for example, Tables 1 and 2 are basically satisfied.It is worthy to note that even if a MST does not strictly satisfy the above settings, it can also be well coped with by the approximation algorithm.


## 5.2. Numerical Result

We test the cases ofp
=
3 and p
=
9. In each case, ten groups (aircraft number n
=
20,40,60
,
…
,
200) of aircraft sequences are randomly generated. Each group contains 20 random sequences; the number of all types of aircraft is the same in each sequence. The MST is randomly generated for each sequence (see detailed setting and its parameters explanation in formula (20)).The estimated landing time (ELT) of aircraft is simulated by a Poisson arrival process, which has been validated by Willemain et al. [21]. The expectation of interval time between neighbor aircraft in ELT is set to be 4
/
5
E
(
MST
), where E
(
MST
) is the mean value of all elements in MST. It models how crowded an airport is. The earliest landing time is set to be one minute less than the ELT, because more than a minute forward move is often not economical [20]. The latest possible landing time is set 60 minutes after the earliest landing time.For approximation algorithm, long aircraft sequences (with more than 30 aircraft) are scheduled each time for 30 aircraft (see the explanation in Section3.2.2). For AC algorithm, the termination criteria are the maximal generations of 100. The parameters in formulas (11)–(13) are set as a
=
1, b
=
5, γ
=
0.1, and Q
=
100. The allowable aircraft are restricted in set {
max
⁡
{
1
,
i
-
5
}
,
…
,
min
⁡
{
n
,
i
+
5
}
} when an ant does its ith visit. For MIP, the traditional B&B search in CPLEX is used and the maximal tree nodes of B&B search are set to be 4000. The numerical result is shown in Table 3 with average runtime and average runway enhancement of the tested 20 sequences in each group. For each sequence, the “runway enhancement” is achieved by W
FCFS
-
W
Π
/
W
FCFS
×
100
%. It is comparison of the makespan between the final sequence Π and the FSFC sequence since FCFS is a widely used method in current runway scheduling system.Table 3
WVM, AC, and MIP to minimize makespan in ASS whenp = 3, 9.
Aircraft  types
Number of aircraft
AC
CPLEX
Approx. algo.
Time
Runway
Time
Runway
Time
Runway
(sec.)
enhancement
(sec.)
enhancement
(sec.)
enhancement
p
=
3
20
4.9
1.34%
0.2
4.07%
0.003
4.60%
30
7.7
3.04%
0.2
4.77%
0.002
6.21%
40
10.5
1.63%
0.4
2.58%
0.003
4.39%
60
16.4
2.93%
0.7
2.70%
0.004
5.09%
80
22.0
1.87%
0.9
1.51%
0.006
4.18%
100
27.8
2.94%
1.2
1.80%
0.007
3.39%
120
33.6
3.68%
1.9
1.59%
0.008
3.81%
140
39.1
2.47%
2.2
1.40%
0.010
3.13%
160
45.2
2.38%
2.1
0.87%
0.011
4.55%
180
51.1
2.05%
2.9
1.16%
0.012
3.69%
200
57.5
2.38%
3.7
1.23%
0.014
2.67%
p
=
9
20
4.9
1.69%
0.2
3.82%
0.004
2.81%
30
7.7
1.32%
0.3
2.35%
0.003
2.64%
40
10.5
2.06%
0.4
1.98%
0.004
4.15%
60
16.2
1.07%
0.6
0.98%
0.006
2.41%
80
22.0
1.17%
1.0
0.74%
0.007
2.63%
100
27.8
1.28%
1.3
0.82%
0.009
1.28%
120
33.7
1.21%
1.9
0.48%
0.011
1.08%
140
39.4
1.36%
2.6
0.84%
0.012
1.04%
160
45.5
1.79%
2.9
0.55%
0.015
1.00%
180
51.9
1.55%
3.1
0.90%
0.020
0.80%
200
57.8
0.99%
3.5
0.68%
0.018
1.09%
Bold characters mark the maximum runway enhancement by these methods.When there are fewer aircraft types (3 types), the approximation algorithm enhances the runway throughput more than AC and CPLEX and costs less time. It validates the performance of the algorithm. Actually classifying the aircraft into 3 types is often enough. If there are too many aircraft types, we can classify the aircraft into several big categories and reconstruct the MST table concerning the big categories other than the aircraft types—each big category contains aircraft types with very close properties. So the ASS in this condition can also be well coped with by the approximation algorithm.When there are 9 aircraft types, the approximation algorithm generally has higher runway enhancement when the number of aircraft is not too many (<100 aircraft). For too many aircraft (100–200 aircraft), AC enhances the runway throughput more. However, the approximation algorithm costs less time than the other two methods.By comparing AC and MIP, we find that MIP (by CPLEX) has better performance when both the number of aircraft types and aircraft are small. For a large number of aircraft (or many aircraft types), it is better to use AC for scheduling other than CPLEX. It is also worthy to note that the approximation algorithm has better performance than CPLEX in almost all the enumerated cases in Table3.


## 6. Conclusions

To cope with aircraft sequencing and scheduling (ASS) problem, we design an approximation algorithm, which is infinitely approaching the lower bound of the optimal solution. Numerical result validates that this algorithm, with less runtime, can get a smaller makespan than AC and CPLEX, especially when the number of aircraft types is not too many. This is a big increase of the runway.



---

*Source: 236756-2014-12-31.xml*