M Sbihi

O Rodionova

D Delahaye

M Mongeau

OPERATIONAL RESEARCH PRACTICE IN AFRICA (ORPA) 2015

This paper discusses the trajectory planning problem for flights in the North Atlantic oceanic airspace (NAT). We develop a mathematical optimization framework in view of better utilizing available capacity by re-routing aircraft. The model is constructed by discretizing the problem parameters. A Mixed integer linear program (MILP) is proposed. Based on the MILP a heuristic to solve real-size instances is also introduced.

Context and problem description

The North Atlantic oceanic airspace accommodates air traffic between North America and Europe. The major traffic flow takes place in two distinct traffic flows during each 24-hour period due to passenger preference, time zone differences and the imposition of night-time noise curfews at the major airports. The westbound flow departing from Europe in the morning, and the eastbound flow departing from North America in the evening. Radar coverage is not, for most parts, available in the NAT Region. Air Traffic Control (ATC) units monitor the progress of flights on the basis of pilot position reports and uses procedural methods. Such procedures are based on an Organized Track System (OTS) (see [START_REF]Guidance concerning air navigation in and above the North Atlantic MNPS airspace[END_REF]). The OTS consists of several, typically 4 to 7, quasi-parallel tracks each of which represents a sequence of great circles joining successive significant waypoints (WPs). The variability of the wind patterns would make a fixed track system unnecessarily penalizing in terms of flight time and consequent fuel usage. As a result, an OTS is set up on a diurnal basis for each of the Westbound and Eastbound flows according to the prevailing winds. Adjacent tracks are separated by 60 Nautical Miles. In vertical direction each track consists of several flight levels spaced by 1000 feet. The construction of OTS ensures vertical and lateral separation between aircraft. The longitudinal (in-track) separation in NAT is assessed in terms of differences in actual and estimated times of arrival at common WPs; and expressed in clock minutes. Current regulations impose large separation minima for aircraft on OTS. The time separation between subsequent aircraft following the same track is 10 minutes. When an aircraft wants to shift from one track to an adjacent track, the separation must be at least 15 minutes with aircraft located on such adjacent track.

Due to the high density of traffic on tracks and these large separation standards, the re-routing maneuver inside OTS can rarely be applied. This leads to increasing the length and the duration of the flights, as well as to increasing the congestion in the continental airspace near the exit of the OTS.

The transition from present ATC tools to airborne-based systems will allow to reduce significantly the present aircraft separation standards: consecutive aircraft following the same track would be separated by only around 2 minutes, and an aircraft performing a re-routing to the adjacent track would be separated by around 3 minutes from aircraft on this track. Obviously, with such reduced separation standards aircraft will be able to change their tracks more frequently [START_REF] Williams | Benefits assessment of reduced separations in North Atlantic Organized Track System[END_REF]. To show the benefits that can be expected from such a reduction of separation standards, the problem was investigated in [START_REF] Rodionova | North Atlantic Aircraft Trajectory Optimization[END_REF] using genetic algorithms. The aim of this study is to give an approach based on mixed integer linear programming.

Contributions

We developed a mathematical optimization framework to better utilize available capacity by re-routing aircraft based on wind conditions and origin/destination of flights. The model is constructed by discretizing the problem parameters. The OTS is represented by a 3D-grid and an MILP path-based formulation is proposed. The program takes (among others things) as input entry and exit tracks and track-entry times of flights. The program then assigns a route to each of these flights explicitly considering separation constraints to minimize the total cruising time within the OTS. The approach can be used with a variety of other aviation-focused metrics. When the number of aircraft increases, a scalability problem rises. The proposed second methodology addresses the scalability problem issue through utilizing a heuristic method. The heuristic recursively defines, and then solves short-term (small-size) subproblems, and partially fixes routes. The heuristic was tested on two test problems based on real air-traffic data and produces near-optimal solutions (typically within 2% of optimality) while standard optimization software fails to solve such instances.

Acknowledgements

This work has been supported by French National Research Agency (ANR) through JCJC program (project ATOMIC nANR 12-JS02-009-01).


J Omer

A Gondran

A Two-Step Hybrid Metaheuristic for Flight Level Allocation in 4D Trajectory Generation

Context

With an already congested European airspace, the predicted increase of air traffic is an important challenge for the decades to come. The current air traffic management (ATM) is based on a geographic structure of the airspace, but an alternative trajectory-based management is considered for more efficiency [START_REF] Gondran | European ATM master plan[END_REF]. In this context, a 4D business trajectory (BT) is negotiated between airlines and ATM authorities. A large part of air traffic control is then delegated to the pilots who are responsible to follow their BTs. The role of the controllers is to monitor the traffic, assist the pilots, and propose new BTs in case of unpredicted events.

