# Strategic Deconfliction of 4D Trajectory and Perturbation Analysis for Air Traffic Control and Automation System

Authors: Xinmin Tang; Yu Zhang; Ping Chen; Bo Li; Songchen Han
Journal: Discrete Dynamics in Nature and Society
 (2016)

---

## Abstract

Strategic 4D trajectory conflict-free planning is recognized as one of the core technologies of next-generation air traffic control and automation systems. To resolve potential conflicts during strategic 4D conflict-free trajectory planning, a protection-zone conflict-control model based on air traffic control separation constraints was proposed, in which relationships between expected arrival time and adjusted arrival time at conflicting waypoints for aircraft queues were built and transformed into dynamic linear equations under the definition of max-plus algebra. A method for strategic deconfliction of 4D trajectory was then proposed using two strategies: arrival time adjustment and departure time adjustment. In addition, departure time and flight duration perturbations were introduced to analyze the sensitivity of the planned strategic conflict-free 4D trajectories, and a robustness index for the conflict-free 4D trajectories was calculated. Finally, the proposed method was tested for the Shanghai air traffic control terminal area. The outcomes demonstrated that the planned strategic conflict-free 4D trajectories could avoid potential conflicts, and the slack time could be used to indicate their robustness. Complexity analysis demonstrated that deconfliction using max-plus algebra is more suitable for deconfliction of 4D trajectory with random sampling period in fix air route.


---

## Body

## 1. Introduction

With the rapid development of global aviation transportation, the contention between supply and demand for limited airspace resources has become increasingly prominent. Therefore, Europe and the United States have implemented next-generation air traffic management systems, called Single European Sky ATM Research (SESAR) and Next-Generation Air Transportation System (NextGen), respectively [1, 2], both with the objective of improving ATC service quality. Obviously, strategic conflict-free 4D trajectory planning under conditions of high-density traffic flow and small separation is one of the main problems that needs to be addressed by next-generation air traffic control and automation systems [3, 4].Trajectory planning can be divided into two categories according to planning phases: tactical trajectory planning and strategic trajectory planning. The former focuses on a 10–30 min look-ahead time window for aircraft. In this phase, individual aircraft departure slots are provided, and reroutings and flight profiles can also be issued in order to avoid bottlenecks and to maximize airspace capacity according to real-time traffic demand [5]. Tactical trajectory planning can be fulfilled by prescribed method, force-field method, and optimized method [6]. The prescribed method determines the aircraft maneuvers among a predefined set of procedures [7, 8], and the planned trajectory is too conservative. The force field method computes aircraft maneuvers based on a modified electrostatic equation [9], and the planned trajectory is not always smooth. The optimized method combines a kinematic model with a set of cost metrics, and the planned trajectory is optimized with the lowest cost. For example, the Center-TRACON Automation System (CTAS) developed by NASA’s Ames Research Center predicted long-range (20 minutes) and short-range (5 minutes) conflicts and offered resolution for such conflicts by using the degrees of freedom of the aircraft while meeting the scheduled times of arrival; the degrees of freedom considered in the resolution included speed, altitude, and routing [10]. In contrast, for the latter case, it focuses on at least one day look-ahead time window for aircraft before flight, and its primary aims are to optimize the overall ATM network performance, minimizing delays and costs. Chen et al. conducted automatic detection of flight plans according to flight separation to detect potential conflicts from the flight plans and then adjusted them to meet separation requirements [11]. In addition, Wu et al. presented a conflict-detection model to detect conflicts that violated lateral separation when trajectories crossed in the flight plan [12]. To resolve potential conflicts occurring between any two intersecting trajectories, Barnier and Allignol proposed a departure-time adjustment strategy and optimization method based on constraint programming. To compute the model constraints, the trajectories were pairwise probed for couples of conflicting waypoints. Hence, it was difficult to use the method to solve large-scale problems in large airspaces [13, 14]. Barnier et al. studied the possible complexity reduction achievable by optimizing aircraft take-off times and employed an evolutionary computation algorithm to minimize the mean delay among the aircraft population [15]. Han et al. presented a method of conflict-free 4D trajectory planning for aircraft by adjusting aircraft departure schedules and speed plans [16]. Chaimatanan et al. proposed a methodology to minimize the number of potential conflicts between aircraft trajectories via route-departure slot allocation strategy at the strategic level. In their research, two metaheuristic optimization approaches were implemented: standard Simulated Annealing (SA) algorithm and hybrid optimization method [17]. Cafieri and Durand proposed new mixed-integer nonlinear programming (MINLP) formulations for deconfliction based on speed regulation, where conflicts were avoided by allowing aircraft to accelerate or decelerate and minimizing the time intervals during which aircraft flies with a modified speed. The proposed heuristic procedure can be used to solve medium-scale problems [18].To improve the robustness of the conflict-free 4D trajectories generated, Dupuy and Porretta stated that the uncertainty associated with the resulting prediction depended on aircraft intent, navigation data, aircraft performance, and meteorological factors and then proposed a trajectory prediction model considering these factors [19]. Meyn presented a method for perturbing air traffic scenarios and analyzing the resulting conflicts. The perturbations consisted of a specified range of spatial and temporal trajectory modifications, and the analysis identified all possible conflicts within the perturbation range [20]. Ruiz et al. presented a strategic deconfliction algorithm based on causal modeling approach to explore the emergent dynamics between the resolution trial trajectories, which was employed to find solutions to respond to network and trajectory-level perturbations [21]. Generally, it has proven necessary to propose a systematic strategic conflict-free 4D trajectory planning method for large-scale airspace and to evaluate the robustness.To resolve potential conflicts during strategic 4D conflict-free trajectory planning while reducing computational complexity and avoid pairwise probing for couples of conflicting waypoints in large airspaces, a protection-zone conflict-control model has been proposed in this paper to plan strategic conflict-free 4D trajectories and analyze their robustness using linear dynamic equations under the definition of max-plus algebra. This approach has been demonstrated to be more suitable for deconfliction of 4D trajectory with random sampling period in fix air route.The remainder of this paper is organized as follows. In Section2, the development of a protection-zone conflict-control model based on air traffic control separation constraints is described. In Section 3, the relationships between expected arrival time and adjusted arrival time at the conflicting waypoint for an aircraft queue were built according to air traffic control separation constraints, which were transformed into dynamic linear equations under the definition of max-plus algebra. In Section 4, the conflict-free 4D trajectory adjusting method is proposed using two strategies: arrival-time adjustment and departure-time adjustment. In Section 5, an index is proposed to evaluate the robustness of strategic conflict-free 4D trajectories. In Section 6, a simulated case of the Shanghai air traffic control terminal area is presented to demonstrate the effectiveness of strategic deconfliction and perturbation analysis of 4D trajectories. In addition, the computational complexities of deconfliction are compared. Finally, conclusions are drawn and future research directions are suggested.


## 2. Air Traffic Discrete-Event Dynamic System Model

### 2.1. Constraint-Free State Transition Model

According to the nominal flight profile model, a whole flight can be divided into multiple segments, and the flight duration in each segment is determined by the aircraft airspeed plan. Thus, the constraint-free state transition model can be depicted by a subclass of Petri nets, and for the notion of Petri nets, one can refer to [22].Definition 1 (constraint-free state transition model).
A constraint-free state transition model is defined as a time-event graphG
=
(
P
G
,
T
G
,
I
G
,
O
G
,
M
G
,
Γ
), where the place set P
G denotes airway segments, the transition set T
G denotes waypoints between two airway segments, the input function I
G
:
P
G
×
T
G
→
N and the output function O
G
:
T
G
×
P
G
→
N represent forward and backward connecting relationships between airway segments and waypoints, respectively, ∀
p
∈
P, |
p
•
|
=
|
p
•
|
=
1, M
G
:
P
G
→
N is marking function, representing the distribution of aircraft in the segments, and Γ
:
P
G
→
R
+ represents the flight duration in segments.
The constraint-free state transition model for an aircraft queue is shown in Figure1, where P
G
=
{
p
1
,
p
2
,
p
3
}, which means there are 3 segments in the airway: T
G
=
{
t
1
,
t
2
,
t
3
}, which means there are 3 waypoints; for input function, I
G
(
p
1
,
t
2
)
=
1, I
G
(
p
2
,
t
3
)
=
1, which means segments p
1 and p
2 are ended by waypoints t
2 and t
3, respectively; for output function, O
G
(
t
1
,
p
1
)
=
1, O
G
(
t
2
,
p
2
)
=
1, O
G
(
t
3
,
p
3
)
=
1, which means segments p
1, p
2, and p
3 are started by waypoints t
1, t
2, and t
3, respectively, for marking M
G
(
p
1
)
=
1, M
G
(
p
2
)
=
1, and M
G
(
p
3
)
=
0, which means there are two aircraft in the segments p
1 and p
2, respectively.
It is assumed that the expected arrival times at waypointt
1 for aircraft queue F
=
{
a
(
1
)
,
a
(
2
)
,
…
,
a
(
K
)
} are input, denoted as U
=
[
u
(
1
)
,
u
(
2
)
,
…
,
u
(
K
)
], the flight durations from waypoint t
i to t
i
+
1 for aircraft queue F, that is, the sojourning times in places p
i are D
i
=
[
τ
i
(
1
)
,
τ
i
(
2
)
,
…
,
τ
i
(
K
)
]
,
i
=
1
,
…
,
n, and the time vector when place p
i is marked is denoted as X
i
=
[
x
i
(
1
)
,
x
i
(
2
)
,
…
,
x
i
(
K
)
]
,
i
=
1
,
…
,
n.
Thus, the state of constraint-free state transition model can be calculated as(1)
x
1
k
=
u
k
x
i
k
=
x
i
-
1
k
+
τ
i
-
1
k
,
k
=
1,2
,
…
,
K
,
i
=
2
,
…
,
n
.
Hence, the arrival times at the last waypointt
n for aircraft queue F are output and denoted as Y
=
[
y
(
1
)
,
y
(
2
)
,
…
,
y
(
K
)
], which can be calculated as(2)
y
k
=
x
n
k
,
k
=
1,2
,
…
,
K
.Figure 1
Constraint-free state transition model.


### 2.2. Horizontal Conflicting Protection Zone

Dowek and Munoz and Rey et al. identify three types of pairwise conflicts from the horizontal and vertical view, respectively [23, 24], combining which 7 possible pairwise conflicts are illustrated in Figure 2, including horizontal following, horizontal opposing, and vertical crossing conflicts occuring between aircrafts from the same route or crossing routes, where the Cartesian coordinate system is defined as follows: choosing the conflicting waypoint O as the origin, setting magnetic north on pressure level at waypoint O as y-axis, setting magnetic east on pressure level at waypoint O as x-axis, and setting normal direction of pressure level at waypoint O as z-axis.Figure 2
Possible types of conflicts.
(a)
Vertical crossing conflict between aircrafts from the same route
(b)
Vertical crossing conflict between aircrafts from the same route
(c)
Horizontal following conflict between aircrafts from the same route
(d)
Horizontal opposite conflict between aircrafts from the same route
(e)
Vertical crossing conflict between aircrafts from crossing routes
(f)
Horizontal crossing conflict from crossing routes
(g)
Horizontal converging conflict between aircrafts from crossing routesAs shown in Figures2(a) and 2(b), let v
1 and v
2 represent level flight speed and vertical crossing speed, respectively, and let γ denote the vertical crossing angle. Then, the speed component v
2
·
cos
⁡
γ denotes the horizontal following or opposing speed, which means that vertical crossing conflict from the same route can be treated as horizontal following or horizontal opposing conflicts, as shown in Figures 2(c) and 2(d) using vertical projection.Similarly, as shown in Figure2(e), the speed components v
1
·
cos
⁡
γ
1 and v
2
·
cos
⁡
γ
2 denote the horizontal crossing speeds from crossing routes, which means that vertical crossing conflict from crossing routes can be treated as horizontal crossing conflict using vertical projection, as shown in Figure 2(f), where α denotes the entering angle and β denotes the leaving angle.In particular, for the horizontal crossing conflict shown in Figure2(f), when α
=
0 and β
=
0, it is transformed into the horizontal following conflict shown in Figure 2(c), and when α
=
π and β
=
π, it is transformed into the horizontal opposing conflict shown in Figure 2(d). When α
≠
0 and β
=
0, it is transformed into the converging conflict shown in Figure 2(g).Therefore, vertical crossing, horizontal following, horizontal opposing, and horizontal converging conflicts can be treated as special cases of horizontal crossing conflict and can be unified under the definition of horizontal crossing conflict. To avoid potential conflicts described above and ensure separation between two aircrafts, the idea of a conflicting protection zone is introduced.Assume that aircrafts are allowed to fly only on fixed air routes to reduce the computational complexity of strategic deconfliction of 4D trajectory, different from the traditional protection zone based on elliptic cylinder, as shown in Figure3(a), whose semimajor axis is a
=
d
m
i
n
(
1
)
/
2, where d
m
i
n
(
1
) denotes the minimum longitudinal separation, the semiminor axis is b
=
d
m
i
n
(
2
)
/
2, where d
m
i
n
(
2
) denotes the minimum lateral separation, and the height is h
=
d
m
i
n
(
3
), where d
m
i
n
(
3
) denotes the minimum vertical separation. For tactical trajectory planning, the conflict waypoints are dynamic and should be detected in real time, and the center of protection zone based on elliptic cylinder is the position of one aircraft, which may cause the motion of protection zone as the aircraft track evolves along the 4D trajectory for its time dimension and increase the computational complexity of conflict detection and resolution. While the potential conflict waypoints for strategic 4D trajectories of different aircraft can be determined in advance. As a result, we can fix the center of protection zone at the potential conflict waypoints, which reduce the computational complexity of conflict detection and resolution, which can be illustrated in computational complexity analysis section. As analyzed above, vertical crossing conflict can be treated as horizontal following or horizontal opposing conflicts using vertical projection, as shown in Figure 3(b). If the dimension of horizontal protection zone meets given requirements, it can be proven that all the separation can be satisfied in combination with the conflict-control strategy.Figure 3
Two different protection zones.
(a)
Traditional protection zone based on elliptic cylinder
(b)
Horizontal projection of traditional protection zone
(c)
Protection zone based on horizontal trianglesThe protection zone based on horizontal triangles is proposed in this study. As shown in Figure3(c), triangles A
O
B, C
O
D, I
O
J, and K
O
L are horizontal protection zones, where the top vertex is a conflicting crossing, following, and converging waypoint, and the lengths of the two sides are considered to meet three types of minimal separation requirements in combination with the conflict-control strategy: (1) the distance between aircraft entering segments A
O and B
O, as well as the distance between aircraft leaving segments O
C and O
D, should meet the minimum lateral separation requirement; (2) the distance between aircraft entering segment A
O and aircraft leaving O
C, as well as the distance between the aircraft entering B
O and leaving O
D, should meet the minimum longitudinal separation requirement; and (3) the distance between aircraft entering segment A
O and aircraft leaving O
D, as well as the distance between the aircraft entering B
O and leaving O
C, should meet the minimum lateral separation requirement.According to the horizontal crossing angles of two crossing routes, the protection zones based on horizontal triangles can be classified into three categories. Figure4 shows type I horizontal crossing protection zone, where δ
≥
π
/
2 and θ
≥
π
/
2, Figure 5 shows type II horizontal crossing protection zone, where δ
≥
π
/
2 and θ
<
π
/
2, or δ
<
π
/
2 and θ
≥
π
/
2, and Figure 6 shows type III horizontal crossing protection zone, where δ
<
π
/
2 and θ
<
π
/
2.Figure 4
Type I horizontal crossing protection zone.Figure 5
Type II horizontal crossing protection zone.Figure 6
Type III horizontal crossing protection zone.If the lengths of the two sides for protection zones are set as follows, all the above constraints can be satisfied in combination with the conflict-control strategy proposed in next section.(3)
d
A
O
=
d
B
O
=
d
m
i
n
1
,
α
=
0
max
⁡
d
m
i
n
1
,
d
m
i
n
2
·
sec
⁡
α
,
0
<
α
<
π
2
max
⁡
d
m
i
n
1
,
d
m
i
n
2
,
α
≥
π
2
d
O
C
=
d
O
D
=
d
m
i
n
1
,
β
=
0
max
⁡
d
m
i
n
1
,
d
m
i
n
2
·
sec
⁡
β
,
0
<
β
<
π
2
max
⁡
d
m
i
n
1
,
d
m
i
n
2
,
β
≥
π
2
d
O
I
=
d
O
J
=
d
m
i
n
2
·
sec
⁡
δ
/
2
2
,
0
<
δ
≥
π
2
max
⁡
d
m
i
n
2
·
sec
⁡
δ
/
2
2
,
d
m
i
n
2
,
δ
≥
π
2
d
O
K
=
d
O
L
=
d
m
i
n
2
·
sec
⁡
θ
/
2
2
,
0
<
θ
<
π
2
max
⁡
d
m
i
n
2
·
sec
⁡
θ
/
2
2
,
d
m
i
n
2
,
θ
≥
π
2
.For simplicity, the constraint-free state transition model of types I, II, and III horizontal crossing protection zones can be described as the same Petri net, as shown Figure7, where each place or transition has three captions that represent the place or transition for type I, type II, and type III constraint-free state transition model, respectively.Figure 7
Constraint-free state transition model of types I, II, and III horizontal crossing protection zone.


