This talk is on an integrated airline scheduling problem which integrates three stages of the planning process that are typically solved in sequence: fleet assignment, aircraft routing and crew pairing. Aircraft maintenance is also taken into account. The objective function aims at minimizing the numbers of the aircraft routes and crew pairings, and the waiting times of crews between consecutive flights. It also aims at maximizing the "robustness" of the solution, i.e. minimizing the number of times that crews need to change aircrafts ("aircraft changes"). We present two Mixed Integer Linear Programming (MILP) formulations for the integrated problem. One formulation, called "path-path model", could be considered the natural model in which both the crew pairings and the aircraft routes are represented by path-based variables. The other formulation, called "arc-path model", is a novel model in which the aircraft routes are represented by arc-based variables. We propose two exact approaches for solving the integrated problem, each one based on one of the presented models. They consist of three phases. In the first one, the Linear Programming (LP) relaxation of the corresponding model is solved to optimality using a column generation on the path-based variables. The second phase consists of deriving a heuristic solution for the problem restricted to the variables generated in the first phase. The third phase makes use the lower and upper bounds to compute an optimal solution. The path-path method implements a branch-and-price approach to dynamically generate the path-based variables. The arc-path approach consists of solves the reduced MILP model defined by all the variables with reduced cost in the gap between the upper and lower bounds. In addition, we describe a "bounding cut" based on computing a lower bound on the number of aircraft changes that are needed in a feasible solution. We empirically show that this cut speeds up the exact methods. These methods are tested on real-world instances with up to 170 flights and three fleet operators, and compared to a heuristic approach in the literature showing the effectiveness of our proposal.
This talk is based on two papers: one is an article published on Omega 43 (2014) 71-82, and the other is an on-going join work with Valentina Cacchiani (University of Bologna).