  Crew Pairing Optimization (CPO) is critical for an airlines' business
viability, given that the crew operating cost is second only to the fuel cost.
CPO aims at generating a set of flight sequences (crew pairings) to cover all
scheduled flights, at minimum cost, while satisfying several legality
constraints. The state-of-the-art heavily relies on relaxing the underlying
Integer Programming Problem into a Linear Programming Problem, which in turn is
solved through the Column Generation (CG) technique. However, with the
alarmingly expanding airlines' operations, CPO is marred by the curse of
dimensionality, rendering the exact CG-implementations obsolete, and
necessitating the heuristic-based CG-implementations. Yet, in literature, the
much prevalent large-scale complex flight networks involving multiple { crew
bases and/or hub-and-spoke sub-networks, largely remain uninvestigated. This
paper proposes a novel CG heuristic, which has enabled the in-house development
of an Airline Crew Pairing Optimizer (AirCROP). The efficacy of the
heuristic/AirCROP has been tested on real-world, large-scale, complex network
instances with over 4,200 flights, 15 crew bases, and multiple hub-and-spoke
sub-networks (resulting in billion-plus possible pairings). Notably, this paper
has a dedicated focus on the proposed CG heuristic (not the entire AirCROP
framework) based on balancing random exploration of pairings; exploitation of
domain knowledge (on optimal solution features); and utilization of the past
computational & search effort through archiving. Though this paper has an
airline context, the proposed CG heuristic may find wider applications across
different domains, by serving as a template on how to utilize domain knowledge
to better tackle combinatorial optimization problems.