### 2.3. Conflicting Protection Zone Control Model

To meet three types of minimal separation requirements mentioned above, the controlled Petri nets with external enabling conditions called control places should be introduced firstly [23].Definition 2 (protection-zone conflict-control model).
A protection-zone conflict-control model is defined as a controlled free-choice Petri netsC
P
N
=
(
P
,
T
,
I
,
O
,
M
,
Γ
)
=
(
G
1
,
G
2
,
P
C
,
I
C
,
O
C
,
M
C
), where G
1 and G
2 represent two related constraint-free state transition models that share the same transition. The place set P
C denotes conflict-control places. The input function I
C
:
P
C
×
T
G
→
N and the output function O
C
:
P
C
×
T
G
→
N represent forward and backward connecting relationships between control places and controlled transitions, respectively. M
C
:
P
C
→
N represents the markings of the conflict-control places.
The type I protection-zone conflict-control modelC
P
N
1 for G
A
O
C and G
B
O
D shown in Figure 7 can be described by the Petri nets shown in Figure 8, where places p
C
(
i
) (1
≤
i
≤
6) denote the conflict-control place, whose initial markings M
C
0
(
p
C
(
i
)
)
=
1 ensure that protection zones A
O
B, C
O
D, I
O
J, K
O
L, A
O
C, and B
O
D can accommodate at most one aircraft each, that is, M
(
p
A
O
)
+
M
(
p
B
O
)
≤
1 and M
(
p
O
C
)
+
M
(
p
O
D
)
≤
1, which ensure the separation requirement (1); M
(
p
A
O
)
+
M
(
p
O
C
)
≤
1 and M
(
p
B
O
)
+
M
(
p
O
D
)
≤
1, which ensure the separation requirement (2); M
(
p
I
O
)
+
M
(
p
O
J
)
≤
1 an M
(
p
K
O
)
+
M
(
p
O
L
)
≤
1, which ensure the separation requirement (3). For the purpose of clarity, the observation places are neglected.
Suppose that the expected arrival time at waypointO of aircraft a
(
k
j
), that is, the k
jth aircraft of aircraft queue in constraint-free state transition model G
j, is u
O
(
k
j
), j
=
1,2 before deconfliction; the moment when conflict-control place p
C
(
i
)
,
i
=
1
,
…
,
6, is marked is denoted by x
C
(
i
)
(
k
j
)
,
j
=
1,2; and the sojourning times in place p
A
I
,
p
I
O
,
…
,
p
J
D for aircraft a
(
k
j
) are τ
A
I
(
k
j
)
,
τ
I
O
(
k
j
)
,
…
,
τ
J
D
(
k
j
), respectively.
Ifu
O
(
k
1
)
≤
u
O
(
k
2
), aircraft a
(
k
1
) is assigned priority to enter protection zones. Hence, the state equation can be expressed as(4)
x
C
1
k
1
=
max
⁡
x
C
5
k
1
-
1
+
τ
A
O
,
s
e
l
x
C
1
k
1
-
1
,
x
C
1
k
2
-
1
+
τ
A
O
,
s
e
l
x
C
3
k
1
-
1
,
x
C
3
k
2
-
1
+
τ
I
O
,
s
e
l
x
C
4
k
1
-
1
,
x
C
4
k
2
-
1
,
s
e
l
x
C
2
k
1
-
1
,
x
C
2
k
2
-
1
,
u
O
k
1
x
C
2
k
1
=
x
C
1
k
1
+
τ
O
C
x
C
3
k
1
=
x
C
1
k
1
x
C
4
k
1
=
x
C
1
k
1
+
τ
O
L
x
C
5
k
1
=
x
C
1
k
1
+
τ
O
C
,where “s
e
l” is a selection operator, which is defined as follows:(5)
s
e
l
x
C
i
k
1
-
1
,
x
C
i
k
2
-
1
=
x
C
i
k
1
-
1
,
u
O
k
1
-
1
≥
u
O
k
2
-
1
x
C
i
k
2
-
1
,
u
O
k
1
-
1
<
u
O
k
2
-
1
,
i
=
1,2
,
…
,
5
.
Else, ifu
O
(
k
2
)
<
u
O
(
k
1
), aircraft a
(
k
2
) is assigned priority to enter protection zones. Hence, the state equation can be expressed as follows:(6)
x
C
1
k
2
=
max
⁡
x
C
6
k
2
-
1
+
τ
B
O
,
s
e
l
x
C
1
k
2
-
1
,
x
C
1
k
1
-
1
+
τ
B
O
,
s
e
l
x
C
4
k
2
-
1
,
x
C
4
k
1
-
1
+
τ
K
O
,
s
e
l
x
C
3
k
2
-
1
,
x
C
3
k
1
-
1
,
s
e
l
x
C
2
k
2
-
1
,
x
C
2
k
1
-
1
,
u
O
k
2
x
C
2
k
2
=
x
C
1
k
2
+
τ
O
D
x
C
3
k
2
=
x
C
1
k
2
+
τ
O
J
x
C
4
k
2
=
x
C
1
k
2
x
C
6
k
2
=
x
C
1
k
2
+
τ
O
D
,where the selection operator “s
e
l” is defined as follows:(7)
s
e
l
x
C
i
k
2
-
1
,
x
C
i
k
1
-
1
=
x
C
i
k
2
-
1
,
u
O
k
2
-
1
≥
u
O
k
1
-
1
x
C
i
k
1
-
1
,
u
O
k
2
-
1
<
u
O
k
1
-
1
,
i
=
1,2
,
…
,
5
.
The strategic conflict-free 4D trajectories for aircraft queuesF
1 and F
2, that is, the adjusted arrival time at waypoint O after deconfliction, can be expressed as(8)
y
O
k
1
=
x
C
1
k
1
,
if
u
O
k
1
≤
u
O
k
2
y
O
k
2
=
x
C
1
k
2
,
if
u
O
k
1
>
u
O
k
2
.
The type II protection-zone conflict-control modelC
P
N
2 for G
A
O
C and G
K
O
D shown in Figure 7 can be described by the Petri nets shown in Figure 9, where places p
C
(
i
) (1
≤
i
≤
6) denote the conflict-control place, whose initial markings M
C
0
(
p
C
(
i
)
)
=
1 ensure that protection zones A
O
K, C
O
D, I
O
J, K
O
L, A
O
C, and B
O
D can accommodate at most one aircraft each; that is, M
(
p
A
O
)
+
M
(
p
K
O
)
≤
1 and M
(
p
O
C
)
+
M
(
p
O
D
)
≤
1, which ensure the separation requirement (1); M
(
p
A
O
)
+
M
(
p
O
C
)
≤
1 and M
(
p
B
O
)
+
M
(
p
O
D
)
≤
1, which ensure the separation requirement (2); M
(
p
I
O
)
+
M
(
p
O
J
)
≤
1 and M
(
p
K
O
)
+
M
(
p
O
L
)
≤
1, which ensure the separation requirement (3). For the purpose of clarity, the observation places are neglected.
Suppose that the expected arrival time at waypointO of aircraft a
(
k
j
), that is, the k
jth aircraft of aircraft queue in constraint-free state transition model G
j, is u
O
(
k
j
), j
=
1,2 before deconfliction; the moment when conflict-control place p
C
(
i
)
,
i
=
1
,
…
,
6, is marked is denoted by x
C
(
i
)
(
k
j
), j
=
1,2; and the sojourning times in places p
A
I
,
p
I
O
,
…
,
p
J
D for aircraft a
(
k
j
) are τ
A
I
(
k
j
)
,
τ
I
O
(
k
j
)
,
…
,
τ
J
D
(
k
j
), respectively.
Ifu
O
(
k
1
)
≤
u
O
(
k
2
), aircraft a
(
k
1
) is assigned priority to enter protection zones. Hence, the state equation can be expressed as (4); else if u
O
(
k
2
)
<
u
O
(
k
1
), aircraft a
(
k
2
) is assigned priority to enter protection zones. Hence, the state equation can be expressed as(9)
x
C
1
k
2
=
max
⁡
x
C
6
k
2
-
1
+
τ
B
O
,
s
e
l
x
C
1
k
2
-
1
,
x
C
1
k
1
-
1
+
τ
K
O
,
s
e
l
x
C
4
k
2
-
1
,
x
C
4
k
1
-
1
+
τ
K
O
,
s
e
l
x
C
3
k
2
-
1
,
x
C
3
k
1
-
1
,
s
e
l
x
C
2
k
2
-
1
,
x
C
2
k
1
-
1
,
u
O
k
2
x
C
2
k
2
=
x
C
1
k
2
+
τ
O
D
x
C
3
k
2
=
x
C
1
k
2
+
τ
O
J
x
C
4
k
2
=
x
C
1
k
2
x
C
6
k
2
=
x
C
1
k
2
+
τ
O
D
,where the selection operator “s
e
l” is defined the same as (7).
The strategic conflict-free 4D trajectories for aircraft queuesF
1 and F
2 in protection-zone conflict-control model, that is, the adjusted arrival time at waypoint O after deconfliction, can be expressed as (8).
The type III protection-zone conflict-control modelC
P
N
3 for G
I
O
L and G
K
O
J shown in Figure 7 can be described by the Petri nets shown in Figure 10, where places p
C
(
i
) (1
≤
i
≤
6) denote the conflict-control place, whose initial markings M
C
0
(
p
C
(
i
)
)
=
1 ensure that protection zones I
O
K, C
O
D, I
O
J, K
O
L, A
O
C, and B
O
D can accommodate at most one aircraft each; that is, M
(
p
I
O
)
+
M
(
p
K
O
)
≤
1 and M
(
p
O
C
)
+
M
(
p
O
D
)
≤
1, which ensure the separation requirement (1); M
(
p
A
O
)
+
M
(
p
O
C
)
≤
1 and M
(
p
B
O
)
+
M
(
p
O
D
)
≤
1, which ensure the separation requirement (2); M
(
p
I
O
)
+
M
(
p
O
J
)
≤
1 and M
(
p
K
O
)
+
M
(
p
O
L
)
≤
1, which ensure the separation requirement (3). For the purpose of clarity, the observation places are neglected.
Suppose that the expected arrival time at waypointO of aircraft a
(
k
j
), that is, the k
jth aircraft of aircraft queue in constraint-free state transition model G
j, is u
O
(
k
j
), j
=
1,2 before deconfliction; the moment when conflict-control place p
C
(
i
)
,
i
=
1
,
…
,
6, is marked is denoted by x
C
(
i
)
(
k
j
), j
=
1,2; and the sojourning times in places p
I
A
,
p
I
O
,
…
,
p
D
J for aircraft a
(
k
j
) are τ
I
A
(
k
j
)
,
τ
I
O
(
k
j
)
,
…
,
τ
D
J
(
k
j
), respectively.
Ifu
O
(
k
1
)
≤
u
O
(
k
2
), aircraft a
(
k
1
) is assigned priority to enter protection zones. Hence, the state equation can be expressed as(10)
x
C
1
k
1
=
max
⁡
x
C
5
k
1
-
1
+
τ
A
O
,
s
e
l
x
C
1
k
1
-
1
,
x
C
1
k
2
-
1
+
τ
I
O
,
s
e
l
x
C
3
k
1
-
1
,
x
C
3
k
2
-
1
+
τ
I
O
,
s
e
l
x
C
4
k
1
-
1
,
x
C
4
k
2
-
1
,
s
e
l
x
C
2
k
1
-
1
,
x
C
2
k
2
-
1
,
u
O
k
1
x
C
2
k
1
=
x
C
1
k
1
+
τ
O
C
x
C
3
k
1
=
x
C
1
k
1
x
C
4
k
1
=
x
C
1
k
1
+
τ
O
L
x
C
5
k
1
=
x
C
1
k
1
+
τ
O
C
,where the selection operator “s
e
l” is defined the same as (7).
Else, ifu
O
(
k
2
)
<
u
O
(
k
1
), aircraft a
(
k
2
) is assigned priority to enter protection zones. Hence, the state transition equation can be expressed as (9).
The strategic conflict-free 4D trajectories for aircraft queuesF
1 and F
2 in protection-zone conflict-control model, that is, the adjusted arrival time at waypoint O after deconfliction, can be expressed as (8).Figure 8
Type I protection-zone conflict-control model.Figure 9
Type II protection-zone conflict-control model.Figure 10
Type III protection-zone conflict-control model.


## 2.1. Constraint-Free State Transition Model

According to the nominal flight profile model, a whole flight can be divided into multiple segments, and the flight duration in each segment is determined by the aircraft airspeed plan. Thus, the constraint-free state transition model can be depicted by a subclass of Petri nets, and for the notion of Petri nets, one can refer to [22].Definition 1 (constraint-free state transition model).
A constraint-free state transition model is defined as a time-event graphG
=
(
P
G
,
T
G
,
I
G
,
O
G
,
M
G
,
Γ
), where the place set P
G denotes airway segments, the transition set T
G denotes waypoints between two airway segments, the input function I
G
:
P
G
×
T
G
→
N and the output function O
G
:
T
G
×
P
G
→
N represent forward and backward connecting relationships between airway segments and waypoints, respectively, ∀
p
∈
P, |
p
•
|
=
|
p
•
|
=
1, M
G
:
P
G
→
N is marking function, representing the distribution of aircraft in the segments, and Γ
:
P
G
→
R
+ represents the flight duration in segments.
The constraint-free state transition model for an aircraft queue is shown in Figure1, where P
G
=
{
p
1
,
p
2
,
p
3
}, which means there are 3 segments in the airway: T
G
=
{
t
1
,
t
2
,
t
3
}, which means there are 3 waypoints; for input function, I
G
(
p
1
,
t
2
)
=
1, I
G
(
p
2
,
t
3
)
=
1, which means segments p
1 and p
2 are ended by waypoints t
2 and t
3, respectively; for output function, O
G
(
t
1
,
p
1
)
=
1, O
G
(
t
2
,
p
2
)
=
1, O
G
(
t
3
,
p
3
)
=
1, which means segments p
1, p
2, and p
3 are started by waypoints t
1, t
2, and t
3, respectively, for marking M
G
(
p
1
)
=
1, M
G
(
p
2
)
=
1, and M
G
(
p
3
)
=
0, which means there are two aircraft in the segments p
1 and p
2, respectively.
It is assumed that the expected arrival times at waypointt
1 for aircraft queue F
=
{
a
(
1
)
,
a
(
2
)
,
…
,
a
(
K
)
} are input, denoted as U
=
[
u
(
1
)
,
u
(
2
)
,
…
,
u
(
K
)
], the flight durations from waypoint t
i to t
i
+
1 for aircraft queue F, that is, the sojourning times in places p
i are D
i
=
[
τ
i
(
1
)
,
τ
i
(
2
)
,
…
,
τ
i
(
K
)
]
,
i
=
1
,
…
,
n, and the time vector when place p
i is marked is denoted as X
i
=
[
x
i
(
1
)
,
x
i
(
2
)
,
…
,
x
i
(
K
)
]
,
i
=
1
,
…
,
n.
Thus, the state of constraint-free state transition model can be calculated as(1)
x
1
k
=
u
k
x
i
k
=
x
i
-
1
k
+
τ
i
-
1
k
,
k
=
1,2
,
…
,
K
,
i
=
2
,
…
,
n
.
Hence, the arrival times at the last waypointt
n for aircraft queue F are output and denoted as Y
=
[
y
(
1
)
,
y
(
2
)
,
…
,
y
(
K
)
], which can be calculated as(2)
y
k
=
x
n
k
,
k
=
1,2
,
…
,
K
.Figure 1
Constraint-free state transition model.


