Crew rostering under a seniority preferential bidding environment using column generation

Abstract

Computerised scheduling using optimisation techniques presents significant potential savings opportunities, particularly for airlines where the aircraft and their crew are a costly resource. This thesis describes the development of a solution to an air crew rostering problem, formulated as a set partitioning model, for the International Pilots at Air New Zealand. The Seniority Preferential Bidding environment under which the pilots are rostered requires the minimum possible denial of crew bids in a hierarchical sense of crew seniority. An approach incorporating a column generator has been developed to ensure this problem can be optimally solved. The use of column generation is a new approach to solving the air crew rostering problem. Results are presented which demonstrate the effectiveness of this technique in this environment. The software developed during this research is currently in use in Air New Zealand's production systems.