Subsequence Generation for the Airline Crew Pairing Problem

Good and fast solutions to the airline crew pairing problem are highly interesting for the airline industry, as crew costs are the biggest expenditure after fuel for an airline. The crew pairing problem is typically modelled as a set partitioning problem and solved by column generation. However, the extremely large number of possible columns naturally has an impact on the solution time. In the solution method of this work we severely limit the number of allowed subsequent ights, i.e. the subsequences, thereby significantly decreasing the number of possible columns. Set partitioning problems with limited subsequence counts are known to be easier to solve, re- sulting in a decrease in solution time. The problem though, is that a small number of deep subsequences might be needed for an optimal or near-optimal solution and these might not have been included by the subsequence limitation. Therefore, we try to identify or generate such subsequences that potentially can improve the solution value. We benchmark the subsequence generation approach against a classical column generation approach on real-life test instances. We consider the LP relaxation and compare the quality and the integrality of the solutions. The LP solutions from the subsequence generation approach are less fractional, but it comes at the cost of a worse solution quality. The approach in the present paper is novel. To our knowledge generation of subsequences have not been described and tested previously in the literature.