## 2.2. Horizontal Conflicting Protection Zone

Dowek and Munoz and Rey et al. identify three types of pairwise conflicts from the horizontal and vertical view, respectively [23, 24], combining which 7 possible pairwise conflicts are illustrated in Figure 2, including horizontal following, horizontal opposing, and vertical crossing conflicts occuring between aircrafts from the same route or crossing routes, where the Cartesian coordinate system is defined as follows: choosing the conflicting waypoint O as the origin, setting magnetic north on pressure level at waypoint O as y-axis, setting magnetic east on pressure level at waypoint O as x-axis, and setting normal direction of pressure level at waypoint O as z-axis.Figure 2
Possible types of conflicts.
(a)
Vertical crossing conflict between aircrafts from the same route
(b)
Vertical crossing conflict between aircrafts from the same route
(c)
Horizontal following conflict between aircrafts from the same route
(d)
Horizontal opposite conflict between aircrafts from the same route
(e)
Vertical crossing conflict between aircrafts from crossing routes
(f)
Horizontal crossing conflict from crossing routes
(g)
Horizontal converging conflict between aircrafts from crossing routesAs shown in Figures2(a) and 2(b), let v
1 and v
2 represent level flight speed and vertical crossing speed, respectively, and let γ denote the vertical crossing angle. Then, the speed component v
2
·
cos
⁡
γ denotes the horizontal following or opposing speed, which means that vertical crossing conflict from the same route can be treated as horizontal following or horizontal opposing conflicts, as shown in Figures 2(c) and 2(d) using vertical projection.Similarly, as shown in Figure2(e), the speed components v
1
·
cos
⁡
γ
1 and v
2
·
cos
⁡
γ
2 denote the horizontal crossing speeds from crossing routes, which means that vertical crossing conflict from crossing routes can be treated as horizontal crossing conflict using vertical projection, as shown in Figure 2(f), where α denotes the entering angle and β denotes the leaving angle.In particular, for the horizontal crossing conflict shown in Figure2(f), when α
=
0 and β
=
0, it is transformed into the horizontal following conflict shown in Figure 2(c), and when α
=
π and β
=
π, it is transformed into the horizontal opposing conflict shown in Figure 2(d). When α
≠
0 and β
=
0, it is transformed into the converging conflict shown in Figure 2(g).Therefore, vertical crossing, horizontal following, horizontal opposing, and horizontal converging conflicts can be treated as special cases of horizontal crossing conflict and can be unified under the definition of horizontal crossing conflict. To avoid potential conflicts described above and ensure separation between two aircrafts, the idea of a conflicting protection zone is introduced.Assume that aircrafts are allowed to fly only on fixed air routes to reduce the computational complexity of strategic deconfliction of 4D trajectory, different from the traditional protection zone based on elliptic cylinder, as shown in Figure3(a), whose semimajor axis is a
=
d
m
i
n
(
1
)
/
2, where d
m
i
n
(
1
) denotes the minimum longitudinal separation, the semiminor axis is b
=
d
m
i
n
(
2
)
/
2, where d
m
i
n
(
2
) denotes the minimum lateral separation, and the height is h
=
d
m
i
n
(
3
), where d
m
i
n
(
3
) denotes the minimum vertical separation. For tactical trajectory planning, the conflict waypoints are dynamic and should be detected in real time, and the center of protection zone based on elliptic cylinder is the position of one aircraft, which may cause the motion of protection zone as the aircraft track evolves along the 4D trajectory for its time dimension and increase the computational complexity of conflict detection and resolution. While the potential conflict waypoints for strategic 4D trajectories of different aircraft can be determined in advance. As a result, we can fix the center of protection zone at the potential conflict waypoints, which reduce the computational complexity of conflict detection and resolution, which can be illustrated in computational complexity analysis section. As analyzed above, vertical crossing conflict can be treated as horizontal following or horizontal opposing conflicts using vertical projection, as shown in Figure 3(b). If the dimension of horizontal protection zone meets given requirements, it can be proven that all the separation can be satisfied in combination with the conflict-control strategy.Figure 3
Two different protection zones.
(a)
Traditional protection zone based on elliptic cylinder
(b)
Horizontal projection of traditional protection zone
(c)
Protection zone based on horizontal trianglesThe protection zone based on horizontal triangles is proposed in this study. As shown in Figure3(c), triangles A
O
B, C
O
D, I
O
J, and K
O
L are horizontal protection zones, where the top vertex is a conflicting crossing, following, and converging waypoint, and the lengths of the two sides are considered to meet three types of minimal separation requirements in combination with the conflict-control strategy: (1) the distance between aircraft entering segments A
O and B
O, as well as the distance between aircraft leaving segments O
C and O
D, should meet the minimum lateral separation requirement; (2) the distance between aircraft entering segment A
O and aircraft leaving O
C, as well as the distance between the aircraft entering B
O and leaving O
D, should meet the minimum longitudinal separation requirement; and (3) the distance between aircraft entering segment A
O and aircraft leaving O
D, as well as the distance between the aircraft entering B
O and leaving O
C, should meet the minimum lateral separation requirement.According to the horizontal crossing angles of two crossing routes, the protection zones based on horizontal triangles can be classified into three categories. Figure4 shows type I horizontal crossing protection zone, where δ
≥
π
/
2 and θ
≥
π
/
2, Figure 5 shows type II horizontal crossing protection zone, where δ
≥
π
/
2 and θ
<
π
/
2, or δ
<
π
/
2 and θ
≥
π
/
2, and Figure 6 shows type III horizontal crossing protection zone, where δ
<
π
/
2 and θ
<
π
/
2.Figure 4
Type I horizontal crossing protection zone.Figure 5
Type II horizontal crossing protection zone.Figure 6
Type III horizontal crossing protection zone.If the lengths of the two sides for protection zones are set as follows, all the above constraints can be satisfied in combination with the conflict-control strategy proposed in next section.(3)
d
A
O
=
d
B
O
=
d
m
i
n
1
,
α
=
0
max
⁡
d
m
i
n
1
,
d
m
i
n
2
·
sec
⁡
α
,
0
<
α
<
π
2
max
⁡
d
m
i
n
1
,
d
m
i
n
2
,
α
≥
π
2
d
O
C
=
d
O
D
=
d
m
i
n
1
,
β
=
0
max
⁡
d
m
i
n
1
,
d
m
i
n
2
·
sec
⁡
β
,
0
<
β
<
π
2
max
⁡
d
m
i
n
1
,
d
m
i
n
2
,
β
≥
π
2
d
O
I
=
d
O
J
=
d
m
i
n
2
·
sec
⁡
δ
/
2
2
,
0
<
δ
≥
π
2
max
⁡
d
m
i
n
2
·
sec
⁡
δ
/
2
2
,
d
m
i
n
2
,
δ
≥
π
2
d
O
K
=
d
O
L
=
d
m
i
n
2
·
sec
⁡
θ
/
2
2
,
0
<
θ
<
π
2
max
⁡
d
m
i
n
2
·
sec
⁡
θ
/
2
2
,
d
m
i
n
2
,
θ
≥
π
2
.For simplicity, the constraint-free state transition model of types I, II, and III horizontal crossing protection zones can be described as the same Petri net, as shown Figure7, where each place or transition has three captions that represent the place or transition for type I, type II, and type III constraint-free state transition model, respectively.Figure 7
Constraint-free state transition model of types I, II, and III horizontal crossing protection zone.


## 2.3. Conflicting Protection Zone Control Model

To meet three types of minimal separation requirements mentioned above, the controlled Petri nets with external enabling conditions called control places should be introduced firstly [23].Definition 2 (protection-zone conflict-control model).
A protection-zone conflict-control model is defined as a controlled free-choice Petri netsC
P
N
=
(
P
,
T
,
I
,
O
,
M
,
Γ
)
=
(
G
1
,
G
2
,
P
C
,
I
C
,
O
C
,
M
C
), where G
1 and G
2 represent two related constraint-free state transition models that share the same transition. The place set P
C denotes conflict-control places. The input function I
C
:
P
C
×
T
G
→
N and the output function O
C
:
P
C
×
T
G
→
N represent forward and backward connecting relationships between control places and controlled transitions, respectively. M
C
:
P
C
→
N represents the markings of the conflict-control places.
The type I protection-zone conflict-control modelC
P
N
1 for G
A
O
C and G
B
O
D shown in Figure 7 can be described by the Petri nets shown in Figure 8, where places p
C
(
i
) (1
≤
i
≤
6) denote the conflict-control place, whose initial markings M
C
0
(
p
C
(
i
)
)
=
1 ensure that protection zones A
O
B, C
O
D, I
O
J, K
O
L, A
O
C, and B
O
D can accommodate at most one aircraft each, that is, M
(
p
A
O
)
+
M
(
p
B
O
)
≤
1 and M
(
p
O
C
)
+
M
(
p
O
D
)
≤
1, which ensure the separation requirement (1); M
(
p
A
O
)
+
M
(
p
O
C
)
≤
1 and M
(
p
B
O
)
+
M
(
p
O
D
)
≤
1, which ensure the separation requirement (2); M
(
p
I
O
)
+
M
(
p
O
J
)
≤
1 an M
(
p
K
O
)
+
M
(
p
O
L
)
≤
1, which ensure the separation requirement (3). For the purpose of clarity, the observation places are neglected.
Suppose that the expected arrival time at waypointO of aircraft a
(
k
j
), that is, the k
jth aircraft of aircraft queue in constraint-free state transition model G
j, is u
O
(
k
j
), j
=
1,2 before deconfliction; the moment when conflict-control place p
C
(
i
)
,
i
=
1
,
…
,
6, is marked is denoted by x
C
(
i
)
(
k
j
)
,
j
=
1,2; and the sojourning times in place p
A
I
,
p
I
O
,
…
,
p
J
D for aircraft a
(
k
j
) are τ
A
I
(
k
j
)
,
τ
I
O
(
k
j
)
,
…
,
τ
J
D
(
k
j
), respectively.
Ifu
O
(
k
1
)
≤
u
O
(
k
2
), aircraft a
(
k
1
) is assigned priority to enter protection zones. Hence, the state equation can be expressed as(4)
x
C
1
k
1
=
max
⁡
x
C
5
k
1
-
1
+
τ
A
O
,
s
e
l
x
C
1
k
1
-
1
,
x
C
1
k
2
-
1
+
τ
A
O
,
s
e
l
x
C
3
k
1
-
1
,
x
C
3
k
2
-
1
+
τ
I
O
,
s
e
l
x
C
4
k
1
-
1
,
x
C
4
k
2
-
1
,
s
e
l
x
C
2
k
1
-
1
,
x
C
2
k
2
-
1
,
u
O
k
1
x
C
2
k
1
=
x
C
1
k
1
+
τ
O
C
x
C
3
k
1
=
x
C
1
k
1
x
C
4
k
1
=
x
C
1
k
1
+
τ
O
L
x
C
5
k
1
=
x
C
1
k
1
+
τ
O
C
,where “s
e
l” is a selection operator, which is defined as follows:(5)
s
e
l
x
C
i
k
1
-
1
,
x
C
i
k
2
-
1
=
x
C
i
k
1
-
1
,
u
O
k
1
-
1
≥
u
O
k
2
-
1
x
C
i
k
2
-
1
,
u
O
k
1
-
1
<
u
O
k
2
-
1
,
i
=
1,2
,
…
,
5
.
Else, ifu
O
(
k
2
)
<
u
O
(
k
1
), aircraft a
(
k
2
) is assigned priority to enter protection zones. Hence, the state equation can be expressed as follows:(6)
x
C
1
k
2
=
max
⁡
x
C
6
k
2
-
1
+
τ
B
O
,
s
e
l
x
C
1
k
2
-
1
,
x
C
1
k
1
-
1
+
τ
B
O
,
s
e
l
x
C
4
k
2
-
1
,
x
C
4
k
1
-
1
+
τ
K
O
,
s
e
l
x
C
3
k
2
-
1
,
x
C
3
k
1
-
1
,
s
e
l
x
C
2
k
2
-
1
,
x
C
2
k
1
-
1
,
u
O
k
2
x
C
2
k
2
=
x
C
1
k
2
+
τ
O
D
x
C
3
k
2
=
x
C
1
k
2
+
τ
O
J
x
C
4
k
2
=
x
C
1
k
2
x
C
6
k
2
=
x
C
1
k
2
+
τ
O
D
,where the selection operator “s
e
l” is defined as follows:(7)
s
e
l
x
C
i
k
2
-
1
,
x
C
i
k
1
-
1
=
x
C
i
k
2
-
1
,
u
O
k
2
-
1
≥
u
O
k
1
-
1
x
C
i
k
1
-
1
,
u
O
k
2
-
1
<
u
O
k
1
-
1
,
i
=
1,2
,
…
,
5
.
The strategic conflict-free 4D trajectories for aircraft queuesF
1 and F
2, that is, the adjusted arrival time at waypoint O after deconfliction, can be expressed as(8)
y
O
k
1
=
x
C
1
k
1
,
if
u
O
k
1
≤
u
O
k
2
y
O
k
2
=
x
C
1
k
2
,
if
u
O
k
1
>
u
O
k
2
.
The type II protection-zone conflict-control modelC
P
N
2 for G
A
O
C and G
K
O
D shown in Figure 7 can be described by the Petri nets shown in Figure 9, where places p
C
(
i
) (1
≤
i
≤
6) denote the conflict-control place, whose initial markings M
C
0
(
p
C
(
i
)
)
=
1 ensure that protection zones A
O
K, C
O
D, I
O
J, K
O
L, A
O
C, and B
O
D can accommodate at most one aircraft each; that is, M
(
p
A
O
)
+
M
(
p
K
O
)
≤
1 and M
(
p
O
C
)
+
M
(
p
O
D
)
≤
1, which ensure the separation requirement (1); M
(
p
A
O
)
+
M
(
p
O
C
)
≤
1 and M
(
p
B
O
)
+
M
(
p
O
D
)
≤
1, which ensure the separation requirement (2); M
(
p
I
O
)
+
M
(
p
O
J
)
≤
1 and M
(
p
K
O
)
+
M
(
p
O
L
)
≤
1, which ensure the separation requirement (3). For the purpose of clarity, the observation places are neglected.
Suppose that the expected arrival time at waypointO of aircraft a
(
k
j
), that is, the k
jth aircraft of aircraft queue in constraint-free state transition model G
j, is u
O
(
k
j
), j
=
1,2 before deconfliction; the moment when conflict-control place p
C
(
i
)
,
i
=
1
,
…
,
6, is marked is denoted by x
C
(
i
)
(
k
j
), j
=
1,2; and the sojourning times in places p
A
I
,
p
I
O
,
…
,
p
J
D for aircraft a
(
k
j
) are τ
A
I
(
k
j
)
,
τ
I
O
(
k
j
)
,
…
,
τ
J
D
(
k
j
), respectively.
Ifu
O
(
k
1
)
≤
u
O
(
k
2
), aircraft a
(
k
1
) is assigned priority to enter protection zones. Hence, the state equation can be expressed as (4); else if u
O
(
k
2
)
<
u
O
(
k
1
), aircraft a
(
k
2
) is assigned priority to enter protection zones. Hence, the state equation can be expressed as(9)
x
C
1
k
2
=
max
⁡
x
C
6
k
2
-
1
+
τ
B
O
,
s
e
l
x
C
1
k
2
-
1
,
x
C
1
k
1
-
1
+
τ
K
O
,
s
e
l
x
C
4
k
2
-
1
,
x
C
4
k
1
-
1
+
τ
K
O
,
s
e
l
x
C
3
k
2
-
1
,
x
C
3
k
1
-
1
,
s
e
l
x
C
2
k
2
-
1
,
x
C
2
k
1
-
1
,
u
O
k
2
x
C
2
k
2
=
x
C
1
k
2
+
τ
O
D
x
C
3
k
2
=
x
C
1
k
2
+
τ
O
J
x
C
4
k
2
=
x
C
1
k
2
x
C
6
k
2
=
x
C
1
k
2
+
τ
O
D
,where the selection operator “s
e
l” is defined the same as (7).
The strategic conflict-free 4D trajectories for aircraft queuesF
1 and F
2 in protection-zone conflict-control model, that is, the adjusted arrival time at waypoint O after deconfliction, can be expressed as (8).
The type III protection-zone conflict-control modelC
P
N
3 for G
I
O
L and G
K
O
J shown in Figure 7 can be described by the Petri nets shown in Figure 10, where places p
C
(
i
) (1
≤
i
≤
6) denote the conflict-control place, whose initial markings M
C
0
(
p
C
(
i
)
)
=
1 ensure that protection zones I
O
K, C
O
D, I
O
J, K
O
L, A
O
C, and B
O
D can accommodate at most one aircraft each; that is, M
(
p
I
O
)
+
M
(
p
K
O
)
≤
1 and M
(
p
O
C
)
+
M
(
p
O
D
)
≤
1, which ensure the separation requirement (1); M
(
p
A
O
)
+
M
(
p
O
C
)
≤
1 and M
(
p
B
O
)
+
M
(
p
O
D
)
≤
1, which ensure the separation requirement (2); M
(
p
I
O
)
+
M
(
p
O
J
)
≤
1 and M
(
p
K
O
)
+
M
(
p
O
L
)
≤
1, which ensure the separation requirement (3). For the purpose of clarity, the observation places are neglected.
Suppose that the expected arrival time at waypointO of aircraft a
(
k
j
), that is, the k
jth aircraft of aircraft queue in constraint-free state transition model G
j, is u
O
(
k
j
), j
=
1,2 before deconfliction; the moment when conflict-control place p
C
(
i
)
,
i
=
1
,
…
,
6, is marked is denoted by x
C
(
i
)
(
k
j
), j
=
1,2; and the sojourning times in places p
I
A
,
p
I
O
,
…
,
p
D
J for aircraft a
(
k
j
) are τ
I
A
(
k
j
)
,
τ
I
O
(
k
j
)
,
…
,
τ
D
J
(
k
j
), respectively.
Ifu
O
(
k
1
)
≤
u
O
(
k
2
), aircraft a
(
k
1
) is assigned priority to enter protection zones. Hence, the state equation can be expressed as(10)
x
C
1
k
1
=
max
⁡
x
C
5
k
1
-
1
+
τ
A
O
,
s
e
l
x
C
1
k
1
-
1
,
x
C
1
k
2
-
1
+
τ
I
O
,
s
e
l
x
C
3
k
1
-
1
,
x
C
3
k
2
-
1
+
τ
I
O
,
s
e
l
x
C
4
k
1
-
1
,
x
C
4
k
2
-
1
,
s
e
l
x
C
2
k
1
-
1
,
x
C
2
k
2
-
1
,
u
O
k
1
x
C
2
k
1
=
x
C
1
k
1
+
τ
O
C
x
C
3
k
1
=
x
C
1
k
1
x
C
4
k
1
=
x
C
1
k
1
+
τ
O
L
x
C
5
k
1
=
x
C
1
k
1
+
τ
O
C
,where the selection operator “s
e
l” is defined the same as (7).
Else, ifu
O
(
k
2
)
<
u
O
(
k
1
), aircraft a
(
k
2
) is assigned priority to enter protection zones. Hence, the state transition equation can be expressed as (9).
The strategic conflict-free 4D trajectories for aircraft queuesF
1 and F
2 in protection-zone conflict-control model, that is, the adjusted arrival time at waypoint O after deconfliction, can be expressed as (8).Figure 8
Type I protection-zone conflict-control model.Figure 9
Type II protection-zone conflict-control model.Figure 10
Type III protection-zone conflict-control model.


