Crew Scheduling has been a significant topic of study for researchers in the past due to its impact on airline costs. It has been mentioned by many sources that crew costs are the second highest expense for airline companies [1]. In fact, a one percent reduction in flying time for pilots can yield up to $500,000/month in savings [2]. Incremental improvements have been presented throughout the years, yet the need for further research is evident as no solution is guaranteed to be optimal, since crew scheduling problems are proven to be NP-hard [3]. Problems of such complexity require comprehensive thought built upon knowledge of previously used techniques. The main motivation for this research is to investigate whether the application of Genetic Algorithms, with an appropriate chromosome representation, can help to improve on the current solutions to crew scheduling. 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 throughout the years. In this study, the focus is on cockpit crew assignment, where pairings are to be assigned along with relative rests to form a monthly schedule, while aiming at maximising crew satisfaction in terms of pilot vacation preferences and preferred flights assigned. Pairings represent a set of flights along with necessary rest periods and briefing times.
The problem is modelled as a directed graph where each node represents a pairing and every arc associates a legal rest period between two pairings. The solutions from the graph- problem are utilised in a customised Greedy Heuristic and a Genetic Algorithm. The results obtained from both techniques are compared to a previous Column Generation approach developed by [4] in order to evaluate the quality of solutions obtained. Results are presented in terms of vacation and flight preferences satisfied. Based on the constraint values established, reduction in costs are reported for six out of seven instances of varying sizes. Competitive airleg satisfaction was obtained, all while providing high vacation satisfaction to cockpit crew. The GA achieved better flight preferences for four out of seven instances while satisfying more vacation preferences in all instances.
References
[1] N. Kohl and S. E. Karisch, “Airline crew rostering: Problem types, modeling, and optimization,” Annals of Operations Research, vol. 127, no. 1, pp. 223-257, Mar 2004.
[2] G. W. Graves, R. D. McBride, I. Gershkoff, D. Anderson, and D. Mahidhara, “Flight crew scheduling,” Management Science, vol. 39, no. 6, pp. 736-745, 1993.
[3] M. R. Garey and D. S. Johnson, Computers and Intractability; A Guide to the Theory of NP Completeness. New York, NY, USA: W. H. Freeman & Co., 1990.
[4] Kasirzadeh, M. Saddoune, and F. Soumis, “Airline crew scheduling: models, algorithms, and data sets,” EURO Journal on Transportation and Logistics, vol. 6, no. 2, pp. 111-137, June 2015.
Student: Isaac Zammit
Supervisor: Dr Colin Layfield
Co-Supervisor: Dr John Abela
Course: B.Sc. IT (Hons.) Software Development