Optimal Solutions to a Real-World Integrated Airline Scheduling Problem

We study an integrated airline scheduling problem for a regional carrier. It integrates three stages of the planning process (i.e., fleet assignment, aircraft routing, and crew pairing) that are typically solved in sequence. Aircraft maintenance is also taken into account. The objective function aims at minimizing a weighted sum of the number of aircraft routes, the number of crew pairings, and the waiting times of crews between consecutive flights. In addition, it aims at maximizing the robustness of the solution by also minimizing the number of times that crews need to change aircraft. We present two mixed integer linear programming models for the integrated problem. The first formulation, called the path-path model , can be considered as the “natural model” in which both the crew pairings and the aircraft routes are represented by path-based variables. The other formulation, called the arc-path model , is a novel model in which the aircraft routes are represented by arc-based variables and the crew pairings by path-based variables. We propose two exact methods (called path-path method and arc-path method) for solving the integrated problem, each one based on one of the proposed models. Both methods consist of three phases. In the first phase, the linear programming relaxation of the corresponding model is solved to optimality by column generation on the path-based variables, thus providing a lower bound. The second phase computes a heuristic solution (upper bound) by using only the variables generated in the first phase. The third phase makes use of the lower and upper bounds (obtained in the previous phases) to compute an optimal solution. We propose a bounding cut based on computing a lower bound on the number of aircraft changes that are needed in a feasible solution, and empirically show that this cut significantly speeds up the exact methods. The proposed methods are tested on real-world instances of a regional carrier with up to 172 flights and three fleet operators. The results show that the arc-path method outperforms the path-path method as well as a heuristic approach from the literature, and derives the optimal solutions for all of the considered instances in at most two hours of computing time.