Many ATFM problems exhibit combinatorial features and a fairly large size, hence they can only be properly handled by automated solvers. Nowadays, most of them are still solved by hand by experts or greedy algorithms, which lead to sub-optimal or incorrect (w.r.t. constraints) solutions. Among the most successful techniques to address such Combinatorial Optimization Problems (COP) stands Constraint Programming, a two-component paradigm combining:
This architecture eases the design, refinement and maintenance of the model, and separates it cleanly from the search component. Then the strategy of the latter can be tailored with high-level goals specifications. The completeness of the solver can also be relaxed to perform greedier search and address bigger problems. The CAP project aims at using FaCiLe, our Functional Constraint Library, to optimally solve ATFM problems within the current ATC system in the two following fields:
The goal of CAP is then to improve solutions efficiency by:
hopefully to optimality.
Mainly planning and scheduling problems.
Requested departure times of flights cannot always be granted because of the limited capacity of each open control sector. To ensure safety, delays are allocated to flights so that the rate of aircraft entering a given sector will not exceed its specified capacity.
The various models used in previous and current studies do not build appropriate solutions:
Marabout:
Compared to the "Standard" model used by the SHAMAN project, Marabout levels out and smoothes the workload, while respecting the capacity constraints over any time period. The left graphs presents the number of flights that will enter the sector boundaries within the next 60 min, sometimes called "(controller) workload", along with the (horizontal) capacity line. The right ones stand for the instantaneous number of aircraft being in the sector. The first graph (top left) shows the effect of the SHAMAN regulation (called "Standard"), which is to ensure that there is a point below the capacity line every 60 min (red circles on the graph). So this too discrete model obviously fails to regulate anything.
|
|
| Workload in the sector: entries within the next 60 min | Instantaneous load of the sector: number of flights |
Below is shown the effect of the Marabout regulation: the workload constantly remains under the capacity line (except for drawing artefacts due to the - web publishable - graphic format). This behaviour is believed to be much more suitable for the controllers than the previous one.
|
|
| Workload smoothing with Marabout | Instantaneous load smoothing with Marabout |
For an entire ATCC, the results is less spectacular as the graphs are flatten by the scale, but the capacity constraints are nevertheless strictly respected (with even a fancy plateau for sector J around noon).
|
| Capacity constraints are strictly satisfied |
ATCC are made of elementary sectors that can be dynamically combined (or split back) to match traffic load. Opening schedules are hand-made daily by experts according to the requested flight plans to ensure that enough controllers will be available to handle the opened positions.
|
|
|
| Raw ATCC opening schedule | Optimized schedule | Optimized schedule with transition costs |
Objectives:
Simplifications:
|
|
|
Main flows in French airspace Only flows with a minimal size are taken into account |
Crossingless flight level allocation: horizontally number of flows, vertically number of FL Green dots correspond to minimal numbers of flights per flow |
Graph Coloring for Air Traffic Flow Management Nicolas Barnier and Pascal Brisset
Annals of Operation Research, August 2004, vol 130, pp 163-178, Kluwer
(2004/07/02)
Coloriage de graphe en programmation par contraintes Nicolas Barnier and Pascal Brisset
5ème congrès de la Société Française de Recherche
Opérationnelle et d'Aide à la Décision ROADEF'03
(2003/01/21)
Application de la programmation par contraintes à des problèmes de
gestion du trafic aérien Nicolas Barnier
Thèse doctorat informatique de l'INP Toulouse
(2002/12/06)
Graph Coloring for Air Traffic Flow Management Nicolas Barnier and Pascal Brisset
CPAIOR'02
(2002/03/07)
Robustesse des solutions du problème d'allocation de créneaux Thomas Riviere
rapport de DEA IFP
(2001/06/25)
FaCiLe: a Functional Constraint Library Nicolas Barnier and Pascal Brisset
CICLOPS'01
(2001/10/05)
Slot Allocation with Constraint Programming: Models and Results Nicolas Barnier, Pascal Brisset and Thomas Riviere
ATM 2001
(2001/07/01)
Allocation de créneaux pour la régulation du trafic aérien Nicolas Barnier, Pascal Brisset
JFPLC'2000
(2000/06/28)
Slot Allocation in Air Traffic Flow Management Nicolas Barnier, Pascal Brisset
PACLP'2000
Also in HTML format
(2000/04/10)
Optimisation par algorithme génétique sous contraintes Nicolas Barnier, Pascal Brisset
TSI 2/1999
(1999/01/05)
Combine & Conquer: Genetic Algorithm and CP for Optimization Nicolas Barnier, Pascal Brisset
Poster at the Fourth Conference on Principles and Practice of Constraint Programming
(1998/10/28)
Optimization by hybridization of a genetic algorithm with constraint satisfaction techniques Nicolas Barnier, Pascal Brisset
IEEE International Congress on Evolutionary Computation
(1998/05/04)
Optimization by Hybridization of a Genetic Algorithm with CSP Techniques Nicolas Barnier
ESSLLI 97
(1997/08/22)
Optimisation par hybridation d'un CSP avec un algorithme génétique Nicolas Barnier, Pascal Brisset
JFPLC'97
(1997/05/26)
Last Update: Wednesday, 28-Mar-2007 12:40:10 UTC
|
WARNING: This web page is no longer maintained. See POM and LOTA
|
|