FLIGHT ATTENDANT ROSTERING FOR SHORT-HAUL AIRLINE OPERATIONS

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