Improvements in column generation methods to solve large scale airline crew scheduling problems

Abstract

Airline crew scheduling problems are one of the most important problems in airline industry that have received considerable attention in operations research literature due to the complexity and the size of the problem. Solving this type of problems optimally is very challenging since the number of variables cannot be counted in most times. Column generation method is very successful in solving this type of problems because it provides the possibility to work with a limited number of variables and ensures to obtain the optimal result at the end of the process. Applying the column generation method, airline crew scheduling problems are divided into two parts as -(1) master problem and -(2) subproblem. Starting with a small number of variables, the master problem, which is an optimization problem, provides the optimal solution for the limited number of variables at each iteration, whereas the subproblem is a resource constrained shortest path problem (RCSP), in which the solution corresponds to the variable (roster) to be added to the master problem at each iteration. During the column generation process, the time consumption for solving the subproblem is larger than that of the master problem. As a result, improvements made on the solution procedure of the subproblem contribute a great deal to the overall e ciency of the column generation method. The contribution of this thesis is two-fold. First, we concentrate on the improvements of the subproblem by attaching a preprocessing algorithm at the very begining of the problem, and transforming RCSP into shortest path problem (SPP). This process was previously suggested in the literature and de ned as three stage approach (TSA), in which the network reduction, network expansion and iterative solution stages are involved. In this thesis, TSA is modi ed by eliminating some steps in some stages in order to make this method more compatible for airline crew scheduling applications. Second, TSA in vectorial form (TSA-V), which is developed in this thesis, is proposed in which the network reduction stage is processed by vectorial comparison of the resources. Computational results also show that TSA-V is more e ective in eliminating the infeasible edges. The e ciencies of both methods are also compared based on the conducted experiments at the computational study part.