Trajectory deconfliction with constraint programming

Nicolas Barnier, Cyril Allignol

To cite this version:

Nicolas Barnier, Cyril Allignol. Trajectory deconfliction with constraint programming. Knowledge
Engineering Review, 2012, 27 (3), pp 291-307. �10.1017/S0269888912000227�. �hal-00935206�

HAL Id: hal-00935206

[Link]
Submitted on 1 Apr 2014

HAL is a multi-disciplinary open access L’archive ouverte pluridisciplinaire HAL, est

archive for the deposit and dissemination of sci- destinée au dépôt et à la diffusion de documents
entific research documents, whether they are pub- scientifiques de niveau recherche, publiés ou non,
lished or not. The documents may come from émanant des établissements d’enseignement et de
teaching and research institutions in France or recherche français ou étrangers, des laboratoires
abroad, or from public or private research centers. publics ou privés.
The Knowledge Engineering Review, Vol. 00:0, 1–15. c 2009, Cambridge University Press
DOI: 10.1017/S000000000000000 Printed in the United Kingdom

Trajectory Deconfliction with Constraint Programming

NICOLAS BARNIER1 , CYRIL ALLIGNOL2

1 École Nationale de l’Aviation Civile, 7 Av. Édouard Belin, 31055 Toulouse, France
E-mail: barnier@[Link]
2 DSNA/DTI, 7 Av. Édouard Belin, 31055 Toulouse, France
E-mail: allignol@[Link]

Abstract
As acknowledged by the SESAR program, current ATC systems must be drastically improved to
accommodate the predicted traffic growth in Europe. In this context, the Episode 3 project aims at
assessing the performance of new ATM concepts, like 4D-trajectory planning and strategic deconfliction.
One of the bottlenecks impeding ATC performances is the hourly capacity constraints defined on each
en-route ATC sector to limit the rate of aircraft. Previous works were mainly focused on optimizing the
current ground holding slot allocation process devised to satisfy these constraints. We propose to estimate
the cost of directly solving all conflicts in the upper airspace with ground holding, provided that aircraft
were able to follow their trajectories accurately.
We present a Constraint Programming (CP) model of this large scale combinatorial optimization
problem and the results obtained with the FaCiLe constraint library. We study the effect of uncertainties on
the departure time and estimate the cost of improving the robustness of our solutions with the Complete
Air Traffic Simulator (CATS). Encouraging results were obtained without uncertainty but the costs of
robust solutions are prohibitive. Our approach may however be improved, e.g. with a prior flight level
allocation and the dynamic resolution of remaining conflicts with one of CATS’ modules.

1 Introduction
In an already saturated European sky, the predicted growth of air traffic volume urges to improve Air
Traffic Management (ATM) efficiency, as attested by the ACARE Strategic Agenda 2 (ACARE 2004) and
the European Single Sky program SESAR. Current ATM optimization strategies, like reducing the size
of control sectors or the distance of separation (reduction of vertical separation with RVSM, reduction of
horizontal separation with P-RNAV), seem to have reached the structural limits of the system, while the
automation of Air Traffic Control (ATC) has known few significant improvements over the last decades
(Garot & Durand 2005).
In this context, the European Commission has launched the Episode 3 (Graham & Young 2006)
research project to assess the concepts studied within SESAR definition phase. Among the key concepts
identified to meet SESAR performance objectives, the planning of 4D-trajectories could result in increased
en-route capacities, while preserving the current level of safety. One of the goals of the Work Package 4
(WP4) of Episode 3 is to estimate how strategic deconfliction schemes could benefit from such regulations
over the current Air Traffic Flow Management (ATFM) process.
Currently, the Central Flow Management Unit (CFMU) in Brussels is in charge of optimizing the
traffic by, among other strategic or tactical measures, allocating departure slots (i.e. a departure time
to be honored within a −5/+10 min margin) to the flights involved in overloaded en-route sectors. The
purpose of this ground holding scheme is to respect the en-route capacity constraints provided by each
ATC Centre (ATCC) as a number of aircraft per hour, according to their daily schedule. Former studies
like (Dalichampt, Petit, Junker & Lebreton 1997, Barnier, Brisset & Rivière 2001) aimed at improving
2 N . BARNIER , C . ALLIGNOL

this slot allocation over the greedy algorithm used at the CFMU. However, one of the limitations of this
regulation model is that the definition of sectors capacities (hourly rate of aircraft entering the sector) is
poorly related to the complexity of the traffic with respect to the controllers workload, as assessed by
(Gianazza & Guittet 2007).
Instead of trying to satisfy en-route capacity constraints, we propose to directly solve the potential
conflicts occurring between any two intersecting trajectories with departure time adjustments. A single
delay would be associated with each flight such that all potential conflicts occurring above a given
flight level1 (FL) would be avoided. This very fine grain model would of course generate much larger
constraints sets than the macroscopic (at the sector level) capacitated ones, but would guarantee conflict-
free trajectories all along the flight path provided that aircraft were able to scrupulously follow their
predicted route in the four dimensions.
Obviously, the latter hypothesis is far from being met nowadays, but the accuracy of Flight Manage-
ment Systems will be a crucial issue for future ATFM and ATC systems, as advocated by (Alliot & Colin
de Verdière 2003) and acknowledged by the Airbus-driven “Technological Enablers” WP6 of Episode 3.
Nevertheless, we believe that our approach may reduce air traffic complexity by “deconflicting” it in
advance. The remaining conflicts due to deviation from the flight plan (or occurring in the lower airspace)
would then be solved dynamically, either by automated resolution systems as proposed by (Granger,
Durand & Alliot 2001, Archambault 2004), or by more standard ATC procedures.
Several optimization paradigms are being evaluated for this purpose, namely meta-heuristics, local
search and Constraint Programming (CP). We will focus here on the CP approach as it offers to obtain
proved bounds on the maximal delays needed to solve the conflicts, which can be used to draw conclusions
on the feasibility of this kind of regulations. Moreover, CP is a technology of choice for implementing
such preliminary work, as the problem can be easily refined by adding new constraints (e.g. connection
constraints between flights using the same aircraft) and to experiment with various search strategies
without changing the rest of the model. A preliminary version of this work with a smaller data set has
been presented in (Barnier & Allignol 2009).
In the following sections, we first briefly introduce ATC and ATFM in Europe, focusing on ground
holding policies and related research projects. Then we describe our model of a conflict-free slot
allocation, starting by the details of the constraints generation and search strategy. Next, our first results
on instances of the French Traffic are presented, as well as the effect of small takeoff time uncertainties.
We end with planned further works to enhance the approach before concluding.

