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

Airline Crew Scheduling: State-of-the-Art

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

Abstract

The airline industry is faced with some of the largest scheduling problems of any industry. The crew scheduling problem involves the optimal allocation of crews to flights. Over the last two decades the magnitude and complexity of crew scheduling problems have grown enormously and airlines are relying more on automated mathematical procedures as a practical necessity. In this paper we survey different approaches studied and discuss the state-of-the-art in solution methodology for the airline crew scheduling problem. We conclude with a discussion about promising areas for further work to make it possible to get very good solutions for the crew scheduling problem.

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

Similar content being viewed by others

References

  • Anbil, R., E. Gelman, B. Patty, and R. Tanga. (1991). “Recent Advances in Crew-Pairing Optimization at American Airlines.” Interfaces 21, 62–74.

    Google Scholar 

  • Anbil, R., E.L. Johnson, and R. Tanga. (1991). “A Gobal Approach to Crew Pairing Optimization.” IBM Systems Journal 31, 71–78

    Article  Google Scholar 

  • Anbil, R., J. Forrest, and W. Pulleyblank. (1998). “Column Generation and the Airline Crew Pairing Problem.” Documenta Mathematica—Journal der Deutschen MathematikerVereinigung, number III in extra volume: proceedings of the ICM.

  • Anderson, E., E. Housos, N. Kohl, and D. Wedelin. (1997). “Crew Pairing Optimization.” In G. Yu, (ed.), OR in airline industry, Kluwer Acad. Publ., Boston.

    Google Scholar 

  • Arabeyre, J. P., J. Feanley, F.C. Stieger, and W. Teather. (1969). “The Airline Crew Scheduling Problem: A Survey.” Transportation Science 3, 140–163.

    Google Scholar 

  • Araoz, J., L. Evans, R.E. Gomory, and E.L. Johnson. (2003). “Cyclic Group and Knapsack Facets.” Mathematical Programming 96(2), 337–408.

    Google Scholar 

  • Balas, E. and M. Padberg. (1976). “Set Partitioning: A Survey.” SIAM Review 18, 710–760.

    Article  Google Scholar 

  • Balas, E. and S.M. Ng. (1986). “On the Set-Covering Polytope I: All Facets with Coefficients {0,1,2}.” MSSR-522, GSIA, Carnegie-Mellon U.

  • Balas, E., S. Ceria, G. Cornuejols, and N. Natraj. (1996). “Gomory Cuts Revisited.” Operations Research Letters 19, 1–9.

    Article  Google Scholar 

  • Barahona, F. and R. Anbil. (1997). “The Volume Algorithm: Producing Primal Solutions with a Subgradient Method.” Research Report RC 21103 (94395), IBM T.J. Watson Research Center, Yorktown Heights, NY.

  • Baker, E.K., L.D. Bodin, and M. Fisher. (1985). “The Development of a Heuristic Set Covering Based System for Aircrew Scheduling.” Transportation Policy Decision Making 3, 95–110.

    Google Scholar 

  • Ball, M. and A. Roberts. (1985). “A Graph Partitioning Approach to Airline Crew Scheduling.” Transportation Science 19(2) 107–126.

    Google Scholar 

  • Barnhart, C., L. Hatay, and E.L. Johnson. (1995). “Deadhead Selection for the Long-Haul Crew Pairing Problem.” Operations Research 43, 491–499.

    Google Scholar 

  • Barnhart, C., E.L. Hohnson, R. Anbil, and L. Hatay. (1994). “A Column Generation Technique for the Long-Haul Crew Assignment Problem.” In T.A. Cirani and R.C. Leachman (eds.), Optimization in Industry II, Wiley.

  • Barnhart, C., E.L. Johnson, G.L. Nemhauser, M.W.P. Savelsbergh, and P.H. Vance. (1998). “Branch-and-Price: Column Generation for Solving Huge Integer Programs.” Operations Research, 43, 491–499.

    Google Scholar 

  • Barutt, J. and T. Hull. (1990). “Airline Crew Scheduling: Supercomputers and Algorithms.” SIAM News 23(6), 1 and 20–22.

    Google Scholar 

  • Beale, E. and J. Tomlin. (1970). “Special Facilities in a General Mathematical Programming System for Non-Convex Problems Using Ordered Sets of Variables.” Proceedings of the 5th International Conference on Operations Research.

  • Bixby, R., W. Cook, A. Cox, and E. Lee. (1995). “Parallel Mixed Integer Programming.” Technical Report CRPC-TR95554, Rice University. Available from ftp://softlib.rice.edu/pub/CRPC-TRs/reports

  • Bornemann, D.R. (1982). “The Evolution of Airline Crew Pairing Optimization.” AGIFORS Crew Management Study Group Proceedings, Rio de Janeiro (April).

  • The Carmen Systems, version 5.1, Carmen Systems AB, Göteborg, Sweden.

  • Chu, H., E. Gelman, and E.L. Johnson. (1997). “Solving Large Scale Crew Scheduling Problem.” European Journal of Operations Research 97, 245–259.

    Article  Google Scholar 

  • Cornuejols, G. and A. Sassano. (1989). “On the 0,1 Facets of the Set Covering Polytope.” Mathematical Programming 43, 101–111.

    Google Scholar 

  • Crowder, H., E.L. Johnson, and M.W. Padberg. (1983). “Solving Large-Scale 0-1 Linear Programming Problems.” Operations Research 31, 803–834.

    Google Scholar 

  • CPLEX Optimization, “Using the CPLEX Callable Library.” 7.0 edn, ILOG Inc.

  • Dantzig, G.B. and P. Wolfe. (1960). “Decomposition Principle for Linear Programs.” Operations Research 8, 101–111.

    Google Scholar 

  • Desrosiers, J., Y. Dumas, M. Desrochers, F. Soumis, B. Sasno, and P. Trudeau. (1991). “A Breakthrough in Airline Crew Scheduling.” Technical Report G-91-11, Les Cahiers du GERAD.

  • Desrochers, J., Y. Dumas, M.M. Solomon, and F. Soumis (1995). “Time Constrained Routing and Scheduling.” In M.E. Ball, T.L. Magnanti, C. Monma and G.L. Nemhauser (eds.), Handbook in Operations Research and Management Science, 8: Network Routing, Elsevier, Amsterdam, 35–140.

  • Desaulniers, G., J. Desrosiers, Y. Dumas, S. Marc, B. Rioux, M.M. Solomon, and F. Soumis. (1997). “Crew Pairing at Air France” 97, 245–259.

    Google Scholar 

  • Ehrgott, M. and D.M. Ryan. (2003). “Constructing Robust Crew Schedules with Bicriteria Optimization.” Journal of Multi-Criteria Decision Analysis 11, 139–150, 2002.

    Google Scholar 

  • Etschmaier, M.M. and D.F.X. Mathaisel. (1985). “Airline Scheduling: An Overview.” Transportation Science 19, 127–138.

    Google Scholar 

  • Fisher, M.L. (1981). “The Lagrangian Relaxation Method for Solving Integer Programming Problems.” Management Science 27(1), 1–18.

    Google Scholar 

  • Forrest, J.J. (1989). “Mathematical Programming with a Library of Optimization Subroutines.” presented at the ORSA/TIMS Joint National Meeting, New York.

  • Freling, R., D. Huisman, and A.P.M. Wagelmans. (2000). “Models And Algorithms For Integration Of Vehicle And Crew Scheduling.” No 189 in Econometric Institute Report from Erasmus University Rotterdam, Econometric Institute.

  • Gander, P.H., M.R. Rosekind, and K.B. Gregory. (1998). “Flight Crew Fatigue.” Aviation, Space and Environmental Medicine 69, (9 Suppl.), B49–B60.

    Google Scholar 

  • Gendron, B. and T.G. Crainic. (1994). “Parallel Branch-and-Bound Algoirithms: Survey and Synthesis.” Operations Research 42, 1042.

    Google Scholar 

  • Gerbracht, R. (1978). “A New Algorithm for Very Large Crew Pairing Problems.” 18th AGIFORS Symposium, Vancouver, British Columbia, CA.

  • Gershkoff, I. (1989). “Optimizing Flight Crew Schedules.” Interfaces 19, 29–43.

    Google Scholar 

  • Gomory, R.E. (1963). “An Algorithm for Integer Solutions to Linear Programs.” In R.L. Graves and P. Wolfe (eds.), Recent Advances in Mathematical Programming, pp. 269–302. McGraw-Hill, New York.

    Google Scholar 

  • R.E. Gomory and E.L. Johnson. (2003). “T-Space and Cutting Planes.” Mathematical Programming Ser. B 96(2), 341–375.

    Article  Google Scholar 

  • Gomory, R.E., E.L. Johnson, and L. Evans. (2003). “Corner Polyhedra and their Applications to Cutting Planes.” Mathematical Programming 96(2), 321–339.

    Article  Google Scholar 

  • Gopalakrishnan, B. and E.L. Johnson. (2003). “Mitigating Crew Fatigue through Crew Pairing Optimization.” Working Paper, School of Industrial and Systems Engineering, Georgia Tech.

  • Graves, G.W., R.D. McBride, and I. Gershkoff. (1993). “Flight Crew Scheduling.” Management Science 39(6), 736–745.

    Google Scholar 

  • Held, M. and R.M. Karp. (1970). “The Travelling Salesman Problem and Minimum Spanning Tress.” Oper. Res. 18, 1138–1162.

    Google Scholar 

  • Held, M. and R.M. Karp. (1971). “The Travelling Salesman Problem and Minimum Spanning Tress: Part II.” Mathematical Programming 1, 6–25.

    Article  Google Scholar 

  • Held, M., P. Wolfe, and H.P. Crowder. (1974). “Validation of Subgradient Optimization.” Mathematical Programming 6, 62–88.

    Article  Google Scholar 

  • Hoffman, K.L. and M. Padberg. (1993). “Solving Airline Crew-Scheduling Problems by Branch-and-Cut.” Management Science 39, 657–682.

    Google Scholar 

  • Hoffman, A.J, A. Kolen, and M. Sakarovitch. (1985). “Totally Balanced and Greedy Matrices.” SIAM Journal on Algebraic and Discrete Methods 6, 721–730.

    Google Scholar 

  • Hoffman, K.L. and M. Padberg. (1991). “Techniques for Improving the LP − representation of 0-1 Linear Programming Problems.” ORSA J. Computing 3, 121–134.

    Google Scholar 

  • Housos, E. and T. Elmroth. (1997). “Automatic Optimization of Subproblems in Schedulign Airline Crews.” Interfaces 27, 68–77.

    Article  Google Scholar 

  • Hu, J. (1996). “Solving Linear Programs Using Primal-Dual Subproblem Simplex Method and Quasi-Explicit Matrices.” Ph.D. Dissertation.

  • Hu, J. and E. Johnson. (1999). “Computational Results with a Primal-Dual Subproblem Simplex Method.” Operations Research Letters 25, 149–158.

    Article  Google Scholar 

  • Johnson E.L. (1989). “Modeling and Strong Linear Programs for Mixed Integer Programming.” In S.W. Wallace (ed.), Algorithms and Model Formulations in Mathematical Programming, NATO ASI Series 51, pp. 1–41.

  • Junger, M. and S. Thienel. (1998). “Introduction to ABACUS - A Branch-and-Cut System.” Operations Research Letters 22, 83–95.

    Article  Google Scholar 

  • Klabjan, D., E. Johnson, and G.L. Nemhauser. (2000). “A Parallel Primal-Dual Simplex Algorithm.” Operations Research Letters 27, 47–55

    Article  Google Scholar 

  • Klabjan, D., E. Johnson, and G.L. Nemhauser, E. Gelman, and S. Ramaswamy. (2002). “Airline Crew Scheduling with Time Windows and Plane Count Constraints.” Transportation Science 36, 337–348.

    Article  Google Scholar 

  • Klabjan, D. and K. Schwan. (2002). “Airline Crew Pairing Generation in Parallel.” Technical report TLI/LEC-99-02.

  • Klabjan, D., E. Johnson, G.L. Nemhauser, E. Gelman, and S. Ramaswamy. (2001). “Solving Large Airline Crew Scheduling Problems: Random Pairing Generation and Strong Branching.” Computational Optimization and Applications 20, 73–91

    Article  Google Scholar 

  • Klabjan, D., E. Johnson, G.L. Nemhauser, E. Gelman, and S. Ramaswamy. (2001). “Airline Crew Scheduling with Regularity.” Transportation Science 35, 359–374.

    Article  Google Scholar 

  • Larson, T. and Z. Liu. (1989). “A Primal Convergence Result for Dual Subgradient Optimization with Application to Multicommodity Network Flows.” Research Report S-581 83, Dept. of Math., Linkoping Institute of Technology.

  • Lavoie, S., M. Minoux, and E. Odier. (1988). “A New Approach to Crew Pairing Problems by Column Generation and Application to Air Transport.” European Journal of Operatiosn Research 35, 45–58.

    Article  Google Scholar 

  • Lemarechal, T. (1975). “An Extention of Davidson Methods to Nondifferentiable Problems.” Mathematical Programming Study 3, 95–109.

    Google Scholar 

  • Lemke, C., H. Salkin, K. Spielberg. (1971). “Set Covering by Single Branch Enumeration with Linear Programming Subproblems.” Operations Research 19, 998–1022.

    Google Scholar 

  • Lemke, C. and K. Spielberg. (1967). “Direct Search Algorithms for Zero-One and Mixed Integer Programming.”Operations Research 15, 892–914.

    Google Scholar 

  • Linderoth, J. and M. Savelsbergh. (1999). “A Computational Study of Search Strategies for Mixed Integer Programs.” Informs Journal on Computing 11, 173–187.

    Google Scholar 

  • Marsten, R.E. and F. Shepardson. (1981). “Exact Solution of Crew Problems using the Set Partitioning Mode: recent Successful Applications.” Networks 11, 165–177.

    Google Scholar 

  • Minoux, M. (1984). “Column Generation Technique in Combinatorial Optimization: A New Application to Crew Pairing Problems.” Proceedings XXIVth AGIFORS Symposium.

  • Mitchell, J.E. (2000). “Branch-and-Cut Algorithms for Combinatorial Optimization Problems.” Handbook of Applied Operations Research, Oxford University Press.

  • Nemhauser, G.L. and L.A. Wolsey. (1999). “Integer and Combinatorial Optimization.” John Wiley, New York.

    Google Scholar 

  • Padberg, M. and G. Rinaldi. (1991). “A Branch-and-Cut Algorithm for the solution of Large-Scale Traveling Salesman Problems.” SIAM Review 33, 1–41.

    Article  Google Scholar 

  • Padberg, M. (1971). “Essays in Integer Programming.” Pd.D. Thesis, GSAI, Carnegie-Mellon U., Pittsburg, PA.

  • Padberg, M. (1972). “On the Facial Struture of the Set Packing Polyhedra.” Mathematical Programming 5, 199–215.

    Article  Google Scholar 

  • Padberg, M. (1975). “A Note on 0-1 Programming.” Operations Research 23, 833–837.

    Google Scholar 

  • Padberg, M. (1977). “On the Complexity of Set Packing Polyhedra.” Annals of Dicrete Mathematics 1, 421–434.

    Article  Google Scholar 

  • Padberg, M. (1979). “Covering, Packing and Knapsack Problems.” Annals of Dicrete Mathematics 4, 265–287.

    Google Scholar 

  • Panayiotis, A., P. Sanders, T. Takkula, and D. Wedelin(2000). “Parallel Integer Optimization for Crew Scheduling.” Annals of Operations Research 99, 141–166.

    Article  Google Scholar 

  • Ralphs, T.K., L. Ladanyi, and L.E. Trotter, Jr. (2001). “Branch, Cut, and Price: Sequential and Parallel.” In D. Naddef and M. Juenger (eds.), Computational Combinatorial Optimization.

  • Rosekind, M.R., P.H. Gander, R.M. Smith, K.J. Weldon, and K.L. McNally. (1994). “Fatigue in Aviation.” Air Line Pilot 63(10), 22–25.

    Google Scholar 

  • Ryan, D.M. and J.C. Falkner. (1988). “On the Integer Properties of Scheduling Set Paritioning Problems.” European Journal of Operations Research 35, 442–456.

    Article  Google Scholar 

  • Ryan, D.M. and B. Foster. (1981). “An Integer Programming Approach to Scheduling.” In A. Wren (ed.), Computer Scheduling of Public Transport Urban Passenger Vehicle and Crew Scheduling. North-Holland, pp. 269–280.

  • Rubin, J. (1971). “Airline Crew Scheduling—The Non-Mathematical Problem.” IBM Technical Report : 320.3006.

  • Rubin, J. (1973). “A Technique for the Solution of Massive Set Covering Problems with Applications to Airline Crew Scheduling.” Transportation Science 7, 34–38.

    Article  Google Scholar 

  • Shor, N.Z. (1985). “Minimization Methods for nondifferentiable functions.” Springer, Berlin.

  • Vance, P.H., A. Atamturk, C. Barnhart, E. Gelman, E. Johnson, A. Krishna, D. Mahindra, G.L. Nemhauser, and R. Rebello. (1997). “A Heuristic Branch-and-Price Approach and Airline Crew Pairing Problem.”

  • Vance, P.H., C. Barnhart, E.L. Johnson, and G.L. Nemhauser (1995). “Airline Crew Scheduling: A New Formulation and Decomposition Algorithm.” Operations Research 45(2), 188–200.

    Google Scholar 

  • Wedelin, D. (1995). “An Algorithm for Large-Sclae 0-1 Integer Programming with Applications to Airline Crew Scheduling.” Annals of Operations Research 57, 283–301.

    Article  Google Scholar 

  • Weir, J. (2002). “A Threee Phase Approach to Solving the Crew Bidline Problem with Rules for Mitigating Crew Fatigue.” Ph.D. Dissertation, Georgia Institute of Technology.

  • Wise, T.H (1995). “Column Generation and Polyhedral Combinatorics for Airline Crew Scheduling.” Ph.D. Dissertation, Cornell U., Ithaca, N.Y.

  • Wolfe, P. (1975). “A Method of Conjugate Subgradients for Minimizing Nondifferentiable Functions.” Mathematical Programming Study 3, 145–173.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institute for Mathematics and its Applications, University of Minnesota, Minneapolis, MN, 55455

    Balaji Gopalakrishnan & Ellis. L. Johnson

Authors
  1. Balaji Gopalakrishnan
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ellis. L. Johnson
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Balaji Gopalakrishnan.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Gopalakrishnan, B., Johnson, E.L. Airline Crew Scheduling: State-of-the-Art. Ann Oper Res 140, 305–337 (2005). https://doi.org/10.1007/s10479-005-3975-3

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10479-005-3975-3

Keywords

Search

Navigation