IDEAS home Printed from https://ideas.repec.org/a/inm/ormnsc/v39y1993i6p657-682.html
   My bibliography  Save this article

Solving Airline Crew Scheduling Problems by Branch-and-Cut

Author

Listed:
  • Karla L. Hoffman

    (Operations Research Department, George Mason University, 4400 University Drive, Fairfax, Virginia 22030)

  • Manfred Padberg

    (New York University, MEC 8-68, New York, New York 10012)

Abstract

The crew scheduling problem is one that has been studied almost continually for the past 40 years but all prior approaches have always approximated the problem of finding an optimal schedule for even the smallest of an airline's fleets. The problem is especially important today since costs for flying personnel of major U.S. carriers have grown and now often exceed $1.3 billion a year and are the second largest item (next to fuel cost) of the total operating cost of major U.S. carriers. Thus even small percentage savings amount to substantial dollar amounts. We present a branch-and-cut approach to solving to proven optimality large set partitioning problems arising within the airline industry. We first provide some background related to this important application and then describe the approach for solving representative problems in this problem class. The branch-and-cut solver generates cutting planes based on the underlying structure of the polytope defined by the convex hull of the feasible integer points and incorporates these cuts into a tree-search algorithm that uses automatic reformulation procedures, heuristics and linear programming technology to assist in the solution. Numerical experiments are reported for a sample of 68 large-scale real-world crew scheduling problems. These problems include both pure set partitioning problems and set partitioning problems with side constraints. These "base constraints" represent contractual labor requirements and have heretofore not been represented explicitly in the construction of crew schedules thus making it impossible to provide any measure of how far the obtained solution was from optimality. An interesting result of obtaining less costly schedules is that the crews themselves are happier with the schedules because they spend more of their duty time flying than waiting on the ground.

Suggested Citation

  • Karla L. Hoffman & Manfred Padberg, 1993. "Solving Airline Crew Scheduling Problems by Branch-and-Cut," Management Science, INFORMS, vol. 39(6), pages 657-682, June.
  • Handle: RePEc:inm:ormnsc:v:39:y:1993:i:6:p:657-682
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/mnsc.39.6.657
    Download Restriction: no

    References listed on IDEAS

    as
    1. JS Armstrong & Fred Collopy, 2004. "Causal Forces: Structuring Knowledge for Time-series Extrapolation," General Economics and Teaching 0412003, EconWPA.
    2. Fildes, Robert & Lusk, Edward J, 1984. "The choice of a forecasting model," Omega, Elsevier, vol. 12(5), pages 427-435.
    3. Scott Armstrong, J., 1988. "Research needs in forecasting," International Journal of Forecasting, Elsevier, vol. 4(3), pages 449-465.
    4. Robert Carbone & JS Armstrong, 2004. "Evaluation of Extrapolative Forecasting Methods: Results of a Survey of Academicians and Practitioners," General Economics and Teaching 0412008, EconWPA.
    5. Robert Carbone & Spyros Makridakis, 1986. "Forecasting When Pattern Changes Occur Beyond the Historical Data," Management Science, INFORMS, vol. 32(3), pages 257-271, March.
    6. Armstrong, J. Scott & Collopy, Fred, 1992. "Error measures for generalizing about forecasting methods: Empirical comparisons," International Journal of Forecasting, Elsevier, vol. 8(1), pages 69-80, June.
    7. Sanders, NR & Ritzman, LP, 1990. "Improving short-term forecasts," Omega, Elsevier, vol. 18(4), pages 365-373.
    Full references (including those not matched with items on IDEAS)

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:ormnsc:v:39:y:1993:i:6:p:657-682. See general information about how to correct material in RePEc.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Mirko Janc). General contact details of provider: http://edirc.repec.org/data/inforea.html .

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.