2 Context and Related Works

2.1 ATC and ATFM

Air Traffic Control (ATC) is a ground-based service provided to ensure the safety and efficiency of the
flow of aircraft. The first goal of ATC is to maintain aircraft separated: outside Terminal Areas (TMA),
i.e. airspace in which approach control service is provided, two aircraft should remain distant from each
other at least by 5 NM (Nautical Mile, 1 NM = 1852 m) horizontally or 1000 ft (1 ft = 0.3048 m) vertically,
as illustrated by the safety volume of figure 1.
The overall system currently implemented in Europe to achieve this goal can be conceptually divided in
several layers or filters by decreasing time horizon with respect to the flight date of the traffic concerned:

1. Strategic (several months before departure time): Air Space Management (ASM). Includes the design
of routes, sectors and procedures (e.g. reduced separation RVSM since 2002, Area Navigation
(RNAV) with fictive beacons...).
2. (Pre-)Tactical (a few days to a few hours before departure time): Air Traffic Flow Management
(ATFM). ATC Centres opening schedules define hourly capacities for each open sectors (or groups
of sectors). To respect these constraints, the Central Flow Management Unit (CFMU) computes and
1
A flight level is a standard nominal altitude, expressed in hundreds of feet from the international standard pressure
datum of 1 013.25 hPa.
 Trajectory Deconfliction with Constraint Programming 3

11
00
0
1 0000
1111
5 NM
0 1111
00
11
1 0000
0000
1111
0
1
0
1
1000 ft
0
1

Figure 1 Vertical and horizontal separation: another aircraft cannot be inside the cylinder at the same time.

updates flow regulations (ground holding delays) and reroutings according to the posted flight plans
whenever and wherever the resulting local workload would exceed the capacity.
3. Real time (2/15 min before conflict): Air Traffic Control (ATC). The controllers are in charge of
the surveillance of the traffic, its coordination with adjacent centres, of potential conflict resolution
by various simple manœuvres (heading, flight level, speed) transmitted to the pilots, as well as the
dynamic reconfiguration of open sectors2 to balance the workload.
4. Emergency (less than 2 min before conflict): safety nets. Includes ground-based (e.g. Short Term
Conflict Alert, Minimum Safety Altitude Warning) and airborne (Traffic alert and Collision Avoid-
ance System (TCAS), Ground Proximity Warning System) systems issuing alarms (as well as simple
resolution manœuvres for the TCAS).

We will focus in the following section on the kind of regulations performed by the CFMU by
postponing the takeoff of aircraft.

2.2 Ground Delays

As aircraft cannot easily be paused en-route3 whenever the traffic complexity becomes too high to be
safely handled by a controller, one of the simplest way to regulate the ATC workload is to postpone
the takeoff of aircraft4 . This kind of measure is however quite unpopular among airlines, as it can be
very costly and may propagate in terms of missed transfers and aircraft rotation (see (Cook, Tanner &
Anderson 2004)), so the delays should be minimized as much as possible.

2.2.1 Satisfying En-Route Sectors Capacity Constraints

The aim of CFMU regulations is to maintain the number of en-route aircraft entering a given subset of
sectors below some bound over given time periods (usually one hour), according to the constraints defined
by local experts (the Flow Management Position, FMP) in each ATCC for the day of traffic. The ATFM
service of the CFMU first identifies the overloaded sectors and responsible flows with the PREDICT
tool, then computes a slot allocation as ground delays for the involved flights with the CASA (Computer
Assisted Slot Allocation) tool described in (CFMU 2000).
CASA is able to take into account many operational constraints and updates to optimize its allocation
process, but the algorithm used has greedy properties and thus cannot guarantee to find a correct solution
(which satisfies all the constraints) or an optimal one. CP technology has been applied with good results
to prove and optimize the allocation process with a relaxed model (Dalichampt et al. 1997) or to smooth
the resulting load profiles (Barnier et al. 2001) with a tighter model.
However, traffic complexity is very hard to define precisely, and sector capacities, expressed as a
maximum number of aircraft entering the sector over a given time period, does not take into account
many parameters relevant to accurately represent the performance of ATC. Observed actual capacities,
2
Note that this activity is usually considered as part of tactical flow management rather than ATC.
3
They may be put on a racetrack pattern before landing if the destination airport is congested though.
4
Note that flights might be delayed for other reasons than en-route capacity violation, like bad weather, equipment
failures or airport congestion.
4 N . BARNIER , C . ALLIGNOL

as well as merging and splitting subset of sectors, chronically present very different profiles than the
predicted ones, as shown in (Gianazza & Guittet 2007).
To overcome this issue, recent works such as (Flener, Pearson, Ågren, Garcia Avello, Çelitkin &
Dissing 2007) use a much more precise and complex workload CP model to dynamically balance the
traffic over the sectors of an ATCC in the upper airspace. Other works, like (Barnier 2002) uses CP
technology as well to optimize the ATCC opening schedules to match the predicted traffic more closely,
or even attempt to redesign airspace sectorisation with better balancing like (Tran Dac & Baptiste 2003).

