  Airline crew pairing optimization problem (CPOP) aims to find a set of flight
sequences (crew pairings) that cover all flights in an airline's highly
constrained flight schedule at minimum cost. Since crew cost is second only to
the fuel cost, CPOP solutioning is critically important for an airline.
However, CPOP is NP-hard, and tackling it is quite challenging. The literature
suggests, that when the CPOP's scale and complexity is reasonably limited, and
an enumeration of all crew pairings is possible, then Metaheuristics are used,
predominantly Genetic Algorithms (GAs). Else, Column Generation (CG) based
Mixed Integer Programming techniques are used. Notably, as per the literature,
a maximum of 45,000 crew pairings have been tackled by GAs. In a significant
departure, this paper considers over 800 flights of a US-based large airline
(with a monthly network of over 33,000 flights), and tests the efficacy of GAs
by enumerating all 400,000+ crew pairings, apriori. Towards it, this paper
proposes a domain-knowledge-driven customized-GA. The utility of incorporating
domain-knowledge in GA operations, particularly initialization and crossover,
is highlighted through suitable experiments. Finally, the proposed GA's
performance is compared with a CG-based approach (developed in-house by the
authors). Though the latter is found to perform better in terms of solution's
cost-quality and run time, it is hoped that this paper will help in better
understanding the strengths and limitations of domain-knowledge-driven
customizations in GAs, for solving combinatorial optimization problems,
including CPOPs.
