On air traffic flow management with rerouting. Part I: Deterministic case

In this paper a deterministic mixed 0-1 model for the air traffic flow management problem is presented. The model allows for flight cancelation and rerouting, if necessary. It considers several types of objective functions to minimize, namely, the number of flights exceeding a given time delay (that can be zero), separable and non-separable ground holding and air delay costs, penalization of alternative routes to the scheduled one for each flight, time unit delay cost to arrive to the nodes (i.e., air sectors and airports) and penalization for advancing arrival to the nodes over the schedule. The arrival and departure capacity at the airports is obviously considered, as well as the capacity of the different sectors in the airspace, being allowed to vary along the time horizon. So, the model is aimed to help for better decision-making regarding the ground holding and air delays imposed on flights in an air network, on a short term policy for a given time horizon. It is so strong that there is no additional cut appending, nor does it require the execution of the branch-and-bound phase to obtain the optimal solution for the problem in many cases of the testbeds with which we have experimented. In the other cases, the help of the cut identifying and heuristic schemes of the state-of-the art optimization engine of choice is required in order to obtain the solution of the problem, and the branch-and-bound phase is not required either. An extensive computational experience is reported for large-scale instances, some of which have been taken from the literature and some others were coming from industry.