Buradasınız

GENETİK ALGORİTMALARIN KULLANIMIYLA KÜME BÖLME MODELİNİN ÇÖZÜLMESİ: EKİP EŞLEŞTİRME UYGULAMASI

THE USAGE OF GENETIC ALGORITHMS TO SOLVE SET PARTITIONING MODEL: CREW PAIRING APPLICATION

Journal Name:

Publication Year:

Keywords (Original Language):

Abstract (2. Language): 
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.
Abstract (Original Language): 
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.

REFERENCES

References: 

[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
Genetik Algoritmaların Kullanımıyla Küme Bölme Modelinin Çözülmesi: Ekip Eşleştirme Uygulaması
ÇETİN
96
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.

Thank you for copying data from http://www.arastirmax.com