Column generation heuristics to airline crew scheduling problem for fair working time

In this paper, the modeling and solution strategies of a practical airline crew scheduling problem are studied. The airline crew scheduling problem to achieve the equalization of working time taking into account for practical constraints such as international and domestic flights, holiday assignments, and grouping constraints is formulated as an integer programming problem. The problem is reformulated as a set partitioning problem by Dantzig-Wolfe decomposition. The column generation algorithm is applied to solve the linear relaxation of the original problem. In order to improve the performance of the algorithm, a column fixing strategy with backtracking is proposed. In the proposed method, the schedule for all crews is obtained efficiently by exploiting the fixing of columns and the execution of the column generation procedure. The backtracking is introduced to find a feasible solution efficiently. The computational results show that the proposed algorithm can find better solutions than greedy-heuristics and the branch and bound procedure solving the original problem by a commercial solver.