A slot allocation policy assigns a time slot for departure to each of a number of flights in order to avoid overload in control sectors and on runways. We present a new solution method for a basic version of the European slot allocation problem. The approach is based on an integer linear programming model, where for each flight there is a set of 0-1 variables each associated with one of its possible departure slots. First, column generation is used to solve the LPrelaxation. This results in the construction of a reasonable set of departure slots for each of the flights. Then, the resulting integer linear program is solved. We also present a rounding heuristic to derive feasible integral solutions from fractional solutions after each iteration of the column generation algorithm. Computational results for real-world problems are encouraging, because they indicate that compared to existing exact optimisation algorithms ourmethod generates solutions of approximately the same quality but requires only a fraction of the computation time. Moreover, they indicate that the rounding heuristic performs well.
Slot Allocation by Column Generation
1997
36 pages
Report
No indication
English
Slot allocation by column generation
TIBKAT | 1997
|British Library Conference Proceedings | 1997
|Wiley | 2015
|Slot allocation - EC slot ruling comes under fire
Online Contents | 2009