A Set Packing Model for the Ground-Holding Problem in Congested Networks

Air traffic flow management (ATFM) consists of several activities performed by control authorities in order to reduce delays due to traffic congestion. Ground holding decisions restrict certain flights from tacking off at the scheduled departure time if congestion is expected at the destination airport. They are motivated by the fact that it is safer to hold an aircraft on the ground than in the air. Several integer linear programming models have been proposed to efficiently solve the ground holding problem (GHP). In this paper we investigate a set packing formulation of the GHP and design a branch-and-cut algorithm to solve the problem in high congestion scenarios, i.e., when lack of capacity induces flights cancellation. The constraint generation is carried out by heuristically solving the separation problem associated with a large class of rank inequalities. This procedure exploits the special structure of the GHP's intersection graphs. The computational results indicate that the proposed algorithm outperforms other algorithms in which flight cancellation has been allowed.