Aksaklıklara Karşı Dayanıklı Ekip Eşleme Problemi İçin Bir Dal-Ücret Algoritması

Abstract

Robust Airline Crew Pairing Problem is a proactive planning approach, which includes considering delays and disruptions that could happen in the operations. The main objective is to create crew pairings that are less prone to disruptions or easier to reschedule once disrupted. We model the problem as a Bi-Objective General Set Covering Problem to minimize the estimated propagated delay while at the same time maintaining a cost effective solution. We exploit historical information on disruptions and separate dataset into two subsets. We optimize the expected propagated delays based on the first portion of the dataset, and limit the price of robustness using ε-constraint method. We develop a branch-and-price based solution algorithm that column generation is applied at each node of the branch-and-bound tree. A field-collected actual schedule dataset for a small-scale Turkish airline which operates short-haul domestic flights on a hub-and-spoke network, is used for the experiments in evaluating the model and the proposed solution method. We also conduct simulation experiments to verify optimization results and to determine the robustness of the obtained solutions, where the second part of the historical data is used as an input. The computational results obtained are encouraging, which show that on average the proposed methodology attains optimal solutions for the obtained dataset and solution times are reasonable enough to conduct several different scenarios for a final decision.

Keywords

• Robust Crew Pairing Optimization, Branch-and-Price Algorithm, Column Generation, Robustness, Delay Propagation.

A Branch-and-Price Algorithm for the Robust Airline Crew Pairing Problem

Abstract

Aksaklıklara Karşı Dayanıklı Ekip Eşleme Problemi, klasik ekip eşleme probleminin çizelgelerin uygulanması safhasında meydana gelebilecek gecikme ve aksaklıkları dikkate alarak yapılan proaktif bir planlama yaklaşımı ile ele alınmış halidir. Yaklaşımda esas amaç, aksaklıklara daha az maruz kalabilecek veya aksaklıklara maruz kalındığı zaman tekrar çizelgelenmesi daha kolay ekip eşlemelerinin üretilmesidir. Söz konusu problem, yayılan gecikmelerin beklenen değerinin enazlanması ve aynı zamanda maliyet-etkin bir çözümün muhafaza edilmesini amaçlayan Çift-Amaçlı Genel Küme Kapsama modeli olarak formüle edilmiştir. Çalışmada, aksaklık bilgilerini içeren geçmiş veri setlerinin kullanılması ve bu veri setinin iki alt parçaya ayrılması önerilmiştir. Veri setinin birinci parçasının yayılan gecikmelerin beklenen değerinin eniyilenmesinde kullanılması öngörülmüş ve dayanıklılığın bedeli, ε-yöntemi kullanılarak sınırlandırılmaya çalışılmıştır. Çözüm yaklaşımı olarak dal-sınır ağacının her bir düğümünde sütun oluşturma yöntemi uygulanan Dal-Ücret algoritması esaslı bir algoritma geliştirilmiştir. Önerilen model ve çözüm yaklaşımının değerlendirilmesi için yapılan deneylerde; Türkiye’de yerleşik, ana dağıtım üssü-kenar üs uçuş ağ yapısını uygulayan, küçük ölçekli bir havayolu şirketine ait gerçek veriler kullanılmıştır. Ayrıca, geçmiş veri setinin ikinci parçası girdi olarak kullanılarak elde edilen eniyileme sonuçlarının geçerlemesi ve çözümlerin dayanıklılığının Yazışma Adresi: Kara Harp Okulu, Savunma Bilimleri Enstitüsü, Harekât Araştırması ABD, Ankara, [e-mail], Gazi Üniversitesi, Mühendislik Fakültesi, Endüstri Müh. Böl., Ankara.belirlenmesi için çeşitli benzetim deneyleri yapılmıştır. Gerçek veri seti kullanılarak elde edilen deneysel sonuçlar umut verici olup önerilen yaklaşımın ortalamada eniyi sonuçlar üretebildiği ve son karar öncesi birçok değişik senaryonun değerlendirilmesine imkân verecek ölçüde, kabul edilebilir çözüm zamanlarında çözümlerin elde edilebildiği gözlenmiştir.

Keywords

• Dayanıklı Ekip Eşleme Eniyilemesi, Dal-Ücret Algoritması, Sütun Oluşturma Yöntemi, Dayanıklılık, Gecikme Yayılımı.

References

