Title of Presentation: Some Aspects of Optimization Methods in Aircrew Scheduling

INFORMS 2002

San Jose, California

Monday, November 18, 2002

Abstract:

Besides constructing aircrew tours of duty or pairings with minimal cost, airlines also wish to construct pairings that are robust in that flight schedule disruptions are less likely to propagate delays into the future. In general a minimal cost solution is likely to lack robustness and conversely a solution with maximum robustness (however this might be measured) is likely to be more expensive. Professor Ryan will describe the aircrew scheduling process and in particular the pairings problem. He will review the development of optimization methods based on the set-partitioning model that produce minimal cost solutions. A measure of robustness for each pairing will then be developed and the concept of a linear robustness objective will be discussed. The two objectives of cost and robustness will be treated in a bi-criterion optimization to generate “efficient” pairings that do not allow a simultaneous improvement in cost and robustness. We show that treating the cost objective as a constraint while maximizing robustness leads to very difficult integer programming problems. This situation can be overcome by treating the cost objective as an elastic constraint and penalizing violations of the constraint in the robustness objective. (Some of this research is joint work with Matthias Ehrgott.)

Bio

David Ryan is Professor of Operations Research at the University of Auckland. Until the end of last year he was Head of the Department of Engineering Science. This year he has been on sabbatical in England, Denmark, Chile and the US. He is responsible for some fundamental and influential ideas in the field of applied combinatorial optimization, such as the set partitioning approach to routing and scheduling, and the constraint branching method for speeding up branch-andbound searches in certain applications. Professor Ryan’s research has significantly influenced OR applications throughout the world, especially with regard to airline crew scheduling problems. His work in this application area resulted in Air New Zealand being selected as a finalist in the 2000 Edelman competition. Professor Ryan has a keen interest in the practical use of OR methods to solve real-world problems and he is an acknowledged master at inspiring students, colleagues and people in industry to practice OR to maximum advantage.