On Learning Combinatorial Patterns to Assist Large-Scale Airline Crew
  Pairing Optimization
  Airline Crew Pairing Optimization (CPO) aims at generating a set of legal
flight sequences (crew pairings), to cover an airline's flight schedule, at
minimum cost. It is usually performed using Column Generation (CG), a
mathematical programming technique for guided search-space exploration. CG
exploits the interdependencies between the current and the preceding
CG-iteration for generating new variables (pairings) during the
optimization-search. However, with the unprecedented scale and complexity of
the emergent flight networks, it has become imperative to learn higher-order
interdependencies among the flight-connection graphs, and utilize those to
enhance the efficacy of the CPO. In first of its kind and what marks a
significant departure from the state-of-the-art, this paper proposes a novel
adaptation of the Variational Graph Auto-Encoder for learning plausible
combinatorial patterns among the flight-connection data obtained through the
search-space exploration by an Airline Crew Pairing Optimizer, AirCROP
(developed by the authors and validated by the research consortium's industrial
sponsor, GE Aviation). The resulting flight-connection predictions are combined
on-the-fly using a novel heuristic to generate new pairings for the optimizer.
The utility of the proposed approach is demonstrated on large-scale (over 4200
flights), real-world, complex flight-networks of US-based airlines,
characterized by multiple hub-and-spoke subnetworks and several crew bases.
