On the Airline Crew Rostering Problem

The problem of finding a work assignment for crew members of an airline in a given time horizon, is addressed. In the literature such a problem is usually referred to as the Airline Crew Rostering problem and consists of constructing monthly schedules for crew members by assigning them pairings, rest periods, leaves, training periods, union activities, and so forth, so as to satisfy the collective agreements and security rules. We formulate the Airline Crew Rostering problem as a 0-1 Multicommodity Flow problem where each employee corresponds to a commodity; determining a monthly schedule for an employee is the same as computing a path on a suitably defined graph while satisfying the clauses of the union conventions and distributing the workload evenly among the employees. Each path on the graph alternates between activity arcs which represent the activities to be covered in the programming period, and compatibility arcs linking together pairs of activities which can be assigned consecutively to the same employee. A preprocessing phase is performed which reduces the dimension of the graph. In order to tighten the linear programming formulation of our model we propose some families of valid inequalities which have proven to be computationally very effective; some of them have the characteristic that can be treated implicitly in the construction of the graph. Computational results obtained with a commercial integer programming solver (CPLEX) are analyzed. Finally, some decomposition techniques are identified which exploit the particular structure of the problem, as an alternative solution approach.