instance, the EEC suggested that our first experiments should allow ground holding by an integer amount of minutes within the range [0*,...,*120]. Hence the total cost of such flight plan modifications could be the total delay incurred by all ground holding, and this cost is to be minimised. Our *assumption* here is that take-off times can be controlled with an accuracy of one minute, which is realistic nowadays.

Under this choice, a *flight plan* for a given flight f is reduced to a time-ordered sequence of pairs (t, c),
indicating that f enters cell c at time t. Also, a modified flight plan is then obtained by adding a delay deltaT[ f ] to all the cell entry times of the original flight plan of f , hence there is a decision variable deltaT[ f ] ∈ [0*,...,*120] for every flight f of the original set of flight plans. Other flight plan modifications are discussed in the discussion of future work in Section 4.

In reality, there is another objective function, as the traffic demands on the cells should also be balanced over time and space. At the time of writing, it is not known yet how to combine any balancing cost with the ground holding cost into a single objective function, so we will just experiment with them separately. Quantifying the balancing cost may be done in many different ways, and we have decided to start with the standard deviation of the demands on the 4600 cells.

In short, the *optimisation problem* of the present work can now be stated as follows: Given a set F of flight plans, a set C of airspace cells, and three moments now < s < e in time, return a modification (only by ground holding) of F of minimal cost, such that the traffic demands on the cells of C never exceed their capacities within the time interval [s*,...,* e]. In practice, an allocated amount *maxIter* of iterations is also given, and we want the best such flight plan modifications that can be computed within *maxIter* iterations.

## 1.3 Contributions And Organisation Of This Paper

This paper makes the following main *contributions*. To our knowledge, this is the first time that multisector planning is attempted on the entire European airspace (and with even many more than the present 20000 flights per day) and the first time that CBLS is applied to an ATM problem. We plan to make our constraints and objective functions progressively more realistic: see the discussion of related and future work in Section 4.

The rest of this paper is organised as follows. In Section 2, we summarise a constraint program modelling the dynamic demand-capacity balancing problem in a multi-sector-planning framework. In Section 3, we report on the experiments we made with that program. Finally, in Section 4, we conclude, discuss related work, and outline future work.

## 2 Model

Our constraint model is written in *Comet* [9], an object-oriented constraint programming language with a back-end for constraint-based local search (available at www.dynadec.com). Some pre-processing
(described below) via *MySQL* is made on the raw instance data, which consists of a possibly very large set of flight plans.