The Preferential Bidding System at Air Canada

Abstract

This paper describes the Preferential Bidding Problem solved in the airline industry to construct personalized monthly schedules for pilots and officers. This problem consists in assigning to crew members pairings, days off, annual leaves, training periods, etc., while considering a set of weighted bids that reflect individual preferences. This assignment must be done under strict seniority restrictions: the construction of a maximum-score schedule for a particular crew member must never be done at the expense of a more senior employee. This research and development project has resulted in the Preferential Bidding System that has been used at Air Canada since May 1995. The solution process is summarized as follows. For each employee, from the most senior to the most junior, a so-called residual problem is solved: given an employee and a set of unassigned pairings, the solution to an integer linear program determines the employee's maximum-score schedule while taking into account all the remaining employees. The residual problem is solved by column generation embedded in a branch-and-bound tree. Integer solutions are obtained by using very efficient cutting planes, without which it would have been impossible to solve some of these residual problems.