| dc.description.abstract | Airline crew scheduling problems have been traditionally formulated as set covering problems or set partitioning problems. To resolve large-scale problems in practice, the column generation approach with integer programming algorithms has usually been employed in decades. When airline carriers face the multi-base operations as well as aircraft type continuity and cabin classes in practical operations, these problems become more complicated and difficult to solve.
In this research, taking into account the aforementioned factors, we introduce new network models that can improve both efficiency and effectiveness of solving crew scheduling problems to help air carriers minimize crew cost and plan proper crew service rotations under the real constraints. Mathematically, the models will be respectively formulated as network flow problems with side constraints and multi-commodity network flow problems. A Lagrangian relaxation-based algorithm, coupled with a subgradient method, the network simplex method and a heuristic for upper bound solution, is suggested to solve the problem. Based on the scenario, which a specific flight is only included in a work duty, we provide a simplified model which is classified as a pure network flow problem. The network simplex method is suggested to solve the simplified model in this research. Furthermore, the flow decomposition algorithm is applied to generate all pairings for cabin crews. In order to evaluate the model in practice, computational tests referring the international operation of a major airline carrier in Taiwan were performed. The results show the network models and the Lagrangian relaxation-based algorithm can be useful for efficiently solving large-scale airline crew scheduling problems. | en_US |