## 3. Description of Air Traffic Control System

### 3.1. Basic Max-Plus Algebra Conflict-Control Model

To simplify the protection-zone conflict-control model, max-plus algebra was employed because it is widely used in discrete-event dynamic system modeling and analysis. Max-plus algebra can be defined as follows: (1) the domain of definition of max-plus algebra isR
-
=
R
∪
{
-
∞
}, where R denotes the real number domain and “-
∞” denotes negative infinity; (2) the two basic operators of max-plus algebra are max operator “⊕” and plus operator “⊗”, where a
⊕
b
=
max
⁡
{
a
,
b
}
,
a
⊗
b
=
a
+
b; thus “0”, “-
∞” are called the identity element and the zero element and denoted by e and ε, respectively [24].For a matrixA
,
B
∈
R
-
m
×
n, then (
A
⊕
B
)
i
j
=
(
A
)
i
j
⊕
(
B
)
i
j
=
max
⁡
{
(
A
)
i
j
,
(
B
)
i
j
}, and for A
∈
R
-
m
×
r and B
∈
R
-
r
×
n, then (11)
A
⊗
B
i
j
=
∑
l
=
1
r
⊕
A
i
l
⊗
B
l
j
=
max
1
≤
l
≤
r
⁡
A
i
l
+
B
l
j
.LetX
k
=
[
x
C
(
1
)
(
k
1
)
,
x
C
(
2
)
(
k
1
)
,
x
C
(
3
)
(
k
1
)
,
x
C
(
4
)
(
k
1
)
,
x
C
(
5
)
(
k
1
), x
C
(
1
)
(
k
2
)
,
x
C
(
2
)
(
k
2
)
,
x
C
(
3
)
(
k
2
)
,
x
C
(
4
)
(
k
2
)
,
x
C
(
6
)
(
k
2
)
]
T, U
(
k
)
=
[
u
O
(
k
1
)
,
u
O
(
k
2
)
]
T, Y
(
k
)
=
[
y
O
(
k
1
)
,
y
O
(
k
2
)
]
T. For the three protection-zone conflict-control models described above, the state and output equations can be expressed in a linear form under the definition of max-plus algebra: (12)
X
k
=
A
s
⊗
X
k
-
1
⊕
B
s
⊗
U
k
Y
k
=
C
s
⊗
X
k
,where the state, input, and output matrices are not constant but depend on expected arrival times u
O
(
k
j
) of aircraft queue queues F
1 and F
2.For the type I protection-zone conflict-control model, the state, input, and output matrices are described as follows.Ifu
O
(
k
1
)
≤
u
O
(
k
2
),(13)
A
s
=
a
1
ε
ε
ε
,
u
O
k
1
-
1
≥
u
O
k
2
-
1
ε
a
1
ε
ε
,
u
O
k
1
-
1
<
u
O
k
2
-
1
,
B
s
=
b
1
ε
,
C
s
=
c
1
ε
T
;else, if u
O
(
k
2
)
<
u
O
(
k
1
),(14)
A
s
=
ε
ε
a
2
ε
,
u
O
k
2
-
1
≥
u
O
k
1
-
1
ε
ε
ε
a
2
,
u
O
k
2
-
1
<
u
O
k
1
-
1
,
B
s
=
ε
b
2
,
C
s
=
ε
c
2
T
,where each element in submatrix ε is ε, and submatrices a
i, b
i, and c
i, (i
=
1,2) are listed as follows: (15)
a
1
=
τ
A
O
e
τ
I
O
e
τ
A
O
τ
A
C
τ
O
C
τ
I
C
τ
O
C
τ
A
C
τ
A
O
e
τ
I
O
e
τ
A
O
τ
A
L
τ
O
L
τ
I
L
τ
O
L
τ
A
L
τ
A
C
τ
O
C
τ
I
C
τ
O
C
τ
A
C
,
b
1
=
e
ε
τ
O
C
ε
e
ε
τ
O
L
ε
τ
O
C
ε
,
c
1
=
e
,
ε
,
ε
,
ε
,
ε
,
ε
,
ε
,
ε
,
ε
,
ε
T
(16)
a
2
=
τ
B
O
e
e
τ
K
O
τ
B
O
τ
B
D
τ
O
D
τ
O
D
τ
K
D
τ
B
D
τ
B
J
τ
O
J
τ
O
J
τ
K
J
τ
B
J
τ
B
O
e
e
τ
K
O
τ
B
O
τ
B
D
τ
O
D
τ
O
D
τ
K
D
τ
B
D
,
b
2
=
ε
e
ε
τ
O
D
ε
τ
O
J
ε
ε
ε
τ
O
D
,
c
2
=
ε
,
ε
,
ε
,
ε
,
ε
,
e
,
ε
,
ε
,
ε
,
ε
T
.For the type II protection-zone conflict-control model, the state, input, and output matrices are described in (13) and (14), and the submatrices a
1, b
1, and c
1 are the same as the type I protection-zone conflict-control model in (15), while the submatrices a
2, b
2, and c
2 are listed as follows:(17)
a
2
=
τ
K
O
e
e
τ
K
O
τ
B
O
τ
K
D
τ
O
D
τ
O
D
τ
K
D
τ
B
D
τ
K
J
τ
O
J
τ
O
J
τ
K
J
τ
B
J
τ
K
O
e
e
τ
K
O
τ
B
O
τ
K
D
τ
O
D
τ
O
D
τ
K
D
τ
B
D
,
b
2
=
ε
e
ε
τ
O
D
ε
τ
O
J
ε
ε
ε
τ
O
D
,
c
2
=
ε
,
ε
,
ε
,
ε
,
ε
,
e
,
ε
,
ε
,
ε
,
ε
T
.For the type III protection-zone conflict-control model, its state, input, and output matrices are described in (13) and (14), and the submatrices a
2, b
2, and c
2 are the same as the type II protection-zone conflict-control model in (17), while the submatrices a
1, b
1, and c
1 are listed as follows: (18)
a
1
=
τ
I
O
e
τ
I
O
e
τ
A
O
τ
I
C
τ
O
C
τ
I
C
τ
O
C
τ
A
C
τ
I
O
e
τ
I
O
e
τ
A
O
τ
I
L
τ
O
L
τ
I
L
τ
O
L
τ
A
L
τ
I
C
τ
O
C
τ
I
C
τ
O
C
τ
A
C
,
b
1
=
e
ε
τ
O
C
ε
e
ε
τ
O
L
ε
τ
O
C
ε
,
c
1
=
e
,
ε
,
ε
,
ε
,
ε
,
ε
,
ε
,
ε
,
ε
,
ε
T
.


### 3.2. Synthesized Air Traffic Control Model

There may be various conflicts in an airspace (e.g., the terminal control area), and, hence, it is necessary to develop a synthesized model that includes all possible basic protection-zone conflict-control models, which can be represented by the graphic symbols shown in Figure11.Figure 11
Graphic symbols for basic protection-zone conflict-control models.
(a)
Horizontal following conflict
(b)
Horizontal crossing conflict
(c)
Horizontal converging conflict
(d)
Vertical crossing conflictConsider the two aircraft queuesF
1 from airport A
1 and F
2 from airport A
2 crossing vertically at waypoint P
1 and following at waypoint P
2, as shown in Figure 12.Figure 12
Synthesized two departing air traffic models.They are supposed to depart fromA
1 and A
2 at U
0
=
[
u
P
2
A
1
(
k
1
)
,
u
P
2
A
2
(
k
2
)
]
T, the flight durations from A
1 and A
2 to P
1 are D
1
=
[
τ
P
1
A
1
(
k
1
)
,
τ
P
1
A
2
(
k
2
)
]
T, and the flight durations from P
1 to P
2 are D
2
=
[
τ
P
2
P
1
(
k
1
)
,
τ
P
2
P
1
(
k
2
)
]
T. Without loss of generality, denote the state, input, and output matrices of the first vertical crossing conflict-control model as A
1, B
1, and C
1, and denote those of the second horizontal following conflict-control model as A
2, B
2, and C
2. Obviously, the following relationships hold:(19)
U
1
=
U
0
⊗
D
1
U
2
=
Y
1
⊗
D
2
.Incorporating the above equations into the two protection-zone conflict-control models, the state and output equations for synthesized air traffic model can be rewritten as(20)
X
1
k
=
A
1
⊗
X
1
k
-
1
⊕
B
1
⊗
D
1
⊗
U
0
Y
1
k
=
C
1
⊗
X
1
k
X
2
k
=
A
2
⊗
X
2
k
-
1
⊕
B
2
⊗
D
2
⊗
C
1
⊗
A
1
⊗
X
1
k
-
1
⊕
B
1
⊗
D
1
⊗
U
0
Y
2
k
=
C
2
⊗
X
2
kwhich can be rewritten as(21)
X
2
k
X
1
k
=
A
2
B
2
⊗
D
2
⊗
C
1
⊗
A
1
ε
A
1
⊗
X
2
k
-
1
X
1
k
-
1
⊕
B
2
⊗
D
2
⊗
C
1
⊗
B
1
⊗
D
1
B
1
⊗
D
1
⊗
U
0
Y
2
k
Y
1
k
=
C
2
ε
ε
C
1
⊗
X
2
k
X
1
k
.By analogy, ifn conflict-control models are connected in series (without fork and join), the synthesized departing air traffic model can be described uniformly as(22)
X
n
k
,
X
n
-
1
k
,
…
,
X
1
k
T
=
A
⊗
X
n
k
-
1
,
X
n
-
1
k
-
1
,
…
,
X
1
k
-
1
T
⊕
B
⊗
U
0
Y
n
k
,
Y
n
-
1
k
,
…
,
Y
1
k
T
=
C
⊗
X
n
k
,
X
n
-
1
k
,
…
,
X
1
k
Tand the state, input, and output matrices of the synthesized model are(23)
A
=
A
n
B
n
⊗
D
n
⊗
C
n
-
1
⊗
A
n
-
1
B
n
-
1
⊗
D
n
-
1
⊗
C
n
-
2
⊗
A
n
-
2
⋯
A
1
ε
A
n
-
1
B
n
-
1
⊗
D
n
-
1
⊗
C
n
-
2
⊗
A
n
-
2
⋯
A
1
⋮
⋮
⋮
⋮
⋮
ε
ε
ε
⋯
A
1
B
=
B
n
⊗
D
n
⊗
C
n
-
1
⊗
B
n
-
1
⊗
D
n
-
1
B
n
-
1
⊗
D
n
-
1
⊗
C
n
-
2
⊗
B
n
-
2
⊗
D
n
-
2
⋯
B
1
⊗
D
1
ε
B
n
-
1
⊗
D
n
-
1
⊗
C
n
-
2
⊗
B
n
-
2
⊗
D
n
-
2
⋯
B
1
⊗
D
1
⋮
⋮
⋮
⋮
ε
ε
⋯
B
1
⊗
D
1
C
=
C
n
ε
⋯
ε
ε
C
n
-
1
⋯
ε
⋮
⋮
⋮
⋮
ε
ε
⋯
C
1
.It can be inferred from the above equations that, given the departure times of an aircraft queue, that is, the initial 4D trajectories before deconfliction and flight durations between two conflicting waypoints, their adjusted arrival time at any conflicting waypoints after deconfliction, that is, conflict-free 4D trajectories, can be obtained by a linear calculation under the definition of max-plus algebra.


