1.1 Airspace management

Aircraft that are due to fly within the European airspace have to choose between visual flight rules (VFRs) and instrument flight rules (IFRs). VFRs are based on the see-and-avoid principle and therefore require good visibility conditions; they are more flexible than IFR and mostly suitable for private aircraft. On the contrary, IFR rely on navigation instruments in the cockpit and allow flying in poor weather conditions. It is the flight mode used by commercial aircraft in Europe.

The diverse performance and mission types between VFR and IFR flights have led to a partition of civil airspace into several classes defined by the International Civil Aviation Organization (ICAO) to reduce the risk of collision. These classes can be roughly distinguished as follows:

• • Controlled airspace, where separation between aircraft is ensured by an air navigation service provider (ANSP).

• • Uncontrolled airspace, where only information and alert services are provided.

More specifically, the upper airspace (above flight level (FL)Footnote ² 180) and crowded areas around the largest airports are not authorized to VFR flights in order to segregate the two types of traffic. Furthermore, some volumes of airspace are military zones subject to strong usage restrictions or even totally forbidden to general air traffic.

To be authorized to fly with IFR through controlled airspace, a flight plan specifying all the characteristics of the flight must be filed with the ANSP, which has to acknowledge it and grant a clearance, possibly with modifications. The flight plan must indicate, among other data, the route to be followed, consisting of a sequence of beacons that structure the route network, as explained in Section 1.1.1.

To ensure trajectory monitoring and separation between aircraft, the controlled airspace classes are further divided into control sectors, which are three-dimensional volumes whose shape and capacity may vary over time and which are allocated to specific teams of controllers, as described in Section 1.1.2. The design of air routes, control sectors, and control centres is called airspace management (ASM) and is discussed in the two following sections.

1.1.1 Air routes

An air route is a sequence of legs (segments) in the horizontal plane, whose extremities, named waypoints, are positioned above ground-based radio beacons. As they are expensive to install and cannot be arbitrarily placed (depending on surrounding terrain), it is costly in terms of time and fuel to adhere to the corresponding route network. However, the accuracy of recent airborne radio navigation systems, like the global positioning systemFootnote ³ (GPS), which are integrated into the flight management system (FMS) responsible for the following of the planned trajectory, has allowed the definition of abstract waypoints that are not associated with any real ground-based devices and has enabled a more efficient usage of airspace. Such a navigation scheme is called area navigation (RNAV). Figure 1 presents a small part of the current route network over France and illustrates these two types of waypoints.

Figure 1

Excerpt of a map of the route network in the south of France. Black dots correspond to real waypoints associated with radio navigation beacons, whereas grey dots are abstract ones. Source: EUROCONTROL

RNAV offers much flexibility to the management of the air route network. Abstract waypoints can be placed so as to shorten significantly the routes, or even design direct routes, that is, shortest routes between two points (e.g., between origin and destination airports, or, more realistically, between entry and exit points of a given controlled airspace volume).

This direct route concept is operationally experimented since March 2011 in the Maastricht control centre (The Netherlands), in the context of the Free Route Airspace Maastricht project (EUROCONTROL, 2011), offering 142 direct routes to cross the concerned airspace. EUROCONTROL claims saving 624 000 NM (nautical miles) over a year, just by authorizing these direct routes off-peak (on weekends and from 00:00 to 08:00 on weekdays). From the year 2013, these routes should be permanently opened, which would require the devising of new control procedures, as traffic following direct routes is more entangled than with standard ones.

Whichever navigation mode is selected, the flight plan must state the origin and destination airports, the time of departure and estimated total duration of the flight, the intended route as a sequence of waypoints, the requested FL, the type of aircraft, and the air speed (plus other secondary data). Flight plans must be filed at least 3 hours before takeoff, which allows control and regulation organizations to know the intents of each controlled flight sufficiently in advance so as to compute the crossed control sectors. For regular flights operated by airlines, the filing of flight plans can be automated by the use of repetitive flight plans.

1.1.2 Control sectors

An airspace with the size and traffic volume of the European one cannot be globally managed by a single team of controllers. The European airspace is therefore divided into functional units, called elementary sectors, which allow the distribution of the control workload over several control stations but requires the coordination of the flows between adjacent sectors. An elementary sector is a volume of airspace bounded by a geographical contour in the horizontal plane, a floor FL and a ceiling FLFootnote ⁴. Depending on traffic demand, elementary sectors can be merged or singled out to form a control sector monitored by a pair of controllers (see Section 1.3.2).

Control centres. The management of control sectors is distributed among 75 European ATCCs, which have the daily responsibility of defining open control sectors and allocating them to controllers. Figure 2 shows the shape of the European ATCC at FL 300 (i.e., around the cruise altitude of most commercial jets). Each control sector is associated with an hourly capacity, which is a number of entering flights that must never be exceeded and is determined by the relevant ATCC.

Figure 2

ECAC control sectors at FL 300. Each control centre is depicted with a distinct shade of grey

The capacity of a control sector is determined empirically, taking into account the volume of the sector; the type of flows—descending or climbing aircraft are more difficult to separate than levelled ones; the number of flow intersections; the presence of restricted (e.g., military) areas; and the experience of past traffic.

Opening scheme. The shape of control sectors can be dynamically modified during the day to match the traffic demand. During peak hours, sectors can be split into smaller ones to provide more capacity, requiring more controllers. But when the traffic is low, it would be wasteful to keep too many open sectors, so they are grouped together and managed by fewer controllers. Only some predefined groups of elementary sectors (connected and manageable from a controller standpoint) can be used to partition each control centre, and the opened sectors must entirely cover the concerned airspace 24 hours a day. Figure 3 illustrates these configuration change operations on a fictitious (small) control centre.

Figure 3

Splitting and merging of control sectors, with each shade of grey corresponding to a distinct control sector. Configuration (a) is adapted to SW–NE flows whereas configuration (b) corresponds to SE–NW ones

As a control centre can be dynamically reconfigured during the day, the global capacity of the corresponding airspace may change accordingly (even if the capacity of a given sector is constant) to match the traffic demand. To anticipate possible congestion, each control centre issues a forecast of its reconfiguration sequence, called an opening scheme, specifying which control sectors will be opened when during the day of operation, taking the filed flight plans and the number of available controllers into account.

Once the opening scheme has been defined with the capacity of each open sector, regulation measures are required to control the traffic while preventing overloads, as explained in Section 1.2.

1.2 Regulations

In Europe, the Central Flow Management Unit (CFMU) is in charge of coordinating the various national control organizations of the ECAC area, so as to ensure flight safety while expediting the flow of traffic. In particular, one of its missions is to regulate traffic flows to prevent congestion and to make the most efficient use of available airspace. This section presents the regulation means, called Air Traffic Flow and Capacity Management (ATFCM), operated by the CFMU to carry its missions through, and the costs of these regulations in terms of delays.

1.3 Air traffic control

The two main objectives of air control services are the safety and fluidity of air traffic. In order to achieve these objectives, five missions have to be carried out successfully, namely preventing collisions between aircraft; preventing collisions between aircraft and potential obstacles; speeding up and organizing air traffic; providing information for safer and more efficient flights; and alerting rescue units when needed.

1.3.2 Methods for air traffic control

Each control sector is handled by a pair of air traffic controllers: a coordinator and a radar controller.

