Sütun oluşturma yaklaşımı ile bir havayolu ekip çizelgeleme uygulaması

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.

An application of airline crew scheduling by using a column generation approach

Crew scheduling problem is one of the hardest and most comprehensive problems encountered in airline planning. In crew scheduling problem, it is aimed to find the minimum costly set of pairings in that each flight leg is covered at least by one crew pairing. In this study, a column generation approach that is commonly used in crew scheduling literature in which variables are dynamically generated, is used to solve the problem. The master problem is formulated as a set covering problem while the subproblem is formulated as a shortest path problem. Initial pairings which are sufficient to obtain a feasible solution, are produced using a linear programming model. The master problem, sub-problem and the model used to generate initial pairings are encoded by GAMS optimization program in an integrated manner and this integrated model is solved iteratively. The algorithm is applied to a private airline company’s crew scheduling problem using real data and optimal crew schedules are obtained.

PDF

___

1. Gopalakrishnan, B., Johnson, E. L., “Airline Crew Scheduling: State-of-The-Art”, Annals of Operations Research, 140 (1): 305-337 (2005).
2. Yan, S. Y., Tu, Y. P., “A Network Model for Airline Cabin Crew Scheduling”, European Journal of Operational Research, 140 (3): 531- 540 (2002).
3. Emden-Weinert, T., Proksch, M., “Best Practice Simulated Annealing for The Airline CrewScheduling Problem”, Journal of Heuristics, 5(4): 419-436 (1999).
4. 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).
5. 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).
6. Kornilakis, H., Stamatopoulos, P., “Crew Pairing Optimization with Genetic Algorithms”, Lecture Notes in Artificial Intelligence, 2308: 109-120 (2002).
7. Özdemir, H. T., Mohan, C. K., “Flight Graph Based Genetic Algorithm for Crew Scheduling in Airlines”, Information Sciences, 133 (3-4): 165- 173 (2001).
8. Minoux, M., “Column Generation Techniques in Combinatorial Optimisation, A New Application to Crew-Pairing Problems”, Proceedings XXIVth AGIFORS Symposium, Strasbourg, France, (1984).
9. Desaulniers, G., Desrosiers, J., Dumas, Y., Solomon, M. M., Soumis, F., “Daily Aircraft Routing and Scheduling”, Management Science, 43(6): 841-855 (1997).
10. Klabjan, D., Johnson, E. L., Nemhauser, G. L., et al., “Airline Crew Scheduling with Regularity”, Transportation Science, 35 (4): 359-374 (2001).
11. Yan, S., Chang, J., “Airline Cocpit Crew Scheduling”, European Journal of Operational Research, 136: 501-511 (2002).
12. 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).