Abstract
The airline crew scheduling problem is the problem of assigning crew itineraries to flights. We develop a new approach for solving the problem that is based on enumerating hundreds of millions random pairings. The linear programming relaxation is solved first and then millions of columns with best reduced cost are selected for the integer program. The number of columns is further reduced by a linear programming based heuristic. Finally an integer solution is obtained with a commercial integer programming solver. The branching rule of the solver is enhanced with a combination of strong branching and a specialized branching rule. The algorithm produces solutions that are significantly better than ones found by current practice.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
R. Anbil, J. Forrest, and W. Pulleyblank, 1998. Column Generation, and the Airline Crew Pairing Problem, Extra Volume Proceedings ICM. Available from http://www.math.uiuc.edu/documenta/xvol-icm/17/17.html.
R. Anbil, E. Gelman, B. Patty, and R. Tanga, “Recent advances in crew pairing optimization at American airlines,” Interfaces vol. 21, pp. 62–74, 1991.
R. Anbil, E. Johnson, and R. Tanga, “A global approach to crew pairing optimization,” IBM Systems Journal, vol. 31, pp. 71–78, 1992.
E. Andersson, E. Housos, N. Kohl, and D. Wedelin, “Crew pairing optimization,” in Operations Research in the Airline Industry, G. Yu (Ed.), Kluwer Academic Publishers, 1998, pp. 228–258.
C. Barnhart, E. Johnson, G. Nemhauser, M. Savelsbergh, and P. Vance, “Branch-and-price: Column generation for solving huge integer programs,” Operations Research, vol. 46, pp. 316–329, 1998.
C. Barnhart, E. Johnson, G. Nemhauser, and P. Vance, “Crew scheduling,” in Handbook of Transportation Science, R.W. Hall (Ed.), Kluwer Scientific Publishers, 1999, pp. 493–521.
E. Beale, and J. Tomlin, “Special facilities in a general mathematical programming system for non-convex problems using ordered sets of variables,” in Proceedings of the 5th International Conference on Operations Research, 1970.
D. Bertsekas, Nonlinear Programming, Athena Scientific, 1995, pp. 79–90.
R. Bixby, W. Cook, A. Cox, and E. Lee, “Parallel mixed integer programming,” Technical Report CRPCTR95554, Rice University. Available from ftp://softlib.rice.edu/pub/CRPC-TRs/reports.
R. Bixby, J. Gregory, I. Lustig, R. Marsten, and D. Shanno, “Very large-scale linear programming: A case study in combining interior point, and simplex methods,” Operations Research, vol. 40, pp. 885–897, 1992.
H. Chu, E. Gelman, and E. Johnson, “Solving large scale crew scheduling problems,” European Journal of Operational Research, vol. 97, pp. 260–268, 1997.
CPLEX Optimization 1997. Using the CPLEX Callable Library, 5.0 edn, ILOG Inc.
J. Desrosiers, Y. Dumas, M. Desrochers, F. Soumis, B. Sanso, and P. Trudeau, “A breakthrough in airline crew scheduling,” Technical Report G-91-11, Cahiers du GERAD.
M. Dyer, A. Frieze, A. Kapoor, R. Kannan, L. Perkovic, and U. Vazirani, “A mildly exponential time algorithm for approximating the number of solutions to a multidimensional knapsack problem.” Unpublished.
T. Feo and M. Resende, “A probabilistic heuristic for a computationally difficult set covering problem,” Operations Research Letters, vol. 8, pp. 67–71, 1989.
I. Gershkoff, “Optimizing flight crew schedules,” Interfaces, vol. 19, pp. 29–43, 1989.
D. Klabjan, “Topics in airline crew scheduling and large scale optimization,” Ph.D. Dissertation, Georgia Institute of Technology, 1999.
D. Klabjan, E. Johnson, and G. Nemhauser, “A parallel primal-dual algorithm,” Technical Report TLI/LEC-99-10, Georgia Institute of Technology, 1990. To appear in Operations Research Letters.
D. Klabjan and K. Schwan, “Airline crew pairing generation in parallel,” Technical Report TLI/LEC-99-02, Georgia Institute of Technology, 1999.
A. Law and W. Kelton. Simulation, Modeling, and Analysis, McGraw-Hill, 1991.
J. Linderoth and M. Savelsbergh, “Acomputational study of search strategies for mixed integer programming,” Informs Journal on Computing, vol. 11, pp. 173–187, 1999.
Message Passing Interface Forum, The MPI Message Passing Standard, 1995. Available from http://www.mpiforum.org.
D. Ryan and B. Foster, “An integer programming approach to scheduling,” in Computer Scheduling of Public Transport Urban Passenger Vehicle, and Crew Scheduling, A. Wren (Ed.), North-Holland, 1981, pp. 269–280.
P. Vance, A. Atamtürk, C. Barnhart, E. Gelman, E. Johnson, A. Krishna, D. Mahidhara, G. Nemhauser, and R. Rebello, “A heuristic branch-and-price approach for the airline crew pairing problem,” Technical Report LEC-97-06, Georgia Institute of Technology, 1997.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Klabjan, D., Johnson, E.L., Nemhauser, G.L. et al. Solving Large Airline Crew Scheduling Problems: Random Pairing Generation and Strong Branching. Computational Optimization and Applications 20, 73–91 (2001). https://doi.org/10.1023/A:1011223523191
Issue Date:
DOI: https://doi.org/10.1023/A:1011223523191