Metaheuristics are methods designed to address difficult optimization problems¹. The term “metaheuristic”, coined by Glover when introducing his tabu search method, refers to high-level strategies guiding lower-level heuristics in the search of optimal or near-optimal solutions. Today, metaheuristics cover a wide range of methods that can be categorized in many different ways: population-based or single-solution, mono-objective or multi-objective, nature- or physics-inspired algorithms, hybrid metaheuristics, etc. These categories may overlap. Population-based metaheuristics, for example, include some nature-inspired methods, such as genetic algorithms or particle swarm optimization algorithms. The simulated annealing algorithm, inspired by the annealing process in metallurgy, is an example of metaheuristic iterating on a single individual. Other examples of single-individual metaheuristics include the tabu search, iterated local search and variable neighborhood search.

Many metaheuristics are iterative stochastic methods, in the sense that they rely on some kind of random walk to explore the search space. They also implement a form of “intelligent bias” toward good solutions, based on the evaluation of the objective function at the points sampled during the search. A typical example is the selection of the best-fit individuals in evolutionary algorithms. Another example is the deterministic selection in the differential evolution algorithm: a candidate individual (trial vector) replaces the current individual only if this improves the evaluation of the objective function. Such a mechanism can be viewed as a “greedy” strategy whose aim is to find a better solution as quickly as possible. In addition to randomness and greediness, a third component that may appear in metaheuristics is memory. The promising zones encountered during the search can be memorized so as to intensify the search in these areas. Conversely, non-promising zones can be forbidden, as in the tabu search, so as to force the algorithm to explore other areas (diversification).

Beyond the mind-catching analogies with real-world phenomena such as the natural evolution, annealing process, bee swarms, ant colonies or bacterial foraging, it is the right mix of these three components – randomness, greediness and memory – that allows metaheuristics to find a good balance between intensification and diversification of the search. As opposed to exact optimization methods, metaheuristics do not guarantee the optimality of the solutions found. They are, however, powerful tools to tackle difficult problems where other methods fail.

Air traffic management (ATM) is an endless source of challenging optimization problems. Between the moment passengers board the aircraft and the moment they arrive at their destination, a flight goes through several phases: pushback at the gate, taxiing between the gate and the runway threshold, takeoff and initial climb following standard instrument departure procedure, cruise, final descent following standard terminal arrival route, landing on the runway and taxiing to the gate. During each phase, the flight is handled by air traffic control organizations: airport ground control, approach and terminal control and en route control. These control organizations provide services ensuring a safe and efficient conduct of flights, from departure to arrival.

The core of the air traffic controllers’ activity is to facilitate the traffic flow through the airspace sectors and on the airport ground surfaces under their responsibility, while avoiding collisions between aircraft. To satisfy this essential safety constraint, they must detect and solve conflicts between trajectories. Such conflicts may occur at any time of the flight, during taxi, takeoff, climb, cruise, descent or landing. The underlying constrained optimization problem is to minimize the deviations from the nominal trajectories while maintaining horizontal or vertical separations between conflicting aircraft. For an airborne aircraft, the air traffic controller can order different types of maneuvers to pilots: horizontal deviations, vertical maneuvers, modified rate of climb or descent or speed adjustments. Conflicts related to runway occupancy can be solved only by optimizing the landing and takeoff sequences. When aircraft are taxiing on the ground, conflict resolution can be achieved by choosing different paths or by making aircraft wait on some taxiways. An additional constraint may then occur: flights must respect their takeoff slots. These slots are traffic regulations enforced by ATM so as to avoid congestion in en route sectors or terminal areas, or at the destination airport. Congestion is actually related to excessive controller workload in some parts of the ATM system. This workload can be alleviated or balanced by several means. One of them is to delay departing flights by allocating takeoff slots. Another is to reroute some flights so as to avoid the congested areas. In addition, the airspace sectors and airways can be designed and managed so as to facilitate traffic flows and alleviate controller workload as much as possible. Strategic activities such as airspace and air route network design are conducted months before the day of operation. The assignment of airspace sectors to controller working positions and the traffic regulation measures – slot allocations and traffic rerouting – can be prepared hours in advance, but they must be adapted in real time considering the effective workload undergone by the controllers.

Several optimization problems have been evoked in this short introduction to ATM: optimal sector design and airways positioning, optimal allocation of airspace sectors to controller working positions, takeoff slot allocation, runway sequencing, conflict resolution for taxiing or airborne aircraft. They are often difficult to model and hard to solve. When building models, one must consider the complexity of the system and the multiple sources of uncertainties (e.g. weather, unknown aircraft parameters and unexpected delays). The problems to solve are not always easy to formulate because they are often complex combinations of interdependent subproblems. In many cases, the size and complexity of the problems being addressed make them hard or even impossible to solve with exact methods.

In this book, we present several applications of metaheuristics to difficult ATM problems. Although metaheuristics applied to ATM is the main focus of this book, we have also tried to present a few cases where specific ATM problems can actually be addressed using other methods, such as computational geometry, clustering techniques, exact tree-search methods and machine learning approaches. We hope this will highlight the advantages and limitations of the different approaches proposed in the literature and by the authors of this book. This should also bring the reader a broader view of what kind of methods can be applied to what problem, sometimes with different problem formulations. In several cases, researchers have proposed hybrid methods combining metaheuristics with exact or heuristic methods to tackle specific problems. Although metaheuristics are not supposed to be problem-specific in general, we will see that real-world problems do sometimes require to replace standard operators – such as mutation or crossover for example, in the case of a genetic algorithm – by problem-specific and possibly hybrid operators.

The book is organized as follows. Chapter 1 describes the ATM context in more detail. The other chapters deal with the different categories of ATM problems being addressed: optimization of air routes (Chapter 2), airspace management (Chapter 3), departure slot allocation (Chapter 4), airport traffic management (Chapter 5) and conflict detection and resolution for airborne aircraft (Chapter 6).