2.2.2 Solving the Conflicts

One of the key ATM operational concept of SESAR which should be investigated by the Episode 3
project is the design of conflict-free 4D-tubes within crowded airspace (whereas separation could be
delegated to aircraft in less dense areas). So instead of only respecting sectors capacities macroscopically,
we propose to evaluate the cost of precisely solving all potential conflicts, by ground holding only, i.e.
without changing the requested trajectory, while minimizing the worst allocated delay to maintain equity
among airlines.
Optimality proofs for the overall sum of the delays can be exponentially harder than our max criterion,
and therefore out of reach for such large problems. However, our search strategy will focus on maintaining
the overall amount of delay as low as possible, while the use of CP technology will provide proved
maximal delay bounds that other optimization techniques (e.g. local search or meta-heuristics) cannot
produce.
This conflict-free model will of course yield much larger problem instances as all of the conflicting
trajectories intervals above a given flight level will be taken into account as constraints. The resulting
problem is intrinsically disjunctive as for each potential conflict between two flights i and j, either i must
precede j or j precede i at each pair of points concerned (see section 3.2).
Other approaches have been presented to solve conflicts in real-time, automating the task of con-
trollers. Some of the most promising ones are centralized techniques that compute simple horizontal
or vertical manœuvres (Granger 2002) and small speed adjustments as proposed by the ERASMUS
project (Archambault 2004). These solvers, based around a meta-heuristic (Genetic Algorithm), can take
uncertainties on ground and vertical speed into account and repeatedly compute solutions for a sliding
time window.

3 Conflict-Free Slot Allocation

3.1 Conflict Detection
Our data are provided by the CATS5 simulator (Alliot, Bosc, Durand & Maugis 1997), which takes as
input all of the filed flight plans concerning the French airspace for a given day of traffic and the relevant
airspace configuration (sectors, waypoints...), and can output the corresponding 4D-trajectories.
To detect all “significant” conflicts, CATS discretizes trajectories with a ∆t = 15 s time step. As
depicted in figure 2, the worst case for conflict detection occurs when two aircraft are following parallel
trajectories separated by a distance D ≤ Nh (Nh = 5 NM being the horizontal separation norm) and
heading in opposite directions at maximum possible speed Vmax = 500 kt. Given a time step ∆t for
trajectories discretization, undetected conflicts may occur when:
  
Nh D
∆t > cos arcsin
Vmax Nh
Therefore, by choosing ∆t = 15 s, false negative detections would only occur for:
  
∆tVmax
D > Nh sin arccos > 4.5 NM
Nh
i.e. for 4.5 NM < D ≤ 5 NM, which is commonly accepted for fast-time simulations as such routing
schemes are not allowed by standard ATM practice.
5
The Complete Air Traffic Simulator developed at DSNA/DTI.
 Trajectory Deconfliction with Constraint Programming 5

Nh

∆t

Figure 2 Influence of time step in conflict detection.

Trajectories are then probed pairwise6 for potential conflicts, ignoring those that could only occur for
greater delays than the given maximal one. The separation norm is thus tested for each pair of points of
the two probed trajectories (up to p = 1300 points per trajectory for up to n = 9500 flights in O(n2 p2 ),
as observed in the largest instances simulated by CATS) as illustrated on figure 3 in the horizontal plane.
Note that trajectory enclosing bounding boxes or sweep line techniques (de Berg, van Kreveld, Overmars
& Schwarzkopf 1998) could be used to lower the detection complexity, but it is here considered as a static
data production phase and its efficiency is not a primary concern of the present study.

pjl

dh< 5 Nm & d v< 1000 ft

pik
i

Figure 3 Detection of conflicting points.

Though the maximal allowed delay can be seen as a parameter of the search algorithm only, it also
affects the conflict detection. Actually, when the maximal allowed delay is increased, the size of the
problem grows as well, as more and more flights tend to be in potential conflict. Ultimately, if a 24 h-delay
would be allowed, the conflict detection could be done regardless of time, as any two space-conflicting
trajectories would generate a constraint. So, whenever a particular instance has been proved inconsistent,
it has to be generated again with higher values of the maximal delay, which will capture later potential
conflicts on the trajectories pairs and increase the size of the instance.
Operationally, flights originating outside the Eurocontrol countries cannot be delayed, so their delay
variable will be fixed to 0 in our constraint model, reducing the number of variables but tightening the
constraints as well and offering less opportunities for optimization. Constraints corresponding to conflicts
occurring between two such flights will of course be discarded as we cannot delay the flights to solve
6
Note that the conflict detection for two given flights is symmetrical, so that only ordered pairs are considered.
6 N . BARNIER , C . ALLIGNOL

them. Such remaining conflicting cases would have to be taken care of by other ATC or ATFM techniques
that will not be addressed in this study.

3.2 Constraint Programming Model

Our 4D-trajectory deconfliction scheme by ground holding is modelled in the following sections using
the versatile formalism of finite domain Constraint Satisfaction Problem (CSP), which is the underlying
modelling component of the Constraint Programming (CP) technology (Van Hentenryck, Simonis &
Dincbas 1992) that we have used to solve the resulting combinatorial optimization problem.

3.2.1 Conflicts Constraints

To compute the constraints of our model, the trajectories (up to 9500 flights for one day of traffic in the
French airspace, see section 4) are pairwise probed for couples of conflicting points. Given a flight i, we
note the input data:

• {pki } the chronologically ordered sequence of the 3D-points of its trajectory;

