A Constraint Programming Approach to Finding Stable Matchings within Airline Manpower Planning

Abstract

The objective of airline manpower planning is to have the right number of pilots with the right qualifications at the right time. To accomplish this, one has to solve the subproblem of assigning pilots to promotion courses such that pilots’ seniority ranks and preferences are taken into account: no senior pilot should be able to find a junior pilot with a promotion that the senior pilot would have preferred. We call this subproblem the airline promotion assignment problem (APA). The objective of this thesis is to develop an efficient model for APA. We show how APA can be modelled as a stable matching problem, and more specifically how it can be formulated as an instance of the hospitals/residents problem with ties and forbidden pairs. A constraint satisfaction problem model for APA is presented, which we have implemented in a constraint programming system. We also present a model for an extension to APA, which we call the airline promotion assignment problem with detailed preferences (APA-D), and which involves additional rules used within a specific airline. We show results from running our constraint programming implementation on different types of test data derived from real airline data. The thesis is concluded with a discussion of our work and some remarks on how the problem could be modelled and solved differently.