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

İPEKÇİ ÇETİN, Emre

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

Emre İpekçi ÇETİN (Akdeniz Üniversitesi, Antalya, Türkiye)

Havacılık ve Uzay Teknolojileri Dergisi

3 0

Yıl: 2011 Cilt: 5 Sayı: 1 Sayfa Aralığı: 89 - 96 Metin Dili: Türkçe İndeks Tarihi: 29-07-2022

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

Öz:

Bu çalışmada ekip planlama problemi içerisinde yer alan uçuş ekibi eşleştirme problemi üzerindedurulmaktadır. Çalışmada küme bölme modeli şeklinde ifade edilen ekip eşleştirme probleminin öncelikletamsayılı programlama ile daha sonra genetik algoritmalarla çözümü MATLAB bilgisayar programındanfaydalanılarak gerçekleştirilmiştir. Genetik algoritmalarla çözüm, seçim yönteminde, çaprazlama yönteminde vepopü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ınperformansı değerlendirilmiştir. Son olarak ekip eşleştirme problemi üzerinde tamsayılı programlama ve genetikalgoritma yönteminin kullanılmasıyla elde edilen sonuçların karşılaştırması yapılmıştır. Genetik algoritmalarınoptimum ya da optimuma yakın sonuçlar vermesinin yanında karar vericiye farklı alternatif çözümler sunarakbunlardan birini tercih etme esnekliği sağladığı görülmüştür.

Anahtar Kelime:

Konular: Mühendislik, Elektrik ve Elektronik Bilgisayar Bilimleri, Yazılım Mühendisliği Bilgisayar Bilimleri, Bilgi Sistemleri

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

Öz:

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

Anahtar Kelime:

Konular: Mühendislik, Elektrik ve Elektronik Bilgisayar Bilimleri, Yazılım Mühendisliği Bilgisayar Bilimleri, Bilgi Sistemleri

Belge Türü: Makale Makale Türü: Araştırma Makalesi Erişim Türü: Erişime Açık

[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.

APA	İPEKÇİ ÇETİN E (2011). Genetik algoritmaların kullanımıyla küme bölme modelinin çözülmesi: ekip eşleştirme uygulaması. , 89 - 96.
Chicago	İPEKÇİ ÇETİN Emre Genetik algoritmaların kullanımıyla küme bölme modelinin çözülmesi: ekip eşleştirme uygulaması. (2011): 89 - 96.
MLA	İPEKÇİ ÇETİN Emre Genetik algoritmaların kullanımıyla küme bölme modelinin çözülmesi: ekip eşleştirme uygulaması. , 2011, ss.89 - 96.
AMA	İPEKÇİ ÇETİN E Genetik algoritmaların kullanımıyla küme bölme modelinin çözülmesi: ekip eşleştirme uygulaması. . 2011; 89 - 96.
Vancouver	İPEKÇİ ÇETİN E Genetik algoritmaların kullanımıyla küme bölme modelinin çözülmesi: ekip eşleştirme uygulaması. . 2011; 89 - 96.
IEEE	İPEKÇİ ÇETİN E "Genetik algoritmaların kullanımıyla küme bölme modelinin çözülmesi: ekip eşleştirme uygulaması." , ss.89 - 96, 2011.
ISNAD	İPEKÇİ ÇETİN, Emre. "Genetik algoritmaların kullanımıyla küme bölme modelinin çözülmesi: ekip eşleştirme uygulaması". (2011), 89-96.

APA	İPEKÇİ ÇETİN E (2011). Genetik algoritmaların kullanımıyla küme bölme modelinin çözülmesi: ekip eşleştirme uygulaması. Havacılık ve Uzay Teknolojileri Dergisi, 5(1), 89 - 96.
Chicago	İPEKÇİ ÇETİN Emre Genetik algoritmaların kullanımıyla küme bölme modelinin çözülmesi: ekip eşleştirme uygulaması. Havacılık ve Uzay Teknolojileri Dergisi 5, no.1 (2011): 89 - 96.
MLA	İPEKÇİ ÇETİN Emre Genetik algoritmaların kullanımıyla küme bölme modelinin çözülmesi: ekip eşleştirme uygulaması. Havacılık ve Uzay Teknolojileri Dergisi, vol.5, no.1, 2011, ss.89 - 96.
AMA	İPEKÇİ ÇETİN E Genetik algoritmaların kullanımıyla küme bölme modelinin çözülmesi: ekip eşleştirme uygulaması. Havacılık ve Uzay Teknolojileri Dergisi. 2011; 5(1): 89 - 96.
Vancouver	İPEKÇİ ÇETİN E Genetik algoritmaların kullanımıyla küme bölme modelinin çözülmesi: ekip eşleştirme uygulaması. Havacılık ve Uzay Teknolojileri Dergisi. 2011; 5(1): 89 - 96.
IEEE	İPEKÇİ ÇETİN E "Genetik algoritmaların kullanımıyla küme bölme modelinin çözülmesi: ekip eşleştirme uygulaması." Havacılık ve Uzay Teknolojileri Dergisi, 5, ss.89 - 96, 2011.
ISNAD	İPEKÇİ ÇETİN, Emre. "Genetik algoritmaların kullanımıyla küme bölme modelinin çözülmesi: ekip eşleştirme uygulaması". Havacılık ve Uzay Teknolojileri Dergisi 5/1 (2011), 89-96.