Bierlaire, M., Eggenberg, N., and Salani, M. (2007)

Column generation methods for disrupted airline schedules

Proceedings of the Sixth Triennial Symposium on Transportation Analysis, Phuket, Thailand

In this paper we consider the recovery of an airline schedule after an unforeseen event, commonly called disruption, that makes the planned schedule unfeasible. In particular we consider the aircraft recovery problem for a quasi-homogeneous fleet of aircrafts, made of regular and reserve planes, where the maintenance constraints are explicitly taken into account and different maintenance constraints can be imposed. We propose a multicommodity network flow model, where each commodity represents a plane, a dynamic programming algorithm to build the underlying network and an heuristic algorithm based on column generation. We provide some computational results on instances obtained from a medium-sized airline.