SÜTUN OLUŞTURMA YAKLAŞIMI İLE BİR HAVAYOLU EKİP ÇİZELGELEME UYGULAMASI

Ekip çizelgeleme problemi, hava yolu planlamasında karşılaşılan zor ve kapsamlı problemlerden biridir. Ekip çizelgeleme probleminde, her uçuş seferinin en az bir ekip eşleştirmesi tarafından kapsandığı minimum maliyetli eşleştirmeler kümesi bulunmaya çalışılır. Bu çalışmada, ekip çizelgeleme probleminin çözümünde literatürde sıkça kullanılan, değişkenlerin dinamik olarak üretildiği bir sütun oluşturma algoritması kullanılmıştır. Ana problem küme kaplama problemi, alt problem ise en kısa yol problemi olarak formüle edilmiştir. Uygun bir çözüm vermeye yetecek sayıda başlangıç eşleştirmesi bir doğrusal programlama modeli kullanılarak oluşturulmuştur. Ana problem, alt problem ve başlangıç eşleştirmelerini oluşturmada kullanılan model bütünleşik olarak GAMS optimizasyon programında kodlanmış ve bu bütünleşik model iteratif olarak çözülmüştür. Algoritma özel bir havayolu şirketinden alınan verilere uygulanmış ve optimal ekip çizelgeleri oluşturulmuştur.

Anahtar Kelimeler:

Havayolu ekip çizelgeleme, ekip eşleştirme problemi, küme kaplama problemi, sütun oluşturma algoritması.

PDF

___

Gopalakrishnan, B., Johnson, E. L., “Airline Crew Scheduling: State-of-The-Art”, Annals of Operations Research, 140 (1): 305-337 (2005).
Yan, S. Y., Tu, Y. P., “A Network Model for Airline Cabin Crew Scheduling”, European Journal of Operational Research, 140 (3): 531-540 (2002).
Emden-Weinert, T., Proksch, M., “Best Practice Simulated Annealing for The Airline Crew Scheduling Problem”, Journal of Heuristics, 5 (4): 419-436 (1999).
Cavique, I., Rego, C., Themido, I., “Subgraph Ejection Chains and Tabu Search for The Crew Scheduling Problem”, Journal of The Operational Research Society, 50 (6): 608-616
(1999).
Vance, P.H., Barnhart, C, Johnson, E.L., Et Al., “Airline Crew Scheduling: A New Formulation and Decomposition Algorithm”, Operations Research, 45 (2): 188-200 (1997).
Kornilakis, H., Stamatopoulos, P., “Crew Pairing Optimization with Genetic Algorithms”, Lecture Notes in Artificial Intelligence, 2308: 109-120 (2002).
Özdemir, H. T., Mohan, C. K., “Flight Graph Based Genetic Algorithm for Crew Scheduling in Airlines”, Information Sciences, 133 (3-4): 165-173 (2001).
Minoux, M., “Column Generation Techniques in Combinatorial Optimisation, A New Application to Crew-Pairing Problems”, Proceedings XXIVth AGIFORS Symposium, Strasbourg, France, (1984).
Desaulniers, G., Desrosiers, J., Dumas, Y., Solomon, M. M., Soumis, F., “Daily Aircraft Routing and Scheduling”, Management Science, 43(6): 841-855 (1997).
Klabjan, D., Johnson, E. L., Nemhauser, G. L., et al., “Airline Crew Scheduling with Regularity”, Transportation Science, 35 (4): 359-374 (2001).
Yan, S., Chang, J., “Airline Cocpit Crew Scheduling”, European Journal of Operational Research, 136: 501-511 (2002).
Cordeau, J.F., Stojkovic, G., Soumis, F., Et Al., “Benders Decomposition for Simultaneous Aircraft Routing and Crew Scheduling”, Transportation Science, 35 (4): 375-388 (2001).