## 3.1. Basic Max-Plus Algebra Conflict-Control Model

To simplify the protection-zone conflict-control model, max-plus algebra was employed because it is widely used in discrete-event dynamic system modeling and analysis. Max-plus algebra can be defined as follows: (1) the domain of definition of max-plus algebra isR
-
=
R
∪
{
-
∞
}, where R denotes the real number domain and “-
∞” denotes negative infinity; (2) the two basic operators of max-plus algebra are max operator “⊕” and plus operator “⊗”, where a
⊕
b
=
max
⁡
{
a
,
b
}
,
a
⊗
b
=
a
+
b; thus “0”, “-
∞” are called the identity element and the zero element and denoted by e and ε, respectively [24].For a matrixA
,
B
∈
R
-
m
×
n, then (
A
⊕
B
)
i
j
=
(
A
)
i
j
⊕
(
B
)
i
j
=
max
⁡
{
(
A
)
i
j
,
(
B
)
i
j
}, and for A
∈
R
-
m
×
r and B
∈
R
-
r
×
n, then (11)
A
⊗
B
i
j
=
∑
l
=
1
r
⊕
A
i
l
⊗
B
l
j
=
max
1
≤
l
≤
r
⁡
A
i
l
+
B
l
j
.LetX
k
=
[
x
C
(
1
)
(
k
1
)
,
x
C
(
2
)
(
k
1
)
,
x
C
(
3
)
(
k
1
)
,
x
C
(
4
)
(
k
1
)
,
x
C
(
5
)
(
k
1
), x
C
(
1
)
(
k
2
)
,
x
C
(
2
)
(
k
2
)
,
x
C
(
3
)
(
k
2
)
,
x
C
(
4
)
(
k
2
)
,
x
C
(
6
)
(
k
2
)
]
T, U
(
k
)
=
[
u
O
(
k
1
)
,
u
O
(
k
2
)
]
T, Y
(
k
)
=
[
y
O
(
k
1
)
,
y
O
(
k
2
)
]
T. For the three protection-zone conflict-control models described above, the state and output equations can be expressed in a linear form under the definition of max-plus algebra: (12)
X
k
=
A
s
⊗
X
k
-
1
⊕
B
s
⊗
U
k
Y
k
=
C
s
⊗
X
k
,where the state, input, and output matrices are not constant but depend on expected arrival times u
O
(
k
j
) of aircraft queue queues F
1 and F
2.For the type I protection-zone conflict-control model, the state, input, and output matrices are described as follows.Ifu
O
(
k
1
)
≤
u
O
(
k
2
),(13)
A
s
=
a
1
ε
ε
ε
,
u
O
k
1
-
1
≥
u
O
k
2
-
1
ε
a
1
ε
ε
,
u
O
k
1
-
1
<
u
O
k
2
-
1
,
B
s
=
b
1
ε
,
C
s
=
c
1
ε
T
;else, if u
O
(
k
2
)
<
u
O
(
k
1
),(14)
A
s
=
ε
ε
a
2
ε
,
u
O
k
2
-
1
≥
u
O
k
1
-
1
ε
ε
ε
a
2
,
u
O
k
2
-
1
<
u
O
k
1
-
1
,
B
s
=
ε
b
2
,
C
s
=
ε
c
2
T
,where each element in submatrix ε is ε, and submatrices a
i, b
i, and c
i, (i
=
1,2) are listed as follows: (15)
a
1
=
τ
A
O
e
τ
I
O
e
τ
A
O
τ
A
C
τ
O
C
τ
I
C
τ
O
C
τ
A
C
τ
A
O
e
τ
I
O
e
τ
A
O
τ
A
L
τ
O
L
τ
I
L
τ
O
L
τ
A
L
τ
A
C
τ
O
C
τ
I
C
τ
O
C
τ
A
C
,
b
1
=
e
ε
τ
O
C
ε
e
ε
τ
O
L
ε
τ
O
C
ε
,
c
1
=
e
,
ε
,
ε
,
ε
,
ε
,
ε
,
ε
,
ε
,
ε
,
ε
T
(16)
a
2
=
τ
B
O
e
e
τ
K
O
τ
B
O
τ
B
D
τ
O
D
τ
O
D
τ
K
D
τ
B
D
τ
B
J
τ
O
J
τ
O
J
τ
K
J
τ
B
J
τ
B
O
e
e
τ
K
O
τ
B
O
τ
B
D
τ
O
D
τ
O
D
τ
K
D
τ
B
D
,
b
2
=
ε
e
ε
τ
O
D
ε
τ
O
J
ε
ε
ε
τ
O
D
,
c
2
=
ε
,
ε
,
ε
,
ε
,
ε
,
e
,
ε
,
ε
,
ε
,
ε
T
.For the type II protection-zone conflict-control model, the state, input, and output matrices are described in (13) and (14), and the submatrices a
1, b
1, and c
1 are the same as the type I protection-zone conflict-control model in (15), while the submatrices a
2, b
2, and c
2 are listed as follows:(17)
a
2
=
τ
K
O
e
e
τ
K
O
τ
B
O
τ
K
D
τ
O
D
τ
O
D
τ
K
D
τ
B
D
τ
K
J
τ
O
J
τ
O
J
τ
K
J
τ
B
J
τ
K
O
e
e
τ
K
O
τ
B
O
τ
K
D
τ
O
D
τ
O
D
τ
K
D
τ
B
D
,
b
2
=
ε
e
ε
τ
O
D
ε
τ
O
J
ε
ε
ε
τ
O
D
,
c
2
=
ε
,
ε
,
ε
,
ε
,
ε
,
e
,
ε
,
ε
,
ε
,
ε
T
.For the type III protection-zone conflict-control model, its state, input, and output matrices are described in (13) and (14), and the submatrices a
2, b
2, and c
2 are the same as the type II protection-zone conflict-control model in (17), while the submatrices a
1, b
1, and c
1 are listed as follows: (18)
a
1
=
τ
I
O
e
τ
I
O
e
τ
A
O
τ
I
C
τ
O
C
τ
I
C
τ
O
C
τ
A
C
τ
I
O
e
τ
I
O
e
τ
A
O
τ
I
L
τ
O
L
τ
I
L
τ
O
L
τ
A
L
τ
I
C
τ
O
C
τ
I
C
τ
O
C
τ
A
C
,
b
1
=
e
ε
τ
O
C
ε
e
ε
τ
O
L
ε
τ
O
C
ε
,
c
1
=
e
,
ε
,
ε
,
ε
,
ε
,
ε
,
ε
,
ε
,
ε
,
ε
T
.


## 3.2. Synthesized Air Traffic Control Model

There may be various conflicts in an airspace (e.g., the terminal control area), and, hence, it is necessary to develop a synthesized model that includes all possible basic protection-zone conflict-control models, which can be represented by the graphic symbols shown in Figure11.Figure 11
Graphic symbols for basic protection-zone conflict-control models.
(a)
Horizontal following conflict
(b)
Horizontal crossing conflict
(c)
Horizontal converging conflict
(d)
Vertical crossing conflictConsider the two aircraft queuesF
1 from airport A
1 and F
2 from airport A
2 crossing vertically at waypoint P
1 and following at waypoint P
2, as shown in Figure 12.Figure 12
Synthesized two departing air traffic models.They are supposed to depart fromA
1 and A
2 at U
0
=
[
u
P
2
A
1
(
k
1
)
,
u
P
2
A
2
(
k
2
)
]
T, the flight durations from A
1 and A
2 to P
1 are D
1
=
[
τ
P
1
A
1
(
k
1
)
,
τ
P
1
A
2
(
k
2
)
]
T, and the flight durations from P
1 to P
2 are D
2
=
[
τ
P
2
P
1
(
k
1
)
,
τ
P
2
P
1
(
k
2
)
]
T. Without loss of generality, denote the state, input, and output matrices of the first vertical crossing conflict-control model as A
1, B
1, and C
1, and denote those of the second horizontal following conflict-control model as A
2, B
2, and C
2. Obviously, the following relationships hold:(19)
U
1
=
U
0
⊗
D
1
U
2
=
Y
1
⊗
D
2
.Incorporating the above equations into the two protection-zone conflict-control models, the state and output equations for synthesized air traffic model can be rewritten as(20)
X
1
k
=
A
1
⊗
X
1
k
-
1
⊕
B
1
⊗
D
1
⊗
U
0
Y
1
k
=
C
1
⊗
X
1
k
X
2
k
=
A
2
⊗
X
2
k
-
1
⊕
B
2
⊗
D
2
⊗
C
1
⊗
A
1
⊗
X
1
k
-
1
⊕
B
1
⊗
D
1
⊗
U
0
Y
2
k
=
C
2
⊗
X
2
kwhich can be rewritten as(21)
X
2
k
X
1
k
=
A
2
B
2
⊗
D
2
⊗
C
1
⊗
A
1
ε
A
1
⊗
X
2
k
-
1
X
1
k
-
1
⊕
B
2
⊗
D
2
⊗
C
1
⊗
B
1
⊗
D
1
B
1
⊗
D
1
⊗
U
0
Y
2
k
Y
1
k
=
C
2
ε
ε
C
1
⊗
X
2
k
X
1
k
.By analogy, ifn conflict-control models are connected in series (without fork and join), the synthesized departing air traffic model can be described uniformly as(22)
X
n
k
,
X
n
-
1
k
,
…
,
X
1
k
T
=
A
⊗
X
n
k
-
1
,
X
n
-
1
k
-
1
,
…
,
X
1
k
-
1
T
⊕
B
⊗
U
0
Y
n
k
,
Y
n
-
1
k
,
…
,
Y
1
k
T
=
C
⊗
X
n
k
,
X
n
-
1
k
,
…
,
X
1
k
Tand the state, input, and output matrices of the synthesized model are(23)
A
=
A
n
B
n
⊗
D
n
⊗
C
n
-
1
⊗
A
n
-
1
B
n
-
1
⊗
D
n
-
1
⊗
C
n
-
2
⊗
A
n
-
2
⋯
A
1
ε
A
n
-
1
B
n
-
1
⊗
D
n
-
1
⊗
C
n
-
2
⊗
A
n
-
2
⋯
A
1
⋮
⋮
⋮
⋮
⋮
ε
ε
ε
⋯
A
1
B
=
B
n
⊗
D
n
⊗
C
n
-
1
⊗
B
n
-
1
⊗
D
n
-
1
B
n
-
1
⊗
D
n
-
1
⊗
C
n
-
2
⊗
B
n
-
2
⊗
D
n
-
2
⋯
B
1
⊗
D
1
ε
B
n
-
1
⊗
D
n
-
1
⊗
C
n
-
2
⊗
B
n
-
2
⊗
D
n
-
2
⋯
B
1
⊗
D
1
⋮
⋮
⋮
⋮
ε
ε
⋯
B
1
⊗
D
1
C
=
C
n
ε
⋯
ε
ε
C
n
-
1
⋯
ε
⋮
⋮
⋮
⋮
ε
ε
⋯
C
1
.It can be inferred from the above equations that, given the departure times of an aircraft queue, that is, the initial 4D trajectories before deconfliction and flight durations between two conflicting waypoints, their adjusted arrival time at any conflicting waypoints after deconfliction, that is, conflict-free 4D trajectories, can be obtained by a linear calculation under the definition of max-plus algebra.


## 4. Strategic Deconfliction of 4D Trajectory

### 4.1. Deconfliction Based on Arrival-Time Adjustment

In the protection-zone conflict-control model for waypointi
,
1
<
i
≤
n, if an aircraft a
(
k
) is expected to arrive at u
i
(
k
) and postponed to arrive at y
i
(
k
), then y
i
(
k
)
≥
u
i
(
k
) must be satisfied. Therefore, the aircraft must slow down or hold for w
i
(
k
)
=
y
i
(
k
)
-
u
i
(
k
) to avoid potential conflicts at conflicting waypoint i. The flight delay for thekth aircraft caused by arrival-time adjustment in segment i
-
1
,
i
¯ corresponding to the ith conflict-control model, can be converted into a difference of input vectors: U
^
i
(
k
)
=
U
i
(
k
)
+
W
i, where the decision variables W
i
=
[
w
i
(
1
)
,
w
i
(
2
)
,
…
,
w
i
(
K
)
]
T represent the flight delay vector in ith conflict-control model, which are treated as integer in practical application. Assuming that the number of following conflict-control models is n
-
i, the impact on the following aircraft can be described as (24)
X
n
k
,
…
,
X
i
+
1
k
,
X
i
k
T
=
A
⊗
X
n
k
-
1
,
…
,
X
i
+
1
k
-
1
,
X
i
k
-
1
T
⊕
B
⊗
U
^
i
Y
n
k
,
…
,
Y
i
+
1
k
,
Y
i
k
T
=
C
⊗
X
n
k
-
1
,
…
,
X
i
+
1
k
-
1
,
X
i
k
-
1
T
.Therefore, the total flight delayW for aircraft queue can be calculated as (25)
W
=
∑
k
=
1
K
y
n
k
-
u
n
k
.From the perspectives of reducing flight delay and improving the rate of flight punctuality, strategic deconfliction based on arrival-time adjustment can be achieved by solving the following integer linear programming under the definition of Max-plus algebra:(26)
m
i
n
1
K
∑
k
=
1
K
y
n
k
-
u
n
k
s
.
t
.
X
n
k
,
…
,
X
i
+
1
k
,
X
i
k
T
=
A
⊗
X
n
k
-
1
,
…
,
X
i
+
1
k
-
1
,
X
i
k
-
1
T
⊕
B
⊗
U
^
i
Y
n
k
,
…
,
Y
i
+
1
k
,
Y
i
k
T
=
C
⊗
X
n
k
-
1
,
…
,
X
i
+
1
k
-
1
,
X
i
k
-
1
T
U
^
i
k
=
U
i
k
+
W
i
W
i
m
i
n
≤
W
i
k
≤
W
i
m
a
x
,where the last constraint represents the admissible flight delay range determined by the speed limitations of aircraft a
(
k
).


### 4.2. Deconfliction Based on Departure-Time Adjustment

To alleviate the increase of air traffic controllers’ workload for frequent speed adjustments or air holding, the air traffic flow management department intends to adjust flight departure times to avoid strategic conflicts. Assume that the initial departure-time vector for aircraft queueF is U
0
=
[
u
0
(
1
)
,
u
0
(
2
)
,
…
,
u
0
(
K
)
]
T, and the adjusted departure-time vector is U
^
0
=
U
0
+
Δ
U
0, where decision variables Δ
U
0
=
[
Δ
u
0
(
1
)
,
Δ
u
0
(
2
)
,
…
,
Δ
u
0
(
K
)
]
T represent the initial departure delay vector, which are treated as integer in practical application. Assume further that there are n consecutive conflicting waypoints in conflict-control models. The impact on the set of aircraft can be described as follows:(27)
X
n
k
,
X
n
-
1
k
,
…
,
X
1
k
T
=
A
⊗
X
n
k
-
1
,
X
n
-
1
k
-
1
,
…
,
X
1
k
-
1
T
⊕
B
⊗
U
^
0
Y
n
k
,
Y
n
-
1
k
,
…
,
Y
1
k
T
=
C
⊗
X
n
k
,
X
n
-
1
k
,
…
,
X
1
k
T
.To avoid conflicts and reduce adjustments to departure time as much as possible, strategic deconfliction based on departure-time adjustment can be achieved by solving the following integer linear programming under the definition of Max-plus algebra:(28)
m
i
n
1
K
∑
k
=
1
K
y
n
k
-
u
n
k
s
.
t
.
X
n
k
,
X
n
-
1
k
,
…
,
X
1
k
T
=
A
⊗
X
n
k
-
1
,
X
n
-
1
k
-
1
,
…
,
X
1
k
-
1
T
⊕
B
⊗
U
^
0
Y
n
k
,
Y
n
-
1
k
,
…
,
Y
1
k
T
=
C
⊗
X
n
k
,
X
n
-
1
k
,
…
,
X
1
k
T
U
^
0
=
U
0
+
Δ
U
0
.


