Uçuş ekip planlamada genetik algoritmalar yönteminin kullanılması

Abstract

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. Özellikle büyük havayolu şirketlerinde yapılan çok ufak iyileştirmelerin bile önemli büyüklükte tasarruflar sağladığı görülmüştür. Problemin karmaşıklığı ve büyüklüğü nedeniyle uygulamaların zamanla kendini sezgisel tekniklerle elde edilen çözümlere bıraktıkları görülmüştür. Bu noktadan hareketle bu çalışmada, havayolu uçuş ekibi planlama problemine uygulamada en çok kullanılan sezgisel yöntemlerden biri olan genetik algoritmalarla çözüm arayışında bulunulmuştur.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 ö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 yada 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.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üş, genetik algoritmalar ve tamsayılı programlama yöntemleriyle çözümleri aranmıştır. Değişken sayısındaki büyüklük problemi karışık ve çözümü zor bir hale getirmiştir. 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. Tezden elde edilen atama planıyla maliyetler açısından tasarruflar sağlayabileceği görülmüştür.

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. Especially for the large-scale airline companies, any small improvement provides important savings. Because of the complexity of the problem and its large scale, the usage of heuristic solving methods become widespread. Starting from this point, genetic algorithms, one of the mostly used heuristic method, is used in airline crew scheduling problem.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 and then it?s solved by genetic algorithms (GA) with MATLAB. The GA solution is tested by different reproduction methods, crossover and population sizes. 120 trials 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 near-optimal solution, but also provides a choice flexibility to the decision maker by suggesting alternative solutions.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 GA and integer programming. The largeness of the variable number makes the problem complicated and hard to solve. 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.