Optimizing Aircraft Routings in response to Groundings and Delays

This paper presents the time-band optimization model for reconstructing aircraft routings in response to groundings and delays experienced over the course of the day. Whenever the schedule is disrupted, the immediate objective of the airlines is to minimize the cost of reassigning aircraft to flights taking into account available resources and other system constraints. Associated costs are measured by flight delays and cancellations. The time-band model is constructed by transforming the routing problem into a time-based network in which the time horizon is discretized. The resulting formulation is an integral minimum cost network flow problem with side constraints. Conditions for which an exact solution to the model represents an optimal solution for the original problem are stated. The transformation procedure is polynomial with respect to the number of airports and flights in the schedule. Computational experience shows that the underlying network structure of the transformed problem often leads to integral solutions when solved with a standard linear programming code. Empirical results using Continental Airline data demonstrate that the solutions obtained are either provably optimal or no more than a few percentage points from the lower bound.