## 4.1. Deconfliction Based on Arrival-Time Adjustment

In the protection-zone conflict-control model for waypointi
,
1
<
i
≤
n, if an aircraft a
(
k
) is expected to arrive at u
i
(
k
) and postponed to arrive at y
i
(
k
), then y
i
(
k
)
≥
u
i
(
k
) must be satisfied. Therefore, the aircraft must slow down or hold for w
i
(
k
)
=
y
i
(
k
)
-
u
i
(
k
) to avoid potential conflicts at conflicting waypoint i. The flight delay for thekth aircraft caused by arrival-time adjustment in segment i
-
1
,
i
¯ corresponding to the ith conflict-control model, can be converted into a difference of input vectors: U
^
i
(
k
)
=
U
i
(
k
)
+
W
i, where the decision variables W
i
=
[
w
i
(
1
)
,
w
i
(
2
)
,
…
,
w
i
(
K
)
]
T represent the flight delay vector in ith conflict-control model, which are treated as integer in practical application. Assuming that the number of following conflict-control models is n
-
i, the impact on the following aircraft can be described as (24)
X
n
k
,
…
,
X
i
+
1
k
,
X
i
k
T
=
A
⊗
X
n
k
-
1
,
…
,
X
i
+
1
k
-
1
,
X
i
k
-
1
T
⊕
B
⊗
U
^
i
Y
n
k
,
…
,
Y
i
+
1
k
,
Y
i
k
T
=
C
⊗
X
n
k
-
1
,
…
,
X
i
+
1
k
-
1
,
X
i
k
-
1
T
.Therefore, the total flight delayW for aircraft queue can be calculated as (25)
W
=
∑
k
=
1
K
y
n
k
-
u
n
k
.From the perspectives of reducing flight delay and improving the rate of flight punctuality, strategic deconfliction based on arrival-time adjustment can be achieved by solving the following integer linear programming under the definition of Max-plus algebra:(26)
m
i
n
1
K
∑
k
=
1
K
y
n
k
-
u
n
k
s
.
t
.
X
n
k
,
…
,
X
i
+
1
k
,
X
i
k
T
=
A
⊗
X
n
k
-
1
,
…
,
X
i
+
1
k
-
1
,
X
i
k
-
1
T
⊕
B
⊗
U
^
i
Y
n
k
,
…
,
Y
i
+
1
k
,
Y
i
k
T
=
C
⊗
X
n
k
-
1
,
…
,
X
i
+
1
k
-
1
,
X
i
k
-
1
T
U
^
i
k
=
U
i
k
+
W
i
W
i
m
i
n
≤
W
i
k
≤
W
i
m
a
x
,where the last constraint represents the admissible flight delay range determined by the speed limitations of aircraft a
(
k
).


## 4.2. Deconfliction Based on Departure-Time Adjustment

To alleviate the increase of air traffic controllers’ workload for frequent speed adjustments or air holding, the air traffic flow management department intends to adjust flight departure times to avoid strategic conflicts. Assume that the initial departure-time vector for aircraft queueF is U
0
=
[
u
0
(
1
)
,
u
0
(
2
)
,
…
,
u
0
(
K
)
]
T, and the adjusted departure-time vector is U
^
0
=
U
0
+
Δ
U
0, where decision variables Δ
U
0
=
[
Δ
u
0
(
1
)
,
Δ
u
0
(
2
)
,
…
,
Δ
u
0
(
K
)
]
T represent the initial departure delay vector, which are treated as integer in practical application. Assume further that there are n consecutive conflicting waypoints in conflict-control models. The impact on the set of aircraft can be described as follows:(27)
X
n
k
,
X
n
-
1
k
,
…
,
X
1
k
T
=
A
⊗
X
n
k
-
1
,
X
n
-
1
k
-
1
,
…
,
X
1
k
-
1
T
⊕
B
⊗
U
^
0
Y
n
k
,
Y
n
-
1
k
,
…
,
Y
1
k
T
=
C
⊗
X
n
k
,
X
n
-
1
k
,
…
,
X
1
k
T
.To avoid conflicts and reduce adjustments to departure time as much as possible, strategic deconfliction based on departure-time adjustment can be achieved by solving the following integer linear programming under the definition of Max-plus algebra:(28)
m
i
n
1
K
∑
k
=
1
K
y
n
k
-
u
n
k
s
.
t
.
X
n
k
,
X
n
-
1
k
,
…
,
X
1
k
T
=
A
⊗
X
n
k
-
1
,
X
n
-
1
k
-
1
,
…
,
X
1
k
-
1
T
⊕
B
⊗
U
^
0
Y
n
k
,
Y
n
-
1
k
,
…
,
Y
1
k
T
=
C
⊗
X
n
k
,
X
n
-
1
k
,
…
,
X
1
k
T
U
^
0
=
U
0
+
Δ
U
0
.


## 5. Conflict-Free 4D Trajectory Perturbation Analysis

### 5.1. Perturbation of 4D Trajectories and Its Propagation

For various reasons arising from navigation errors, meteorological influences, and human factors, the departure time and flight duration of an aircraft may be perturbed, which implies that the planned strategic conflict-free 4D trajectories may not be executed strictly. As a result, the robustness of these trajectories becomes very important for dealing with perturbations. To evaluate the robustness of the planned strategic conflict-free 4D trajectories, two types of virtual perturbations are introduced: a departure-time perturbation and a flight duration perturbation between two conflicting waypoints.Suppose that the departure-time perturbation of aircrafta
(
k
) is Δ
u
(
k
); then the departure-time perturbation vector is Δ
U
0
=
[
0,0
,
…
,
Δ
u
(
k
)
,
…
,
0
]
T. Let U
^
0
=
U
0
⊗
Δ
U
0; then the propagation of the departure-time perturbation can be analyzed using (16), and the total arrival-time delay perturbation for aircraft queue can be calculated as Δ
Y
n
(
k
)
=
Y
n
′
(
k
)
-
Y
n
(
k
).Suppose that the flight duration perturbation for aircrafta
(
k
) in segment i is Δ
d
i
(
k
); then the flight duration perturbation vector Δ
D
i
=
[
0,0
,
…
,
Δ
d
i
(
k
)
,
…
,
0
]
T. Let U
^
i
=
Y
i
-
1
(
k
)
⊗
D
i
(
k
)
⊗
Δ
D
i
(
k
); then the propagation of the flight duration perturbation can similarly be analyzed by the max-plus algebra equation (19). Hence, the total arrival-time delay perturbation for aircraft queue can be calculated as Δ
Y
n
(
k
)
=
Y
n
′
(
k
)
-
Y
n
(
k
).


### 5.2. Slack Time Analysis of Conflict-Free 4D Trajectories

Given the total arrival-time delay perturbationΔ
Y
n
(
k
) for aircraft queue F, the metric of total flight delay for aircraft queue F can be obtained by(29)
C
K
Δ
u
k
,
Δ
d
i
k
=
β
·
Δ
Y
n
k
T
=
∑
k
=
1
K
β
k
·
Δ
y
n
k
,where β
=
[
β
1
,
β
2
,
…
,
β
K
] is a weight vector for total flight delay of each aircraft. Hence, the sensitivity of this metric to departure-time perturbation and flight-duration perturbation can be calculated as(30)
α
Δ
u
k
=
∂
C
K
Δ
u
k
,
Δ
d
i
k
∂
Δ
u
k
α
Δ
d
i
k
=
∂
C
K
Δ
u
k
,
Δ
d
i
k
∂
Δ
d
i
k
.A typical metric for total flight delay curve is shown in Figure13. Clearly, there are several perturbation intervals [
Δ
u
1
m
i
n
(
k
)
,
Δ
u
1
m
a
x
(
k
)
], [
Δ
u
2
m
i
n
(
k
)
,
Δ
u
2
m
a
x
(
k
)
], and [
Δ
u
3
m
i
n
(
k
)
,
Δ
u
3
m
a
x
(
k
)
] satisfying α
Δ
u
(
k
)
=
0, whereas α
Δ
u
(
k
)
>
0 for other intervals. For strategic conflict-free 4D trajectories, if a departure-time perturbation interval [
Δ
u
m
i
n
(
k
)
,
Δ
u
m
a
x
(
k
)
] satisfies α
Δ
u
(
k
)
=
0, that is, the total flight delay for aircraft queue F is not affected by the departure-time perturbation interval, the interval can be called a slack departure-time interval. Similarly, if a flight-duration perturbation interval [
Δ
d
i
m
i
n
(
k
)
,
Δ
d
i
m
a
x
(
k
)
] in segment i (i
<
n) satisfies α
Δ
d
i
(
k
)
=
0, which means that the total flight delay of aircraft queue F is not affected by the flight duration perturbation interval, this interval can be called a slack flight duration interval.Figure 13
Total flight delay metric for a departure-time perturbation.Obviously, the span of the slack departure time interval and the slack flight duration interval reflects the robustness of 4D conflict-free trajectory. Given an initial departure-time vectorU
0, the robustness index of the planned strategic conflict-free 4D trajectories Y
i
(
k
) can be expressed as follows:(31)
R
U
0
=
min
⁡
1
K
∑
k
=
1
K
β
k
·
Δ
u
m
a
x
k
-
Δ
u
m
i
n
k
,
1
K
∑
k
=
1
K
β
k
Δ
d
i
m
a
x
k
-
Δ
d
i
m
i
n
k
,
i
≤
n
.If there exist two initial departure time vectorsU
0
(
1
) and U
0
(
2
), and the robustness index satisfies R
(
U
0
(
1
)
)
=
0, then the planned strategic conflict-free 4D trajectories Y
i
(
1
)
(
k
) derived from the initial departure-time vector U
0
(
1
) are not robust at all. If the robustness index satisfies R
(
U
0
(
1
)
)
>
R
(
U
0
(
2
)
)
>
0, then the planned strategic conflict-free 4D trajectories Y
n
(
1
)
(
k
) derived from the initial departure-time vector U
0
(
1
) are more robust than those derived from U
0
(
2
).


## 5.1. Perturbation of 4D Trajectories and Its Propagation

For various reasons arising from navigation errors, meteorological influences, and human factors, the departure time and flight duration of an aircraft may be perturbed, which implies that the planned strategic conflict-free 4D trajectories may not be executed strictly. As a result, the robustness of these trajectories becomes very important for dealing with perturbations. To evaluate the robustness of the planned strategic conflict-free 4D trajectories, two types of virtual perturbations are introduced: a departure-time perturbation and a flight duration perturbation between two conflicting waypoints.Suppose that the departure-time perturbation of aircrafta
(
k
) is Δ
u
(
k
); then the departure-time perturbation vector is Δ
U
0
=
[
0,0
,
…
,
Δ
u
(
k
)
,
…
,
0
]
T. Let U
^
0
=
U
0
⊗
Δ
U
0; then the propagation of the departure-time perturbation can be analyzed using (16), and the total arrival-time delay perturbation for aircraft queue can be calculated as Δ
Y
n
(
k
)
=
Y
n
′
(
k
)
-
Y
n
(
k
).Suppose that the flight duration perturbation for aircrafta
(
k
) in segment i is Δ
d
i
(
k
); then the flight duration perturbation vector Δ
D
i
=
[
0,0
,
…
,
Δ
d
i
(
k
)
,
…
,
0
]
T. Let U
^
i
=
Y
i
-
1
(
k
)
⊗
D
i
(
k
)
⊗
Δ
D
i
(
k
); then the propagation of the flight duration perturbation can similarly be analyzed by the max-plus algebra equation (19). Hence, the total arrival-time delay perturbation for aircraft queue can be calculated as Δ
Y
n
(
k
)
=
Y
n
′
(
k
)
-
Y
n
(
k
).


## 5.2. Slack Time Analysis of Conflict-Free 4D Trajectories

Given the total arrival-time delay perturbationΔ
Y
n
(
k
) for aircraft queue F, the metric of total flight delay for aircraft queue F can be obtained by(29)
C
K
Δ
u
k
,
Δ
d
i
k
=
β
·
Δ
Y
n
k
T
=
∑
k
=
1
K
β
k
·
Δ
y
n
k
,where β
=
[
β
1
,
β
2
,
…
,
β
K
] is a weight vector for total flight delay of each aircraft. Hence, the sensitivity of this metric to departure-time perturbation and flight-duration perturbation can be calculated as(30)
α
Δ
u
k
=
∂
C
K
Δ
u
k
,
Δ
d
i
k
∂
Δ
u
k
α
Δ
d
i
k
=
∂
C
K
Δ
u
k
,
Δ
d
i
k
∂
Δ
d
i
k
.A typical metric for total flight delay curve is shown in Figure13. Clearly, there are several perturbation intervals [
Δ
u
1
m
i
n
(
k
)
,
Δ
u
1
m
a
x
(
k
)
], [
Δ
u
2
m
i
n
(
k
)
,
Δ
u
2
m
a
x
(
k
)
], and [
Δ
u
3
m
i
n
(
k
)
,
Δ
u
3
m
a
x
(
k
)
] satisfying α
Δ
u
(
k
)
=
0, whereas α
Δ
u
(
k
)
>
0 for other intervals. For strategic conflict-free 4D trajectories, if a departure-time perturbation interval [
Δ
u
m
i
n
(
k
)
,
Δ
u
m
a
x
(
k
)
] satisfies α
Δ
u
(
k
)
=
0, that is, the total flight delay for aircraft queue F is not affected by the departure-time perturbation interval, the interval can be called a slack departure-time interval. Similarly, if a flight-duration perturbation interval [
Δ
d
i
m
i
n
(
k
)
,
Δ
d
i
m
a
x
(
k
)
] in segment i (i
<
n) satisfies α
Δ
d
i
(
k
)
=
0, which means that the total flight delay of aircraft queue F is not affected by the flight duration perturbation interval, this interval can be called a slack flight duration interval.Figure 13
Total flight delay metric for a departure-time perturbation.Obviously, the span of the slack departure time interval and the slack flight duration interval reflects the robustness of 4D conflict-free trajectory. Given an initial departure-time vectorU
0, the robustness index of the planned strategic conflict-free 4D trajectories Y
i
(
k
) can be expressed as follows:(31)
R
U
0
=
min
⁡
1
K
∑
k
=
1
K
β
k
·
Δ
u
m
a
x
k
-
Δ
u
m
i
n
k
,
1
K
∑
k
=
1
K
β
k
Δ
d
i
m
a
x
k
-
Δ
d
i
m
i
n
k
,
i
≤
n
.If there exist two initial departure time vectorsU
0
(
1
) and U
0
(
2
), and the robustness index satisfies R
(
U
0
(
1
)
)
=
0, then the planned strategic conflict-free 4D trajectories Y
i
(
1
)
(
k
) derived from the initial departure-time vector U
0
(
1
) are not robust at all. If the robustness index satisfies R
(
U
0
(
1
)
)
>
R
(
U
0
(
2
)
)
>
0, then the planned strategic conflict-free 4D trajectories Y
n
(
1
)
(
k
) derived from the initial departure-time vector U
0
(
1
) are more robust than those derived from U
0
(
2
).


## 6. Simulation and Discussion

### 6.1. Simulated Case Study

