Pricing by local search in column generation for the airline crew pairing problem

Official URL: http://192.168.1.20/record=b1302917 (Table of Contents)

The airline crew pairing problem (ACP) is finding the least costly set of crew pairings so that each flight given in the flight schedule is covered. The ACP is traditionally modeled either as a set partitioning problem or a set covering problem. Due to the large number of possible pairings (columns), these models are usually solved by the column generation (CG) method. For the ACP, the pricing subproblem of the CG corresponds to a multi-label shortest path problem (MLSP) typically solved over a flight network. The MLSP over the flight network is NP-hard and it suffers from an exponential complexity even for moderate size flight networks. In order to overcome the complexity of the pricing subproblem, we propose a column generation method to solve the ACP, in which a hybrid pricing procedure is used. In this hybrid procedure, the pricing subproblem consists of three steps. First, we apply a local search mechanism on the partial duty period pool to construct pairings with negative reduced cost. In cases local search mechanism cannot find such a pairing, we execute a heuristic MLSP algorithm over the partial duty network to price out negative reduced cost pairings for the restricted master problem (RMP). If this method also fails, we solve the MLSP over the flight network. By adopting this hybrid approach, we aim to decrease the number of CG iterations where the MLSP is executed over the flight network, and reduce the computation time per iteration as well as the total computation time. We test the efficiency of our approach on real-life instances acquired from a local airline company, and present numerical results.