Ekip çizelgeleme probleminin küme bölme modeli ile çözümü

Havayolu taşımacılığında uçuş ekibi maliyetlerinin ekonomik olarak önemli bir paya sahip olması uzun yıllardan beri şirketlerle yöneylem araştırmacılarını ve matematik topluluklarını aynı amaç etrafında bir araya getirmektedir. Üretilen matematiksel modeller ve yazılan bilgisayar programlarındaki temel hedef ekip üyelerinin maliyetini minimize edecek çözümler üretmektir. Ekip planlamanın iki aşamasını oluşturan ve genellikle ayrı olarak ele alınan ekip eşleştirme ve ekip atama problemleri bu çalışmada bütünleşik bir yapıda ele alınmıştır. Çalışmada küme bölme modeli formunda ifade edilen ekip eşleştirme probleminin tamsayılı programlama ile çözümü MATLAB bilgisayar programından faydalanılarak gerçekleştirilmiştir. Uygulamanın ikinci kısmını oluşturan ve ekip eşleştirme sonuçlarının girdi olarak kullanıldığı ekip atama problemi yine küme bölme modeline dönüştürülmüş ve tamsayılı programlama yöntemiyle çözümü aranmıştır. Xpress-MP programı yardımıyla elde edilen sonuçlarla, uygulamanın yapıldığı havayolu şirketinin ekip planlama uzmanının gerçekleştirdiği atamalar karşılaştırılmıştır. Çalışmadan elde edilen atama planıyla maliyetler açısından tasarruflar sağlanabileceği görülmüştür.

The solution of crew scheduling problem with set partitioning model

Airline crew costs, becoming a major economical element, has been taking attention of both operation researchers and mathematic community and bringing them together with companies to work in cooperation for long years. The proposed mathematical models and computer programs have the aim of cost minimization of crew members. Crew pairing and crew assignment problems, which constitute the two phases of airline crew scheduling and are generally considered separate, are taken as a whole in this study. The airline crew pairing problem expressed in a set partitioning model is first solved by integer programming with MATLAB. In the second part of the application, the results of the crew pairing solutions are used as inputs for the crew assignment, again it’s converted to the set partitioning model and solutions are searched with integer programming. The solutions found by using Xpress-MP are compared with the crew assignment of the firm’s planning expert, where the study is executed. The solutions of the study propose that cost advantage can be obtained by using the assignment plan developed in this study.

___

  • [1] Ernst, A.T., Jiang, H., Krishnamoorthy, M. and Sier, D., “Staff Scheduling and Rostering: A Review of Applications”, Methods and Models, 153: 3-27, 2004.
  • [2] Sarucan, A., “Bir Raylı Ulaşım Sisteminde Personel Çizelgeleme Problemine Bütünleşik Yaklaşım”, Selçuk Üniversitesi Fen Bilimleri Enstitüsü, Yayınlanmamış Yüksek Lisans Tezi, 1999.
  • [3] Güngör, İ., “İşgücü Maliyetlerinin Minimizasyonu, Vardiya Planlaması, Modeller, Algoritmalar ve Uygulamalar”, Asil Yayın Dağıtım, 2005.
  • [4] İpekçi Çetin, E., Uçuş Ekibi Planlamada Genetik Algoritmalar Yönteminin Kullanılması, Akdeniz Üniversitesi Sosyal Bilimler Enstitüsü, Yayınlanmamış Doktora Tezi, 2008.
  • [5] Ulucan, A. ve Eryiğit, M., “Hava Taşımacılığı Planlamasında Yöneylem Araştırması Modellerinin Kullanımı”, Ankara Üniversitesi SBF Dergisi, 59(4): 227-248, 2004.
  • [6] Barnhart, C. and Shenoi, R.G., “An Approximate Model and Solution Approach for The Long-Haul Crew Pairing Problem”, Transportation Science, 32(3): 221-231, 1998.
  • [7] Stojkovic, M., Soumis, F. and Desrosiers, J. “The Operational Airline Crew Scheduling Problem”, Transportation Science, 32(3): 232-245, 1998.
  • [8] Day, P.R. and Ryan, D.M., “Flight Attendant Rostering for Short-Haul Airline Operations”, Operations Research, 45(5): 649-661, 1997.
  • [9] Şenöz, Ç. “Sivil Havacılık Sektöründeki Küçük İşletmeler İçin Filo Atama Ve Tayfa Eşleştirme Modellerinin Birleştirilerek Uygulanması”, Hacettepe Üniversitesi Sosyal Bilimler Enstitüsü, Yayınlanmamış Yüksek Lisans Tezi, 2005.
  • [10] 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.
  • [11] Moudani, El. W., Cosenza, C.A.N. and Mora- Camino, F., “An Intelligent Approach for Solving the Airline Crew Rostering Problem”, Computer Systems and Applications, ACS/IEEE International Conference, 2001.
  • [12] Gopalakrishnan, B. and Johnson, E.L., “Airline Crew Scheduling: State of The Art”, Annals of Operations Research, 140: 305-337, 2005.
  • [13] Lohatepanont, M. and Barnhart, C., “Airline Schedule Planning: Integrated Models and Algorithms for Schedule Design and Fleet Assignment”, Transportation Science, 38(1): 19-32, 2004.
  • [14] Gopalan, R. and Talluri, K.T., “Mathematical Models In Airline Schedule Planning: A Survey”, Annals of Operations Research, 76: 155-185, 1998.
  • [15] Gamache, M., Soumis, F., Marquis, G. and Desrosiers, J., “A Column Generation Approach For Large-Scale Air Crew Rostering Problems”, Operations Research, 47(2): 247-263, 1999.
  • [16] Chu, P.C. and 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)
  • [17] Güngör, İ. ve 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.