variable and tries to minimise the violation by using the minimum value in its domain. This state reduces the violation of the constraints very quickly but disregards the total delay, whereas the first state aims at reducing the total delay. Finally, when the violation of the constraints falls below an experimentally determined threshold of 5, the third state is activated to expand the neighbourhood to all the variables, so that it is guaranteed that the next move is the best one toward the solution, as long as we are not at local minimum. The slow performance of the last state will not affect the heuristic since it only applies to the last few violated variables.

The meta-heuristic employs diversification to escape local minima. The search procedure is depicted in Algorithm 3. The diversification is also moving toward a better objective function by selecting a set of flights and setting their delays to zero. The selection is not totally random as it uses a reverse sequence of probabilities derived from (4) with a ratio of 1.5. Once the constraints are satisfied, the diversification level is set to a higher value in order to ensure more modification to the flights' delays, and the state changes according to the new violations. This process continues to satisfy the constraints again, while the objective function is monitored to store the best solution so far before timing out or maximum number of iteration is reached.

It is worth mentioning that, for a problem on such a large number of variables and constraints, achieving a smaller neighbourhood requires much more time per move, which is not acceptable in realtime conditions. Therefore, a simpler yet faster search procedure can reach better solutions. In our case, the algorithm can produce acceptable results in a very short time but it will not be able to converge to the optimal solution given enough time.

## 3 Experiments

The EEC has provided us with a generated data-set of foreseen traffic of the year 2030, namely approximately 50000 flights per day, including their entry times into the currently considered 4600 cells and 1200 airports of the ECAC airspace.

The experiments were performed with *Comet* (revision 2 beta) under Linux Ubuntu 9.0 (32 bit) on an Intel Core 2 Duo T7300 2.0GHz with 2MB cache and 4GB RAM (of which only 2GB are available to *Comet*). The code is allocating more than 1GB memory to solve the most complex instance.

Our experimental results are based on two time intervals for re-planning. The first chosen interval is from s = 9 pm to e = 10 pm, which is a reasonably busy hour. The second chosen interval generates the most congested cells and corresponds to the flights departing from s = 5 pm to e = 6 pm; there are cells in this interval entered by more than 250 flights per hour. Table 1 shows statistics on the cell demands for these two intervals, taken every t = 12 minutes in a sliding window of w = 60 minutes. These statistics are measured before and after running the minimisation of the total delay, with now preceding s by 3 hours, g = 120 minutes of maximum ground holding, w 0 = 0 (no demand re-balancing in the objective function), and *maxIter* = 40000 iterations allocated; the minimum and median values are the same before and after optimisation. Note that all mean values have shrunk, except for the last sliding window of the first interval, because many flights were delayed to fall into that window. The last two columns confirm that the demands on the cells can indeed hugely exceed their capacity (maximum cap = 40 flight entries per hour), but also show that this capacity can actually be enforced by ground-holding flights for up to g = 120 minutes.

The distribution of the delays among the relevant flights for the first interval is presented in Figure 2 as a histogram. Note the logarithmic scale of the vertical axis: the vast majority of the flights are not ground-held at all and, as wanted, the numbers of flights are more or less decreasing when the delays are