The coordinator is in charge of medium-term traffic organization. The main duty consists in the transfer of aircraft from the sector to the next sector or from the previous sector. The exchanged information is transmitted to the radar controller in the form of a strip, which is a small piece of paper that sums up important characteristics of each flight: altitude, speed, route, etc.

The radar controller ensures flight safety and a fluid traffic. The main duty is the prevention of collisions by indicating (by radio) manoeuvres to aircraft in order to respect a separation norm, which is a minimum safety distance, defined for en-route traffic (ICAO, 1996) as 5 NM horizontally and 1000 ft vertically (see Figure 4). A radar visualization provides for each flight its identification number, position, and speed. Different types of manoeuvres might be proposed, such as heading change, speed adjustment, FL change, or anticipated descent.

Figure 4

Separation norm for en-route traffic. No other aircraft must enter this volume

1.4 Limits and perspectives

The current ATM system, as described in the previous sections, is efficient and reactive. However, some areas in the European airspace are regularly saturated, thus showing structural limits of the model. As for air traffic, predictions by EUROCONTROL indicate a continuous growth for the next decades (see Section 1.4.1). This growth is likely to saturate the current system (see Section 1.4.2). We state the impact of trajectory prediction accuracy on the performance of ATM systems (see Section 1.4.3) and present some perspectives for ATM, in terms of both operational concepts and research studies (see Section 1.4.4).

1.4.1 Traffic evolution in Europe

Traffic forecasts provided by the Statistics and Forecasts (STATFOR) unit of EUROCONTROL (STATFOR, 2010) indicate a growth tendency in spite of the economic crisis taking place these last years. Several growth scenarios are considered for the year 2030, taking into account economic, technological, and environmental parameters:

• • Scenario A—Global Growth: strong economic growth, increasing globalization, resource availability enhanced by technology.

• • Scenario C—Regulated Growth: moderate economic growth, regulations to take into account the stakes of sustainable development.

• • Scenario D—Fragmenting World: increasing tensions between regions, leading to reduced trade and weaker economies.

• • Scenario E—Resource Limits (Peak Oil): oil supply deficiency after a production peak in the year 2020, economies unable to react.

In a previous version of the forecast, Scenario B was based on current growth indicators. It was discarded in favour of Scenario E, which was considered to be more relevant. Regardless of the selected scenario, STATFOR predicts a significant growth of European air traffic, as depicted in Figure 5, namely 40–120% more flights in the year 2030 compared to the situation in the year 2009.

Figure 5

Air traffic predictions in Europe for the year 2030: annual number of flights (millions) for several growth scenarios. Source: EUROCONTROL/STATFOR

2.1 Combinatorial problems

Solving a combinatorial problem involves finding a combination of discrete finite objects that satisfies some given constraints. Candidate solutions are combinations that may be encountered during a solution attempt, but they need not satisfy all given constraints. Solutions are candidate solutions that satisfy all the given constraints. Many combinatorial problems are hard to solve because there are very many candidate solutions and very few solutions: this is because a candidate solution to an individual constraint need not be a candidate solution to another individual constraint, but a solution has to be found that satisfies all given constraints. Often the only known way to solve a combinatorial problem is by intelligently searching through all the possible candidate solutions.

These problems occur in many real-world situations. Examples are scheduling, timetabling, planning, logistics, transportation, configuration, personnel allocation (rostering), sequencing, flow management, bin packing, and floor design. For solving these problems, one must find values for some given decision variables (which are the unknowns) within their given domains (which are sets of possible values), so that some given constraints (which are relations) on these variables are satisfied and possibly that some cost (or benefit) expression, called the objective function, on these variables is minimized (or maximized). One distinguishes between satisfaction problems (where there is no objective function) and optimization problems (where there is an objective function).

For example, consider the following scheduling problem. We have a set of flights, each of which will pass through a sequence of control sectors that is assumed to be known in advance. We assume that the airspeed is predetermined, so the flight time of each flight in each of its control sectors is known. Each control sector has a load limit that specifies the maximum number of flights that can be present in it at any time. For each flight, we use a decision variable that denotes its takeoff time. For each flight, there are constraints on when it can take off. For each control sector, there is a constraint that enforces its load limit. A satisfaction problem is to find takeoff times that respect all constraints. An objective function could include a measure of load balancing to ensure that at all times each control sector has a similar number of flights present.

In real life, combinatorial problems are often crucial, as the world is becoming increasingly complex and competitive, and as we need a more sustainable industry and society. Prime objectives are the efficient handling of scarce or expensive resources and the minimization of environmental impact. Modern combinatorial problem solver software usually outperforms the best human experts by a wide margin in solving time and solution quality, hence research is very active in this area.

2.2 Problem modelling via constraints

Constraint programming (CP) is a successful approach to the modelling and solving of combinatorial problems. Its core idea is to capture islands of structure, also called combinatorial sub-structures, that are commonly occurring within such problems and to encapsulate declaratively their procedural inference algorithms by designing specialized reusable software components, called constraints.

As a running example, let us consider the Kakuro puzzle, with the caveat that this is not meant to imply that the discussed techniques are limited to (small) puzzles. See the left side of Figure 6: each word of a Kakuro puzzle is made of non-zero digits, under the two constraints that the letters of each word are pairwise distinct and add up to the number to the left (for horizontal words) or on top (for vertical words) of the word. Hence there is one decision variable for each letter of the puzzle, with the integer set {1, 2, …, 9} as domain. This is a satisfaction problem, as there is no objective function. The solution to this puzzle is given on the right side of Figure 6; note that a Kakuro puzzle is always designed so as to have a unique solution.

Figure 6

A Kakuro puzzle (on the left) and its solution (on the right), both taken from the crossword package for LaTeX by Gerd Neugebauer at CTAN.org

Beside the usual binary comparison constraints (<, ≤, =, ≠, ≥, >), with arguments involving the usual binary arithmetic operators (+, −, ·, etc.), a large number of combinatorial constraints (usually called global constraints in the literature), involving more complex structures and a non-fixed number of arguments, have been identified.

For example, the AllDifferent({x ₁, …, x_n}) constraint requires its n decision variables x_i to take pairwise different values. This constraint is useful in many challenging real-life problems, as well as for modelling the first constraint of the Kakuro puzzle, as there is an AllDifferent constraint on each word. Each such constraint wraps a conjunction of binary x_i ≠ x_j constraints into a single n-ary constraint; this enables a more global view of the structure of the problem, which is a prerequisite for solving it efficiently (as we shall see in Section 2.3).

As another example, the Sum({x ₁, …, x_n}, Rel, c) constraint requires the sum x ₁+⋯+x_n of the n decision variables x_i to be in relation Rel with the constant c. This constraint can be used for modelling the second constraint of the Kakuro puzzle, as there is a Sum({x ₁, …, x_n}, =, s) constraint for each word [x ₁, …, x_n] with required sum s.

Hundreds of useful constraints have been identified and are described in the Global Constraint Catalogue Beldiceanu et al. (Reference Beldiceanu, Carlsson and Rampon2007), the most famous ones being element (Van Hentenryck & Carillon, 1998), cumulative (Aggoun & Beldiceanu, Reference Aggoun and Beldiceanu1993), AllDifferent (Régin, Reference Régin1994), and cardinality (Régin, Reference Régin1996).

Constraints can be combined to model a combinatorial problem in a declarative and very high-level fashion. For example, the Kakuro puzzle can essentially be modelled as follows, assuming that a hint for word w with required sum s is encoded as the pair 〈w, s〉:

