On Large-Scale Airline Crew Pairing Generation

Crew operating cost is the second largest cost component of an airlines' total operating cost (second only to the fuel cost) and even marginal cost savings here may amount to millions of dollars, annually. Towards it, a crew needs to be efficiently assigned a sequence of flights starting and eliding at the same crew base (a crew pairing). The challenge for an airline is to generate crew pairings which completely cover a finite set of flights over a particular time window, with minimum cost, while satisfying multiple legality constraints linked to airlines' own regulations, labor laws, and government safety rules etc. The success in solving the associated constrained optimization problem largely depends on solving NP-complete subproblems, linked to the generation of a feasible solution (legal crew pairings covering all flights) and generation of pairings with reasonable cost-quality. In an attempt to address these subproblems in a computationally- and time-efficient manner, the contributions of this paper relate to the use and characterization of network structure for pairing generation; enhancement of the graph traversal algorithm, namely Depth-first Search (DFS); its parallel implementation on multiple processors of a single computer; and embedding of cost considerations during pairing generation itself towards boosting the optimizer's performance subsequently. The utility of the cited contributions is demonstrated on medium (similar to 2000 flights) and large (similar to 4000 flights) data sets provided by GE Aviation.