Integrated aircraft routing and crew pairing problem by benders decomposition

Abstract

The traditional airline planning is usually divided in several stages and solved sequentially, due to its size and complexity. The early stage results are inputs to the subsequent stage problems. Therefore, this sequential method may result in sub-optimality in planning. However, a fully integrated model is not tractable because of its enormous size. Nonetheless, benefits can be gained by partially integrating elements of the planning process. This paper uses the Benders decomposition to solve the integrated aircraft routing and crew pairing problem. Reversing the conventional approach, the crew pairing is formulated as the Benders master problem while a linear program on the selection of an aircraft maintenance routing is considered as the subproblem. We exploit the structure of the subproblem and identify two types of feasibility cuts. Test cases are generated to compare these two types of cuts. One of them is found to be stronger while the other is found to be computationally more efficient.