Optimized Crew Scheduling at Air New Zealand

The aircrew-scheduling problem consists of two important subproblems: the tours-of-duty planning problem to generate minimum-cost tours of duty (sequences of duty periods and rest periods) to cover all scheduled flights, and the rostering problem to assign tours of duty to individual crew members. Between 1986 and 1999, Air New Zealand staff and consultants in collaboration with the University of Auckland have developed eight application-specific optimization-based computer systems to solve all aspects of the tours-of-duty planning and rostering processes for Air New Zealand's national and international operations. These systems have saved NZ$15,655,000 per year while providing crew rosters that better respect crew members' preferences.