The French National Research Agency Projects for science

Voir cette page en français

ANR funded project

JCJC - SIMI 2 - Science informatique et applications (JCJC SIMI 2)
Edition 2012


ATOMIC


Air Traffic Optimization via Mixed Integer Computation

Towards solving air traffic management problems through Mathematics
Air traffic is at the core of the social and economic dynamism of our society, and an efficient Air Traffic Management has evidently a deep impact on the social, economic, environmental and industrial context. This project focuses on the development of mathematical optimization to solve problems arising in air traffic management. An example is the aircraft conflict avoidance problem, which occurs when aircraft are too close to each other according to their predicted trajectories.

A smarter and more efficient air traffic
The main aim is contributing to the advancement in both modeling stimulating real-life problems arising in air traffic management and developing efficient methods for their solution, using mixed-integer nonlinear optimization.
The project fits perfectly within the framework of the research carried out in France, particularly in Toulouse, around aeronautics.

Optimization
Mathematical approaches from mixed-integer nonlinear optimization will be developed. The optimization will be performed developing specific strategies to deal with the computational difficulty of the target large-scale problems. Deterministic Branch-and-Bound (BB)-type methods (spatial-Branch-and-Bound and interval-Branch-and-Bound variants) will be primarily considered. To deal with the difficulty of the problem, other strategies will be also explored, where the optimality guarantee is forsaken in exchange for the computational efficiency. Specifically, we will investigate hybridization of mathematical programming techniques and (meta)-heuristics.

Results

The expected outcome of the project is the availability of automatic tools able to integrate the work of air traffic controllers. These tools will be based on mathematical models from mixed integer optimization and on new effective optimization methods and algorithms.

Outlook

Starting from the results obtained for the considered specific application, we will seek to identify more general classes of problems to which the developed techniques can be applied.

Scientific outputs and patents

Common or individual scientific publications will be realized.
The expected progresses will be published in international journals of the field and will be presented in international conferences.

Partners

ENAC Ecole Nationale de l'Aviation Civile

ANR grant: 189 613 euros
Beginning and duration: janvier 2013 - 36 mois

Submission abstract

Mixed-Integer Nonlinear Programming (MINLP) deals with the most general optimization problems, involving both continuous and discrete variables and nonlinear constraint functions. These are among the most challenging computational optimization problems, arising in countless applications from various areas. While research on mixed-integer linear optimization is quite advanced, MINLP is considered an emerging area that is likely to grow in the coming years. MINLP models being in general very difficult to solve, they require exploiting their properties and developing special solution techniques to reduce the computational effort. The ATOMIC project is in the framework of this hot research topic, with the aim of contributing to the advancement in both modeling stimulating real-life problems and developing efficient methods for their solution.
A number of challenging problems arising in Air Traffic Management (ATM) constitute interesting research topics particularly in Operations Research and Optimization and naturally lead to MINLP models. Air traffic is at the core of the social and economic dynamism of our society, and an efficient Air Traffic Management has evidently a deep impact on the social, economic, environmental and industrial context. In this framework, a few problems urgently need addressing to ensure a higher level of automation in ATM and consequently more efficiency and safety. The present project focuses on air traffic conflicts, which occur when aircraft are too close to each other according to their predicted trajectories. Mixed-Integer Nonlinear Programming formulations appear to be the natural candidates for these addressed ATM problems, where the need for modeling logical choices suggests the simultaneous presence of mixed (continuous-integer) variables and nonlinear constraints arise from separation condition modeling.
Solution algorithms for these ATM problems are mainly based on evolutionary computation. While these methods are computationally efficient, the global optimal solution and even a feasible solution (with no conflict) is not guaranteed to be achieved in a given time. Recent advances in mixed-integer linear and nonlinear programming open new perspectives that have been lacking in earlier researches on conflict avoidance and can have an impact on its effective solution. The present project is therefore aimed to fully exploiting and developing mixed-integer optimization techniques to propose efficient solutions. The optimization will be performed developing specific strategies to deal with the computational difficulty of the target large-scale problems. Deterministic Branch-and-Bound (BB)-type methods (spatial-Branch-and-Bound and interval-Branch-and-Bound variants) will be primarily considered, exploring strategies that can have an impact on the algorithm's ability to provide an optimal solution, including for example strong reformulations and branching strategies. To deal with the difficulty of the problem, other strategies will be also explored, where the optimality guarantee is forsaken in exchange for the computational efficiency. Specifically, we will investigate hybridization of mathematical programming techniques and (meta)-heuristics, in a “matheuristic” framework, where an essential feature is the exploitation of the features of the conceived mathematical programming models of the addressed problem. Starting from the results obtained for the considered specific application, we will seek to identify more general classes of MINLP problems to which the developed techniques can be applied.
Expected results of the project include new mathematical models from mixed-integer programming and effective optimization methods, as well as a software library implementing the proposed algorithms.

 

ANR Programme: JCJC - SIMI 2 - Science informatique et applications (JCJC SIMI 2) 2012

Project ID: ANR-12-JS02-0009

Project coordinator:
Madame Sonia CAFIERI (Ecole Nationale de l'Aviation Civile)
sonia.cafieri@nullenac.fr

Project web site: http://atomic.recherche.enac.fr/

 

Back to the previous page

 

The project coordinator is the author of this abstract and is therefore responsible for the content of the summary. The ANR disclaims all responsibility in connection with its content.