• tki the time at which the flight will be at point pki , should it not be delayed.

We define a set D of decision variables:

D = {δi , ∀i ∈ [1, n]}

of finite domain [0, max delay] that represent the delay associated with each of the n flights (between 6000
and 8000 after processing for our experiments). The value of max delay is typically chosen as 90 min and
increased as needed when no solution is found – up to 300 min in our experiments, see section 4. As
explained in section 3.1, the size of the instance grows with max delay.
We will describe our model using the following auxiliary variables (defined for each unique pair of
delay variables, i.e. exactly 12 n(n − 1)):

• θik = tki + δi the date at which flight i will be at point pki if it is delayed by δi ;
• dij = δj − δi the difference of the delays of flight j and i.

For any geometrically conflicting points pki and plj such that the separation norm is violated (dh being
the distance in the horizontal plane and dv in the vertical plane):

dh (pki , plj ) < 5 NM and dv (pki , plj ) < 1000 ft

we must temporally ensure that:

θik 6= θjl
which can be rewritten with the difference variables dij :

dij 6= tki − tlj

Starting at the first such point pki that conflicts with a point of flight j, we take into account the whole
continuous segment of trajectory j conflicting with pki , beginning at point pljk and ending at some point
pljk +r :
{plj , ∀l ∈ [lk , lk + r]}
for some r, and we impose on the difference of the delays of flight i and j that:

dij 6∈ {tki − tlj , ∀l ∈ [lk , lk + r]}

which can be rewritten as:

dij 6∈ [lbk , ubk ]
with lbk and ubk being respectively the lower and upper bound of the set of tki − tlj .
 Trajectory Deconfliction with Constraint Programming 7

If the next point pk+1

i of the trajectory of flight i conflicts with a further segment of flight j, we will
obtain another forbidden segment for dij :
dij 6∈ [lbk+1 , ubk+1 ]
taking part in the same potential conflict. To ensure separation we must then impose:
dij 6∈ [min(lbk , lbk+1 ), max(ubk , ubk+1 )]
as the conflicting segments of flight j overlap.
So if we take into account all the successive points of flight i, starting at pki , that conflict with
overlapping segments of flight j, up to some last point pk+s i , with lb1 = min{lbk+u , u ∈ [0, s]} and
k+u
ub1 = max{ub , u ∈ [0, s]} being the overall lower and upper bounds of the corresponding forbidden
intervals for dij , we can define the first conflict between flights i and j:
dij 6∈ [lb1 , ub1 ]
Note that we take as parameters of the problem instance the maximal allowable delay max delay, therefore
the domain of dij = δj − δi is the interval [−max delay, max delay]. We simply discard the conflict
whenever ub < −max delay or lb > max delay.

1561
1621

1240
1230
1220
1210
1200
1190
1180
1170
1160
1150

Figure 4 Three potential conflicts between two flights: one near Paris airport at low altitude and two other en-route
at the cruising altitude of the lower flight. The gray scale corresponds to time (in minutes) along the trajectory, the
lighter the later.

A pair of flights may conflicts several disjoint times over their entire trajectories (as illustrated on figure
4), so several such disjoint intervals may be forbidden for the difference of their delays. For two flights i
and j conflicting σ times over their whole trajectories, we then have:
1 σ
dij 6∈ [lb1 , ub ] ∪ · · · ∪ [lbσ , ub ]
or, rewritten as a disjunctive constraint over the decision variables:
(−max delay ≤ δj − δi < lb1 ) ∨
1
(ub < δj − δi < lb2 ) ∨ · · · ∨
σ−1
(ub < δj − δ i < lbσ ) ∨
σ
(ub < δj − δi ≤ max delay)
8 N . BARNIER , C . ALLIGNOL

σ
provided that lb1 > −max delay and ub < max delay, otherwise the first or last part of the disjunction
is discarded.
As aforementioned, the cost is simply defined as the maximal allocated delay, to ensure equity among
the various postponed flights:
cost = max{δi , ∀i ∈ [1, n]}
However, the overall sum of the delays is of utmost importance as well for the quality of a solution and
we will take it into account within the search strategy to provide realistic max-optimal solutions during
the resolution of the problem.

3.2.2 Further Instance Processing

The takeoff and landing part of trajectories are truncated around airports within a given radius (usually
10 NM) as the traffic is considered handled with specific procedures by the TMA control services in these
zones.
After the computation of the conflict constraints, the whole instance is scaled down to a more
reasonable time step than the 15 s used during conflict detection. We ensure that the original forbidden
intervals are strictly included in the scaled ones, with appropriate interval arithmetic operations which can
possibly merge conflicting disjoint intervals. A 1 min time step was chosen for the resolution: a smaller
time step would not have been realistic for a departure time, whereas a greater one would have reduced
the set of feasible solutions. Besides, a 1 min time step seems compliant with the SESAR objectives of
±3 min precision for takeoff time.
Moreover, the flight level of the detected conflicts can be filtered, for example to only take into account
conflicts occurring within the upper airspace (from FL200 and above). The minimal and maximal altitude
of each conflict is recorded during the detection stage and a conflict is discarded if it entirely occurs below
or above the specified airspace slice.
It is also possible to filter the time interval during which the conflicts may occur, taking the time bounds
of the allowable delay into account. Any conflict strictly occurring outside the given time interval is then
discarded.
Eventually, all the flights that do not have any conflict with any other flight are withdrawn from the
instance.

3.2.3 Conflict Extension

To improve the robustness of our solutions towards uncertainty on the departure times of the flights, we
add an extra parameter ext that extends conflicting intervals by a fix amount of time. Such an extension
of ext minutes stretching the start and the end of a conflict will be able to manage uncertainties of ± ext2
minutes on the departure slot (see section 4.4), at the price of an increase in the cost of the solutions.
We expect that this extension scheme may as well be able to diminish the effects of other sources
of uncertainty (e.g. vertical and ground speed) regarding the number of remaining conflicts during
simulation.

