The Airline Industry is one of the fastest-growing industries in the world. To keep up with such
demand and remain, profitable researchers, are actively finding ways to optimise different aspects
of an airline’s operations in any way possible. This is because even a small boost in
optimality can result in huge savings for the airline. One such operational problem is the Airline Crew
Scheduling problem, a complex problem which, because it is NP-Hard, has no way of being solved to
optimality in polynomial time. Therefore, different researchers have been providing techniques,
ranging from Column Generation, which is the most common method found in literature, to other
heuristics such as Branch and Price and Lagrangian Relaxation as well as meta-heuristics like Genetic
Algorithms and Simulated Annealing, to find a solution to achieve near-optimality in polynomial
time.
This problem is also routinely sub-divided into Crew Pairing and Crew Assignment, the former of
which is being focused upon in this study. We, therefore, are looking to find a combination of
pairings which cover all flights within a monthly period for the minimum cost.
In this study, a solution is proposed whereby a graph in conjunction with a depth-first search is
utilised is used to find all legal pairings under several predefined and variable legal, temporal,
spatial and fleet constraints. These pairings are then used to generate random solutions of relatively
high cost which are then inputted as the population into a genetic algorithm.
Solutions obtained after the optimisation of the initially generated chromosomes are than compared
to an initial solution generated using Column Generation, provided with the data set used which
itself was obtained from a major US carrier. Promising results were recorded and explained within
the paper as well as possibilities for future work to improve upon the provided solution.
Student: Liam Gatt
Course: B.Sc. IT (Hons.) Software Development
Supervisor: Prof. John Abela