Heuristic and meta-heuristic approaches to cockpit crew scheduling

Abstract

Scheduling problems are of keen interest to many researchers, mostly due to the challenge of obtaining near-optimal results in polynomial time. Research for crew scheduling has been conducted and incremental improvements have been presented throughout the years, yet the need for further research is evident as no solution can be guaranteed to be optimal, since crew scheduling is proved to be an NP-hard problem. Problems of such complexity require comprehensive thought on the problem representation in order to provide a satisfactory end solution. The main motivation for this research is to investigate whether or not the application of Genetic Algorithms with an appropriate chromosome representation can help to improve on the current solutions to crew scheduling. Undoubtedly, managing to provide a solution that improves on the current state-of-the-art is hard to achieve. The current state-of-the-art technique for crew scheduling is Column Generation, due to its wide use in literature and the impressive results presented through such an approach. This study considers the crew assignment problem for cock-pit crew, where the problem is modelled as a graph. The initial solutions from the graph provide feasible schedules that comply to the airline regulations established. Such solutions represent the population for the Genetic Algorithm. The Genetic Algorithm is then compared to a Column Generation approach in terms of crew satisfaction and results are presented for data from a major US carrier. Satisfactory results are reported. Aspects for further research are discussed as to possibly improve upon the solution.