An application of column generation to the airline crew pairing problem

Abstract

As the competitive market between airline industries increases, the search for ways to edge over competitors is a never-ending struggle for every airline company. Every company has its own techniques for finding the best way to make the highest profit, whilst abiding by the strict rules and regulations imposed upon by the authorities. Over the years, optimising the airline crew pairing problem has been proven to be an essential area of research through which airline companies can reduce their operational costs. The crew paring problem involves the assignment of a predetermined set of flights to pairings such that no flight is left uncovered and the total cost of pairings is minimised. The aim of this dissertation is mainly to analyse the success of column generation when applied to the airline crew pairing problem. Column generation has been renowned to be one of the best techniques to solve these kind of optimisation problems, as it decomposes the main problem into subproblems, thus making computations more manageable and efficient. An integer programming model as well as a mixed integer programming model have been proposed to optimise this complex crew pairing problem. Care was taken to obtain results that reflect the current airline situation, mainly by using real-life data, obtained from a major North-American airline company, and also by considering the latest rules and regulations. Several instances of different sizes of flight sets have been considered and solved through Python software together with a GUROBI solver, to show that column generation provides efficient results to the airline crew pairing problem.