Methodology for crew-pairing problem in airline crew scheduling

Abstract

Crew scheduling problem is divided into two sub problems, crew pairing and crew assignment problems. In literature, there are many studies on crew pairing problem and in this study also main subject is crew pairing problem. In this thesis, previous work on crew pairing problem is investigated and a hybrid method is developed by combining previous methods. In this study, the mathematical representation of the crew pairing problem is explained. Basically, the problem is represented as integer programming problem but to reduce the complexity it is relaxed to linear programming (LP) problem. Most well-known method for solving large size of LP is sprint method. Also in previous studies, another method which is called dynamic pairing generation is developed. Commonly for finding integer values after solving LP, branch and bound or branch on follow-on method is used. Also, Carmen algorithm is another method for getting integer values after finding LP solution. In hybrid method, for solving LP problem sprint method is used. For finding integer values, after solving LP problem Carmen algorithm is implemented. Experiments show that Carmen algorithm is very fast but it gives bad results. Therefore, another version of hybrid method is implemented which also starts with sprint method and uses branch on follow-on method to find integer solutions. In the last section, the comparison of the test results between Carmen algorithm and branch on follow-on method is given. As a conclusion a brief summary on hybrid method is explained and for future work is given.