AIRLINE CREW PAIRING OPTIMIZATION FOR LARGESCALE & COMPLEX FLIGHT NETWORKS

Abstract

Airline Crew Scheduling (ACS) is one of the most crucial planning activities for an airline, since the crew operating cost is second only to the fuel cost. ACS entails a combination of two optimization problems, namely, Crew Pairing Optimization Problem (CPOP) and Crew Assignment Problem, which are usually tackled in a sequential manner. This thesis has its focus on CPOP, where the aim is to generate a set of flight sequences (each called a crew pairing) to cover all the flights in an airline’s flight schedule, at minimum cost, while satisfying hundreds of legality constraints linked to the federations’ safety regulations, airline-specific rules, labor laws, etc. CPOP is an NP-hard combinatorial optimization problem, to tackle which the state-ofthe- art relies on relaxing the underlying Integer Programming Problem (IPP) into a Linear Programming Problem (LPP), and solving the latter by invoking an LP solver and relying on Column Generation (CG) technique to generate new pairings as part of the pricing subproblem. Finally, the resulting LPP solution is integerized using an IP solver and/or a special (connection-fixing/pairing-enumeration) heuristic. The challenge associated with this strategy is that even though the LP solver may lead to a near-optimal LPP solution, the scope of finding a good-cost IPP solution is limited to the pairings available in the LPP solution. To overcome this challenge, heuristic implementations of branch-and-price algorithm, in which CG is utilized to generate new pairings during the integerization phase too (at the nodes of the IP-search tree), have been employed. Numerous branch-and-price frameworks with varying algorithmic choices (say, which branching scheme to adopt, or which node to select first, etc.) have been proposed in CPOP’s literature. However, the number of pricing sub-problems (corresponding to the combination of each crew base and each day of the planning horizon), that are to be solved in each iteration of CG, increases drastically with the scale and complexity of the flight networks. This necessitates efficient solutioning of the pricing sub-problems. Recognition of this has paved the way towards domain-knowledge-driven CG strategies to generate a i manageable, yet crucial part of the overall pairings’ space, as part of the solution to the pricing sub-problem. Though rich in promise, the efficacy of these CG strategies remains unexplored vis- a-vis the emergent large-scale and complex flight networks, characterized by multiple crew bases and multiple hub-and-spoke sub-networks, wherein billions of legal pairings are possible. To overcome the challenges associated with the scale and complexity of airline networks, this thesis proposes domain-knowledge driven CG heuristic, leading up to an Airline Crew Pairing Optimization Framework (AirCROP). Its constitutive modules comprise of a Legal Crew Pairing Generator, an Initial Feasible Solution Generator, and an Optimization Engine enabled by CG-driven LPP-solutioning and IPP-solutioning submodules. Notably, the novelty of AirCROP lies in not just the design of its constitutive modules, but also in how these modules interact. In that, while the domain-knowledge-driven CG heuristic contributes to an efficient solutioning of the pricing sub-problems under the LPPsolutioning submodule, the intermittent interactions of its CG-driven LPP-solutioning and IPP-solutioning submodules help in abating the limitations of the IPP-relaxation approach. Besides this, the distinctive contribution of this thesis lies in its empirical investigation of the critically important questions relating to the sensitivity of AirCROP ’s performance towards the sources of variability, the choice of different methods in its modules and their parameter settings, which the literature is otherwise silent on. The utility of the above propositions within the gamut of AirCROP has been demonstrated through extensive experiments on real-world airline test cases, pertaining to largescale and complex flight networks– marked by over 4,200 flights, 15 crew bases, multiple hub-and-spoke sub-networks (involving several billion legal pairings). The efficacy of the obtained results on different test cases has been validated by GE Aviation– consortium’s Industrial sponsor. It may be interesting to note, that even though the above propositions have an airline context, they can serve as a template on how to utilize domain knowledge to better tackle large-scale combinatorial optimization problems across different domains.