3.3 Search Strategy

The constraints of the problem are reminiscent of the disjunctive mutual exclusion constraints often used
to model scheduling problems (Baptiste, Le Pape & Nuijten 2001). At a coarse grain, we could consider
each conflicting area as a machine on which to process two tasks of different lengths (depending on the
speed of the aircraft). Several conflicts along a trajectory could even be seen as the ordered tasks of a
given job, as in the Job-shop Scheduling Problem (JSP).
However, the comparison does not hold much further. First, the time intervals between any two conflict-
tasks of the same trajectory are fixed, as only one delay variable is associated with each flight (unlike the
JSP where all tasks are only related with precedence constraints). Second, to consider a potential conflict in
three dimensions only, as the transitive closure of the overlapping conflicting segments, with task lengths
proportional to the time spent by the aircraft within the area, is misleading. In this setting, the conflict
 Trajectory Deconfliction with Constraint Programming 9

associated with two catching-up flights on the same route would be the entire trajectory, preventing them
from being airborne at the same time! Obviously, our model is much more precise and allows two aircraft
on the same route to be separated by 5 NM only. Third, the number of “conflict machines”, if not quadratic
in the number of “flight jobs” as it could ultimately grow for arbitrary instances, is quite huge anyway as
shown on figure 6 and cannot be easily related with any known standard scheduling problem.
Nevertheless, the branching scheme of our search strategy to solve this essentially disjunctive problem
is inspired by standard scheduling techniques. For instance, trying to start the search by directly labelling
the delay variables δi may impede the search because of thrashing (i.e. repeatedly fail over the same
constraint), as the constraints are expressed over the differences dij . In this case, a more efficient filtering
can be obtained by feeding the propagation of the arithmetic constraints with new domain bounds for the
dij auxiliary variables.
In this respect, our search strategy first try to order pairs of conflicting flights by adding the constraint
dij < lb or dij > ub in the case of a single conflicting interval. If there are several holes in the domain of
dij , branching is repeated with the bounds of the remaining holes. The variable dij with highest sparsity,
i.e. the smallest ratio between the domain size and the difference of the domain bounds, is chosen first for
branching.
To compensate for the cost being defined as the maximal delay only, disregarding the total amount of
time, we choose to branch first within the dij interval corresponding to the minimum potential increase
for its delay variables δi and δj . Such an interval would be the closest to 0, while if dij were far from 0,
then at least one delay would be large. Whenever the search backtracks over such a decision, this interval
is discarded and we branch on the next one recursively.
When all conflicts are ordered and there is no more hole in the domain of the dij , we start labelling the
decision variables δi with a standard dom/deg selection heuristic: the variable with the smallest domain,
and the highest number of constraints in case of tie, is dynamically selected. Then, the values closest to 0
are probed first to attempt to keep the total amount of delay as low as possible.
After the first solution is found, the branch and bound algorithm proceeds by dichotomy on the cost
domain to find the optimal solution with respect to minimization of the maximal allocated delay, while
keeping low the overall amount of delay thanks to the search strategy.

4 Results
We have implemented this CP model with the FaCiLe library (Barnier & Brisset 2001) and obtained the
following results on various day of traffic in 2007. Our data set consists in full days of traffic within
the French airspace for all ATCCs, with up to 9500 flights and 600 000 intersecting pairs of trajectories
taken into account for the largest instances we could optimally solve. About 10% of the flights are non-
European flights, their delays will therefore be fixed to 0 as aforementioned. Among these flights, the
remaining unsolvable conflicts amounts to 5%-10% of the number of undelayable flights.

4.1 Data Processing

The resulting constraint graphs typically exhibit only one single large connected component of maximal
degree that can be greater than 300, i.e. a single flight may conflict with more than 300 other flights. Large
cliques can also be found, as large as involving more than 60 flights, which indicates the presence of very
entangled and dense traffic areas. The hardness of the conflict constraints is quite unevenly distributed,
with two peaks for respectively very small and very large forbidden intervals.
We mainly tune the size of our instances by choosing the minimal flight level for which the conflicts
are taken into account, aiming at the upper airspace (above FL200) where most of the cruising traffic
occurs. However, we were able to optimally solve one instance with more than 6600 flights and 630 000
conflicting pairs, taking all conflicts into account for the whole day, regardless of the flight level. Figure 5
shows the number of flights of our instances as a function of the minimal FL. The plots present two parts,
one very steep from the maximal FL to FL300, then flights add up at a slower rate in the lower airspace
– note that plots are labelled with their date and the type of routes (standard or direct), e.g. “070123s” for
the day of traffic on the 23rd of January 2007 with standard routes.
10 N . BARNIER , C . ALLIGNOL

9000
070123s
070123d
070622s
8000 080812s
080812d
080813s
7000 081007s

6000

5000

4000

3000

2000

1000

0
0 50 100 150 200 250 300 350 400

Figure 5 Number of flights w.r.t. minimal flight level.

The number of conflicting pairs is not quite quadratic with the number of flights, as mentioned in
section 3.2 and shown on figure 6, but is quite huge anyhow, reaching 630 000 for our largest instance.

700000
070123s
070123d
070622s
080812s
600000 080812d
080813s
081007s

500000

400000

300000

200000

100000

0
0 1000 2000 3000 4000 5000 6000 7000 8000 9000

Figure 6 Number of conflicts w.r.t. number of flights.

4.2 Numerical Results

