  Crew pairing optimization (CPO) is critically important for any airline,
since its crew operating costs are second-largest, next to the fuel-cost. CPO
aims at generating a set of flight sequences (crew pairings) covering a
flight-schedule, at minimum-cost, while satisfying several legality
constraints. For large-scale complex flight networks, billion-plus legal
pairings (variables) are possible, rendering their offline enumeration
intractable and an exhaustive search for their minimum-cost full
flight-coverage subset impractical. Even generating an initial feasible
solution (IFS: a manageable set of legal pairings covering all flights), which
could be subsequently optimized is a difficult (NP-complete) problem. Though,
as part of a larger project the authors have developed a crew pairing optimizer
(AirCROP), this paper dedicatedly focuses on IFS-generation through a novel
heuristic based on divide-and-cover strategy and Integer Programming. For
real-world large and complex flight network datasets (including over 3200
flights and 15 crew bases) provided by GE Aviation, the proposed heuristic
shows upto a ten-fold speed improvement over another state-of-the-art approach.
Unprecedentedly, this paper presents an empirical investigation of the impact
of IFS-cost on the final (optimized) solution-cost, revealing that too low an
IFS-cost does not necessarily imply faster convergence for AirCROP or even
lower cost for the optimized solution.