During the negotiation procedure, airlines send their demands regarding their preferred takeoff time and cruising altitude. ATM then computes BTs accommodating these demands while meeting safety requirements, and other structural constraints. The main safety constraint is that no conflict occurs, i.e. every pair of aircraft remains separated with either one of two reference horizontal and vertical separation distances. One key issue is thus to compute a set of trajectories without conflict. Omer and Chaboud [START_REF] Omer | Automated conflict free planning. experiments on real air traffic data[END_REF] suggest a simulation-based approach to modify conflicting forecast trajectories using an automated conflict resolution. The conflict resolution can be handled with mathematical programming [START_REF] Omer | Hybridization of nonlinear and mixed-integer linear programming for aircraft separation with trajectory recovery[END_REF], but it might result in irregular and complex trajectories if a lot of conflicts have to be dealt with. The purpose of this work is to develop a flight level (FL) allocation algorithm to avoid most losses of separation occurring between cruising flights before running the automated conflict resolution.

Model: target graph vertex coloring

Our model is a modified version of the list coloring problem of Allignol et al. [START_REF] Allignol | Optimized flight level allocation at the continental scale[END_REF]. Assuming that the airspace is layered into FLs separated with the vertical reference separation distance, the separation can be guaranteed by allocating different FLs to each pair of aircraft that doesn't meet the horizontal separation. Given a set of aircraft V , a graph of conflict G(V, E) is built by connecting a pair of aircraft with an edge when a loss of horizontal separation is detected between their trajectories. If each FL is matched to one color, the FL allocation problem is equivalent to searching for a coloring of G(V, E) that minimizes the gap with the preferred flight levels (PFLs). This problem is called target coloring: each vertex (each flight) has one target color (PFL). The particularity of the context is that we do not intend to compute separated trajectories with the FL allocation alone. Remaining conflicts are allowed as long as their numbers does not overcome a given threshold C. It means that colorings with less than C conflicting edges are allowed (one edge is in conflict if its vertices have the same color). Denoting δ F Li,F Lj the Kronecker function returning 1 if F L i = F L j and 0 otherwise, the model to solve is:

min    i∈V (F L i -P F L i ) 2 : (i,j)∈E δ F Li,F Lj ≤ C    (1)
where (i,j)∈E δ F Li,F Lj corresponds to the number of conflicting edges and i∈V (F

L i -P F L i ) 2
is a distance between the solution and the target coloring. A drawback of defining a threshold C is that a solution of ( 1) is likely to leave exactly C conflicts. Let Z 1 be the best known value of (1), a second step model is then solved to trade a small extra violation of demands with more conflict resolutions:

min    (i,j)∈E δ F Li,F Lj : i∈V (F L i -P F L i ) 2 ≤ (1 + ρ)Z 1    (2)
3 Algorithm: H 2 col-t, variant of H 2 col for target coloring [START_REF] Moalic | Variations on Memetic Algorithms for Graph Coloring Problems[END_REF] is a hybrid evolutionary algorithm based on the HEA memetic algorithm [START_REF] Galinier | Hybrid evolutionary algorithms for graph coloring[END_REF]. Like HEA, H 2 col blends a greedy partition crossover and the Tabucol [START_REF] Hertz | Using Tabu Search Techniques for Graph Coloring[END_REF] tabu search procedure, but its main originality is that the population of solutions is reduced to only two individuals. With this modification, H 2 col obtains very good results on the DIMACS benchmark for standard vertex coloring. For this reason we base the solution of the FL allocation problem on H 2 col. In order to tackle the target coloring problem, some modifications are made on the crossover operator and on the Tabucol algorithm, and ( 1) and ( 2) are solved sequentially with the same method. First, the threshold constraint is treated as a second objective. Tabucol then considers the two objectives in a lexicographic order giving priority to the constraint satisfaction. For instance, while solving (1), Tabucol first focuses on getting less than C conflicts before lowering the violation of demands. As regards the crossover, the operator of HEA is designed to deal with the symmetry that exists between the colors in standard vertex coloring. In contrast, the targets partially break this symmetry, so classical crossover operators are combined with the greedy partition crossover of HEA. This new algorithm is denoted H 2 col-t.

H 2 col

Experimental tests and perspectives

The algorithm is tested on European air traffic data. The historical flight plans of several days of traffic are used to get the demands. Two sets of initial trajectories are then computed by respecting the current network of routes or joining the arrival and destination airports with direct routes. To evaluate the benefit H 2 col-t, a comparison is made with the tabu search algorithm alone and with a version of H 2 col-t using more than two solutions in its population. Preliminary results show the efficiency of H 2 col-t on large instances involving more than 30 000 flights.

In the future, it is necessary to focus on conflicts involving two aircraft in evolution. Modifying their cruise altitude is generally irrelevant, but small delays in the take-off times could succeed in avoiding a large number of losses of separation. Using an appropriate model, H 2 col-t should also be a promising method to solve this problem.

Acknowledgements

The second author gratefully acknowledges financial support under grant ANR 12-JS02-009-01 "ATOMIC".