Using the departing air traffic flow of the Shanghai terminal control area as our case study, as shown in Figure14, all conflicts can be divided into three categories: vertical crossing conflicts at POMOK, DADAT, and EKIMU between the aircraft queue from ZSSS airport and ZSPD airport to PIKAS, AND, and VMB, respectively; horizontal converging conflicts at waypoints OLGAP and NINAS from ZSSS airport and ZSPD airport to SX and RUXIL; and horizontal following conflicts at waypoints SX, PIKAS, ALDAP, AND, RUXIL, and VMB.Figure 14
Departing air traffic model of the Shanghai terminal control area.The departing air traffic model can be synthesized as shown in Figure15, where directional solid lines connecting two basic protection-zone conflict-control models denote the flight duration τ
i
,
j from waypoint i to waypoint j, whereas directional dashed lines denote only connecting relationships.Figure 15
Synthesized departing air traffic model of the Shanghai terminal area.Aircraft queueF
1 departing from ZSSS and F
2 departing from ZSPD to PIKAS via POMOK in Shanghai terminal area were chosen as the case study. This case includes two types of conflict-control models: the converging conflict-control model for POMOK and the vertical crossing conflict-control model for PIKAS, as shown in Figure 15.First, flight information for aircraft queuesF
1 (14 aircrafts departing from ZSSS) and F
2 (14 aircrafts departing from ZSPD) in two hours was extracted from flight plans of Shanghai terminal control area, as shown in Table 1.Table 1
Flight information for aircraft queues in two hours.
Aircraft number
Flight number
Aircraft type
Departure time
Departure airport
Arrival airport
A0001
CSH9363
B738
14:02
ZSPD
ZHHH
A0002
CES5147
B737
14:08
ZSSS
ZBTJ
A0003
CSN6534
A319
14:09
ZSPD
ZYTL
A0004
JAL8878
B763
14:11
ZSSS
ZBTJ
A0005
CES5403
A320
14:14
ZSPD
ZUUU
A0006
CES5113
A321
14:17
ZSSS
ZBAA
A0007
CES5633
B738
14:21
ZSSS
ZWWW
A0008
CDG4662
B738
14:24
ZSSS
ZSQD
A0009
CSH9201
B738
14:25
ZSPD
ZLXY
A0010
CES5553
A321
14:27
ZSSS
ZBSJ
A0011
CES5605
A319
14:27
ZSPD
ZYTX
A0012
CSH9197
B738
14:37
ZSSS
ZSQD
A0013
CES2287
B733
14:40
ZSSS
ZSWH
A0014
CSH9129
B738
14:47
ZSSS
ZBTJ
A0015
CSH9183
B738
15:00
ZSPD
ZYTX
A0016
CCA1558
B772
15:04
ZSSS
ZBAA
A0017
CSH9543
B738
15:04
ZSPD
ZUUU
A0018
CDG1164
B738
15:11
ZSSS
ZSJN
A0019
CES5625
A320
15:12
ZSPD
ZYTL
A0020
CES522
A320
15:14
ZSPD
ZLXY
A0021
CES5649
A320
15:31
ZSSS
ZSWH
A0022
CCA1949
A319
15:31
ZSPD
ZUUU
A0023
CSN6524
A321
15:35
ZSPD
ZYTL
A0024
CQH8850
A320
15:43
ZSPD
ZYTX
A0025
CSH9105
B763
15:45
ZSSS
ZBAA
A0026
CSN6506
A320
15:51
ZSPD
ZYTX
A0027
CSH823
B752
15:52
ZSSS
ZBAA
A0028
CES2506
B738
15:57
ZSPD
ZHHHThe converging conflict-control model for POMOK and the vertical crossing conflict-control model for PIKAS both can be treated as a special case of type I horizontal crossing protection zone thatα
=
0, β
=
0, θ
=
π, and δ
=
π. Let the minimum requirement of separation be d
m
i
n
(
1
)
=
10 km and d
m
i
n
(
2
)
=
6 km; thus the parameters of two special cases of type I horizontal crossing protection zone are listed in Table 2.Table 2
Parameters of two special cases of type I horizontal crossing protection zone.
Horizontal crossing protection zone
d
A
O, d
B
O (km)
d
O
C, d
O
D (km)
d
O
I, d
O
J (km)
d
O
K, d
O
L (km)
POMOK
10
10
6
6
PIKAS
10
10
6
6For simplicity, suppose that the ground speed of aircraft queuesF
1 and F
2 arriving at POMOK and PIKAS is about v
P
O
M
O
K
=
450 km/h and v
P
I
K
A
S
=
540 km/h, respectively. Hence, the sojourning time in the places of POMOK and PIKAS protection-zone conflict-control model are shown in Table 3.Table 3
The sojourning times in the places of two protection-zone conflict-control models.
Protection-zone conflict-control model
τ
A
O, τ
B
O (s)
τ
I
O, τ
K
O (s)
τ
O
C, τ
O
D (s)
τ
I
C, τ
K
D (s)
τ
A
C, τ
B
D (s)
τ
O
L, τ
O
J (s)
τ
I
L, τ
K
J (s)
τ
A
L, τ
B
J (s)
POMOK
80
48
80
128
160
48
96
128
PIKAS
66.7
40
66.7
106.7
133.3
40
80
106.7Table4 lists the 4D trajectories calculated from aircraft performance before deconfliction, where U
0 represents departure time of aircraft queues F
1 and F
2 and D
1 and D
2 represent the flight duration from departure to POMOK and the flight duration from POMOK to PIKAS. Suppose that the minimum unit of departure time and flight delay is one second; we develop a Java based solver to solve the optimization problem (26) and problem (28), which overloads operators “+” and “∗,” and Branch and Bound method is employed to optimize flight delay vector and initial departure delay vector. The flight delay vector W
1 based on arrival-time adjustment strategy and the adjusted departure time U
^
0 based on departure-time adjustment strategy are shown in Table 4. Y
1 and Y
2 represent the adjusted arrival time at POMOK and at PIKAS, respectively, for the synthesized departing air traffic model of POMKO and PIKAS after deconfliction, as shown in Table 4.Table 4
Parameters of synthesized converging and following conflict-control models.
Aircraft number
U
0 (s)
D
1 (s)
U
1 (s)
D
2 (s)
U
2 (s)
W
1 (s)
U
^
0 (s)
Y
1 (s)
Y
2 (s)
A0001
120
489
609
457
1066
0
120
609
1066
A0002
480
330
810
461
1271
0
480
810
1271
A0003
540
499
1039
443
1484
38
578
1077
1520
A0004
660
321
981
453
1434
0
660
981
1434
A0005
840
495
1335
443
1778
0
840
1335
1778
A0006
1020
328
1348
453
1848
83
1103
1431
1884
A0007
1260
327
1587
464
2051
4
1264
1591
2055
A0008
1440
327
1767
464
2231
0
1440
1767
2231
A0009
1500
489
1989
457
2465
55
1555
2044
2501
A0010
1620
328
1948
453
2401
0
1620
1948
2401
A0011
1620
499
2119
443
2562
85
1705
2204
2647
A0012
2220
327
2547
464
3011
0
2220
2547
3011
A0013
2400
323
2723
461
3184
0
2400
2723
3184
A0014
2820
327
3147
464
3611
0
2820
3147
3611
A0015
3600
489
4089
457
4546
0
3600
4089
4546
A0016
3840
340
4180
455
4635
5
3845
4185
4640
A0017
3840
489
4329
457
4786
0
3840
4329
4786
A0018
4260
327
4587
463
5050
0
4260
4587
5050
A0019
4320
495
4815
443
5258
0
4320
4815
5258
A0020
4440
495
4935
443
5378
40
4480
4975
5418
A0021
5460
334
5794
453
6247
0
5460
5794
6247
A0022
5460
499
5959
443
6402
0
5460
5959
6402
A0023
5700
489
6189
443
6632
0
5700
6189
6632
A0024
6180
495
6175
443
7124
42
6222
6717
7160
A0025
6300
321
6621
453
7074
0
6300
6621
7074
A0026
6660
495
7155
443
7598
0
6660
7155
7598
A0027
6720
309
7029
465
7494
0
6720
7029
7494
A0028
7020
489
7509
457
7966
0
7020
7509
7966The separations between two adjacent aircrafts arriving at POMOK and PIKAS before and after deconfliction are shown in Figures16 and 17, respectively. According to Figures 16 and 17, the separation for pairs of aircrafts (A0003, A0004), (A0005, A0006), (A0009, A0010), and (A0024, A0025) before deconfliction is less than the minimum separation requirements. After deconfliction, the departure times or arrival times at POMOK for A0003, A0006, A0009, A0011, A0016, A0020, and A0024 aircraft are delayed by 38 s, 83 s, 4 s, 55 s, 85 s, 5 s, 40 s, and 42 s to avoid conflicts, respectively; thus, the separation between each pair of adjacent aircrafts satisfies the minimum separation requirements, which demonstrates that the planned strategic deconfliction based on both departure-time adjustment strategy and arrival-time adjustment strategy could avoid potential conflicts effectively.Figure 16
Separation between two adjacent aircrafts arriving at POMOK.Figure 17
Separation between two adjacent aircrafts arriving at PIKAS.In addition, to analyze the robustness of the planned strategic conflict-free 4D trajectories, the departure-time perturbation analysis with two different minimum requirements of separation settings was investigated, where the first separation setting wasd
m
i
n
(
1
)
=
10 km and d
m
i
n
(
2
)
=
6 km and the second was d
m
i
n
(
1
)
=
15 km and d
m
i
n
(
2
)
=
9 km. The slack departure-time intervals for the aircraft queue are shown in Figure 18. Hence, the robustness index of the planned strategic conflict-free 4D trajectories can be calculated as R
(
U
^
0
)
=
134.1 s and R
(
U
^
0
′
)
=
73.4 s using (31), respectively. R
(
U
0
)
>
R
(
U
0
′
) shows that increasing the minimum requirement of separation will reduce the slack departure-time interval for the aircraft queue, which implies that increasing the safety margin may lead to the reduction of the robustness of the planned strategic conflict-free 4D trajectories so that setting reasonable minimum requirement of separation can also balance the safety margin and the stability of air traffic flow.Figure 18
Slack departure-time intervals with two different minimum requirements of separations.In addition, we developed an Air Traffic Control and Automation Simulating System (ATCASS) to refine and validate the planned strategic conflict-free 4D trajectory. By loading the planned strategic 4D conflict-free trajectories, ATTSS can sample the 4D trajectory with any given sampling period and generate 4D conflict-free trajectory points according to airway model, aircraft performance model, and aircraft speed profile. As shown in Figure19, up to 280 aircrafts departing from or landing at ZSSS and ZSPD in 2 hours were simulated. We employed the arriving time adjustment strategy to plan the conflict-free trajectory and set the sampling period as 4 s.Figure 19
4D trajectory simulating for Shanghai terminal control area.To investigate the relationship between the number of aircrafts in queues and the performance of deconfliction, we simulated three scenarios using ATCASS. The first scenario loaded only the planned strategic 4D conflict-free trajectories for the first 200 aircrafts, the second loaded that for the first 240 aircrafts, and the third loaded that for all 280 aircrafts. We recorded and analyzed the mean value and the standard deviation of separation between the two adjacent aircrafts in landing and departing aircraft queues, as shown in Figure20. In addition, we calculated the mean flight delay for aircraft landing at ZSPD and ZSSS and departing from ZSPD and ZSSS, respectively, as shown in Figure 21.Figure 20
Statistics of separation for three scenarios.Figure 21
Statistics of flight delay for three scenarios.The simulated results show that the mean value and standard deviation of separation between two adjacent aircrafts in landing and departing aircraft queues decrease with the increasing number of aircrafts, and the mean flight delay increases with the increasing number of aircrafts, which implies that the distribution of separation between two adjacent aircrafts becomes smoother after deconfliction; thus, the efficiency of airspace can be improved to some extent. Moreover, the number of conflicts and total flight delay are obviously positively related, but strategic deconfliction of 4D based on arriving time adjustment strategy is not very helpful for reduction of flight delay.


### 6.2. Computational Complexity Analysis

As mentioned, the computational complexity of departure-time adjustment strategy based on constraint programming proposed by Barnier [13] is related to the total number of aircrafts n
A and the number of sampling points n
P in each trajectory. In this optimization method, the trajectories are pairwise probed for couples of conflicting waypoints; hence the computational complexity for conflict detection should be O
(
n
A
2
·
n
P
2
), where n
A
2 represents the complexity of probing whether aircrafts conflict with each other and n
P
2 represents the complexity of probing two sampling points from each potential trajectory. During conflict resolution, the branching scheme of search strategy is employed, whose computational complexity is O
(
2
n
C
), where n
C represents the number of conflicts.The computational complexity of mixed-integer nonlinear programming for deconfliction based on speed regulation proposed in reference [18] is related to the number of time horizons n
H, the number of conflicting zones n
Z, and the radius of the circle representing the considered airspace R. The conflicting zone lies around the center of the circle where aircrafts are placed, and aircrafts may be in conflict with each other. Hence, the computational complexity for conflict probing should be O
(
n
H
·
n
Z
·
n
R
(
n
R
-
1
)
/
2
)
=
O
(
n
H
·
n
A
·
(
n
R
-
1
)
/
2
), where n
R
=
ρ
π
R
2 represents the number of aircrafts in conflicting zone, n
R
(
n
R
-
1
)
/
2 represents the number of potential conflicts in conflicting zone, and n
A
=
n
Z
·
n
R represents the total number of aircrafts. During conflict resolution using spatial Branch and Bound algorithm, the computational complexity is O
(
n
H
·
2
n
R
C
), where n
R
C represents the number of conflicts in conflicting zone.According to (22), the computational complexity of the proposed strategic conflict-free 4D trajectory planning method is related to the number of conflicting waypoints n
W and the number of aircrafts n
Q in the queue. Because the stated equation is a linear equation under the definition of max plus algebra, the computational complexity for conflict detection is O
(
n
W
·
n
Q
(
n
Q
-
1
)
/
2
), where n
Q
(
n
Q
-
1
)
/
2 represents the possible queue sequencings according to their arrival time at a conflicting waypoint. During conflict resolution using optimization problems (26) and (28), the computational complexity is O
(
2
n
Q
C
) and O
(
n
W
·
2
n
Q
C
), respectively, where n
Q
C represents the number of conflicts in the queue.Table5 shows a comparison of computational complexities of constraint programming, mixed-integer nonlinear programming, and max-plus algebra planning. It shows that n
C
≫
n
R
C
>
n
Q
C and n
W
·
2
n
Q
C
<
n
H
·
2
n
R
C
≪
2
n
C for strategic deconfliction of trajectory with large number of potential conflicts, further demonstrating that max-plus algebra is more suitable for deconfliction of 4D trajectory with random sampling period in fix air route.Table 5
Comparison of computational complexities of different methods.
Method
Conflict detection
Conflict resolution
Constraint programming
O
(
n
A
2
⋅
n
P
2
)
O
(
2
n
C
)
Mixed-integer programming
O
(
n
H
⋅
n
A
⋅
(
n
R
-
1
)
/
2
)
O
(
n
H
⋅
2
n
R
C
)
Max-plus algebra planning
O
(
n
W
⋅
n
Q
(
n
Q
-
1
)
/
2
)
O
(
2
n
Q
C
) or O
(
n
W
⋅
2
n
Q
C
)


## 6.1. Simulated Case Study

