Robust airline scheduling under block-time uncertainty

Airline schedule development continues to remain one of the most challenging planning activities for any airline. An airline schedule comprises a list of flights and specifies the origin, destination, scheduled departure, and arrival time of each flight in the airline's network. A critical component of the schedule development activity is the choice of flight block-times, which depend on several factors. Many airlines decide schedule blocktimes based on fixed percentiles of block-time distributions built from historical data, however, such techniques have not resulted in significantly improved on-time performance (OTP) of the schedule during operations. Thus, from a passenger's perspective, the service-level guarantee of an airline's network continues to be low. We first define two service-level metrics for an airline schedule. The first one is similar to the OTP measure of the U.S. Department of Transportation and we define it as the flight service level. The second metric, called the network service level, is geared toward completion of passenger itineraries. We then develop a stochastic integer programming formulation that optimally perturbs a given schedule to maximize expected profit, while ensuring the two service levels. We also develop a variant of this model that maximizes service levels, while achieving desired network profitability. To solve these models, we develop an efficient algorithm that guarantees optimality. Through extensive computational experiments, using real-world data, we demonstrate that our models and algorithms are efficient and achieve the desired trade-off between service level and profitability.