Robust airline scheduling under block-time uncertainty

Milind Sohoni*, Yu Ching Lee, Diego Klabjan

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

46 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)451-464
Number of pages14
JournalTransportation Science
Issue number4
StatePublished - Nov 2011


  • Airline planning
  • Robust scheduling
  • Stochastic optimization

ASJC Scopus subject areas

  • Civil and Structural Engineering
  • Transportation


Dive into the research topics of 'Robust airline scheduling under block-time uncertainty'. Together they form a unique fingerprint.

Cite this