A column generation algorithm and an application for airline crew scheduling problem

Crew scheduling problem is one of the hard and comprehensive problems faced with in airline planning. Since personel costs is the biggest expenditure that an airline could control, assigning crews to flight legs effectively is crucial in airline planning. In crew scheduling problem, the goal is to find the minimum costly set of pairings in that each flight leg is covered at least by one crew pairing. But generating all possible crew pairings is fairly difficult and it also means that a lot of pairings which will not take place in the optimal solution, may be generated unnecessarily. In this study, a column generation approach that is commonly used in crew scheduling literature in which variables are dynamically generated is used for airline crew scheduling problem. The master problem is formulated as a set covering problem while the subproblem is formulated as a shortest path problem. Initial pairings, which are enough to give a feasible solution, are produced and the master and sub-problems are solved iteratively. Dual values related to flight legs obtained from the solution of the master problem is used in the objective function of the sub-problem. The algortihm is applied to a private airline company?s crew scheduling problem using real datas and optimal crew schedules are obtained.