(1)

For combinatorial problems, CP is not limited to decision variables with finite integer domains: arbitrary enumerations can be used as domains, as well as domains over higher-order data such as sets (of integers) and graphs.

In the following sub-section, we show that constraints are not just a convenience for high-level modelling, but can also be exploited during the solution process.

2.3 Problem solving by inference and search

By intelligent search, we mean search where at least some form of inference takes place at every step of the search in order to reduce the cost of brute-force search (Hooker, Reference Hooker2007):

In the following, we discuss two CP ways of solving problems that have been modelled using constraints. The classical approach is to perform systematic search (Section 2.3.1), and a more recent approach is to trade for time the guarantees of systematic search by performing stochastic local search (SLS; Section 2.3.2): the two approaches use completely different forms of inference, which is encapsulated in reusable fashion within the constraints (Section 2.3.3).

2.3.1 Systematic search

Classically, CP solves combinatorial problems by systematic tree search, together with backtracking, and performs at every node of the search tree a particular kind of inference called propagation. After explaining propagation, we will explain in more detail how such systematic search is conducted.

Propagation of one constraint. For each individual constraint, a propagation algorithm (or propagator) prunes the domains of its decision variables by eliminating impossible values according to some desired level of consistency. For example, under domain consistency (DC) every domain value of every decision variable participates in some solution to the constraint that involves domain values of the other decision variables. Also, under bound consistency (BC) every domain bound of every decision variable participates in some solution to the constraint that involves domain values of the other decision variables.

For example, consider the constraint AllDifferent ({x, y, z}). Let x, y range over the domain {1, 3} and z over {1, 2, 3, 4}: we denote this state by {x, y↦{1, 3}, z↦{1, 2, 3, 4}}. From this state, propagation to DC leads to the state {x, y↦{1, 3}, z↦{2, 4}} since x and y must split the values 1 and 3 between themselves so that z cannot take any of these two values. From the same start state {x, y↦{1, 3}, z↦{1, 2, 3, 4}}, propagation to BC leads to the state {x, y↦{1, 3}, z↦{2, 3, 4}} since there do exist solutions to the constraint where z takes its new lower bound value 2 or its old (and new) upper bound value 4, so that the unfeasibility of the intermediate value 3 is not even checked. Note that, in this case, the resulting DC state is strictly stronger than the resulting BC state: while the initial state encodes a set of 2·2·4 = 16 candidate solutions, the BC state encodes a subset thereof with 2·2·3 = 12 candidate solutions, and the DC state encodes a subset of both with only 2·2·2 = 8 candidate solutions, including the four solutions. From a second start state {x, y, z↦{1, 2}}, propagation to DC or BC leads to the propagator signalling failure, because it is impossible to assign two values to three variables so that the latter are pairwise distinct. From a third start state {x↦{1}, y↦{3}, z↦{2, 4}}, propagation to DC or BC leads to no propagation, but the propagator can simultaneously detect that all 1·1·2 = 2 candidate solutions actually are solutions, so that the propagator can signal subsumption (or entailment).

The propagation of a constraint amounts to reasoning with possible domain values, but there is no obligation to prune all the impossible domain values, as just witnessed when comparing DC and BC. If a constraint has multiple propagators achieving different strengths of consistency (under different time complexities), then there is a default propagator but the modeller may also choose one of them, possibly via experiments to find out which one leads to the best trade-off in search effort; this is the first non-declarative annotation that may be added to an otherwise declarative constraint model (and we will encounter a second one below). Also, the propagator of a constraint only reasons locally, namely about the decision variables of that constraint, rather than globally, about all the decision variables of the entire problem.

Propagation of multiple constraints. Let us now consider the propagation of an entire conjunction of constraints, such as a constraint model like (1). Each constraint is propagated to its desired strength of consistency: this may take multiple invocations of some propagators and is choreographed by a fixpoint algorithm, which computes the weakest common fixpoint of all the propagators.

For example, consider the conjunction of binary disequality constraints, which is equivalent to the constraint AllDifferent ({x, y, z}) of the previous example. From the first start state {x, y↦{1, 3}, z↦{1, 2, 3, 4}}, propagation to the fixpoint of the three propagators, each propagated to DC or BC, achieves no pruning at all (unlike in the previous example), because each individual α ≠ β constraint is unsatisfiable only when its two variables α and β range over the same singleton domain. From the second start state {x, y, z↦{1, 2}}, propagation under DC and BC to the fixpoint also achieves no pruning at all (unlike in the previous example), so that search (see below) is necessary to reveal the inconsistency of the conjunction. This example actually mostly illustrates the importance of combinatorial constraints compared with their decompositions into conjunctions of more basic constraints, but a more interesting fixpoint computation will be given in the next example.

Search. We are now in position to explain how systematic tree search is conducted in order to solve a combinatorial problem modelled as a conjunction of constraints. It is an interleaving of propagation and search. Each node consists of the currently non-subsumed constraints and the current fixpoint state of all the propagators. The root of the tree has the fixpoint of the propagators for all the constraints of the model. As long as there exist non-subsumed constraints, the tree is grown at some leaf by branching into at least two sub-problems, obtained by mutually exclusive decisions on some decision variables. Decisions must be constraints themselves, hence they have propagators: the fixpoint algorithm is launched for computing each child of the considered leaf. Backtracking is performed when the fixpoint algorithm fails because the propagator of some constraint signals failure.

For example, at the fixpoint {x, y↦{1, 3}, z↦{1, 2, 3, 4}} of the previous example for , no propagator is subsumed. Upon exploring the sub-problems obtained for the decisions x = 1 and x ≠ 1, the search tree of Figure 7 is obtained. Note that on each leaf all three propagators are subsumed. The same branching would have been obtained from the node that was obtained in a previous example.

Figure 7

Search tree, with propagation at every node

Note that all communication between two constraints happens via the state of their shared decision variables: if the propagator of one constraint makes a suitable change to the state of a shared variable, then the propagator of the other constraint may be invoked.

Branching is subject to heuristics for the choice of the leaf as well as the choice of the decision variables, domain values, and predicates used in the decisions made. The leaf is usually chosen under depth-first search. Predefined branching heuristics can be combined for designing the decisions, or entirely new branching heuristics can be programmed. Many branching heuristics can be written in problem-independent fashion. Intuitively, such generic heuristics tackle the hardest parts of a problem first, such as the critical resources in scheduling problems.

For example, a commonly used variable selection heuristic is to follow the fail-first principle and choose one of the decision variables that currently has the smallest domain, as one can thus provoke failure (if any) earlier, since in the presence of propagation not all decision variables need to take a value before detecting failure. Thus, exponentially larger parts of the search tree are pruned upon earlier failure. Conversely, a commonly used value selection heuristic is to follow the best-first principle and choose a value that is most likely to lead to success (if possible), since one need not consider all values to find a first solution. Recently, adaptive heuristics have been designed, such as weighted degree (Boussemart et al., Reference Boussemart, Hemery, Lecoutre and Sais2004) they make decisions based on information collected during the search.

Other than the already mentioned indication of the desired strength of consistency for the constraints of the model, the provision of these branching heuristics constitutes the second non-declarative annotation that may be added to an otherwise declarative constraint model. The resulting search strategy is often the part of a constraint model that requires the most expertise. Novice constraint programmers can rely on default strategies.

