A Column Generation Based Algorithm for Airline Cabin Crew Rostering Problem

摘要

Airline crew rostering problem is an important research area in airline operations research. In this paper, we present a column generation based algorithm to solve this problem. The objective is to assign a personalized roster to crew member which minimize the number of unassigned pairings and ensure the fairness to crew members. To minimize the unassigned pairings, when there is a shortage of qualified crew members, we offer operation to allow relaxing some soft rules when generate rosters. Line-of-Work for crew members are generated in parallel, which improve the efficiency of the algorithm. The algorithm we propose in this paper has been put into production in a major airline in China and has a good performance.