This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Achour, H. Articles by Desaulniers, G. Search for Related Content

An Exact Solution Approach for the Preferential Bidding System Problem in the Airline Industry

École Polytechnique de Montréal and GERAD, C.P. 6079 succ. Centre-ville, Montréal, Québec, Canada H3C 3A7
École Polytechnique de Montréal and GERAD, C.P. 6079 succ. Centre-ville, Montréal, Québec, Canada H3C 3A7
École Polytechnique de Montréal and GERAD, C.P. 6079 succ. Centre-ville, Montréal, Québec, Canada H3C 3A7
École Polytechnique de Montréal and GERAD, C.P. 6079 succ. Centre-ville, Montréal, Québec, Canada H3C 3A7
heykel.achour{at}gerad.ca
michel.gamache{at}polymtl.ca
francois.soumis{at}gerad.ca
guy.desaulniers{at}gerad.ca

This paper introduces the first exact approach for constructing aircrew member personalized monthly work schedules when a preferential bidding system (PBS) is used. With such a system, each employee bids for his/her preferred activities, yielding a bidding score for each feasible schedule. The PBS problem thus consists of assigning to each employee a schedule that maximizes his/her preferences, in order of seniority, while covering all crew pairings. The proposed exact solution approach relies on column generation, and when a tentative maximum score for a crew member is established, it explicitly enumerates for that employee all feasible schedules with that score. Tests on real-life cases show that this approach can substantially improve the quality of the solutions produced by the best known existing method in similar computational times.

Key Words: airline industry; crew scheduling; preferential bidding system; branch and price
History: Received: December 2004; revised: June 2006; accepted: July 2006.