We were systematically able to obtain optimal solutions within affordable computation times for all the
instances where the 4 GB memory of our Core 2 Duo at 2.4 GHz were not exhausted. However, the search
strategy exposed in section 3.3 was not always the best, and for some instances, a chronological labelling
breaking ties with a standard dom/deg ordering could obtain solutions faster or with a lower overall
 Trajectory Deconfliction with Constraint Programming 11

amount of delay. The following graphs only exhibits the results of the best search strategy for conciseness
reasons.
As shown in figure 7, small instances are solved in a few seconds whereas the biggest ones could take
almost one minute, growing only quadratically with the number of flights (figure 7(a)). We plan to address
larger instances, hopefully European ones, on a computer with more memory.

60
070123s
070123d
070622s
080812s
080812d
50 080813s
081007s

40

30

20

10

0
0 1000 2000 3000 4000 5000 6000 7000 8000 9000

(a) Computation time (optimality proof) in seconds w.r.t. number of flights.

60
070123s
070123d
070622s
080812s
080812d
50 080813s
081007s

40

30

20

10

0
0 50 100 150 200 250 300 350 400

(b) Computation time (optimality proof) in seconds w.r.t. minimal flight level.

Figure 7 Computation times.

However, the cost of this conflict-free slot allocation can be quite high for the busiest days (our worst
case above FL350 is 182 min for the most delayed flight with a max delay of 300 min to compute the
instance), but may be more reasonable (around 60-90 min) for less crowded days. Figure 8 shows that the
12 N . BARNIER , C . ALLIGNOL

cost grows steadily for small instances (i.e. at high minimal FL), but jumps as soon as we add the main
flows of traffic around FL350 for bigger instances. The optimal cost then seems to be stable for larger
instances, triggered only by the flights added around FL350 (see figure 8(b)).

200
070123s
070123d
180 070622s
080812s
080812d
080813s
160 081007s

140

120

100

80

60

40

20

0
0 1000 2000 3000 4000 5000 6000 7000 8000 9000

(a) Optimal cost w.r.t. the number of flights.

200
070123s
070123d
180 070622s
080812s
080812d
080813s
160 081007s

140

120

100

80

60

40

20

0
260 280 300 320 340 360 380 400

(b) Optimal cost w.r.t. the minimal flight level.

Figure 8 Optimal costs.

The corresponding overall delay sum (figure 9) and percentage of delayed flights (figure 10) exhibit of
course a more steady behavior, dramatically increasing with the largest instances only.
(Central Office for Delay Analysis 2009) provides some statistics on observed ATFM delays. In this
report, a flight is considered delayed if its observed delay is more than 5 min. For 2009, the average delay
per delayed flight (with respect to the previous definition) was 20 min. Even if we do not optimize the
mean delay, we can see on figure 11 that our figures remain comparable to the actual CFMU delays:
 Trajectory Deconfliction with Constraint Programming 13

14000
070123s
070123d
070622s
080812s
12000 080812d
080813s
081007s

10000

8000

6000

4000

2000

0
0 1000 2000 3000 4000 5000 6000 7000 8000 9000

(a) Total amount of delay in minutes w.r.t. the number of flights.

14000
070123s
070123d
070622s
080812s
12000 080812d
080813s
081007s

10000

8000

6000

4000

2000

0
0 50 100 150 200 250 300 350 400

(b) Total amount of delay in minutes w.r.t. the minimal flight level.

Figure 9 Total amount of delay.

in most cases, the mean delay per delayed aircraft is strictly under 20 min. The worst cases occur for
extremely small instances with very few flights (or high minimal FL) where the number of delayed flights
is so low that their statistical distribution is meaningless.

4.3 Standard and Direct Routes

For one of the days of traffic (plots labelled “070123s” and “070123d”), we have also tested our model on
direct routes. We say that aircraft follow a direct route when they fly in straight line at the requested flight
level from origin to destination, as opposed to standard routes where their path from origin to destination
14 N . BARNIER , C . ALLIGNOL

0.35
070123s
070123d
070622s
080812s
0.3 080812d
080813s
081007s

0.25

0.2

0.15

0.1

0.05

0
0 1000 2000 3000 4000 5000 6000 7000 8000 9000

(a) Ratio of delayed flights w.r.t. the number of flights.

0.35
070123s
070123d
070622s
080812s
0.3 080812d
080813s
081007s

0.25

0.2

0.15

0.1

0.05

0
0 50 100 150 200 250 300 350 400

(b) Ratio of delayed flights w.r.t. the minimal flight level.

Figure 10 Ratio of delayed flights.

is a succession of segments between waypoints. Direct routes are the ideal trajectories for airlines, with
respect to operational cost, but such a traffic would be hardly controllable for human operators and ATC
would have to be fully automated in this context.
However, they tend to generate constraint graphs with a lower tightness (see figure 6), and it is
interesting to observe that overall delay sums are smaller than the ones associated with standard routes on
figure 9(b). Flights following standard routes tend to be on closer trajectories, suitable for the efficiency of
current ATC procedures, but not using airspace to its full capacity. The max cost can be greater with direct
routes though, depending on the day of traffic and on the minimal flight level considered, as observed on
figure 8 for 08/12/2008 (labelled “080812s” and “080812d”).
 Trajectory Deconfliction with Constraint Programming 15

35
070123s
070123d
070622s
080812s
080812d
080813s
30 081007s

25

20

15

10
1000 2000 3000 4000 5000 6000 7000 8000 9000

(a) Mean delay per delayed flight w.r.t. the number of flights.

35
070123s
070123d
070622s
080812s
080812d
080813s
30 081007s

25

20

15

10
0 50 100 150 200 250 300 350 400

(b) Mean delay per delayed flight w.r.t. the minimal flight level.