It is important to stress that propagation at every node of the search tree, instead of just at its leaves, usually reduces the size of the search tree in a very drastic way, so that the overhead at every node of the search tree is well amortized by overall time gains.

Return to modelling. If experiments reveal that the current combination of model, consistency strengths, and branching heuristics is not powerful enough to solve problem instances with suitable effort, then one may have to reconsider the declarative model if no alternatives to the procedural choices turn out good enough.

For example, the Kakuro model (1) is very naïve, as there is poor communication via propagation between the AllDifferent and Sum constraints. Consider in Figure 6 the top-left horizontal word [x, y]: it is of length 2 and has the desired sum 4, hence the constraints AllDifferent ({x, y}) and Sum ({x, y}, = , 4) occur in the model, with the initial state {x, y↦{1, 2, …, 9}}. However, the fixpoint even under DC of the propagators of these two constraints is {x, y↦{1, 2, 3}}, hence the unfeasibility of value 2 is not inferred! Fortunately, it is easy to design, with the help of the Regular meta-constraint (Beldiceanu et al., Reference Beldiceanu, Carlsson and Petit2004; Pesant, Reference Pesant2004), a DC propagator for a custom constraint AllDiffSum so that AllDiffSum ({x, y}, = , 4) infers {x, y↦{1, 3}}. The resulting model

is orders of magnitude faster than the original one, especially upon hint-specific refinements such as rather using AllDifferent for words of length 9, because their sum can only be 45.

2.3.3 Conclusion about search and the role of constraints in search

Both in constraint-based systematic search and in CBLS, a problem solver software (or simply: solver) need only provide the master search algorithm, as well as implementations of the built-in (meta-)heuristics and constraints that are used in the problem model. The modeller is free to design custom (meta-)heuristics and constraints. A constraint fully declaratively encapsulates inference algorithms (propagators or violation functions and delta functions), which have been written once and for all and are invoked by the master search algorithm and the (meta-)heuristics in order to conduct the search for solutions.

The usage of constraints achieves code reusability. It also entails a clean separation between the declarative and non-declarative parts of the problem model (which together form the input to the solver), as well as a clean separation between search and inference within the solver itself. The slogan of CP is

because we also have more code modularity.

2.4 Success stories and solvers

CP has been an area of research since the late 1980s and is now a mature technology that has been successfully used for tackling a wide range of real-world complex problems, especially for scheduling (where the foundations were laid in Baptiste et al., Reference Baptiste, Le Pape and Nuijten2001), personnel rostering, and configuration problems. Practical applications are discussed, for example, in Freuder and Wallace (Reference Freuder and Wallace2000), Rossi et al. (Reference Rossi, van Beek and Walsh2006) and Wallace (Reference Wallace2007b).

Many CP solvers have been designed, the currently most used ones including CHIP (by www.cosytec.com), Choco (Choco Team (2010), at choco.emn.fr), Comet (Van Hentenryck and Michel (Reference Van Hentenryck and Michel2005), at www.dynadec.com), ECLiPSe (Apt and Wallace (Reference Apt and Wallace2006), at elipseclp.org), IBM ILOG CPLEX CP Optimizer (formerly known as ILOG Solver), JaCoP (at www.jacop.eu), Gecode (Gecode Team (2006), at www.gecode.org), and SICStus Prolog (Carlsson et al. (Reference Carlsson, Ottosson and Carlson1997), at www.sics.se/sicstus). It is worth noting that the modelling languages Comet (Van Hentenryck and Michel, Reference Van Hentenryck and Michel2005) and (Mini)Zinc (Garcia de la Banda et al. (Reference Garcia de la Banda, Marriott, Rafeh and Wallace2006), at www.g12.csse.unimelb.edu.au/minizinc) are equipped with multiple solvers of different combinatorial problem solving technologies, including CP and SLS.

2.5 Perspectives

We have seen (in Section 2.3.2) that the core idea of CP, namely the concept of constraint, can be successfully exported to another combinatorial problem solving technology, namely SLS, giving rise to CBLS. This creates opportunities for a deeper hybridization of propagation-based solving and CBLS solving (Wallace, Reference Wallace2007a). But there is no reason to stop with SLS. In fact, the concept of constraint is being exported to other combinatorial problem solving technologies, such as Boolean satisfiability (SAT), giving rise to satisfiability modulo theories (SMT), and integer programming (IP) (Hooker, Reference Hooker2007). We argue that CP is an ideal integration technology for hybrid solving.

Note that SLS traditionally has no notion of modelling language. Also, SAT and IP traditionally rely on modelling languages that are much lower-level (but still declarative) than those of CP and CBLS, but their solvers offer a unique black-box search heuristic, so that the user cannot investigate (as in CP and SLS) the design of a custom search (meta-)heuristic in order to override the default one in case the latter is deemed not efficient enough. For many (non-expert) users, the inconvenience of the lower-level modelling languages of SAT and IP is well offset by the availability of highly tuned black-box search, as search tuning is to them a daunting aspect of CP and SLS. Such a reflex recourse to SAT and IP misses opportunities, though, as no combinatorial problem solving technology can outperform all the other ones on all problems. Anecdotal evidence about when to apply which technology, or which hybridization of technologies, is slowly emerging. For example, propagation-based CP is emerging as the technology of choice for scheduling, personnel rostering, and configuration problems.

The remainder of this paper is an annotated bibliography on the usage of CP solvers, both propagation-based ones and CBLS ones, to problems in ATM. We also compare CP results with those of other techniques from artificial intelligence and knowledge representation, especially non-CBLS approaches to SLS, such as genetic programming; we are not aware of any papers using SAT or SMT solvers in this area. There is a very vast literature on using IP solvers and custom ad hoc algorithms, and we cannot do justice to it within reasonable size limitations (but see Leal de Matos and Ormerod (Reference Leal de Matos and Ormerod2000) for instance).

It is important to note that most of the discussed papers do not describe an application that could in principle be deployed. Instead, most works describe tools for long-term research about investigating the impact of new approaches to ATM, especially that current approaches may not scale to future airspace demands. We argue that CP is an ideal technology for this scenario, at it allows very fast prototyping of new or revised constraints compared with ad hoc algorithm design, without sacrificing (much) in efficiency. The stringent real-time demands of actually deployed applications are secondary at this moment since faster hardware will be available by the time of deployment and since extra effort can be put until then into increasing the performance (if not into designing from scratch a custom algorithm).

3.1 Route network design

The current route network in Europe is based on radio beacons, as described in Section 1.1.1. However, with the increasing precision of navigation systems, other types of routes might be considered in order to enhance traffic flow management (shorter routes, lower workload, etc.). In this context, Barnier and Brisset (Reference Barnier and Brisset2004) try to build a network of direct routes (i.e., straight routes from origin to destination) over the French airspace. Aircraft that share the same route are aggregated into flows, and a pairwise detection of intersections is performed between these flows. A CP algorithm then performs a flight-level allocation, so that two intersecting flows are vertically separated. The application of this method to several days of French domestic traffic shows that at least 20–24 FLs are necessary to avoid all crossings. However, unlike Barnier and Allignol (Reference Barnier and Allignol2011), this study does not take into account the preferred FLs, which reflect the performance of aircraft.

