Slot allocation with constraint programming : models and results
Barnier, Nicolas ; Brisset, Pascal ; Rivière, Thomas
HAL, hal-00938015 / Harvested from HAL
Current European Air Traffic Control system is far exceeded by the demand and the resulting delays are a financial and psychological burden for airlines and passengers. The Central Flow Management Unit, in charge of regulating the flights to respect en-route capacity constraints of Air Traffic Control Centres, uses a greedy algorithm to allocate departure slots which features several drawbacks concerning soundness, interpretation of the constraints and optimization. A new model taking advantage of Constraint Programming (CP) has been proposed within the SHAMAN system (from CENA) but still suffers from unevenly distributed workload and capacity violation. This paper presents two alternative models, also implemented using CP technology, of the slot allocation problem focused on the controllers workload: an extension of the SHAMAN model with a standard formulation, and a novel approach involving the sort constraint. Both of them can maintain workload constantly below a given capacity and the latter also provides efficient failure proof on over-constrained instances. The behaviours of the different models are discussed and results are presented with partial and full instances from real French air traffic data set. We eventually describe the potential operational improvement supplied by these continuous models.
Publié le : 2001-12-04
Classification:  slot allocation,  constraint programming,  combinatorial optimization,  modelling,  [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC]
@article{hal-00938015,
     author = {Barnier, Nicolas and Brisset, Pascal and Rivi\`ere, Thomas},
     title = {Slot allocation with constraint programming : models and results},
     journal = {HAL},
     volume = {2001},
     number = {0},
     year = {2001},
     language = {en},
     url = {http://dml.mathdoc.fr/item/hal-00938015}
}
Barnier, Nicolas; Brisset, Pascal; Rivière, Thomas. Slot allocation with constraint programming : models and results. HAL, Tome 2001 (2001) no. 0, . http://gdmltest.u-ga.fr/item/hal-00938015/