Genetik algoritmaların kullanımıyla küme bölme modelinin çözülmesi: ekip eşleştirme uygulaması

Bu çalışmada ekip planlama problemi içerisinde yer alan uçuş ekibi eşleştirme problemi üzerinde durulmaktadır. Çalışmada küme bölme modeli şeklinde ifade edilen ekip eşleştirme probleminin öncelikle tamsayılı programlama ile daha sonra genetik algoritmalarla çözümü MATLAB bilgisayar programından faydalanılarak gerçekleştirilmiştir. Genetik algoritmalarla çözüm, seçim yönteminde, çaprazlama yönteminde ve popülasyon büyüklüğünde yapılan değişikliklerle test edilmiştir. Genetik algoritma yönteminin farklı parametrelerinin kullanıldığı 120 deneme yapılarak küme bölme modeli üzerinde genetik algoritmaların performansı değerlendirilmiştir. Son olarak ekip eşleştirme problemi üzerinde tamsayılı programlama ve genetik algoritma yönteminin kullanılmasıyla elde edilen sonuçların karşılaştırması yapılmıştır. Genetik algoritmaların optimum ya da optimuma yakın sonuçlar vermesinin yanında karar vericiye farklı alternatif çözümler sunarak bunlardan birini tercih etme esnekliği sağladığı görülmüştür.

The usage of genetic algorithms to solve set partitioning model: crew pairing application

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.

___

  • [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.
Havacılık ve Uzay Teknolojileri Dergisi-Cover
  • ISSN: 1304-0448
  • Yayın Aralığı: Yılda 2 Sayı
  • Başlangıç: 2003
  • Yayıncı: Dr. Öğr. Üyesi Fatma Kutlu Gündoğdu