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

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

Özet

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.

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.