Column Generation Methods for Disrupted Airline Schedules

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 heterogeneous 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. The aim is to find the optimal combination of routes within a given makespan for each plane in order to recover to the initial schedule, given the initial schedule and the disrupted state of the planes. We propose a column generation scheme based on a multicommodity network flow model, where each commodity represents a plane, a dynamic programming algorithm to build the underlying networks and a dynamic programming algorithm to solve the pricing problem. This project arises from a collaboration between EPFL and APM Technologies, which is a small company selling IT solutions to airlines. We provide some computational results on real world instances obtained from a medium size airline, Thomas Cook Airlines, one of APM main customers.