JILSA  Vol.4 No.1 , February 2012
An Improved Genetic Algorithm for Crew Pairing Optimization
Crew pairing is a sequence of flights beginning and ending at the same crewbase. Crew pairing planning is one of the primary processes in airline crew scheduling; it is also the primary cost-determining phase in airline crew scheduling. Optimizing crew pairings in an airline timetable helps minimize operational crew costs and maximize crew utilization. There are numerous restrictions that must be considered and just as many regulations that must be satisfied in crew pairing generation. The most important regulations—and the ones that make crew pairing planning a highly constrained optimization problem—are the the limits of the flight and the duty periods. Keeping these restrictions and regulations in mind, the main goal of the optimization is the generation of low cost sets of valid crew pairings which cover all flights in the airline’s timetable. For this research study, We examined studies about crew pairing optimization and used these previously existing methods of crew pairing to develop a new solution of the crew pairing problem using genetic algorithms. As part of the study we created a new genetic operator—called perturbation operator.Unlike traditional genetic algorithm implementations, this new perturbation operator provides much more stable results, an obvious increase in the convergence rate, and takes into account the existence of multiple crewbases.

Cite this paper
B. Zeren and İ. Özkol, "An Improved Genetic Algorithm for Crew Pairing Optimization," Journal of Intelligent Learning Systems and Applications, Vol. 4 No. 1, 2012, pp. 70-80. doi: 10.4236/jilsa.2012.41007.
[1]   H. T. Ozdemir and C. K. Mohan, “Flight Graph Based Genetic Algorithm for Crew Scheduling in Airlines,” Information Sciences, Vol. 133, No. 3-4, 2001, pp. 165-173. doi:10.1016/S0020-0255(01)00083-4

[2]   F. M. Zeghal and M. Minoux, “Modeling and Solving a Crew Assignment Problem in Air Transportation,” European Journal of Operational Research, Vol. 175, No. 1, 2006, pp. 187-209.doi:10.1016/j.ejor.2004.11.028

[3]   Republic of Turkey Ministry of Transport, Maritime Affairs and Communication, “Instruction on Flying Team’s Task and Resting Terms and Principles of Application,” 2005. http://www.shgm.gov.tr/doc3/sht6a50.doc

[4]   J. E. Beasley and P. C. Chu, “A Genetic Algorithm for the Set Covering Problem,” European Journal of Operational Research, Vol. 94, No. 2, 1996, pp. 392-404. doi:10.1016/0377-2217(95)00159-X

[5]   J. H. Holland, “Adaptation in Natural and Artificial Systems,” MIT Press, Cambridge, 1975.

[6]   C. P. Medard and N. Sawhney, “Airline Crew Scheduling —from Planning to Operations,” 2005. http://www.carmen.se/research_development/research_reports.htm

[7]   H. Kornilakis and P. Stamatopoulos, “Crew Pairing Optimization with Genetic Algorithms,” Lecture Notes in Computer Science, Vol. 2308, 2002, pp. 109-120. doi:10.1007/3-540-46014-4_11

[8]   C. Barnhart, et al., “Branch-and-Price: Column Generation for Solving Huge Integer Programs,” Operations Research, Vol. 46, No. 3, 1998, pp. 316-329. doi:10.1287/opre.46.3.316

[9]   D. Klabjan, E. L. Johnson and G. L. Nemhauser, “Solving Large Airline Crew Scheduling Problems: Random Pairing Generation and Strong Branching,” Computational Optimization and Applications, Vol. 20, No. 1, 2001, pp. 73-91. doi:10.1023/A:1011223523191

[10]   L. F. G. Hernandez, “Evolutionary Divide and Conquer for the Set-Covering Problem,” Lecture Notes in Computer Science, Vol. 1143, 1996, pp. 198-208. doi:10.1007/BFb0032784

[11]   U. Aickelin, “An Indirect Genetic Algorithm for Set Covering Problems,” Journal of the Operational Research Society, Vol. 53, No. 10, 2002, pp. 1118-1126. doi:10.1057/palgrave.jors.2601317

[12]   T. Park and K. R. Ryu, “Crew Pairing Optimization by a Genetic Algorithm with Unexpressed Genes,” Journal of Intelligent Manufacturing, Vol. 17, No. 4, 2006, pp. 375383. doi:10.1007/s10845-005-0011-z

[13]   L. H. Lee, C. Ung Lee and Y. P. Tan, “A Multi-Objective Genetic Algorithm for Robust Flight Scheduling Using Simulation,” European Journal of Operational Research, 2007, Vol. 177, No. 3, 2007, pp. 1948-1968. doi:10.1016/j.ejor.2005.12.014

[14]   C. Barnhart, A. M. Cohn, E. L. Johnson, D. Klabjan, G. L. Nemhauser and P. H. Vance, “Handbook of Transportation Science,” Springer, Berlin, 2003.

[15]   D. Wedelin, “The Design of a 0-1 Optimizer and Its Application in the Carmen System,” European Journal of Operational Research, Vol. 87, No. 3, 1995, pp. 722-730. doi:10.1016/0377-2217(95)00243-X

[16]   Turkish Airlines Flight Schedule Document, 2007. http://www.turkishairlines.com/en-INT/online_services/schedule/time_table.aspx