Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Solving a large-scale integrated fleet assignment and crew pairing problem

  • Original Paper
  • Published:
Annals of Operations Research Aims and scope Submit manuscript

Abstract

Airline schedule planning problems are typically decomposed into smaller problems, which are solved in a sequential manner, due to the complexity of the overall problems. This results in suboptimal solutions as well as feasibility issues in the consecutive phases. In this study, we address the integrated fleet assignment and crew pairing problem (IFACPP) of a European Airline. The specific network and cost structures allow us to develop novel approaches to this integrated problem. We propose an optimization-driven algorithm that can efficiently handle large scale instances of the IFACPP. We perform a computational study on real-world monthly flight schedules to test the performance of our solution method. Based on the results on instances with up to 27,500 flight legs, we show that our algorithm provides solutions with significant cost savings over the sequential approach.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2

Similar content being viewed by others

References

  • Abara, J. (1989). Applying integer linear programming to the fleet assignment problem. Interfaces, 19(4), 20–28.

    Article  Google Scholar 

  • Ahuja, R. K., Goodstein, J., Mukherjee, A., Orlin, J. B., & Sharma, D. (2007). A very large-scale neighborhood search algorithm for the combined through-fleet-assignment model. INFORMS Journal on Computing, 19(3), 416–428.

    Article  Google Scholar 

  • Anbil, R., Gelman, E., Patty, B., & Tanga, R. (1991). Recent advances in crew-pairing optimization at american airlines. Interfaces, 21, 62–74.

    Article  Google Scholar 

  • Arabeyre, J. P., Fearnley, J., Steiger, F. C., & Teather, W. (1969). The airline crew scheduling problem: A survey. Transportation Science, 3(2), 140–163.

    Article  Google Scholar 

  • Atasoy, B., Salani, M., & Bierlaire, M. (2014). An integrated airline scheduling, fleeting, and pricing model for a monopolized market. Computer-Aided Civil and Infrastructure Engineering, 29(2), 76–90. ISSN 10939687.

  • Aydemir-Karadag, A., Dengiz, B., & Bolat, A. (2013). Crew pairing optimization based on hybrid approaches. Computers and Industrial Engineering, 65, 87–96.

    Article  Google Scholar 

  • Azadeh, A., Asadipour, G., Eivazy, H., & Nazari-Shirkouhi, S. (2012). A unique hybrid particle swarm optimisation algorithm for simulation and improvement of crew scheduling problem. International Journal of Operational Research, 13(4), 406–422.

    Article  Google Scholar 

  • Azadeh, A., Farahani, M. H., Eivazy, H., Nazari-Shirkouhi, S., & Asadipour, G. (2013). A hybrid meta-heuristic algorithm for optimization of crew scheduling. Applied Soft Computing, 13, 158–164.

    Article  Google Scholar 

  • Barnhart, C., Johnson, E., Anbil, R., & Hatay, L. (1994). A column generation technique for the long-haul crew assignment problem. In T. Ciriano & R. Leachman (Eds.), Optimization in Industry: Volume “II’ (7-22 ed.). London: Wiley.

    Google Scholar 

  • Barnhart, C., Boland, N. L., Clarke, L. W., Johnson, E. L., Nemhauser, G. L., & Shenoi, R. G. (1998a). Flight string models for aircraft fleeting and routing. Transportation Science, 32(3), 208–220.

    Article  Google Scholar 

  • Barnhart, C., Johnson, E. L., Nemhauser, G. L., Savelsbergh, M. W. P., & Vance, P. H. (1998b). Branch-and-price: Column generation for solving huge integer programs. Operations Research, 46(3), 316–329.

    Article  Google Scholar 

  • Barnhart, C., Lu, F., & Shenoi, R. (1998c). Integrated airlineschedule planning. In: G. Yu (ed.), In: Operations Research in the airline industry, vol. 9 of international series in operations research and management science, pp. 384–403. Springer, Berlin

  • Barnhart, C., Kniker, T. S., & Lohatepanont, M. (2002). Itinerary-based airline fleet assignment. Transportation Science, 36(2), 199–217.

    Article  Google Scholar 

  • Barnhart, C., Belobaba, P., & Odoni, A. R. (2003a). Applications of operations research in the air transport industry. Transportation Science, 37(4), 368–391.

    Article  Google Scholar 

  • Barnhart, C., Cohn, A. M., Johnson, E. J., Klabjan, D., Nemhauser, G. L., & Vance, P. H. (2003b). Airline crew scheduling. In R. W. Hall (Ed.), Handbook of transportation science (2nd ed.). Norwell: Kluwer Academic Publishers.

    Google Scholar 

  • Bélanger, N., Desaulniers, G., Soumis, F., Desrosiers, J., & Lavigne, J. (2006). Weekly airline fleet assignment with homogeneity. Transportation Research Part B: Methodological, 40(4), 306–318.

    Article  Google Scholar 

  • Berge, M. E., & Hopperstad, C. A. (1993). Demand driven dispatch: A method for dynamic aircraft capacity assignment, models and algorithms. Operations Research, 41(1), 153–168.

    Article  Google Scholar 

  • Butchers, E. R., Day, P. R., Goldie, A. P., Miller, S., Meyer, J. A., Ryan, D. M., et al. (2001). Optimized crew scheduling at Air New Zealand. Interfaces, 31(1), 30–56.

    Article  Google Scholar 

  • Cavique, L., Rego, C., & Themido, I. (1999). Subgraph ejection chains and tabu search for the crew scheduling problem. Journal of the Operational Research Society, 50(6), 608–616.

    Article  Google Scholar 

  • Chen, C.-H., Liu, T.-K., & Chou, J.-H. (2013). Integrated short-haul airline crew scheduling using multiobjective optimization genetic algorithms. IEEE Transactions On Systems, Man, and Cybernetics: Systems, 43(5), 1077–1090.

    Article  Google Scholar 

  • Clarke, L. W., Hane, C. A., Johnson, E. L., & Nemhauser, G. L. (1996). Maintenance and crew considerations in fleet assignment. Transportation Science, 30(3), 249–260.

    Article  Google Scholar 

  • Cohn, A. M., & Barnhart, C. (2003). Improving crew scheduling by incorporating key maintenance routing decisions. Operations Research, 51(3), 387–396.

    Article  Google Scholar 

  • Cordeau, J., Goran, S., Soumis, F., & Desrosiers, J. (2001). Benders decomposition for simultaneous aircraft routing and crew scheduling. Transportation Science, 35(4), 375–388.

    Article  Google Scholar 

  • Daskin, M. S., & Panayotopoulos, N. D. (1989). A lagrangian relaxation approach to assigning aircraft to routes in hub and spoke networks. Transportation Science, 23(2), 91–99.

    Article  Google Scholar 

  • Deng, G.-F., & Lin, W.-T. (2011). Ant colony optimization-based algorithm for airline crew scheduling problem. Expert Systems with Applications, 38(5), 5787–5793.

    Article  Google Scholar 

  • Desaulniers, G., Desrosiers, J., Dumas, Y., Solomon, M. M., & Soumis, F. (1997). Daily aircraft routing and scheduling. Management Science, 43(6), 841–855.

    Article  Google Scholar 

  • Desrosiers, J., Gamache, M., Soumis, F., & Desaulniers, G. (1998). Crew scheduling in air transportation. In T. Crainic & G. Laporte (Eds.), Fleet Management and Logistics. Norwell: Kluwer Academic Publishers.

    Google Scholar 

  • Dück, V., Wesselmann, F., & Suhl, L. (2011). Implementing a branch and price and cut method for the airline crew pairing optimization problem. Public Transport, 3, 43–64.

    Article  Google Scholar 

  • Emden-Weinert, T., & Proksch, M. (1999). Best practice simulated annealing for the airline crew scheduling problem. Journal of Heuristics, 5, 419–436.

    Article  Google Scholar 

  • Erdogan, G., Haouari, M., Ormeci Matoglu, M., & Ozener, O. O. (2015). Solving a large-scale crew pairing problem. Journal of Operational Research Society, 66, 1742–1754.

    Article  Google Scholar 

  • Gao, C., Johnson, E., & Smith, B. (2009). Integrated airline fleet and crew robust planning. Transportation Science, 43(1), 2–16.

    Article  Google Scholar 

  • Gershkoff, I. (1989). Optimizing flight crew schedules. Interfaces, 19, 29–43.

    Article  Google Scholar 

  • Gopalakrishnan, B., & Johnson, E. (2005). Airline crew scheduling: State-of-the-art. Annals of Operations Research, 140, 305–337.

    Article  Google Scholar 

  • Gu, Z., Johnson, E. L., Nemhauser, G. L., & Yinhua, W. (1994). Some properties of the fleet assignment problem. Operations Research Letters, 15(2), 59–71.

    Article  Google Scholar 

  • Hane, C. A., Barnhart, C., Johnson, E. L., Marsten, R. E., Nemhauser, G. L., & Sigismondi, G. (1995). The fleet assignment problem: Solving a large-scale integer program. Mathematical Programming, 70(1–3), 211–232.

    Google Scholar 

  • Haouari, M., Sherali, H. D., Mansour, F. Zl, & Aissaoui, N. (2011). Exact approaches for integrated aircraft fleeting and routing at Tunisair. Computational Optimization and Applications, 49(2), 213–239.

    Article  Google Scholar 

  • Kasirzadeh, A., Saddoune, M., & Soumis, F. (2015). Airline crew scheduling: Models, algorithms, and data sets. EURO Journal on Transportation and Logistics. doi:10.1007/s13676-015-0080-x.

  • Klabjan, D., Johnson, E. L., Nemhauser, G. L., Gelman, E., & Ramaswamy, S. (2002). Airline crew scheduling with time windows and plane-count constraints. Transportation Science, 36(3), 337–348.

    Article  Google Scholar 

  • Levine, D. (1996). Application of a hybrid genetic algorithm to airline crew scheduling. Computers and Operations Research, 23(6), 547–558.

    Article  Google Scholar 

  • Lohatepanont, M., & Barnhart, C. (2004). Airline schedule planning: Integrated models and algorithms for schedule design and fleet assignment. Transportation Science, 38(1), 19–32. ISSN 00411655.

  • Mercier, A., & Soumis, F. (2007). An integrated aircraft routing, crew scheduling and flight retiming model. Computers and Operations Research, 34(8), 2251–2265. ISSN 0305-0548.

  • Mercier, A., Cordeau, J., & Soumisa, F. (2005). A computational study of Benders decomposition for the integrated aircraft routing and crew scheduling problem. Computers and Operations Research, 32(6), 1451–1476. ISSN 0305-0548.

  • Ozdemir, H. T., & Mohan, C. K. (2001). Flight graph based genetic algorithm for crew scheduling in airlines. Information Sciences, 133(34), 165–173.

    Article  Google Scholar 

  • Paleologo, G., & Snowdon, J. L. (2007). Airline optimization. In: A. Ravi Ravindran (Ed.), Operations Research and Management Science Handbook, chapter 20 (2nd ed., pp. 1–31). London: CRC Press.

  • Panayiotis, A., Sanders, P., Takkula, T., & Wedelin, D. (2000). Parallel integer optimization for crew scheduling. Annals of Operations Research, 99(1–4), 141–166.

    Google Scholar 

  • Papadakos, N. (2009). Integrated airline scheduling. Computers and Operations Research, 36(1), 176–195. ISSN 0305-0548.

  • Rexing, B., Barnhart, C., Kniker, T., Jarrah, A., & Krishnamurthy, N. (2000). Airline fleet assignment with time windows. Transportation Science, 34(1), 1–20.

    Article  Google Scholar 

  • Rushmeier, R. A., & Kontogiorgis, S. A. (1997). Advances in the optimization of airline fleet assignment. Transportation Science, 31(2), 159–169.

    Article  Google Scholar 

  • Ryan, D. M. (1992). The solution of massive generalized set partitioning problems in aircrew rostering. The Journal of the Operational Research Society, 43(5), 459–467.

  • Saddoune, M., Desaulniers, G., & Soumis, F. (2013). Aircrew pairings with possible repetitions of the same flight number. Computers and Operations Research, 40(3), 805–814.

    Article  Google Scholar 

  • Sandhu, R., & Klabjan, D. (2007). Integrated airline fleeting and crew-pairing decisions. Operations Research, 55(3), 439–456.

    Article  Google Scholar 

  • Sherali, H. D., Bish, E. K., & Zhu, X. (2006). Airline fleet assignment concepts, models, and algorithms. European Journal of Operational Research, 172(1), 1–30.

    Article  Google Scholar 

  • Sherali, H. D., Bae, K., & Haouari, M. (2010). Integrated airline schedule design and fleet assignment: Polyhedral analysis and Benders’ decomposition approach. INFORMS Journal on Computing, 22(4), 500–513.

  • Sherali, H. D., Bae, K., & Haouari, M. (2013). A benders decomposition approach for an integrated airline schedule design and fleet assignment problem with flight retiming, schedule balance, and demand recapture. Annals of Operations Research, 210(1), 213–244. ISSN 0254-5330.

  • Subramanian, R. A., Scheff, R. P., Quillinan, J. D., Wiper, D. S., & Marsten, R. E. (1994). Coldstart: Fleet assignment at delta air lines. Interfaces, 24(1), 104–120.

    Article  Google Scholar 

  • Subramanian, S., & Sherali, H. D. (2008). An effective deflected subgradient optimization scheme for implementing column generation for large-scale airline crew scheduling problems. INFORMS Journal on Computing, 20(4), 565–578. ISSN 10919856.

  • Vance, P. H., Barnhart, C., Johnson, E. L., & Nemhauser, G. L. (1997). Airline crew scheduling: A new formulation and decomposition algorithm. Operations Research, 45, 183–200.

    Article  Google Scholar 

  • Wang, D., Shebalov, S., & Klabjan, D. (2013). Attractiveness-based airline network models with embedded spill and recapture. Journal of Airline and Airport Management, 4(1), 1–25.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Engineering, Ozyegin University, Istanbul, Turkey

    Okan Örsan Özener & Hasan Sözer

  2. Peter T Paul College of Business and Economics, University of New Hampshire, Durham, NH, USA

    Melda Örmeci Matoğlu

  3. School of Management, University of Bath, Bath, BA2 7AY, UK

    Güneş Erdoğan

  4. Department of Mechanical and Industrial Engineering, College of Engineering, Qatar University, Doha, Qatar

    Mohamed Haouari

Authors
  1. Okan Örsan Özener
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Melda Örmeci Matoğlu
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Güneş Erdoğan
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Mohamed Haouari
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Hasan Sözer
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Melda Örmeci Matoğlu.

Additional information

This project is funded in part by TUBITAK Grant 110M308.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Özener, O.Ö., Örmeci Matoğlu, M., Erdoğan, G. et al. Solving a large-scale integrated fleet assignment and crew pairing problem. Ann Oper Res 253, 477–500 (2017). https://doi.org/10.1007/s10479-016-2319-9

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10479-016-2319-9

Keywords

Search

Navigation