Robust Airline Scheduling with Controllable Cruise Times and Chance Constraints

Abstract

Robust airline schedules can be considered as flight schedules that are likely to minimize passenger delay. Airlines usually add an additional time—e.g., schedule padding—to scheduled gate-to-gate flight times to make their schedules less susceptible to variability and disruptions. There is a critical trade-off between any kind of buffer time and daily aircraft productivity. Aircraft speed control is a practical alternative to inserting idle times into schedules. In this study, block times are considered in two parts: Cruise times that are controllable and non-cruise times that are subject to uncertainty. Cruise time controllability is used together with idle time insertion to satisfy passenger connection service levels while ensuring minimum costs. To handle the nonlinearity of the cost functions, they are represented via second-order conic inequalities. The uncertainty in non-cruise times is modeled through chance constraints on passenger connection service levels, which are then expressed using second-order conic inequalities. Overall, it is shown, that a 2% increase in fuel costs cuts down 60% of idle time costs. A computational study shows that exact solutions can be obtained by commercial solvers in seconds for a single-hub schedule and in minutes for a four-hub daily schedule of a major U.S. carrier.

Keywords::

• Robust airline scheduling
• second-order cone programming

Appendix A: Formulation allowing low service levels

When β ≥ 1, the expected value of a log Laplace is infinity. In this case, one can formulate the problem by using the geometric mean of log Laplace random variable in constraint (7(7). ). We will show that when β ≥ 1 the problem can still be reformulated using second-order conic inequalities. We will have no restriction on γ_ij, so the results are valid for all possible values of γ; i.e., 0 ≤ γ_ij ≤ 1.

We first explore the properties of the quantile function given in Equation (1(1). ). In Proposition A1, we show that the second piece of quantile function F^{− 1}_X(γ) is always greater than or equal to the first piece.

Proposition A1.

Denote the first and the second pieces of F^{− 1}_X(γ) by f₁(γ) and f₂(γ), respectively, so, Then, the inequality f₂(γ) ≥ f₁(γ) always holds for 0 ≤ γ ≤ 1. Furthermore, f₂(γ) = f₁(γ) only holds when γ = 1/2.

Proof. Consider Notice that, e^α > 0, . Moreover, always holds since is always true. Next, observe that f₂(γ) − f₁(γ) = 0 when γ = 1/2.

Proposition A2 states that F^{− 1}_X(γ) is a convex function.

Proposition A2.

F⁻¹(γ) is a convex function when β_i ≥ 1.

Proof. Both f₁(γ) and f₂(γ) are convex for 0 ≤ γ ≤ 1. The result follows.

Proposition A3.

The chance constraint (4(4). ); that is, in the problem formulation can be replaced with the following constraints: (A1). (A2). where z_ij is a 0-1 decision variable defined as

Proof. Proposition A1 shows that f₂(γ) ≥ f₁(γ) always holds. Thus, when γ_ij ≥ 1/2, z_ij = 1, f₂(γ_ij) bounds the right-hand side x_j − x_i − TP_ij − f_i; i.e., constraint (A2(A2). ) is active, whereas when γ_ij < 1/2 and z_ij = 0, f₁(γ_ij) bounds the right-hand side x_j − x_i − TP_ij − f_i; i.e. constraint (A1(A1). ) is active.

Proposition A4.

When β ≥ 1, constraints (A1(A1). )–(A2(A2). ) are both representable by second-order conic inequalities.

Proof. First, consider Equation (A1) and Since β_i ≥ 1, by making the conversion as before, we obtain which is obviously in the form of Equation (17(17). ) and hence can be represented via conic inequalities.

Next, consider Equation (A2(A2). ), which is obtained by multiplying the left-hand side of constraint (12) by z_ij. Constraint (12) is second-order cone programming representable by Proposition 2.

Add auxiliary variables v_ij and w_ij such that (A3). (A4). and we get Suppose that β_i = a_i/b_i, where a_i, b_i are integers. Since z_ij ∈ {0, 1}, we can equivalently write To put this inequality in the form of Equation (17(17). ), we can increase the exponent of z_ij and still get an equivalent inequality since z_ij ∈ {0, 1}: where The proof follows.

Proposition A5.

The expected value of log Laplace variable X with parameters α and β_i is finite only for β_i < 1 and has value .

Proof. Define δ such that α = ln(δ). Then, we can rewrite f_X(x) as below: Using the distribution function, we can calculate expected value of X by Define Then whereas Consequently, for α and 0 < β_i < 1 we get

Additional information

Notes on contributors

A. Serasu Duran

A. Serasu Duran is currently a Ph.D. student in Operations Management at the Kellogg School of Management. She received her M.S. and B.S. degrees in Industrial Engineering from Bilkent University. Her research interests include transportation, environmental and energy economics, and operations management in general. She uses various methods including stochastic modeling, optimization, empirical studies, and both structural and reduced-form econometrics in her research.

Sinan Gürel

Sinan Gürel is an Associate Professor in the Department of Industrial Engineering, Middle East Technical University, Turkey. He received his Ph.D. degree from the Department of Industrial Engineering at Bilkent University. His research interests include airline disruption management, scheduling, and applications of second-order cone programming.

M. Selim Aktürk

M. Selim Aktürk is a Professor and Chair of the Department of Industrial Engineering at Bilkent University. His recent research interests include production scheduling and airline disruption management.