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

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.