conflicts in terms of the flight phase of each aircraft involved in the
conflict.
The study focused on the en route environment because almost
two-thirds of real operational conflicts occurred when both aircraft
were in the cruise phase. By considering only those conflicts in which
both aircraft were in the cruise phase, we detected an average of 250
conflicts per day. This gave a total of 18,000 conflicts over the entire
period.
2.
Conflict Resolution Based on Historical Data
To identify the resolution applied by the controllers to each conflict
in the dataset, we defined a set of criteria to assess the adherence of the
actual trajectory flown (radar track) to the theoretical trajectory as
given by the flight plan. The criteria, set out in Eqs. (4) and (5), were
used to classify the conflict-resolution maneuvers (temporal or
vertical) performed by the controller.
The histograms in Fig. 13 give the breakdown of the temporal
and vertical deviations of the conflicts. As previously explained,
horizontal conflict-resolution actions are not included in
the model.
Any conflict with a vertical deviation of within 1000 ft will not
be resolved vertically. However, it is not easy to determine the
temporal deviation limit below which a conflict will not be solved
temporally, as this will depend on the aircraft involved in the conflict.
Thus, every temporal deviation is considered when developing the
temporal conflict-resolution model. However, when the model is
applied, if the temporal maneuver does not solve the conflict, it is not
considered a potential optimal resolution.
In Fig. 13a, a negative value of temporal resolution means that the
flight passes over the geometric point where the conflict was detected
(GPC) later than the estimated time, whereas a positive value means
that it passes over the point earlier than predicted. In Fig. 13b, a
negative value of vertical resolution means that the flight passes
below at the time when the conflict was detected (TC), whereas a
positive value means that it passes over at the TC.
3.
Development of Model
Figure 14 gives the histograms of the temporal deviation as a
function of the relationship between the trajectories of the aircraft
involved in the conflict. The most common temporal resolutions are
those with a small temporal deviation.
We applied the k-means algorithm to the histograms in order to
detect k clusters. The cluster centroids are indicated in Fig. 14,
reflecting the highest density regions.
Table 3
Breakdown of vertical deviation of conflicts as a function of relationship
between aircraft
Same track
Crossing tracks
(45
–90 deg)
Crossing tracks
(90
–135 deg)
Reciprocal track
Feet
% Conflicts
Feet
% Conflicts
Feet
% Conflicts
Feet
% Conflicts
−10;000
0.3
−11;000
0.4
−7;000
0.7
−7;000
0.2
−7;000
0.5
−9;000
0.5
−6;000
1.1
−6;000
0.4
−6;000
0.8
−7;000
0.4
−4;000
3.0
−5;000
0.8
−5;000
0.4
−6;000
0.5
−3;000
0.5
−4;000
1.6
−4;000
1.6
−5;000
1.0
−2;000
6.8
−3;000
1.1
−3;000
1.0
−4;000
2.4
−1;000
4.2
−2;000
6.0
−2;000
8.9
−3;000
1.8
1,000
2.2
−1;000
2.0
−1;000
2.8
−2;000
12.0
2,000
7.8
1,000
1.8
1,000
0.9
−1;000
6.7
4,000
0.6
2,000
11.7
2,000
9.4
1,000
1.1
6,000
0.4
3,000
0.4
4,000
1.2
2,000
5.8
13,000
0.4
4,000
1.1
6,000
0.3
4,000
0.6
14,000
0.4
6,000
0.2
0
50
100
150
200
250
300
0
1
2
3
4
5
6
1
4
8
13
19
27
36
47
63
79
102
121
147
183
261
tan ( )
Frequency (%)
Fig. 16
Breakdown of Pareto frontier slopes for all conflicts in the study.
Additional fuel (kg)
-20
-15
-10
-5
0
5
x 10
3
tan( )
1
tan( )
4
tan( )
8
tan( )
13
tan( )
19
tan( )
27
tan( )
36
tan( )
47
tan( )
63
tan( )
79
tan( )
102
tan( )
121
tan( )
147
tan( )
183
Maximum
likelihood
Minimum
fuel
tan( )
261
Fig. 17
Daily additional fuel consumed as a function of different criteria.
624
CALVO-FERNÁNDEZ ET AL.
Downloaded by UNIV. OF ARIZONA on March 14, 2017 | http://arc.aiaa.org | DOI: 10.2514/1.G000691
Table 2 gives the breakdown of temporal deviation of conflicts as a
function of the relationship between the trajectories of the aircraft
involved in the conflict. Thus, the model gives a discrete number of
temporal resolutions with the corresponding likelihood based on
actual controller performance. The discrete number of temporal
resolutions is equal to the number of centroids.
Figure 15 gives the vertical deviation as a function of the relationship
between the trajectories of the aircraft involved in the conflict.
We applied the k-means algorithm to the histograms and, once
again, the centroids are shown. The vertical conflict-resolution model
(Table 3) gives a discrete number of vertical resolutions with the
corresponding likelihood of their being implemented.
This model was specifically developed for use in the operational
scenario described. It would need to be tested further to ensure its
applicability to different environments, with similar conflict-
resolution protocols.
B.
Multiobjective Optimization of Proposed Solutions
The conflict-resolution model was applied to the conflicts detected
in the strategic phase (over 48 randomly selected days), resulting in a
set of potential resolutions per conflict. We used the
ε-constraint
method to detect the Pareto frontier for each particular conflict.
We then populated a number of optimal solutions along the
Pareto frontiers of each conflict to find the global optimal solution
for all the conflicts. As mentioned in Sec. II.E, there are
intermediate solutions between the solutions that satisfy the
requirement for minimum fuel and maximum likelihood of ATC
resolution. We used Pareto frontiers slopes (tan
α) to populate the
intermediate solutions.
Figure 16 shows the histogram with the Pareto frontiers slopes for
all conflicts. This enabled us to choose the values of tan
α used in this
study to populate a number of intermediate solutions along the Pareto
frontiers.
The next step was to apply the k-means algorithm to the histogram.
The centroids detected were used as the values of tan
α to populate a
number of intermediate solutions along the Pareto frontiers of each
conflict.
Then, we applied minimum fuel consumption, maximum
likelihood of ATC resolution, and the intermediate criteria by setting
the values of tan
α. The fits of the results after applying each criterion
are represented in Figs. 17 and 18.
Figure 17 shows the daily additional fuel consumed after applying
the aforementioned criteria to solve the conflicts.
The continental Spain FIR is divided into a number of sectors, and
each one is assigned to an active control working position. To analyze
the fit of the likelihood of ATC resolution, we calculated the
occupancy (number of aircraft) of each sector. This was done using
time intervals of 5 min.
We also calculated the occupancy of the most congested sector for
each interval and each criterion. Using optimal flow management, we
could reduce the occupancy of the most congested sectors, thereby
reducing congestion, and consequently the controller
’s workload.
By incorporating efficient ATC practices to the model, it is safe to
assume that the greater the likelihood of ATC resolution, the more
homogeneous the flow distribution.
Figure 18 gives the percentage of intervals in which the most
congested sector (for each criterion) has a greater occupancy than the
most congested sector when the criterion is the maximum likelihood
of ATC resolution. From the figure, it is clear that, when the criterion
is closer to the maximum likelihood of ATC resolution, the number of
congested sectors is reduced, as is the controller
’s workload.
By converting the quantities used in both cases to a common unit of
measure, we can obtain the overall optimal solution. For example, in
Fig. 17, the kilograms of additional fuel consumed are easily
converted to monetary units. Similarly, in Fig. 18, we may be able to
assign some financial cost to or benefit from an increase or decrease
in congestion. The resulting conflict-free plan would be the global
optimal solution: in other words, the one that best balances the needs
of all the actors in the ATM system.
IV.
Conclusions
This study proposes a methodology for conflict-free planning
using a data-driven approach. The model is built with 72 days of
operational data from the continental Spain flight information
region. This contained information on the conflict-resolution
actions, in the tactical phase of more than 300,000 flights, taken by
air traffic controllers. The methodology is consistent with a
reference business trajectory scenario in which conflict-free planning
is addressed.
This methodology is divided into three processes: the first process
develops the data-driven conflict-resolution model. This is applied, in
the strategic phase, to a specific traffic forecast. Finally, we identify
the optimal solution using a multiobjective optimization.
The data-driven air traffic control model allows incorporation of
ATC expertise into the conflict-resolution models. This avoids the
need for specific conflict-resolution algorithms. A benefit of this
approach is that the data-driven methodology is able to incorporate
new operational procedures, due to the fact that they are intrinsically
contained within the operational data used to generate or update
the model.
The model balances the (sometimes competing) needs of the
different actors in the ATM system. In particular, it attempts to
provide more efficient air traffic flow management to the benefit of
the air navigation service providers. The main benefit to the ANSPs is
the reduction in the number of conflicts during the strategic phase. By
applying the conflict-resolution model in the strategic phase, an 85%
reduction in conflicts can be achieved as compared with the original
flight plan. In the en route sectors of the continental Spain FIR,
workload studies have shown that 15
–30% of control actions were
due to conflict resolution. It is, therefore, safe to say that, by using a
plan in which conflicts are considerably reduced, an increase in
capacity can be expected. In other words, there will be fewer tactical
resolution actions and an increase in less labor-intensive activities,
such as monitoring.
The model also takes the airlines
’ perspective into account by
permitting tradeoffs between competing criteria via a multi-
objective
optimization
process.
Specifically,
the
airlines
’
perspective is taken into account through the use of the minimum
fuel consumption criterion when resolving conflicts. By focusing
on minimum fuel consumption rather than trying to maximize the
% Intervals
0
2
4
6
8
1
additional aircraft
2 additional aircraft
3 additional aircraft
tan( )
1
tan( )
4
tan( )
8
tan( )
13
tan( )
19
tan( )
27
tan( )
36
tan( )
47
tan( )
63
tan( )
79
tan( )
102
tan( )
121
tan( )
147
tan( )
183
Maximum
likelihood
Minimum
fuel
tan( )
261
Fig. 18
Breakdown of intervals with additional aircraft in the most congested sectors as a function of different criteria compared with the criterion of the
maximum likelihood of ATC resolution.
CALVO-FERNÁNDEZ ET AL.
625
Downloaded by UNIV. OF ARIZONA on March 14, 2017 | http://arc.aiaa.org | DOI: 10.2514/1.G000691
likelihood of ATC resolution, it is possible to achieve a 0.35%
reduction in the fuel consumed, which equates to a savings of more
than 20 ton (ton refers metric tons) of fuel each day within the
continental Spain FIR cruise phase.
The incorporation of multiobjective criteria into the planning
phase is a significant step forward in the implementation of
trajectory-based operations and extended ATC planning within a
reference business trajectory/shared business trajectory scenario.
Acknowledgment
All the calculations carried out in this study are available from the
authors on request by sending an email to the addresses provided.
References
[1] SESAR Joint Undertaking,
“European ATM Master Plan: The Roadmap
for Delivering High Performing Aviation for Europe: Executive View:
Edition 2015,
” Bruxelles, Feb. 2016.
doi:10.2829/240873
[2] Isaacson, D., and Robinson, J.,
“A Knowledge-Based Conflict
Resolution Algorithm for Terminal Area Air Traffic Control Advisory
Generation,
” AIAA Guidance, Navigation, and Control Conference and
Exhibit, Guidance, Navigation, and Control and Co-Located
Conferences, AIAA Paper 2001-4116, 2001.
doi:10.2514/6.2001-4116
[3] SESAR Joint Undertaking,
“P07.06.01-D37 Step 2 V1 Network
Performance Monitoring & Management Report,
” Bruxelles, 2014.
[4] Sesar Consortium,
“SESAR Concept of Operations,” Document
No. DLT-0612-222-01-00, Bruxelles, July 2007.
[5] Arnaldo, R., Sáez, F. J., and García, E.,
“Towards Higher Levels of
Automation in ATM,
” 28th International Congress of the Aeronautical
Sciences, ICAS Paper 2012-10.1.1, Sept. 2012.
[6] Kuchar, J. K., and Yang, L. C.,
“A Review of Conflict Detection and
Resolution Modeling Methods,
” IEEE Transactions on Intelligent
Transportation Systems, Vol. 1, No. 4, Dec. 2000, pp. 179
–189.
doi:10.1109/6979.898217
[7] Xiangmin, G., Xuejun, Z., Dong, H., Yanbo, Z., Ji, L., and Jing, S.,
“A
Strategic Flight Conflict Avoidance Approach Based on a Memetic
Algorithm,
” Chinese Journal of Aeronautics, Vol. 27, No. 1, Feb. 2014,
pp. 93
–101.
doi:10.1016/j.cja.2013.12.002
[8] Valenzuela, A., and Rivas, D.,
“Conflict Resolution in Converging Air
Traffic Using Trajectory Patterns,
” Journal of Guidance, Control, and
Dynamics, Vol. 34, No. 4, 2011, pp. 1172
–1189.
doi:10.2514/1.50751
[9] Matsuno, Y., Tsuchiya, T., and Matayoshi, N.,
“Near-Optimal Control
for Aircraft Conflict Resolution in the Presence of Uncertainty,
” Journal
of Guidance, Control, and Dynamics, Vol. 39, No. 2, 2016, pp. 326
–338.
doi:10.2514/1.G001227
[10] Durand, N., and Barnier, N.,
“Does ATM Need Centralized
Coordination? Autonomous Conflict Resolution Analysis in a
Constrained Speed Environment,
” Air Traffic Control Quarterly,
Vol. 23, No. 4, 2015, pp. 325
–346.
[11] Frazzoli, E., Mao, Z.-H., Oh, J.-H., and Feron, E.,
“Resolution of
Conflicts Involving Many Aircraft via Semidefinite Programming,
”
Journal of Guidance, Control, and Dynamics, Vol. 24, No. 1, 2001,
pp. 79
–86.
doi:10.2514/2.4678
[12] Clements, J. C.,
“Optimal Simultaneous Pairwise Conflict Resolution
Maneuvers in Air Traffic Management,
” Journal of Guidance, Control,
and Dynamics, Vol. 25, No. 4, 2002, pp. 815
–818.
doi:10.2514/2.4950
[13] Raghunathan, A. U., Gopal, V., Subramanian, D., Biegler, L. T., and
Samad, T.,
“Dynamic Optimization Strategies for Three-Dimensional
Conflict Resolution of Multiple Aircraft,
” Journal of Guidance,
Control, and Dynamics, Vol. 27, No. 4, 2004, pp. 586
–594.
doi:10.2514/1.11168
[14] Hu, J., Prandini, M., and Sastry, S.,
“Optimal Coordinated Maneuvers
for Three-Dimensional Aircraft Conflict Resolution,
” Journal of
Guidance, Control, and Dynamics, Vol. 25, No. 5, 2002, pp. 888
–900.
doi:10.2514/2.4982
[15] Green, S., and Grace, M.,
“Conflict-Free Planning for en Route Spacing
—A Concept for Integrating Conflict Probe and Miles-in-Trail,”
Guidance, Navigation, and Control Conference and Exhibit, Guidance,
Navigation, and Control and Co-Located Conferences, AIAA Paper
1999-3988, 1999.
doi:10.2514/6.1999-3988
[16] Flicker, R., and Fricke, M.,
“Improvement on the Acceptance of a
Conflict Resolution System by Air Traffic Controllers,
” The 6th USA/
Europe Air Traffic Management Research and Development Seminar,
EUROCONTROL/FAA Paper 27, June 2005.
[17] Huang, H., and Tomlin, C.,
“A Network-Based Approach to En-Route
Sector Aircraft Trajectory Planning,
” AIAA Guidance, Navigation, and
Control Conference, Guidance, Navigation, and Control and Co-
Located Conferences, AIAA Paper 2009-6169, 2009.
doi:10.2514/6.2009-6169
[18] Yokoyama, N.,
“Decentralized Model Predictive Control for
Planning Three-Dimensional Conflict-Free Trajectories,
” AIAA
Guidance, Navigation, and Control Conference, AIAA Paper 2014-
0970, 2014.
doi:10.2514/6.2014-0970
[19] Marzuoli, A., Gariel, M., Vela, A., and Feron, E.,
“Data-Based Modeling
and Optimization of En Route Traffic,
” Journal of Guidance, Control,
and Dynamics, Vol. 37, No. 6, 2014, pp. 1930
–1945.
doi:10.2514/1.G000010
[20] Salaun, E., Gariel, M., Vela, A. E., and Feron, E.,
“Aircraft Proximity
Maps Based on Data-Driven Flow Modeling,
” Journal of Guidance,
Control, and Dynamics, Vol. 35, No. 2, 2012, pp. 563
–577.
doi:10.2514/1.53859
[21] Solomatine, D. P., and Ostfeld, A.,
“Data-Driven Modelling: Some Past
Experiences and New Approaches,
” Journal of Hydrodynamics,
Vol. 10, No. 1, 2008, pp. 3
–22.
[22] Liu, J., and Han, D.,
“On Selection of the Optimal Data Time Interval for
Real-Time Hydrological Forecasting,
” Hydrology and Earth System
Sciences, Vol. 17, 2013, pp. 3639
–3659.
doi:10.5194/hess-17-3639-2013
[23] Batterson, J. G., and Klein, V.,
“Partitioning of Flight Data for
Aerodynamic Modeling of Aircraft at High Angles of Attack,
” Journal
of Aircraft, Vol. 26, No. 4, 1989, pp. 334
–339.
doi:10.2514/3.45765
[24] Dong, J., Wang, G., and Li, D.,
“Optimal Pilot Interval Design for the
Dedicated Pilot Channel,
” IEEE Pacific Rim Conference on
Communications, Computers and Signal Processing (PACRIM 2003),
Vol. 2, IEEE, Piscataway, NJ, Aug. 2003, pp. 635
–637.
[25] Ivanescu, D.,
“Conflict Detection Tools Impact on Controller Taskload
—Fast Time Study,” EUROCONTROL Experimental Centre, EEC
Note No. 010/10, Bruxelles, June 2010.
[26] Durand, N., and Gotteland, J. B.,
“Genetic Algorithms Applied to Air
Traffic Management,
” Metaheuristics for Hard Optimization, Springer,
New York, 2006, pp. 277
–306.
[27] Barnier, N., and Allignol, C.,
“4-D—Trajectory Deconfliction Through
Departure Time Adjustment,
” The 8th USA/Europe Air Traffic
Management Research and Development Seminar, EUROCONTROL/
FAA Paper 143, July 2009.
[28] Isaacson, D. R., and Erzberger, H.,
“Design of a Conflict Detection
Algorithm for the Center/TRACON Automation System,
” AIAA/IEEE
Proceedings 16th Digital Avionics Systems Conference, Vol. 2,
Oct. 1997, pp. 9.3-1
–9.3-9.
[29] Maimon, O., and Rokach, L., Data Mining and Knowledge Discovery
Handbook, Springer, New York, 2010, pp. 269
–270.
[30]
“Air Traffic Management,” 15th ed., International Civil Aviation
Organization Doc. 4444-ATM/501, Montreal 2007.
[31] Berkhin, P.,
“A Survey of Clustering Data Mining Techniques,” edited
by
Kogan,
J.,
Nicholas,
C.,
and
Teboulle,
M.,
Grouping
Multidimensional Data, Springer, New York, 2009, pp. 25
–71.
[32] Li, L., Das, S., Hansman, R. J., Palacios, R., and Srivastava, A. N.,
“Analysis of Flight Data Using Clustering Techniques for Detecting
Abnormal Operations,
” Journal of Aerospace Information Systems,
Vol. 12, No. 9, 2015, pp. 587
–598.
doi:10.2514/1.I010329
[33] Sammut, C., and Webb, G. I., Encyclopedia of Machine Learning,
Springer, New York, 2010, pp. 270
–273.
[34] Nirmala, A. M., and Saravanan, S.,
“A Study on Clustering Techniques
on Matlab,
” International Journal of Science and Research, Vol. 3,
No. 11, Nov. 2014, pp. 1497
–1502.
[35] Rizvi, F.,
“Reducing Earth Topography Resolution for SMAP Mission
Ground Tracks Using K-Means Clustering,
” AIAA Infotech@Aerospace
(I@A) Conference, Guidance, Navigation, and Control and Co-Located
Conferences, AIAA Paper 2013-4823, 2013.
doi:10.2514/6.2013-4823
[36] He, Z., Xu, X., and Deng, S.,
“Squeezer. An Efficient Algorithm for
Clustering Categorical Data,
” Journal of Computer Science and
Technology, Vol. 17, No. 5, 2002, pp. 611
–624.
doi:10.1007/BF02948829
[37] Hyndman, R. J.,
“The Problem with Sturges Rule for Constructing
Histograms,
” Monash Univ., Australia, Jan. 1995.
626
CALVO-FERNÁNDEZ ET AL.
Downloaded by UNIV. OF ARIZONA on March 14, 2017 | http://arc.aiaa.org | DOI: 10.2514/1.G000691
[38] Sturges, H.,
“The Choice of a Class-Interval,” Journal of American
Statistical Association, Vol. 21, No. 153, 1926, pp. 65
–66.
doi:10.1080/01621459.1926.10502161
[39] Nuic, A.,
“User Manual for the Base of Aircraft Data (BADA),” Rev. 3.6,
EUROCONTROL Experimental Centre, EEC Note No. 10/04,
Bruxelles, July 2004.
[40] Doush, I. A., and Bataineh, M. Q.,
“Hybridized NaGa-II and MOEA/D
with Harmony Search Algorithm to Solve Multi-Objective Optimization
Problems,
” ICONIP 2015, Part I, LNCS 9489, edited by Arik, S., et al.,
Springer International Publ., Switzerland, pp. 606
–614.
[41] Marceau, G., and Schoenauer, M.,
“Strategic Planning in Air Traffic
Control as a Multi-Objective Stochastic Optimization Problem,
” The
10th USA/Europe Air Traffic Management Research and Development
Seminar, EUROCONTROL/FAA Paper 315, June 2013.
[42] Devi, S., and Jagadev, A. K.,
“Comparison of Various Approaches in
Multi-Objective Particle Swarm Optimization (MOPSO): Empirical
Study. Multi-Swarm Intelligence,
” Multi-Objective Swarm Intelligence,
Springer, New York, 2015, pp. 75
–103.
[43] Van Veldhuizen, D. A., and Lamont, G. B.,
“Multiobjective
Evolutionary Algorithm Research: A History and Analysis,
” Dept. of
Electrical and Computer Engineering, Air Force Inst. of Technology
TR-98-03, 1998.
[44] Messac, A., and Mattson, C. A.,
“Normal Constraint Method with
Guarantee of Even Representation of Complete Pareto Frontier,
” AIAA
Journal, Vol. 42, No. 10, 2004, pp. 2101
–2111.
doi:10.2514/1.8977
[45] Hazelrigg, G. A., Systems Engineering: An Approach to Information-
Based Design, Prentice
–Hall, Upper Saddle River, NJ, 1996, p. 10.
CALVO-FERNÁNDEZ ET AL.
627
Downloaded by UNIV. OF ARIZONA on March 14, 2017 | http://arc.aiaa.org | DOI: 10.2514/1.G000691