Using the departing air traffic flow of the Shanghai terminal control area as our case study, as shown in Figure14, all conflicts can be divided into three categories: vertical crossing conflicts at POMOK, DADAT, and EKIMU between the aircraft queue from ZSSS airport and ZSPD airport to PIKAS, AND, and VMB, respectively; horizontal converging conflicts at waypoints OLGAP and NINAS from ZSSS airport and ZSPD airport to SX and RUXIL; and horizontal following conflicts at waypoints SX, PIKAS, ALDAP, AND, RUXIL, and VMB.Figure 14
Departing air traffic model of the Shanghai terminal control area.The departing air traffic model can be synthesized as shown in Figure15, where directional solid lines connecting two basic protection-zone conflict-control models denote the flight duration τ
i
,
j from waypoint i to waypoint j, whereas directional dashed lines denote only connecting relationships.Figure 15
Synthesized departing air traffic model of the Shanghai terminal area.Aircraft queueF
1 departing from ZSSS and F
2 departing from ZSPD to PIKAS via POMOK in Shanghai terminal area were chosen as the case study. This case includes two types of conflict-control models: the converging conflict-control model for POMOK and the vertical crossing conflict-control model for PIKAS, as shown in Figure 15.First, flight information for aircraft queuesF
1 (14 aircrafts departing from ZSSS) and F
2 (14 aircrafts departing from ZSPD) in two hours was extracted from flight plans of Shanghai terminal control area, as shown in Table 1.Table 1
Flight information for aircraft queues in two hours.
Aircraft number
Flight number
Aircraft type
Departure time
Departure airport
Arrival airport
A0001
CSH9363
B738
14:02
ZSPD
ZHHH
A0002
CES5147
B737
14:08
ZSSS
ZBTJ
A0003
CSN6534
A319
14:09
ZSPD
ZYTL
A0004
JAL8878
B763
14:11
ZSSS
ZBTJ
A0005
CES5403
A320
14:14
ZSPD
ZUUU
A0006
CES5113
A321
14:17
ZSSS
ZBAA
A0007
CES5633
B738
14:21
ZSSS
ZWWW
A0008
CDG4662
B738
14:24
ZSSS
ZSQD
A0009
CSH9201
B738
14:25
ZSPD
ZLXY
A0010
CES5553
A321
14:27
ZSSS
ZBSJ
A0011
CES5605
A319
14:27
ZSPD
ZYTX
A0012
CSH9197
B738
14:37
ZSSS
ZSQD
A0013
CES2287
B733
14:40
ZSSS
ZSWH
A0014
CSH9129
B738
14:47
ZSSS
ZBTJ
A0015
CSH9183
B738
15:00
ZSPD
ZYTX
A0016
CCA1558
B772
15:04
ZSSS
ZBAA
A0017
CSH9543
B738
15:04
ZSPD
ZUUU
A0018
CDG1164
B738
15:11
ZSSS
ZSJN
A0019
CES5625
A320
15:12
ZSPD
ZYTL
A0020
CES522
A320
15:14
ZSPD
ZLXY
A0021
CES5649
A320
15:31
ZSSS
ZSWH
A0022
CCA1949
A319
15:31
ZSPD
ZUUU
A0023
CSN6524
A321
15:35
ZSPD
ZYTL
A0024
CQH8850
A320
15:43
ZSPD
ZYTX
A0025
CSH9105
B763
15:45
ZSSS
ZBAA
A0026
CSN6506
A320
15:51
ZSPD
ZYTX
A0027
CSH823
B752
15:52
ZSSS
ZBAA
A0028
CES2506
B738
15:57
ZSPD
ZHHHThe converging conflict-control model for POMOK and the vertical crossing conflict-control model for PIKAS both can be treated as a special case of type I horizontal crossing protection zone thatα
=
0, β
=
0, θ
=
π, and δ
=
π. Let the minimum requirement of separation be d
m
i
n
(
1
)
=
10 km and d
m
i
n
(
2
)
=
6 km; thus the parameters of two special cases of type I horizontal crossing protection zone are listed in Table 2.Table 2
Parameters of two special cases of type I horizontal crossing protection zone.
Horizontal crossing protection zone
d
A
O, d
B
O (km)
d
O
C, d
O
D (km)
d
O
I, d
O
J (km)
d
O
K, d
O
L (km)
POMOK
10
10
6
6
PIKAS
10
10
6
6For simplicity, suppose that the ground speed of aircraft queuesF
1 and F
2 arriving at POMOK and PIKAS is about v
P
O
M
O
K
=
450 km/h and v
P
I
K
A
S
=
540 km/h, respectively. Hence, the sojourning time in the places of POMOK and PIKAS protection-zone conflict-control model are shown in Table 3.Table 3
The sojourning times in the places of two protection-zone conflict-control models.
Protection-zone conflict-control model
τ
A
O, τ
B
O (s)
τ
I
O, τ
K
O (s)
τ
O
C, τ
O
D (s)
τ
I
C, τ
K
D (s)
τ
A
C, τ
B
D (s)
τ
O
L, τ
O
J (s)
τ
I
L, τ
K
J (s)
τ
A
L, τ
B
J (s)
POMOK
80
48
80
128
160
48
96
128
PIKAS
66.7
40
66.7
106.7
133.3
40
80
106.7Table4 lists the 4D trajectories calculated from aircraft performance before deconfliction, where U
0 represents departure time of aircraft queues F
1 and F
2 and D
1 and D
2 represent the flight duration from departure to POMOK and the flight duration from POMOK to PIKAS. Suppose that the minimum unit of departure time and flight delay is one second; we develop a Java based solver to solve the optimization problem (26) and problem (28), which overloads operators “+” and “∗,” and Branch and Bound method is employed to optimize flight delay vector and initial departure delay vector. The flight delay vector W
1 based on arrival-time adjustment strategy and the adjusted departure time U
^
0 based on departure-time adjustment strategy are shown in Table 4. Y
1 and Y
2 represent the adjusted arrival time at POMOK and at PIKAS, respectively, for the synthesized departing air traffic model of POMKO and PIKAS after deconfliction, as shown in Table 4.Table 4
Parameters of synthesized converging and following conflict-control models.
Aircraft number
U
0 (s)
D
1 (s)
U
1 (s)
D
2 (s)
U
2 (s)
W
1 (s)
U
^
0 (s)
Y
1 (s)
Y
2 (s)
A0001
120
489
609
457
1066
0
120
609
1066
A0002
480
330
810
461
1271
0
480
810
1271
A0003
540
499
1039
443
1484
38
578
1077
1520
A0004
660
321
981
453
1434
0
660
981
1434
A0005
840
495
1335
443
1778
0
840
1335
1778
A0006
1020
328
1348
453
1848
83
1103
1431
1884
A0007
1260
327
1587
464
2051
4
1264
1591
2055
A0008
1440
327
1767
464
2231
0
1440
1767
2231
A0009
1500
489
1989
457
2465
55
1555
2044
2501
A0010
1620
328
1948
453
2401
0
1620
1948
2401
A0011
1620
499
2119
443
2562
85
1705
2204
2647
A0012
2220
327
2547
464
3011
0
2220
2547
3011
A0013
2400
323
2723
461
3184
0
2400
2723
3184
A0014
2820
327
3147
464
3611
0
2820
3147
3611
A0015
3600
489
4089
457
4546
0
3600
4089
4546
A0016
3840
340
4180
455
4635
5
3845
4185
4640
A0017
3840
489
4329
457
4786
0
3840
4329
4786
A0018
4260
327
4587
463
5050
0
4260
4587
5050
A0019
4320
495
4815
443
5258
0
4320
4815
5258
A0020
4440
495
4935
443
5378
40
4480
4975
5418
A0021
5460
334
5794
453
6247
0
5460
5794
6247
A0022
5460
499
5959
443
6402
0
5460
5959
6402
A0023
5700
489
6189
443
6632
0
5700
6189
6632
A0024
6180
495
6175
443
7124
42
6222
6717
7160
A0025
6300
321
6621
453
7074
0
6300
6621
7074
A0026
6660
495
7155
443
7598
0
6660
7155
7598
A0027
6720
309
7029
465
7494
0
6720
7029
7494
A0028
7020
489
7509
457
7966
0
7020
7509
7966The separations between two adjacent aircrafts arriving at POMOK and PIKAS before and after deconfliction are shown in Figures16 and 17, respectively. According to Figures 16 and 17, the separation for pairs of aircrafts (A0003, A0004), (A0005, A0006), (A0009, A0010), and (A0024, A0025) before deconfliction is less than the minimum separation requirements. After deconfliction, the departure times or arrival times at POMOK for A0003, A0006, A0009, A0011, A0016, A0020, and A0024 aircraft are delayed by 38 s, 83 s, 4 s, 55 s, 85 s, 5 s, 40 s, and 42 s to avoid conflicts, respectively; thus, the separation between each pair of adjacent aircrafts satisfies the minimum separation requirements, which demonstrates that the planned strategic deconfliction based on both departure-time adjustment strategy and arrival-time adjustment strategy could avoid potential conflicts effectively.Figure 16
Separation between two adjacent aircrafts arriving at POMOK.Figure 17
Separation between two adjacent aircrafts arriving at PIKAS.In addition, to analyze the robustness of the planned strategic conflict-free 4D trajectories, the departure-time perturbation analysis with two different minimum requirements of separation settings was investigated, where the first separation setting wasd
m
i
n
(
1
)
=
10 km and d
m
i
n
(
2
)
=
6 km and the second was d
m
i
n
(
1
)
=
15 km and d
m
i
n
(
2
)
=
9 km. The slack departure-time intervals for the aircraft queue are shown in Figure 18. Hence, the robustness index of the planned strategic conflict-free 4D trajectories can be calculated as R
(
U
^
0
)
=
134.1 s and R
(
U
^
0
′
)
=
73.4 s using (31), respectively. R
(
U
0
)
>
R
(
U
0
′
) shows that increasing the minimum requirement of separation will reduce the slack departure-time interval for the aircraft queue, which implies that increasing the safety margin may lead to the reduction of the robustness of the planned strategic conflict-free 4D trajectories so that setting reasonable minimum requirement of separation can also balance the safety margin and the stability of air traffic flow.Figure 18
Slack departure-time intervals with two different minimum requirements of separations.In addition, we developed an Air Traffic Control and Automation Simulating System (ATCASS) to refine and validate the planned strategic conflict-free 4D trajectory. By loading the planned strategic 4D conflict-free trajectories, ATTSS can sample the 4D trajectory with any given sampling period and generate 4D conflict-free trajectory points according to airway model, aircraft performance model, and aircraft speed profile. As shown in Figure19, up to 280 aircrafts departing from or landing at ZSSS and ZSPD in 2 hours were simulated. We employed the arriving time adjustment strategy to plan the conflict-free trajectory and set the sampling period as 4 s.Figure 19
4D trajectory simulating for Shanghai terminal control area.To investigate the relationship between the number of aircrafts in queues and the performance of deconfliction, we simulated three scenarios using ATCASS. The first scenario loaded only the planned strategic 4D conflict-free trajectories for the first 200 aircrafts, the second loaded that for the first 240 aircrafts, and the third loaded that for all 280 aircrafts. We recorded and analyzed the mean value and the standard deviation of separation between the two adjacent aircrafts in landing and departing aircraft queues, as shown in Figure20. In addition, we calculated the mean flight delay for aircraft landing at ZSPD and ZSSS and departing from ZSPD and ZSSS, respectively, as shown in Figure 21.Figure 20
Statistics of separation for three scenarios.Figure 21
Statistics of flight delay for three scenarios.The simulated results show that the mean value and standard deviation of separation between two adjacent aircrafts in landing and departing aircraft queues decrease with the increasing number of aircrafts, and the mean flight delay increases with the increasing number of aircrafts, which implies that the distribution of separation between two adjacent aircrafts becomes smoother after deconfliction; thus, the efficiency of airspace can be improved to some extent. Moreover, the number of conflicts and total flight delay are obviously positively related, but strategic deconfliction of 4D based on arriving time adjustment strategy is not very helpful for reduction of flight delay.


## 6.2. Computational Complexity Analysis

As mentioned, the computational complexity of departure-time adjustment strategy based on constraint programming proposed by Barnier [13] is related to the total number of aircrafts n
A and the number of sampling points n
P in each trajectory. In this optimization method, the trajectories are pairwise probed for couples of conflicting waypoints; hence the computational complexity for conflict detection should be O
(
n
A
2
·
n
P
2
), where n
A
2 represents the complexity of probing whether aircrafts conflict with each other and n
P
2 represents the complexity of probing two sampling points from each potential trajectory. During conflict resolution, the branching scheme of search strategy is employed, whose computational complexity is O
(
2
n
C
), where n
C represents the number of conflicts.The computational complexity of mixed-integer nonlinear programming for deconfliction based on speed regulation proposed in reference [18] is related to the number of time horizons n
H, the number of conflicting zones n
Z, and the radius of the circle representing the considered airspace R. The conflicting zone lies around the center of the circle where aircrafts are placed, and aircrafts may be in conflict with each other. Hence, the computational complexity for conflict probing should be O
(
n
H
·
n
Z
·
n
R
(
n
R
-
1
)
/
2
)
=
O
(
n
H
·
n
A
·
(
n
R
-
1
)
/
2
), where n
R
=
ρ
π
R
2 represents the number of aircrafts in conflicting zone, n
R
(
n
R
-
1
)
/
2 represents the number of potential conflicts in conflicting zone, and n
A
=
n
Z
·
n
R represents the total number of aircrafts. During conflict resolution using spatial Branch and Bound algorithm, the computational complexity is O
(
n
H
·
2
n
R
C
), where n
R
C represents the number of conflicts in conflicting zone.According to (22), the computational complexity of the proposed strategic conflict-free 4D trajectory planning method is related to the number of conflicting waypoints n
W and the number of aircrafts n
Q in the queue. Because the stated equation is a linear equation under the definition of max plus algebra, the computational complexity for conflict detection is O
(
n
W
·
n
Q
(
n
Q
-
1
)
/
2
), where n
Q
(
n
Q
-
1
)
/
2 represents the possible queue sequencings according to their arrival time at a conflicting waypoint. During conflict resolution using optimization problems (26) and (28), the computational complexity is O
(
2
n
Q
C
) and O
(
n
W
·
2
n
Q
C
), respectively, where n
Q
C represents the number of conflicts in the queue.Table5 shows a comparison of computational complexities of constraint programming, mixed-integer nonlinear programming, and max-plus algebra planning. It shows that n
C
≫
n
R
C
>
n
Q
C and n
W
·
2
n
Q
C
<
n
H
·
2
n
R
C
≪
2
n
C for strategic deconfliction of trajectory with large number of potential conflicts, further demonstrating that max-plus algebra is more suitable for deconfliction of 4D trajectory with random sampling period in fix air route.Table 5
Comparison of computational complexities of different methods.
Method
Conflict detection
Conflict resolution
Constraint programming
O
(
n
A
2
⋅
n
P
2
)
O
(
2
n
C
)
Mixed-integer programming
O
(
n
H
⋅
n
A
⋅
(
n
R
-
1
)
/
2
)
O
(
n
H
⋅
2
n
R
C
)
Max-plus algebra planning
O
(
n
W
⋅
n
Q
(
n
Q
-
1
)
/
2
)
O
(
2
n
Q
C
) or O
(
n
W
⋅
2
n
Q
C
)


## 7. Conclusions and Future Work

In this paper, to resolve potential conflicts during strategic 4D conflict-free trajectory planning, a protection-zone conflict-control model was established according to air traffic control separation constraints. Relationships between expected arrival time and adjusted arrival time at conflicting waypoints for aircraft queue were built and transformed into dynamic linear equations under the definition of max-plus algebra. On this basis, a strategic deconfliction of 4D trajectory method was proposed using two strategies: arrival time adjustment and departure time adjustment. Perturbations in departure time and flight duration were introduced to analyze the robustness of the adjusted 4D trajectory, and a robustness index for conflict-free 4D trajectory was proposed as well.Results from the simulated case with a real air traffic flight plan show that the separation between each pair of adjacent aircrafts satisfies the minimum separation requirements, which demonstrated that the planned strategic deconfliction based on both departure time adjustment strategy and arrival time adjustment strategy can avoid potential conflicts effectively. In addition, perturbation analysis shows that increasing the minimum requirement of separation will reduce the slack departure time interval for aircraft queues. Computational complexity analysis demonstrated that deconfliction by max-plus algebra planning is more suitable for deconfliction of 4D trajectory with random sampling period in fix air route.In this research, it has been assumed that all conflict-control models are connected in a series (without fork and join), and, therefore, the synthesized air traffic model can be described uniformly and calculated recursively. However, for an actual complex airspace, conflict-control models could be cross-connected. Such problems will be tackled in our future work.



---

*Source: 7028305-2016-09-25.xml*