Construction of optimal tours of duty for long-haul flight attendants

Abstract

A Tour of Duty (TOD) is an alternating sequence of duty periods and rest periods that makes up a work schedule for a number of people. An airline's flight schedule is fully crewed by the interaction of a large number of TODs, combined in such a way that each flight will have the required number of crew on board. Constructing the set of TODs for a given airline schedule that minimises the cost of crewing all flights is a complex task. Contractual rules and regulations governing legal TODs are often very complicated, and contribute to TOD problem complexity. The Long-Haul/International Flight Attendant problem is probably the most difficult of all the TOD problems because the number of flight attendants required on a flight depends on the aircraft type, and flight attendants are qualified to operate on many different aircraft types. This means that crews can split into smaller groups and recombine with other groups to form different complements. This thesis describes the problem and presents a novel approach that is used to solve the problem. This approach involves a combination of column generation and model refinement using row generation. The approach has been successfully applied to an international airline's crew scheduling problem. Very significant savings have been achieved over existing manual methods. The software developed is capable of being used as a tool to evaluate potential changes to the contractual rules, as well as the impact of flight schedule changes.