A hybrid scatter search for the airline crew rostering problem

An airline company needs to assign a roster to all necessary crew members such that the airline is able to operate all the duties of its flight schedule. In our problem formulation, the objective is to assign a personalized roster to each regular crew member minimizing the overall operational costs while ensuring impartiality among crew members and maximizing the social quality of the schedule. To that purpose, we present a hybrid scatter search algorithm which encompasses different complementary meta-heuristic crew scheduling crossover operators and local search methods. Detailed computational experiments are presented and comparison is made with a branch-and-price procedure and a variable neighborhood search.An airline company needs to assign a roster to all necessary crew members such that the airline is able to operate all the duties of its flight schedule. In our problem formulation, the objective is to assign a personalized roster to each regular crew member minimizing the overall operational costs while ensuring impartiality among crew members and maximizing the social quality of the schedule. To that purpose, we present a hybrid scatter search algorithm which encompasses different complementary meta-heuristic crew scheduling crossover operators and local search methods. Detailed computational experiments are presented and comparison is made with a branch-and-price procedure and a variable neighborhood search.C