A column generation algorithm for disrupted airline schedules

We consider the recovery of an airline schedule after an unforeseen event, called {\em 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 aircrafts' maintenances are planned in an optimal way in order to satisfy the operational regulations. We propose a column generation scheme, where the pricing problem is modeled as a commodity flow problem on a dedicated network, one for each plane of the fleet. We present a dynamic programming algorithm to build the underlying networks and a dynamic programming algorithm for resource constrained elementary shortest paths to solve the pricing problem. We provide some computational results on real world instances.