Figure 11 Mean delay per delayed flight. In this figure, for comparison with CFMU delay, we consider that a flight
is delayed if its delay is greater or equal to 5 min.

4.4 Robustness Towards Uncertainty

Our model and algorithm were validated by taking the generated solutions as input delays for the CATS
simulator. We observed that the few remaining conflicts occur below the chosen minimal flight level only,
or involve flights originating outside the Eurocontrol area, which cannot be delayed in our model (see
section 3.1).
However, this first validation does not take into account any uncertainty with respect to departure
time or aircraft navigation (i.e. aircraft not following its 4D-trajectory precisely enough). To assess the
robustness of our solutions, we have added an uncertainty parameter err on departure times within
16 N . BARNIER , C . ALLIGNOL

CATS. Takeoffs are randomly shifted by a bounded amount of time uniformly7 chosen in the interval
[− err err
2 , + 2 ].

%conflicts
100
80
60
40
20
0
0
1
2
ext 3 5 6
3 4
4 0 1 2
err

Figure 12 Percentage of remaining conflicts w.r.t. conflict extension and departure time error in minutes.

New validation tests were carried out with various values of err to assess the effect of the conflict
extension parameter ext (defined in section 3.2.3) to compensate for the uncertainties. As expected,
figure 12 shows that for the region where ext ≥ err, no conflict remains: all points below the ext = err
dashed line on the xy-plane exhibit a conflict percentage equal to zero. Above this line, the ratio of
remaining conflicts increases with err for a given ext and when ext diminishes for a given err, reaching
75% for the highest point (err = 6 and ext = 0).

35
FL 350
FL 300
FL 200
30

25

20

15

10

0
0 1 2 3 4

Figure 13 Mean delay per delayed flight w.r.t. conflict extension in minutes. The indicated flight levels are the
minimal flight levels used for conflict detection.

7
A better approach would involve a statistical analysis to approximate the probability distribution of the discrepancy
between scheduled and actual takeoff times.
 Trajectory Deconfliction with Constraint Programming 17

However, increasing the ext parameter leads to an increase in the total amount of delay as illustrated in
figure 13. The added delays can be far too costly for higher values of ext, especially for large instances.
The target figures for efficiency within SESAR are:

• at least 98% of flights departing on time (on-time departure being defined as actual departure less
than 3 min before or after scheduled departure),
• the average departure delay of delayed flights must not exceed 10 min.

For the traffic sample used in figure 13, the delays are higher than 15 min per delayed flight, with more
than 60% delayed flights, far from the above objectives. Thus we cannot hope to solve all conflicts with
this technique alone within SESAR time slot objectives (±3 min precision on take-off time), let alone
CFMU margins (−5/+10 min slot around take-off time), as operational delay cost would be prohibitive.
As presented in the next section, other regulation or dynamic resolution techniques may be used to
overcome this issue.

5 Further Work
These first results are encouraging but we have only addressed so far the resolution of conflicts within
the French airspace. However, in a unified European ATC context, all conflicting traffic throughout the
Eurocontrol countries should be taken into account. Such instances would comprise up to 30 000 flights
per day. We plan to experiment with various refinements of our algorithm to address such large scale
problems.

5.1 Prior Flight Level Allocation

To be able to address such large instances, while maintaining reasonable maximal delay figures, we plan
to combine our ground holding algorithm with a prior flight level allocation stage, possibly using CP
technology as well, as described in (Barnier & Brisset 2002).
This first step, which tries to minimize the number of horizontally conflicting flows by separating them
vertically (trying as well to deviate as little as possible from requested FLs), is expected to deconflict the
traffic by a substantial amount before time slot allocation. The optimal cost should then remain within
much better bounds than with the raw traffic.

5.2 Sliding Time Windows

For large European instances, we also plan to adapt our algorithm to repeatedly solve slices of the problem
on a limited time window Tw , then to keep only the earliest part of the solution over a smaller interval
λ and to slide the resolution window by λ. Parameters Tw and λ must be carefully chosen according to
the computation time of the resolution and the cumulative effects of uncertainties. Similar approaches are
used for dynamic conflict resolution in the CATS solver as described in (Granger et al. 2001).

5.3 Resolution with CATS Modules

Various real-time resolution algorithms have already been implemented within the CATS simulator
(Granger 2002, Granger et al. 2001, Archambault 2004) with very good results. We would like to assess
our regulation schemes further by observing the workload of these algorithms when provided with our
solutions and various kind of uncertainties, and whether the automatic resolution can cope with our delays
or if the resulting manœuvres will warp our planning entirely.

6 Conclusion
We have presented a new ground holding approach to solve all potential conflicts occurring above
a given flight level for a day of traffic in the French airspace. Rather than trying to respect sector
capacity constraints, we model each possibly conflicting situations between any two aircraft and impose
18 N . BARNIER , C . ALLIGNOL

adjustments of departure times to keep them separated, with the hypothesis that aircraft could precisely
follow their planned 4D-trajectories.
The resulting problem size is huge, but our CP algorithm is able to reach optimal solutions for all
conflicts occurring inside the upper airspace. The resulting maximal delay, overall delay sum and ratio
of delayed flights can be comparable to delays allocated by the CFMU, but for the busiest days, solving
all conflicts by ground delaying can be far too costly. Nevertheless, our solutions were validated with the
CATS simulator, checking that no conflict under the given flight level for a delayable aircraft remains.
We have also presented a first step toward taking uncertainties into account by extending the forbidden
intervals of conflicting flights. However, an extension as small as 4 min, which is able to cope only with
a ±2 min-uncertainty on the departure time generates tremendous amounts of delays, far above SESAR
performance objectives.
We plan to overcome these issues and further assess the possible outcomes of 4D-trajectory planning
in the context of Episode 3 WP4 and address larger (European) instances with various techniques like
combining our delay algorithm with a prior flight level allocation, repeatedly solving the problem on a
sliding time windows or solving the remaining conflicts with a CATS resolution module.

