A Recovery Algorithm for a Disrupted Airline Schedule

The airline scheduling is a very large and complex problem. Moreover, it is common that only a minority of the initial schedules are carried out as planned because of delays, airport closures or other unforeseen events. Thus, given an actual state of the resources, a so called "disruption" arises when a schedule becomes unrealizable. The problem the scheduler is then faced with is to re-allocate the resources in order to get back to the initial schedule and to define what the priorities are: minimize the recovery time or minimize a given cost function. In this presentation, we will describe briefly a network model and a recovery algorithm based on column generation that solves the minimal cost recovery problem for a given maximal recovery time. We will focus the attention on the recovery network used at the pricing problem level. In particular we will describe some ideas that are useful to speed up the whole algorithm.