Column generation approaches to a robust airline crew pairing model for managing extra flights

Abstract

A typical airline crew pairing problem aims at selecting a set of flight sequences (pairings) for crews such that each flight in the regular schedule is covered by one crew. In this thesis, we consider the management of potential extra flights that can possibly be introduced to the regular flight schedule during operation at a later point in time. Without delaying or canceling any existing flight, we try to handle these extra flights within the regular schedule and refer to the resulting mathematical model as a robust airline crew pairing model. The objective function of the robust model involves not only the regular pairing costs but also the opportunity costs for failing to cover the extra flights. Due to the large number of variables (pairings), a typical crew pairing model is usually solved by column generation methods. Before applying column generation to the proposed robust model, we first discuss several procedures to cover the extra flights by a given set of feasible pairings. However, these procedures introduce extra column-dependent constraints to the model. That is, as new columns are added by column generation to the model, the number of constraints may also increase. Similarly if a column is removed from the model, then some of these extra constraints may be deleted. To handle this dynamic change both in the number of constraints and variables we propose two approaches. The main idea behind these approaches is to generate a set of pairings (column pool) so that the number of constraints can be fixed. To this end, we flag the pairings that can be used for covering the extra flights and keep them in a special pool. We illustrate the proposed column generation approaches on a set of actual data acquired from a local airline.