Rather than building direct routes, which might be difficult to handle by controllers at the continental scale, Brisset and Rivière (Reference Brisset and Rivière2005) propose to forge a route network over Europe that minimizes the travel distances, starting from a uniform grid in which cells are 240 km side-length squares; this methodology was driven by a new ATM concept called sector-less (Duong et al., Reference Duong, Gawinowski, Nicolaon and Smith2001). A simulated annealing meta-heuristic is used to move nodes in the grid, thus modifying the network. Evaluation is performed using the Floyd–Warshall shortest path algorithm. A second approach uses invariants, the analogue of constraints in CBLS solvers (see Section 2.3.2), to maintain shortest paths, improving the results of the meta-heuristic. The results obtained under this approach lead to travel distances comparable with those on the current route network, and showed the non-viability of the sector-less concept.

Perspectives. The design of a route network is a challenging problem: the use of direct routes makes the traffic difficult to handle by controllers, whereas creating a network from an initial grid proved not to be better than the current network. More efficient approaches could consist in defining multiple routes for each origin-destination pair, and performing an allocation of flights to such routes, as proposed by Leal de Matos and Powell (Reference Leal de Matos and Powell2003). This would also help the process of dynamic re-routing in case of hazardous meteorological phenomena or active military zones for example.

3.2 Contingency planning

Upon any failure of ATFCM, such as downtime of the computer-assisted slot allocation (CASA) system, no timely updates from ATFCM are available and the air traffic controllers of each aerodrome have no idea whether it is proper to release a flight or not. The only time a contingency plan was activated was in the afternoon of 17 May 2002. Towards this, EUROCONTROL requires the publication of a contingency plan, which indicates for each major aerodrome and geographical direction a series of flow directives, each consisting of a time span and a maximum number of hourly departure slots for that time span. For instance, for destinations to the west of Brussels National Airport (Belgium), from 09:00 to 12:00 a maximum of seven flights might be allowed to take off, but only four from 12:00 to 14:00. These flow directives are computed in such a way that some safety, efficiency, and fairness objectives are satisfied, also taking into account the traffic from minor aerodromes.

