Solving large airline crew scheduling problems: Random pairing generation and strong branching

Diego Klabjan*, Ellis L. Johnson, George L. Nemhauser, Eric Gelman, Srini Ramaswamy

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

73 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)73-91
Number of pages19
JournalComputational Optimization and Applications
Volume20
Issue number1
DOIs
StatePublished - Oct 2001

Keywords

  • Airline crew scheduling
  • Branch-and-bound
  • Transportation

ASJC Scopus subject areas

  • Control and Optimization
  • Computational Mathematics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Solving large airline crew scheduling problems: Random pairing generation and strong branching'. Together they form a unique fingerprint.

Cite this