A Novel Column Generation Heuristic for Airline Crew Pairing Optimization with Large-scale Complex Flight Networks

For an airline, the crew operating cost is second only to the fuel cost, making the crew pairing optimization (CPO) critical for business viability. Its aim is to generate a set of flight sequences (crew pairings) that cover all flights in an airline's schedule, at minimum cost, while satisfying several legality constraints. Being an NP-hard combinatorial optimization problem, CPO is tackled by relaxing the underlying Integer Programming Problem into a Linear Programming Problem, and solving the latter through Column generation (CG) technique. However, with the expansion of airlines' operations lately, the curse of dimensionality renders the exact CG-implementations obsolete, paving the way for heuristic-based CG-implementations. Yet, the much prevalent large-scale complex flight networks involving multiple-crew bases and hub-and-spoke sub-networks, largely remain unaddressed. To bridge the research gap, this paper proposes a novel CG heuristic, which has enabled in-house development of an Airline Crew Pairing Optimizer (AirCROP). The efficacy of the heuristic/AirCROP has been: (a) tested on real-world airline data with an unprecedented conjunct scale-and-complexity, marked by over 4200 flights, 15 crew bases, and over a billion pairings, and (b) validated by the research consortium's industrial sponsor. This paper has a dedicated focus on the proposed CG heuristic which constitutes the core search mechanism of the optimizer, by balancing random exploration (of pairings' space), exploitation of domain knowledge (on optimal solution's features), and utilization of the past computational effort through archiving. Though this paper has an airline context, the underlying propositions may find applications across different domains as the proposed CG heuristic can serve as a template on how to utilize domain knowledge to better tackle large-scale combinatorial optimization problems.