The generation of contingency plans within the CFMU of EUROCONTROL is currently done by human experts, with inadequate tool support for constructing globally optimal flow directives. Biannually, namely for the winter and summer timetables, they develop a three-fold contingency plan, namely one for weekdays, one for Saturdays, and one for Sundays. The total effort takes about two person-months per year. The current contingency plan can always be downloaded from the CFMU website (http://www.cfmu.eurocontrol.int/).

Contingency planning that is (more) automated and (more) geared towards constructing globally optimal flow directives is desirable, especially that it could then be done at the tactical level instead of the current strategic level, so that the quality of the generated contingency plans would be increased. Towards this, a feasibility study using CBLS was done, initially for the sub-problem where the flows and time spans have already been identified, so that only the optimal hourly rates are to be inferred: these initial results are reported from a CP perspective by Sundequist Blomdahl et al. (Reference Sundequist Blomdahl, Flener and Pearson2010a) and from an ATM perspective in Sundequist Blomdahl et al. (Reference Sundequist Blomdahl, Flener and Pearson2010b). Subsequently, entire flow directives (including the time spans) for given flows were inferred (Sundequist Blomdahl et al., Reference Sundequist Blomdahl, Flener and Pearson2012). Flows typically do not change much between contingency plans anyway, but could also be pushed into the optimization. Tested on the entire European airspace (with over 30 000 daily flights in the year 2008), the CBLS model (written in Comet) outperforms the human experts in terms of flight takeoff delays and sector capacity violations of the generated contingency plans.

Perspectives. The feasibility study was deemed successful and further development of the prototype is currently being considered by the CFMU, possibly leading to actual deployment.

3.3 Airspace sectorization

The design of control sectors described in Section 1.1.2 is largely based on expertise and simulation tools, and is carried out locally and incrementally to alleviate recurring congestion situations. Sectors are designed so as to keep the workload of controllers manageable for the typical flow of traffic that crosses the corresponding airspace along predefined routes (see Section 1.1.1). As mentioned in Section 1.3.2, the workload induced by the flow of traffic includes the monitoring of aircraft trajectories, the detection and resolution of conflicts, and the coordination with adjacent sectors whenever flights enter or exit the sector. The design of control sectors should therefore encompass these costs, as well as structural ATC hard constraints like convexity (and connectivity) with respect to air routes, minimal distance between a border and a crossing point, etc.

The main approaches to optimize the design of sectorization are either graph-based models with vertices representing intersections and edges the available routes, or geometry-based models that tile the airspace with basic cells. In both cases, the solution consists of a partition of the components of the model (vertices or cells) to form optimized control sectors that minimize controller workload and balance the traffic. The graph-based model is more compact than the geometry-based model, but the former does not directly define the sector borders as does the latter, so geometrical sectors still have to be constructed from the partition of vertices.

Building on the model of Delahaye et al. (Reference Delahaye, Schoenauer and Alliot1998) that solves the graph-based version of the problem with a genetic algorithm and uses a Voronoï diagram to define precisely the borders of sectors, Tran Dac et al. (Reference Tran Dac, Baptiste and Duong2005) present a CP approach taking most of the aforementioned operational constraints into account. To be able to solve large instances, the problem is solved with a hybrid algorithm using first a good solution obtained with a heuristic and then locally improving the solution with an exact CP formulation on small subsets of the sectors. Geometrical sectors are then built with triangulation techniques similar to the ones used by Delahaye et al. (Reference Delahaye, Schoenauer and Alliot1998). Problem instances of up to 1000 vertices to partition in 80 sectors are solved.

Jägare (Reference Jägare2011) starts from a division of the airspace into hexagonal cells, say with a diameter of 5 NM and a height of 1000 ft, and aims at clustering these cells into a given number of sectors, so that some hard constraints are satisfied (namely balanced sector workloads, no flight re-entries into the same sector, and no flight crossings of sectors in less than a minute) and the number of sector entry points is minimized. Custom propagators had to be designed for these constraints. The data for the experiments is provided by the Arithmetic Simulation Tool for ATFCM and Advanced Concept (ASTAAC) tool of the EUROCONTROL Experimental Centre (EEC). This tool actually pre-clusters some cells into abstract functional blocks (AFBs) according to additional constraints (sufficient distance from potential conflicts and trajectories to sector boundaries), so that the input to sectorization is actually a division of the airspace into cells and AFBs. Experiments were run on up to a few hundred thousand cells, to be clustered into five sectors. In comparable run-times on the same machine, the constraint program produces much better sectorizations than NEVAC Sector Builder, which is a greedy algorithm that comes with ASTAAC and considers the no-re-entry and no-short-crossing constraints to be soft and yet does not systematically yield fewer sector entry points. Two hard constraints, namely the physical contiguity and compactness of the resulting sectors were initially not implemented: the resulting sectors are sometimes disconnected or of highly irregular shapes, so that current air traffic controllers would be very uncomfortable in working with them. The design of new constraints for enforcing contiguity and compactness is on-going work: when ready, they can be plugged into the current constraint program without changing anything else, except possibly the heuristics of the search procedure.

On a larger scale, the sectorization problem once more occurs while designing air-traffic control centres (there are currently 75 ATCCs in Europe), which have the responsibility for a group of sectors located in a limited zone of airspace. Traditionally, European ATCCs were essentially limited to national airspace zones, but in the context of the Single European Sky, EUROCONTROL was mandated to establish transnational functional airspace blocks (FABs, not to be mixed up with AFB) so as to enforce regional cooperation in the seamless management and control of traffic flows in the ECAC zone. To this end, Bichot and Durand (Reference Bichot and Durand2007) propose a novel meta-heuristic called fusion fission (and inspired by the corresponding nuclear-physical phenomenon), which is particularly well-suited to solve the graph partitioning problem used to model this airspace design problem: vertices are sectors, weighted by the number of aircraft crossing it, and edges between two neighbouring sectors are weighted by the number of aircraft passing from a sector to another one; the algorithm then attempts to minimize the weight of edges cut by the partition, which corresponds to coordination workload between ATCCs, and maximize the weight of vertices in each part, keeping an imbalance factor of 2 between parts (as the largest ATCCs may contain twice as many sectors as the smallest ones). The fusion fission meta-heuristic seems to outperform consistently the compared partitioning libraries and outputs FABs that much improve over the coordination workload and imbalance of the current ATCC partition.

Perspectives. The implementation of airspace optimizations that alter the shape of basic control sectors implies a heavy cost in controller training, as controllers are highly specialized in the management of their specific sectors and it takes several years to qualify them on new sectors. Moreover, the redesign of ATCCs would induce a new dispatch of radar data and probably the building of costly new infrastructures to host them. Contrary to lighter optimizations that only concern current control structures without modifying them, like the optimization of opening schemes described in the next section, changes in airspace design have very important transition costs and must be very carefully planned.

3.4 Sector opening scheme

In order to adapt the capacity of ATCCs to traffic demand, flow management experts (called flow management position: FMP) work out an open-sectors plan for each ATCC (as described in Section 1.1.2), depending on the number of available controllers. The latter may vary during the day from a single pair handling the whole centre during off-peak hours to enough people to control each elementary sector individually, according to a predetermined schedule roughly fitting the traffic forecast. Only predetermined configurations can be usedFootnote ⁸ and the schedule of open sectors should match the forecast as closely as possible without exceeding the declared capacity (associated with each possible configuration) in order to guarantee the safety of flights while avoiding over-sized ATCC configurations and the wasting of resources. Along with flight plans, these opening schemes define the main input to the slot allocation phase of the pre-tactical regulations (see Sections 1.2 and 3.6).

Delahaye et al. (Reference Delahaye, Alliot, Schoenauer and Farges1995) propose to model the optimization of opening schemes as a problem of partitioning a graph into connected components, similarly to the optimization of the sectorization presented by Delahaye et al. (Reference Delahaye, Schoenauer and Alliot1998) and mentioned in Section 3.3. For a fixed number of regroupings (merged or individual sectors), the suggested optimization criterion combines the balancing of the control workload in each sector and the minimization of the coordination workload between sectors. As in Delahaye et al. (Reference Delahaye, Schoenauer and Alliot1998), the problem is solved with a genetic algorithm and the process is iterated hourly in order to match dynamically the traffic, but the variation of the number of open sectors is not taken into account.

Kerlirzin et al. (Reference Kerlirzin, Manchon, Plusquellec and Gotteland2000) present an interactive tool for FMPs to minimize the number of required ATFCM regulations. Starting with all the capacity constraints, the corresponding slot allocation problem is solved with CP as described by Chemla et al. (Reference Chemla, Diaz, Kerlirzin and Manchon1995) and mentioned in Section 3.6. Only the most penalizing sectors are then constrained to be regulated with a capacity limit, according to some user-defined participation threshold, and the slot allocation is computed again. If overloads appear to be too much in excess (above 20% in the study), the process is iterated with a smaller participation threshold.

To automate the determination of opening schedules, both Barnier (Reference Barnier2002), using CP, and Gianazza et al. (Reference Gianazza, Alliot and Granger2002), comparing two tree search methods (A* and branch-and-bound) and a genetic algorithm, solve the problem for predefined operational groups of sectors only and compute an optimal partition with respect to the distance to the maximal capacity for each hour, penalizing overloads and underloads to avoid wasting ATC resources. The number of available controllers during the day is taken into account as an upper bound for the number of open sectors for each hourly configuration, which contributes to the optimization criterion as well. Both studies report optimal results and short computation times for CP and the ad hoc branch-and-bound algorithm, resulting in less costly opening schemes, both in terms of required controllers and in terms of slot allocation delay. Furthermore, Barnier (Reference Barnier2002) attempts to take the transition between successive configurations into account as an additional constraint, in order to generate operationally feasible schemes at the price of a slight increase in the cost.

However, as explained in Section 1.4.2, the hourly capacity defined as a number of flights entering a sector may not be the most appropriate criterion to model the workload of controllers. Moreover, as remarked by Barnier (Reference Barnier2002), actual sector openings observed during operations are only remotely connected to pre-tactical opening schemes, which are much more dynamic and almost constantly exceeding declared capacities. To model the ATC workload better, Gianazza and Guittet (Reference Gianazza and Guittet2006) investigate the links between a set of metrics from the literature and the grouping or ungrouping decisions taken by controllers, which should correspond to workload thresholds. A neural network is trained on actual data and the most significant factors are subsequently extracted. Simulations with a neural network, considering a reduced set of metrics only, show the relevance of the approach, as the splitting and merging decisions are accurately predicted.

Perspectives. Sector opening schemes seem to be a good candidate for optimization technologies like CP, as they replace human expertise by sound optimization algorithms without changing operational procedures, and as they may reduce the cost of both the slot allocation phase and ATC by better matching the offered capacity to the traffic demand. However, as capacities only approximately represent workload and as real openings generally do not closely adhere to the opening plan, the operational impact of optimized plans should be further assessed by real-life experimentation.

3.5 Workload management

As stated in Section 1.4.2, reducing the workload of controllers is mandatory in order to be able to cope with an increasing European traffic demand. Considering the sector-based structure of the current ATC system, it is a way of increasing airspace capacity. In this context, many metrics have been defined to model workload and act as criteria for various optimization methods: linear programming, SLS, CP, etc.

Hildum and Smith (Reference Hildum and Smith2007) propose to reduce workload by constructing a movement plan that is conflict-free. Rather than considering conflict avoidance from a local and tactical perspective, a scheduling process in space and time is applied, taking into account likely areas of congestion. The airspace is modelled using octrees, a three-dimensional extension of the well-known quadtrees, which greatly improve the computational complexity of finding such constrained areas. This scheme is applied on a set of military-like missions where aircraft must reach a target from one of the departure bases and come back; the largest solved instance involved 1000 targets and 10 bases. Building upon this preliminary approach, a technique for improving robustness is introduced in Hildum and Smith (Reference Hildum and Smith2012). A coarser-grained conflict relation models an envelope within which aircraft are allowed to move in order to avoid conflicts in a reactive manner. An octree structure is again used to generate conflicting neighbourhoods in a limited computation time.

The ERASMUS project (En-Route Air traffic Soft Management Ultimate System) of Villiers (Reference Villiers2004) aims at dynamically reducing traffic workload by means of small speed adjustments. Trajectories are predicted over a 20-minute anticipation window and checked for potential conflicting situations. When possible, conflicts are avoided by slightly changing aircraft speed (usually within a −3% to +6% margin). Otherwise, that is when speed regulation is not enough, the controller in charge solves the conflict with usual techniques. Therefore, this method can be seen, from the controller's point of view, as a filter that could be integrated in two different ways into the current system: either as a subliminal filter where speed modifications are small enough to fit within the uncertainty on the controller's perception of speeds, or as an informative filter by asking the controller for validation of the speed change. The first prototypes for this project use an evolutionary algorithm to solve conflicts, minimizing the number of manoeuvres as a first criterion and the overall delay induced by the speed changes as a second one.

Instead of performing conflict avoidance in a tactical setting with a short notification time, Barnier and Allignol (Reference Barnier and Allignol2009) propose a conflict-free planning method based on CP. An exact four-dimensionless conflict model is introduced, where each violated constraint implies a conflict in a fast-time simulation. The only degrees of freedom during planning are takeoff times, taken for each flight in a bounded interval (usually 90 minutes for national traffic). Starting from simulated four-dimensionless trajectories, the problem of allocating a takeoff time to each flight so that no conflict occurs during the considered time period (usually 24 hours) is modelled as a constraint satisfaction problem. The optimization phase aims at minimizing the maximum allocated delay, so as to preserve equity among airlines and be able to obtain an optimal solution in reasonable computation time. The global performance of the planning, which can be measured by the sum of all delays, is maintained at a low value thanks to adapted search heuristics. Instances involving up to 9000 flights (for 24 hours of traffic in the French airspace) are solved within one minute. More details about the model and results on numerous traffic samples are found in Barnier and Allignol (Reference Barnier and Allignol2012). In order to enhance further the planning, a prior flight-level allocation is introduced in Barnier and Allignol (Reference Barnier and Allignol2011), aiming at reducing the workload of the takeoff time allocation problem. This prior phase is also solved with CP, minimizing the deviation between allocated FLs and optimal FLs.

Flener et al. (Reference Flener, Pearson, Ågren, Garcia Avello, Çeliktin and Dissing2007a, Reference Flener, Pearson, Ågren, Garcia Avello, Çeliktin and Dissing2007b) resolve traffic workload in a multi-sector planning context. They use a definition (QinetiQ, 2004) of the moment workload of a sector s at a moment m as a weighted average of the number of flights that are at m inside s, the number of flights that are at m in climbing or descending phase inside s, and the number of flights that are at m at most 2 minutes beyond the entry to s or before the exit from s; note that the workload does not depend on potentially interacting pairs of flights, because it was found that traffic volume and vertical state already capture this effect. The interval workload of a sector s during a time interval is the average of the moment complexities of s at sampled moments within . On a rolling horizon basis, the objective is to balance the complexities of the sectors of the considered airspace during a short interval some 20–90 minutes into the future. This is achieved as a side effect of minimizing the sum of the interval complexities of the considered sectors during that interval. The allowed forms of workload resolution, and hence the constraints, are any combination of the following:

• • Temporal Re-Profiling. Change the entry time of a flight into the chosen airspace: if it is not airborne yet, then change its takeoff time by an integer amount of minutes in [−5, …, +10], else change its remaining approach time by a speed-up rate of at most 5% or a slow-down rate of at most 10%.

• • Vertical Re-Profiling. Change the altitude of passage of a flight over a way-point in the chosen airspace by an integer amount of FLs within [−30, …, +10], so that the flight climbs at most 10 levels per minute, or descends at most 30 levels per minute if it is a jet, or descends at most 10 levels per minute if it is a turbo-prop.

The underlying assumptions are that sector entry times can be controlled with an accuracy of one minute (so that a flight profile is just shifted in time upon temporal re-profiling) and that flight time between two waypoints does not change if one restricts the vertical re-profiling to be ‘small’. The resulting re-profiling can be subliminal from the air traffic controller perspective. In order to make this a non-zero-sum game, the user can set the percentage of flights that must be kept within the chosen airspace (rather than risk being delayed into the next interval); also note that vertical re-profiling can reduce the workload of a sector without increasing it in another sector. A prototype was designed by CP to experiment on the upper-airspace sectors of the BeNeLux countries, which have very high traffic demands, during the busiest day of the year 2004: compared with the original CFMU flight profiles, 2 runtime minutes suffice to almost halve the complexities and balance them much better. Constraints (such as lower and upper workload bounds after the re-balancing, first-scheduled first-served ground-holding, airline equity on re-profiling, etc.) can be added in a modular fashion to make the scenario more realistic.

Perspectives. Handling uncertainties remains one of the main challenges for workload management, which is often implemented as a strategic filter (see Section 1). Indeed, the prediction of aircraft positions far in advance is currently subject to numerous sources of uncertainty (wind force and direction, takeoff time, vertical profile, etc.) that can only be dispelled at a shorter term. Therefore, regulation measures are too costly for large uncertainties, so that a dynamic iteration process can be necessary in order to update periodically the flight information and thus enhance the prediction, as mentioned in the introduction of Section 3.

3.6 Slot allocation

Since the early 1990s, several studies have been carried out to improve ATFCM regulations, in particular by research and development teams at the French civil aviation research centre, Centre d’Études de la Navigation Aérienne, such as the early work of Chemla et al. (Reference Chemla, Diaz, Kerlirzin and Manchon1995), which laid the foundation for the modelling by CP of the slot allocation problem, and at the EEC in Brétigny, France. The algorithm that computes the slot allocation in the CASA software, described by CFMU (2011) and in Section 1.2.2, is a greedy algorithm, very robust and efficient in a dynamic operational context, but not based on a rigorous mathematical modelling and suffering from some flaws that combinatorial optimization technologies like CP can help to prevent.

First, CASA does not try to maintain a valid solution whenever a flight is subject to multiple delays, as the two main constraints of its specification, namely sector capacity and the first-scheduled first-served principle, can be violated. However, most studies, especially the one by Dalichampt et al. (Reference Dalichampt, Petit, Junker and Lebreton2001), question the pertinence of adherence to the latter, which has too costly an impact on the overall amount of delay to justify the notion of fairness it implements. A few other studies, such as those by Degrand and Mercier (Reference Degrand and Mercier2000) and Hassani Bijarbooneh et al. (Reference Hassani Bijarbooneh, Flener and Pearson2009), allow some capacity constraints to be relaxed so as to provide the best possible solutions for over-constrained instances in a dynamic operational context.

Second, CASA does not attempt to optimize globally the amount of delay—which is an NP-hard problem—besides locally improving later slots when flights are dynamically cancelled or postponed. All cited studies formulate a proper mathematical model and solve it with well-established combinatorial optimization algorithms belonging to operational research, CP, or SLS. Depending on the qualities of the algorithm and the goal of the study, either an optimal solution or a feasibility proof is searched for with complete algorithms such as those by Degrand and Mercier (Reference Degrand and Mercier2000) and Barnier et al. (Reference Barnier, Brisset and Rivière2001), or good solutions are obtained quickly with stochastic algorithms such as those by Hassani Bijarbooneh et al. (Reference Hassani Bijarbooneh, Flener and Pearson2009) and Junker (Reference Junker2012).

A side effect of these mathematical formulations of the ATFCM problem is to challenge the relevance of sector capacity being defined as a number of aircraft entering a given sector in one hour (see Section 1.1.2), because the time period over which the constraint should be enforced is not clearly specified. CASA implicitly considers a very tight version equivalent to imposing the constraint over any time period starting at multiples of the length of the slots (i.e., 60/capacity), such that the capacity demand is evenly distributed in a regulated sector. However, as explained by Barnier et al. (Reference Barnier, Brisset and Rivière2001) and Junker (Reference Junker2012), if ATFCM models literally adhere to the definition of sector capacity by opening schemes (see Section 1.1.2), then the capacity demand may reach twice the bound specified by the constraint for the intermediate time windows, which would jeopardize the safety of flights. Also, traffic peaks are likely to occur over short time periods, especially at the beginning of the hourly constraints, where flights exceeding the capacity of the previous time window would be put back by optimizing algorithms to maintain the delay cost as low as possible. To address this issue, Barnier et al. (Reference Barnier, Brisset and Rivière2001) compare overlapping hourly constraints and a dual model using the sort constraint introduced by Bleuzen-Guernalec and Colmerauer (Reference Bleuzen-Guernalec and Colmerauer1997), equivalent to placing hourly constraint at any time step, whereas Junker (Reference Junker2012) studies the impact of smoothing constraints, which are capacity constraints over shorter time periods (down to 10 minutes), proportional to the hourly one.

Perspectives. Other studies focusing on controller behaviour, such as the one by Gianazza and Guittet (Reference Gianazza and Guittet2006), have concluded that capacity alone does not accurately estimate the workload but that other factors have to be taken into account (see Section 1.4.2). Degrand and Mercier (Reference Degrand and Mercier2000) compare regulations constrained by classical capacity and by load capacity constraint regulation, which restricts the number of flight simultaneously allowed in a given sector at each time step and is not as tight as capacity, concluding that the latter is much more efficient with respect to the amount of delay. Barnier and Allignol (Reference Barnier and Allignol2012) even propose to abandon the aggregated model with sectors and capacity, and to compute directly a conflict-free slot allocation to decrease controller workload and increase ATC efficiency.

The question also arose whether, instead of dynamically adjusting airspace demand to a static airspace capacity, one should rather dynamically adjust airspace capacity to airspace demand, by dynamically designing sectors that can handle the current demand, as discussed in Section 3.3.

3.7 Departure management and runway allocation

At an airport, there are many flights that need to be managed both before and after takeoff. For takeoff, this is typically done by three controllers: the preflight controller, the taxiway controller, and finally the runway controller. Each controller tries to optimize the flow of flights for his section. The runway controller is given a sequence of flights by the preflight controller, and there are, at that point, only limited possibilities to reorder the flights. The runway controller then directs each plane to a specific exit point into the airspace of the airport. Each flight is allocated a departure slot, which is specified as a 15-minute time window. At an airport, the runways are a scarce resource. A flight has to be managed from leaving the airport stand to takeoff and finally to its exit point, while taking into account possible conflicts with other flights and the use of scarce physical resources.

In van Leeuwen and van Hanxleden Houwert (Reference van Leeuwen and van Hanxleden Houwert2003), a decision support tool is presented to aid the controllers in planning the movements of flights within an airport and its airspace. The problem of optimizing flights is modelled first using CP. The constraints capture the topological layout of an airport, the required takeoff times of the flights, the characteristics of each flight (depending on the weight of the aircraft, only certain runways can be used), adequate separation between takeoffs on the same runway, and the eventual required exit point from the airspace of the airport.

The CP model is able to schedule medium-size airports, such as Prague (Czech Republic), but for larger airports either no solution is found quickly enough (the tool is intended to be used in real time) or no solution is found. This is because for larger airports, the given constraint problem is often over-constrained. That is, there is no solution that satisfies all the constraints simultaneously. An extension is proposed that uses constraint relaxations. When the CP model finds no solution in time, the controller is given the option to relax some of the constraints in order to find a solution. The system provides, when possible, reasons why no solution can be found, and gives the controller the option to reschedule individual flights. Priority is given not to overload the controllers with too much information, but to offer them enough information to provide a simple resolution of the scheduling conflict.

Perspectives. With the current trend of extending saturated airports with new runways and taxiways to accommodate the growing demand, airport traffic becomes more complex to manage, leaving room for optimization technologies (such as CP) capable of taking into account the diverse operational constraints that taint the combined allocation and shortest path problems inherent to airport management. Furthermore, depending on the airport configuration, departure management generally is closely intertwined with arrival management, such that airport management tools should simultaneously optimize both the takeoff rates and the landing rates, like the airport simulator and optimizer based on branch-and-bound and genetic algorithms proposed by Deau et al. (Reference Deau, Gotteland and Durand2009).

3.8 Arrival management

As airport capacity is becoming a scarce resource in the ATM system, it is essential to plan the traffic carefully in approach areas in order to avoid traffic peaks. These approach areas have a particularly high traffic density, as many aircraft converge to a single point before the runway. Furthermore, successive landings must be sequenced, taking into account a minimal time interval corresponding to a safety spacing so as to avoid wake vortex.

Artiouchine et al. (Reference Artiouchine, Baptiste and Dürr2008a) present a scheduling approach to this problem. All possible trajectories are pre-computed, taking into account allowed manoeuvres: speed changes that slightly modify the landing time, and the use of holding patterns that generate a constant delay (usually 4 minutes). This pre-processing provides a set of possible landing times for each aircraft. A branch-and-cut method is proposed to solve the resulting scheduling problem, using constraint propagation to filter the search space. This approach outperforms the standard mixed integer programming approach by Bayen et al. (Reference Bayen, Tomlin, Ye and Zhang2004), solving instances with up to 90 jobs (i.e., aircraft) within a few seconds.

Artiouchine et al. (Reference Artiouchine, Baptiste and Mattioli2008b) propose an analogy between the arrival sequencing problem and the k-king problem. In this simplified model, time is discretized and airspace is represented as a two-dimensional chessboard, where the runway is a special square. Aircraft move as a king does on a chessboard. The objective is to get all aircraft to land (i.e., to empty the chessboard) as soon as possible. The k-king problem is modelled as a constraint satisfaction problem and several constraint propagation algorithms are tested. Solutions are obtained for small instances, ranging from 6 aircraft on a 5 × 5 chessboard to 14 aircraft on a 7 × 7 chessboard. Future work is to use techniques such as no-good recording (Schiex & Verfaillie, Reference Schiex and Verfaillie1993) in order to speed up the search and thus be able to handle larger instances.

Perspectives. Both methods are limited to single-runway configurations. Taking multiple runways into accountFootnote ⁹, as proposed by Berge et al. (Reference Berge, Haraldsdottir and Scharl2006) with a branch-and-bound approach, might lead to better results, but at the cost of larger problem instances.

3.9 Verification

For a few years now, CP has also been used for software verification. The aim is to produce test data for a given piece of code or to perform verification tasks on programs, such as finding non-executable parts. Gotlieb (Reference Gotlieb2012) proposes a combination of bound-consistency filtering and linear programming for this task, with an application on a critical part of the Traffic Alert and Collision Avoidance System (TCAS). TCAS is an on-board conflict detection and resolution system that outputs warnings about possible short-term collisions and manoeuvres in order to avoid them. TCAS is part of the emergency filter (see Section 1). In this approach, the input source code is transformed into a constraint system P using predefined rules for each construct (function calls, conditionals, etc.). If one wants to check an assertion A, then a solution search is performed on , which either validates A (if no solution is found) or exhibits test input that violates it. The tested source code contained 173 lines of C code, with 10 properties to prove. The task was performed within 20 seconds, with six properties proved and counter-examples found for each of the four remaining properties.

Perspectives. Further work is planned to address larger programs with thousands of lines of code. A dedicated finite-domain solver could be developed towards this.