Real-time decision support for integration of airline flight cancellations and delays .1. Mathematical formulation

An important decision faced by airline schedulers is how to adapt the flight schedule and aircraft assignment to unforeseen perturbations in an established schedule. In the face of unforeseen aircraft delays, schedulers have to decide which flights to delay, and when delays become excessive, which to cancel. Current scheduling models deal with simple decision problems of delay or cancellation, but not with both simultaneously. But in practice the optimal decision may involve results from the integration of both flight cancellations and delays. In this paper, a quadratic 0-1 programming model is presented for the integrated decision problem. The model is a profit maximization program that takes into account the different cost penalties of delay and of flight cancellation. Also, the model is extended to formulate some special cases such as the ferrying of surplus aircraft and the replacement of different type of aircraft. Finally, some special properties of the model are given, resulting in a conversion of the discrete mathematical program into a continuous one that is easier to solve. An algorithm and computational experiments are presented in a subsequent Part II of this paper.