THE USAGE OF GENETIC ALGORITHMS TO SOLVE SET PARTITIONING MODEL: CREW PAIRING APPLICATION

  • Emre İpekçi Çetin
Keywords: Crew pairing, set partitioning model, genetic algorithms

Abstract

Crew pairing, which constitute the one phase of airline crew planning  is deliberated in this study. The airline crew pairing problem expressed in a set partitioning model is first solved by integer programming and then it is solved by genetic algorithms (GA) with MATLAB. The GA solution is tested by different crossover methods and population sizes. 120 experiments are made with these parameters and its performance is evaluated on the set partitioning model. Lastly, the integer programming and GA solutions of the crew pairing problem are compared. It’s seen that GA gives not only an optimal or nearoptimal solution, but also provides a choice flexibility to the decision maker by suggesting alternative solutions.

References

[1] Barnhart, C., Shenoi, R.G., “An Approximate Model and Solution Approach for the Long-Haul Crew Pairing Problem” Transportation Science, 32, 221-231, 1998.
[2] Butchers E.R., Day P.R., Goldie A.P., Miller S., Meyer J.A., Ryan D.M., Scott A.C., Wallace C.A., “Optimized Crew Scheduling at Air New Zealand”, Interfaces, 31(1), 30-56, 2001.
[3] Chu, H.D., Gelman, E., Johnson, E.L., “Solving Large Scale Crew Scheduling Problems”, European Journal of Operational Research, 97, 260-268, 1997.
[4] Chu, P.C., Beasley, J.E., “Constraint Handling in Genetic Algorithms: The Set Partitioning Problem”, Journal of Heuristics, 11, 323-357, 1998.
[5] Chu, P.C., Beasley, A., “A Genetic Algorithm for the Set Partitioning Problem”, Technical Report, Imperial College, The Management School, London, England, 1995. http://citeseer.ist.psu.edu/chu95genetic.html (erişim tarihi 13.11.2006)
[6] Day, P.R., Ryan, D.M., “Flight Attendant Rostering for Short-Haul Airline Operations”, Operations Research, 45, 649-661, 1997.
[7] Gamache, M., Soumis, F., Marquis, G., Desrosiers, J., “A Column Generation Approach For Large-Scale Air Crew Rostering Problems”, Operations Research, 47, 247-263, 1999.
[8] Guo Y., Mellouli T., Suhl L., Thiel M.P., “A Partially Integrated Airline Crew Scheduling Approach With Time-Dependent Crew Capacities and Multiple Home Bases”, European Journal of Operational Research, 171, 1169-1181, 2006.
[9] Güngör, İ., Eroğlu, A., “Küme Örtüleme Problemi ve Bir Uygulama”, Süleyman Demirel Üniversitesi İktisadi ve İdari Bilimler Fakültesi Dergisi, 2, 377-386, 1997.
[10] Hoffman, K.L., Padberg, M., “Solving Airline Crew Scheduling Problems by Branch and Cut”, Management Science, 39, 657-682, 1993.
[11] İpekçi Çetin, E., Kuruüzüm, A. ve Irmak, S., “Ekip Çizelgeleme Probleminin Küme Bölme Modeli ile Çözümü”, Havacılık ve Uzay Teknolojileri Dergisi, 3,4, 47-54, 2008.
Kerati, S., Moudani, W.E., Coligny, M.D. and Mora-Camino F., “A Heuristic Genetic Algorithm Approach for the Airline Crew Scheduling Problem”, Workshop on Multiple Objective Metaheuristics, Paris, 2002.
[12] Kohl N., Karisch S.E., “Airline Crew Rostering: Problem Types, Modeling, and Optimization”, Annals of Operations Research, 127, 223-257, 2004.
[13] MathWorks, Genetic Algorithm and Direct Search Toolbox User’s Guide, 2004.
[14] Moudani El. W., Cosenza C.A.N., Mora-Camino F., “An intelligent approach for solving the airline crew rostering problem”, Computer Systems and Applications, ACS/IEEE International Conference, 73-79, 2001.
[15] Özdamar K.,. “Paket Programlar ile İstatistiksel Veri Analizi”, Kaan Kitabevi, Eskişehir, 2004.
[16] Sohoni M.G., Johnson E.L., Bailey T.G. “Operational Airline Reserve Crew Planning”, Journal of Scheduling., 9, 203-221, 2006.
[17] Stojkovic, M., Soumis, F., Desrosiers, J., “The Operational Airline Crew Scheduling Problem”, Transportation Science, 32, 232-245, 1998.
[18] Şen, Z., “Genetik Algoritmalar ve En İyileme Yöntemleri, Su Vakfı Yayınları, İstanbul, 2004.
[19] Ulucan, A., Eryiğit, M., “Hava Taşımacılığı Planlamasında Yöneylem Araştırması Modellerinin Kullanımı”, Ankara Üniversitesi SBF Dergisi, 59, 227-248, 2004.
[20] Vance, P.H., Barnhart, C., Johnson, E.L., Nemhauser, G.L., “Airline Crew Scheduling: a New Formulation and Decomposition Algorithm”, Operations Research, 45, 188-200, 1997.
[21] Yan, S., Chang, J.C., “Airline Cockpit Crew Scheduling”, European Journal of Operational Research, 136, 501-511, 2002.
Published
2011-01-24
How to Cite
[1]
E. İpekçi Çetin, “THE USAGE OF GENETIC ALGORITHMS TO SOLVE SET PARTITIONING MODEL: CREW PAIRING APPLICATION”, JAST, vol. 5, no. 1, pp. 89-96, Jan. 2011.
Section
Articles