Flight attendant rostering for short-haul airline operations

The construction of flight attendant (cabin crew) rosters for short-haul (domestic) airline flight services that satisfies rostering constraints and employment contract regulations is a combinatorially complex problem. In this paper the problem is described and an effective optimisation-based solution method is introduced. The rostering problem involves the allocation of days-off and various duties to each crew member over a roster period. The days-off and the duty allocation problems are separated into two distinct subproblems. The days-off allocation solution approach involves complete enumeration of all possible days-off lines for each crew member over the roster period, and then the solution of a set partitioning optimisation to determine a best quality feasible days-off roster. The duty allocation solution approach first involves the generation of many lines-of-work consistent with the days-off solution for each crew member over a subroster period and then the solution of a set partitioning optimisation to determine an optimal feasible subroster. These two steps of generation and optimisation are repeated for each subsequent subroster period until a full legal and feasible roster is constructed for the complete roster period. The use of subrosters reduces the combinatorial complexity resulting in problems that can be solved efficiently. After construction of the initial roster, the quality can often be improved using re-rostering techniques. The method leads to efficient construction of good quality legal rosters, and has been used to produce all short-haul flight attendant rosters at Air New Zealand since 1993.