Skip to main content
SpringerLink
Log in

Solving a large-scale crew pairing problem

  • General Paper
  • Published:
Journal of the Operational Research Society

Abstract

Airline companies seek to solve the problem of determining an assignment of crews to a pre-determined flight schedule with minimum total cost, called the Crew Pairing Problem (CPP). Most of the existing studies focus on the CPP of North American airlines, which widely differs from that of most European airline companies in terms of the objective function, the flight structure, and the planning horizon. In this study, we develop an optimization-driven heuristic algorithm that can efficiently handle large-scale instances of the CPP that must be solved on a monthly basis. We perform computational experiments using flight schedules of an European airline company to test the performance of the solution method. Our computational results demonstrate that our algorithm is able to provide high-quality solutions to monthly instances with up to 27 000 flight legs.

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

Access this article

Log in via an institution

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

Instant access to the full article PDF.

Institutional subscriptions

Figure 1
Figure 2

Similar content being viewed by others

References

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

    Article  Google Scholar 

  • Andersson E, Housos E, Kohl N and Wedelin D (1998). Crew pairing optimization. In: Yu G (ed). Operations Research in the Airline Industry. Chapter 8. Kluwer Academic Publishers: Norwell: pp 228–258.

    Chapter  Google Scholar 

  • Arabeyre JP, Fearnley J, Steiger FC and Teather W (1969). The airline crew scheduling problem: A survey. Transportation Science 3 (2): 140–163.

    Article  Google Scholar 

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

    Article  Google Scholar 

  • Azadeh A, Asadipour G, Eivazy H and 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 MH, Eivazy H, Nazari-Shirkouhi S and Asadipour G (2013). A hybrid meta-heuristic algorithm for optimization of crew scheduling. Applied Soft Computing 13 (1): 158–164.

    Article  Google Scholar 

  • Barnhart C and Shenoi RG (1998). An approximate model and solution approach for the long-haul crew pairing problem. Transportation Science 32 (3): 221–231.

    Article  Google Scholar 

  • Barnhart C, Johnson E, Anbil R and Hatay L (1994). A column generation technique for the long-haul crew assignment problem. In: Ciriano T and Leachman R (eds). Optimization in Industry: Volume ‘II’. John Wiley and Sons: Chicester, UK, pp 7–22.

    Google Scholar 

  • Barnhart C, Johnson EL, Nemhauser GL, Savelsbergh MWP and Vance PH (1998a). Branch-and-price: Column generation for solving huge integer programs. Operations Research 46 (3): 316–329.

    Article  Google Scholar 

  • Barnhart C, Lu F and Shenoi R (1998b). Integrated airline schedule planning. In: Yu G (ed). Operations Research in the Airline Industry. Kluwer Academic Publishers: Boston, MA, pp 384–403.

    Chapter  Google Scholar 

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

    Article  Google Scholar 

  • Barnhart C, Cohn AM, Johnson EJ, Klabjan D, Nemhauser GL and Vance PH (2003b). Airline crew scheduling. In: Hall RW (ed). Handbook of Transportation Science. 2nd edn, Chapter 14. Kluwer Academic Publishers: Norwell, pp 517–560.

    Chapter  Google Scholar 

  • Beasley J and Cao B (1996). A tree search algorithm for the crewscheduling problem. European Journal of Operational Research 94 (3): 517–526.

    Article  Google Scholar 

  • Burke EK, De Causmaecker P, De Maere G, Mulder J, Paelinck M and Vanden Berghe G (2010). A multi-objective approach for robust airline scheduling. Computers & Operations Research 37 (5): 822–832.

    Article  Google Scholar 

  • Butchers ER et al (2001). Optimized crew scheduling at Air New Zealand. Interfaces 31 (1): 30–56.

    Article  Google Scholar 

  • Cavique L, Rego C and 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, Yan S and Chen M (2010). Applying Lagrangian relaxation-based algorithms for airline coordinated flight scheduling problems. Computers & Industrial Engineering 59 (3): 398–410.

    Article  Google Scholar 

  • Chen C-H, Liu T-K and 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 

  • Clausen J, Larsen A, Larsen J and Rezanova NJ (2010). Disruption management in the airline industry concepts, models and methods. Computers & Operations Research 37 (5): 809–821.

    Article  Google Scholar 

  • Deng G-F and 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 

  • Derigs U and Schafer S (2014). A note on extending the generic crew scheduling model of Beasley and Cao by deadheads and layovers. Journal of the Operational Research Society 65 (5): 633–644.

    Article  Google Scholar 

  • Desaulniers G et al (1997). Crew pairing at Air France. European Journal of Operational Research 97 (2): 245–259.

    Article  Google Scholar 

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

    Google Scholar 

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

    Article  Google Scholar 

  • Dück V, Ionescu L, Kliewer N and Suhl L (2012). Increasing stability of crew and aircraft schedules. Transportation Research Part C: Emerging Technologies 20 (1): 47–61.

    Article  Google Scholar 

  • Dunbar M, Froyland G and Wu C-L (2012). Robust airline schedule planning: Minimizing propagated delay in an integrated routing and crewing framework. Transportation Science 46 (2): 204–216.

    Article  Google Scholar 

  • Dunbar M, Froyland G and Wu C-L (2014). An integrated scenario-based approach for robust aircraft routing,crew pairing and re-timing. Computers & Operations Research 45: 68–86.

    Article  Google Scholar 

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

    Article  Google Scholar 

  • Gao C, Johnson E and 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 (4): 29–43.

    Article  Google Scholar 

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

    Article  Google Scholar 

  • Hoffman KL and Padberg M (1993). Solving airline crew scheduling problems by branch-and-cut. Management Science 39 (6): 657–682.

    Article  Google Scholar 

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

    Article  Google Scholar 

  • Lu D and Gzara F (2014). The robust crew pairing problem: Model and solution methodology. Journal of Global Optimization 1–26, published online 10 July 2014, doi 10.1007/s10898-014-0222-y.

  • Makri A and Klabjan D (2004). A new pricing scheme for airline crew scheduling. INFORMS Journal on Computing 16 (1): 56–67.

    Article  Google Scholar 

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

    Article  Google Scholar 

  • Muter I et al (2013). Solving a robust airline crew pairing problem with column generation. Computers & Operations Research 40 (3): 815–830.

    Article  Google Scholar 

  • Ozdemir HT and Mohan CK (2001). Flight graph based genetic algorithm for crew scheduling in airlines. Information Sciences. Evolutionary Algorithms 133 (34): 165–173.

    Article  Google Scholar 

  • Pita JP, Adler N and Antunes AP (2014). Socially-oriented flight scheduling and fleet assignment model with an application to Norway. Transportation Research Part B: Methodological 61 (0): 17–32.

    Article  Google Scholar 

  • Pita JP, Barnhart C and Antunes AP (2013). Integrated flight scheduling and fleet assignment under airport congestion. Transportation Science 47 (4): 477–492.

    Article  Google Scholar 

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

    Article  Google Scholar 

  • Saddoune M, Desaulniers G, Elhallaou I and Soumis F (2011). Integrated airline crew scheduling: A bi-dynamic constraint aggregation method using neighborhoods. European Journal of Operational Research 212 (3): 445–454.

    Article  Google Scholar 

  • Saddoune M, Desaulniers G, Elhallaou I and Soumis F (2012). Integrated airline crew pairing and crew assignment by dynamic constraint aggregation. Transportation Science 46 (1): 39–55.

    Article  Google Scholar 

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

    Article  Google Scholar 

  • Salazar-González J-J (2014). Approaches to solve the fleet-assignment, aircraft-routing, crew-pairing and crew-rostering problems of a regional carrier. Omega 43 (0): 71–82.

    Article  Google Scholar 

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

    Article  Google Scholar 

  • Subramanian S and Sherali HD (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.

    Article  Google Scholar 

  • Tekiner H, Birbil SI and Bülbül K (2009). Robust crew pairing for managing extra flights. Computers & Operations Research 36 (6): 2031–2048.

    Article  Google Scholar 

  • Vance PH (1993). Crew scheduling, cutting stock, and column generation: Solving huge integer programs. PhD Thesis, School of Industrial and Systems Engineering, Georgia Institute of Technology: Atlanta, GA.

  • Vance PH, Barnhart C, Johnson EL and Nemhauser GL (1997). Airline crew scheduling: A new formulation and decomposition algorithm. Operations Research 45 (2): 183–200.

    Article  Google Scholar 

  • Weide O, Ryan D and Ehrgott M (2010). An iterative approach to robust and integrated aircraft routing and crew scheduling. Computers & Operations Research 37 (5): 833–844.

    Article  Google Scholar 

  • Yan S and Tu Y-P (2002). A network model for airline cabin crew scheduling. European Journal of Operational Research 140 (3): 531–540.

    Article  Google Scholar 

  • Yen JW and Birge JR (2006). A stochastic programming approach to the airline crew scheduling problem. Transportation Science 40 (1): 3–14.

    Article  Google Scholar 

Download references

Acknowledgements

This project is funded in part by TUBITAK grant 110M308. We thank the five anonymous referees for their valuable comments, which have improved the paper substantially.

Author information

Authors and Affiliations

  1. University of Bath, Bath, UK

    Güneş Erdoğan

  2. Qatar University, Doha, Qatar

    Mohamed Haouari

  3. University of New Hampshire, Durham, USA

    Melda Örmeci Matoglu

  4. Ozyegin University, Istanbul, Turkey

    Okan Örsan Özener

Authors
  1. Güneş Erdoğan
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Mohamed Haouari
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Melda Örmeci Matoglu
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Okan Örsan Özener
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Güneş Erdoğan.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Erdoğan, G., Haouari, M., Matoglu, M. et al. Solving a large-scale crew pairing problem. J Oper Res Soc 66, 1742–1754 (2015). https://doi.org/10.1057/jors.2015.2

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1057/jors.2015.2

Keywords

Search

Navigation