Abstract
Next to fuel costs, crew costs are the largest direct operating cost of airlines. Therefore much research has been devoted to the planning and scheduling of crews over the last thirty years. The planning and scheduling of crews is usually considered as two problems: the crew pairing problem and the crew assignment (rostering) problem. These problems are solved sequentially. In this paper we focus on the pairing problem. The aim of the paper is twofold. First, we give an overview of the crew pairing problem and synthesize the optimization methods that have been published previously. Second, we present the Carmen pairing construction system which is in operation at most major European airlines. Our purpose is to identify the particular properties of the Carmen system that have made this system the preferred decision support system for crew pairing optimization in Europe.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
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, vol. 21. no. 1, pp. 62–74.
Anbil, R., R. Tanga and E.L. Johnson (1992), “A global approach to crew-pairing optimization”, IBM Systems Journal, vol. 31, no. 1, pp. 71–78.
Anbil, R., C. Barnhart, L. Hatay, E.L. Johnson and V.S. Ramakrishnan (1993), “Crew-pairing Optimization at American Airlines Decision Technology”, Optimization in Industry, eds.: Ciriani, T.A. and R.C. Leachman, John Wiley and Sons Ltd..
Barutt, J. and T. Hull (1990), “Airline Crew Scheduling: Supercomputers and Algorithms”, SIAM News, vol. 23, no. 6, pp. 1 and 20–22.
Caparara, A., M. Fischetti and P. Toth (1995), A Heuristic Algorithm for the Set Covering Problem, working paper.
Ceria, S., P. Nobili and A. Sassano (1995), A Lagrangean-based Heuristic-for Large-scale Covering Problems, working paper.
Cplex Optimization Inc. (1994), Using the CPLEX Callable Library, Cplex Optimization Inc., Suite 279, 930 Tahoe Blvd., Bldg. 802, Incline Village, NV 89451-9436, USA.
Desaulniers, G., J. Desrosiers, M.M. Solomon and F. Soumis (1994), Daily Aircraft Routing and Scheduling, Research report G-94-21, GERAD, Montreal, Canada.
Desaulniers, G., J. Desrosiers, Y. Dumas, S. Marc, B. Rioux, M.M. Solomon and F. Soumis (1995), Crew Pairing at Air France, Research report G-93-39, GERAD, Montreal, Canada.
Desrosiers, J., Y. Dumas, M.M. Solomon and F. Soumis (1995), “Time Constrained Routing and Scheduling”, in Handbooks in Operations Research and Management Science, vol. 8: Network Routing, eds.: Ball, M.O., T.L. Magnanti, C.L Monma and G.L. Nemhauser, North-Holland, Amsterdam, The Netherlands.
Elmroth T. and Housos E. (1996), “Automatic Subproblem Optimization for Airline Crew Scheduling”, Interfaces (to be published).
Engel, F. (1995), Summary over test runs, Internal report, Carmen Systems AB, Gothenburg, Sweden.
Garfinkel, R.S. and G.L. Nemhauser (1972), Integer Programming, John Wiley and Sons.
Gershkoff, I. (1989), “Optimizing Flight Crew Schedules”, Interfaces, vol. 19, no. 4, pp. 29–43.
Graves, G.W., R.D. McBride and I. Gershkoff (1993), “Flight Crew Scheduling”, Management Science, vol. 39, no. 6, pp. 736–745.
Hoffman, K.L. and M. Padberg (1993), “Solving Airline Crew Scheduling Problems by Branch-and-Cut”, Management Science, vol. 39, no. 6, pp. 657–682.
Lavoie, S., M. Minoux and E. Odier (1988), “A new approach for crew pairing problems by column generation with an application to air transportation”, European Journal of Operational Research, vol. 35, pp. 45–58.
Marsten, R. (1994), Crew Scheduling with RALPH, Presentation given at the workshop “Optimization in Production and Transportation”, The Hague, The Netherlands, November 9–11, 1994.
Nemhauser, G.L and L.A. Wolsey (1988), Integer and Combinatorial Optimization, Wiley-Interscience.
Pulleyblank, W.R. (1994), An Airline Crew Pairing Optimization System, Presentation given at the workshop “Optimization in Production and Transportation”, The Hague, The Netherlands, November 9–11, 1994.
Ryan, D.M. and J.C. Falkner (1987), “A Bus Crew Scheduling System Using a Set Partitioning Model”, Asia Pacific Journal of Operational Research, no. 4, pp. 39–56.
Wedelin, D. (1995), “An algorithm for large scale 0-1 integer programming with application to airline crew scheduling”, Annals of Operations Research, vol. 57, pp. 283–301.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1998 Springer Science+Business Media New York
About this chapter
Cite this chapter
Andersson, E., Housos, E., Kohl, N., Wedelin, D. (1998). Crew Pairing Optimization. In: Yu, G. (eds) Operations Research in the Airline Industry. International Series in Operations Research & Management Science, vol 9. Springer, Boston, MA. https://doi.org/10.1007/978-1-4615-5501-8_8
Download citation
DOI: https://doi.org/10.1007/978-1-4615-5501-8_8
Publisher Name: Springer, Boston, MA
Print ISBN: 978-1-4613-7513-5
Online ISBN: 978-1-4615-5501-8
eBook Packages: Springer Book Archive