1. Achterberg, T. (2009). SCIP: solving constraint integer programs. Mathematical Programming Computation, 1(1), 1-41.
2. AhmadBeygi, S., Cohn, A., Guan, Y., & Belobaba, P. (2008). Analysis of the potential for delay propagation in passenger airline networks. Journal of Air Transport Management, 14(5), 221-236.
3. Airlines for America, A. (2013, December). Annual and Per-Minute Cost of Delays to U.S. Airlines. Retrieved from Airlines for America (A4A): http://www.airlines.org/Pages/Annual-and-Per-Minute-Cost-of-Delays-toU.S.-Airlines.aspx
4. Anbil, R., Forrest, J. J., & Pulleyblank, W. R. (1998). Column generation and the airline crew pairing problem. Documenta Mathematica, 3, 677-686.
5. Barnhart, C., & Shenoi, R. G. (1998). An approximate model and solution approach for the long-haul crew pairing problem. Transportation Science, 32(3), 221-231.
6. Barnhart, C., Cohn, A. M., Johnson, E. L., Klabjan, D., Nemhauser, G. L., & Vance, P. H. (2003). Airline crew scheduling. In Handbook of transportation science (pp. 517-560). Springer.
7. Barnhart, C., Johnson, E. L., Nemhauser, G. L., Savelsbergh, M. W., & Vance, P. H. (1998). Branch-and-price: Column generation for solving huge integer programs. Operations research, 46(3), 316-329.
8. Chiraphadhanakul, V., & Barnhart, C. (2011). Robust flight schedules through slack re-allocation. EURO Journal on Transportation and Logistics, 1-30. Cook, A., & Tanner, G. (2011). Modelling the airline costs of delay propagation.

9. Desaulniers, G. (2010). Branch-and-price-and-cut for the split-delivery vehicle routing problem with time windows. Operations research, 58(1), 179-192. Desaulniers, G., Desrosiers, J., & Solomon, M. M. (2005). Column generation (Vol. 5). Springer.
10. Desaulniers, G., Desrosiers, J., Dumas, Y., Marc, S., Rioux, B., Solomon, M. M., et al. (1997). Crew pairing at air France. European Journal of Operational Research, 97(2), 245-259.
11. Ehrgott, M., & Ryan, D. M. (2002). Constructing robust crew schedules with bicriteria optimization. Journal of Multi-Criteria Decision Analysis, 11(3), 139-1
12. Guest, T. (2007). A Matter of Time: Air Traffic Delay in Europe Vol.2. Tech. rep., EUROCONTROL, Brussels, Belgium.
13. Hoffman, K. L., & Padberg, M. (1993). Solving airline crew scheduling problems by branch-and-cut. Management Science, 39(6), 657-682.
14. Jetzki, M. (2009). The propagation of air transport delays in Europe. Master's thesis, RWTH Aachen University, Airport and Air Transportation Research.
15. Lan, S., Clarke, J.-P., & Barnhart, C. (2006). Planning for robust airline operations: Optimizing aircraft routings and flight departure times to minimize passenger disruptions. Transportation Science, 40(1), 15-28.
16. Lee, L. H., Huang, H. C., Lee, C., Chew, E. P., Jaruphongsa, W., Yong, Y. Y., et al. (2003). Simulation of airports/aviation systems: discrete event simulation model for airline operations: SIMAIR. Proceedings of the 35th conference on Winter simulation: driving innovation, (pp. 1656-1662).
17. Lohatepanont, M., & Barnhart, C. (2004). Airline schedule planning: Integrated models and algorithms for schedule design and fleet assignment. Transportation Science, 38(1), 19-32.
18. Lucian, I., & Natalia, K. (2011). Increasing Flexibility of Airline Crew Schedules. Procedia - Social and Behavioral Sciences, 20(The State of the Art in the European Quantitative Oriented Transportation and Logistics Research 14th Euro Working Group on Transportation & 26th Mini Euro Conference & 1st European Scientific Conference on Air Transport), 101910
19. Marla, L., & Barnhart, C. (2010). Robust optimization: Lessons learned from aircraft routing. Tech. rep., working paper.
20. McShan, S., & Windle, R. (1989). The implications of hub-and-spoke routing for airline costs and competitiveness. Logistics and Transportation Review, 25(3).
21. Ryan, D., & Falkner, J. (1988). On the integer properties of scheduling set partitioning models. European journal of operational research, 35(3), 4424
22. Savelsbergh, M. (1997). A branch-and-price algorithm for the generalized assignment problem. Operations Research, 45(6), 831-841.
23. Schaefer, A. J., Johnson, E. L., Kleywegt, A. J., & Nemhauser, G. L. (2005). Airline Crew Scheduling Under Uncertainty. Transportation Science, 39(3), 340-348.
24. Shebalov, S., & Klabjan, D. (2006). Robust Airline Crew Pairing: Move-up Crews. Transportation Science, 40(3), 300-312.
25. Tam, B., & Ehrgott, M. (2007). Multi-objective Approaches to the Unit Crewing Problem in Airline Crew Scheduling. Report University of Auckland School of Engineering 660.
26. Tam, B., Ehrgott, M., Ryan, D., & Zakeri, G. (2011). A comparison of stochastic programming and bi-objective optimisation approaches to robust airline crew scheduling. OR Spectrum, 33(1), 49-75.
27. Tam, M. B. (2011). Optimisation approaches for robust airline crew scheduling. PhD Thesis-University of Auckland.
28. Vance, P. H., Barnhart, C., Johnson, E. L., & Nemhauser, G. L. (1997). Airline crew scheduling: A new formulation and decomposition algorithm.
29. Operations Research, 45(2), 188-200. Wu, C.-L., & Caves, R. E. (2003). The punctuality performance of aircraft rotations in a network of airports. Transportation Planning and Technology, 26(5), 417-436.
30. Yen, J. W., & Birge, J. R. (2006). A stochastic programming approach to the airline crew scheduling problem. Transportation Science, 40(1), 3-14.