Acknowledgments
The authors would like to thank the anonymous referees for their valuable suggestions and constructive
comments that helped to improve this paper.

Glossary

ACARE Advisory Council for Aeronautics Research in Europe

ASM Airspace Management
ATC Air Traffic Control
ATCC ATC Center
ATFM Air Traffic Flow Management
ATM Air Traffic Management
CASA Computer Assisted Slot Allocation
CATS Complete Air Traffic Simulator
CFMU Central Flow Management Unit
CP Constraint Programming
CSP Constraint Satisfaction Problem
DSNA Direction des Services de la Navigation Aérienne
DTI Direction de la Technique et de l’Innovation
ENAC École Nationale de l’Aviation Civile
ERASMUS En-Route Air Traffic Soft Management Ultimate System
FaCiLe Functional Constraint Library
FMP Flow Management Position
FL Flight Level
ft foot/feet, 1 ft = 0.3048 m
GPWS Ground Proximity Warning System
JSP Job-shop Scheduling Problem
NM Nautical Mile, 1 NM = 1852 m
P-RNAV Precision Area Navigation
PREDICT Variant of TACT used for Pre-Tactical Work
RNAV Area Navigation
RVSM Reduced Vertical Separation Minima
SESAR Single European Sky ATM Research
TACT Tactical System
TCAS Traffic alert and Collision Avoidance System
 Trajectory Deconfliction with Constraint Programming 19

TMA Terminal Area

WP Work Package

References
ACARE (2004), Strategic research agenda 2 (SRA 2), Technical report, Advisory Council for Aeronautics Research
in Europe.
Alliot, J.-M., Bosc, J.-F., Durand, N. & Maugis, L. (1997), CATS: A Complete Air Traffic Simulator, in ‘16th DASC’.
Alliot, J.-M. & Colin de Verdière, D. (2003), ATM: 20 ans d’effort et perspectives, in ‘Symposium de l’Académie
Nationale de l’Air et de l’Espace : vers l’automatisation du vol et sa gestion’.
Archambault, N. (2004), Speed uncertainty and speed regulation in conflict detection and resolution in air traffic
control, in ‘ICRAT’2004’.
Baptiste, P., Le Pape, C. & Nuijten, W. (2001), Constraint-Based Scheduling, Applying Constraint Programming to
Scheduling Problems, Kluwer’s International Series in Operations Research & Management Science, Springer.
Barnier, N. (2002), Application de la programmation par contraintes à des problèmes de gestion du trafic aérien, PhD
thesis, Institut National Polytechnique de Toulouse.
Barnier, N. & Allignol, C. (2009), 4D-Trajectory deconfliction through departure time adjustment, in ‘International
Air Traffic Management R&D Seminar ATM-2009’, Napa (CA), USA.
Barnier, N. & Brisset, P. (2001), FaCiLe: a Functional Constraint Library, in ‘Colloquium on Implementation of
Constraint and LOgic Programming Systems CICLOPS’01 (Workshop of CP’01)’, Paphos, Cyprus.
Barnier, N. & Brisset, P. (2002), Graph coloring for air traffic flow management, in ‘CPAIOR’02: Fourth International
Workshop on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimisation
Problems’, Le Croisic, France, pp. 133–147.
Barnier, N., Brisset, P. & Rivière, T. (2001), Slot allocation with constraint programming: Models and results, in
‘International Air Traffic Management R&D Seminar ATM-2001’, Santa Fe (NM), USA.
Central Office for Delay Analysis (2009), CODA digest – delays to air transport in Europe, Technical report,
Eurocontrol.
CFMU (2000), Basic CFMU Handbook - General & CFMU Systems, 6.0 edn.
Cook, A. J., Tanner, G. & Anderson, S. (2004), Evaluating the true cost to airlines of one minute of airborne or ground
delay: Final report, Technical report, Eurocontrol.
Dalichampt, M., Petit, E., Junker, U. & Lebreton, J. (1997), Innovative slot allocation (ISA), Technical report,
Eurocontrol.
de Berg, M., van Kreveld, M., Overmars, M. & Schwarzkopf, O. (1998), Computational Geometry – Algorithms and
Applications, Springer.
Flener, P., Pearson, J., Ågren, M., Garcia Avello, C., Çelitkin, M. & Dissing, S. (2007), ‘Air-traffic complexity
resolution in multi-sector planning’, Journal of Air Transport Management 13(6), 323–328.
Garot, J.-M. & Durand, N. (2005), Failures in the automation of air traffic control, in ‘Colloque de l’AAA’.
Gianazza, D. & Guittet, K. (2007), Selection and evaluation of air traffic complexity metrics, in ‘25th DASC’.
Graham, R. & Young, D. (2006), Preparing an initial assessment of the SESAR concept of operations “EP3: Single
european sky implementation support through validation”, Technical report, Eurocontrol Experimental Centre,
France.
Granger, G. (2002), Détection et résolution de conflits aériens : modélisations et analyse, PhD thesis, École
Polytechnique.
Granger, G., Durand, N. & Alliot, J.-M. (2001), Optimal resolution of en route conflicts, in ‘International Air Traffic
Management R&D Seminar ATM-2001’, Santa Fe (NM), USA.
Tran Dac, H. & Baptiste, P. (2003), Airspace sectorization by constraint programming, in ‘RIVF’03’.
Van Hentenryck, P., Simonis, H. & Dincbas, M. (1992), ‘Constraint satisfaction using constraint logic programming’,
Artificial Intelligence 58(1-3), 113–159.