Abstract:
Every airline must solve the aircraft and aircrew scheduling problems. The crew rostering problem is an important component of the aircrew scheduling problem. The construction of flight attendant rosters for short-haul airline flight services must satisfy rostering constraints, employment contract regulations and equitability requirements. This is a Combinatorially complex problem. In this thesis 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 sub-problems. 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 sub-roster period, and then the solution of a set partitioning optimisation to determine an optimal feasible sub-roster. These two steps of generation and optimisation are repeated for each subsequent sub-roster period until a full legal and feasible roster is constructed for the complete roster period. The use of sub-rosters reduces the combinatorial complexity resulting in problems which can be solved efficiently. After construction of the initial roster, the quality can often be improved using re-rostering techniques. The method leads to the efficient construction of good quality legal rosters. Important issues related to implementation are also discussed. The roster-building process has been used to produce all short-haul flight attendant rosters at Air New Zealand since 1993. An algorithm to efficiently solve the set partitioning optimisation problems is described. A linear programming relaxation problem is solved followed by an evaluation of a branch and bound search tree. Special mathematical techniques are implemented to improve the effectiveness of the solution algorithm. The relative effectiveness of primal and dual steepest edge algorithms is analysed.