Advanced Search
MyIDEAS: Login to save this article or follow this journal

Solving Airline Crew Scheduling Problems by Branch-and-Cut

Contents:

Author Info

  • 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)

Registered author(s):

    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.

    Download Info

    If you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
    File URL: http://dx.doi.org/10.1287/mnsc.39.6.657
    Download Restriction: no

    Bibliographic Info

    Article provided by INFORMS in its journal Management Science.

    Volume (Year): 39 (1993)
    Issue (Month): 6 (June)
    Pages: 657-682

    as in new window
    Handle: RePEc:inm:ormnsc:v:39:y:1993:i:6:p:657-682

    Contact details of provider:
    Postal: 7240 Parkway Drive, Suite 300, Hanover, MD 21076 USA
    Phone: +1-443-757-3500
    Fax: 443-757-3515
    Email:
    Web page: http://www.informs.org/
    More information through EDIRC

    Related research

    Keywords: zero-one programming; set partitioning; crew scheduling; polyhedral cuts; preprocessing; heuristics; automatic reformulation; branch-and-cut; scientific computation;

    References

    No references listed on IDEAS
    You can help add them by filling out this form.

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as in new window

    Cited by:
    1. Xia, Mu & Koehler, Gary J. & Whinston, Andrew B., 2004. "Pricing combinatorial auctions," European Journal of Operational Research, Elsevier, vol. 154(1), pages 251-270, April.
    2. Aardal,Karen & Hoesel,Stan,van, 1995. "Polyhedral techniques in combinatorial optimization," Research Memorandum 014, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
    3. Rönnberg, Elina & Larsson, Torbjörn, 2009. "Column generation in the integral simplex method," European Journal of Operational Research, Elsevier, vol. 192(1), pages 333-342, January.
    4. Bredström, David & Jörnsten, Kurt & Rönnqvist, Mikael, 2007. "Searching for optimal integer solutions to set partitioning problems using column generation," Discussion Papers 2007/20, Department of Business and Management Science, Norwegian School of Economics.
    5. Yan, Shangyao & Chang, Jei-Chi, 2002. "Airline cockpit crew scheduling," European Journal of Operational Research, Elsevier, vol. 136(3), pages 501-511, February.
    6. Kroon, L.G. & Fischetti, M., 2000. "Crew Scheduling for Netherlands Railways: "destination: customer"," ERIM Report Series Research in Management ERS-2000-56-LIS, Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam.
    7. Ernst, A. T. & Jiang, H. & Krishnamoorthy, M. & Sier, D., 2004. "Staff scheduling and rostering: A review of applications, methods and models," European Journal of Operational Research, Elsevier, vol. 153(1), pages 3-27, February.
    8. Sriram, Chellappan & Haghani, Ali, 2003. "An optimization model for aircraft maintenance scheduling and re-assignment," Transportation Research Part A: Policy and Practice, Elsevier, vol. 37(1), pages 29-48, January.
    9. Drexl, Andreas & Jörnsten, Kurt & Knof, Diether, 2005. "Non-linear anonymous pricing in combinatorial auctions," Discussion Papers 2005/6, Department of Business and Management Science, Norwegian School of Economics.
    10. Wark, Peter & Holt, John & Ronnqvist, Mikael & Ryan, David, 1997. "Aircrew schedule generation using repeated matching," European Journal of Operational Research, Elsevier, vol. 102(1), pages 21-35, October.
    11. Beasley, J. E. & Cao, B., 1996. "A tree search algorithm for the crew scheduling problem," European Journal of Operational Research, Elsevier, vol. 94(3), pages 517-526, November.
    12. Abbink, E.J.W., 2008. "Solving large scale crew scheduling problems by using iterative partitioning," Econometric Institute Research Papers EI 2008-03, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    13. Darby-Dowman, K. & Fink, R. K. & Mitra, G. & Smith, J. W., 1995. "An intelligent system for US Coast Guard cutter scheduling," European Journal of Operational Research, Elsevier, vol. 87(3), pages 574-585, December.
    14. B. Maenhout & M. Vanhoucke, 2007. "A Hybrid Scatter Search Heuristic for Personalized Crew Rostering in the Airline Industry," Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium 07/454, Ghent University, Faculty of Economics and Business Administration.
    15. Liu, Jiyin & MacCarthy, B. L., 1997. "A global MILP model for FMS scheduling," European Journal of Operational Research, Elsevier, vol. 100(3), pages 441-453, August.
    16. Bjorndal, M. H. & Caprara, A. & Cowling, P. I. & Della Croce, F. & Lourenco, H. & Malucelli, F. & Orman, A. J. & Pisinger, D. & Rego, C. & Salazar, J. J., 1995. "Some thoughts on combinatorial optimisation," European Journal of Operational Research, Elsevier, vol. 83(2), pages 253-270, June.
    17. Desaulniers, G. & Desrosiers, J. & Dumas, Y. & Marc, S. & Rioux, B. & Solomon, M. M. & Soumis, F., 1997. "Crew pairing at Air France," European Journal of Operational Research, Elsevier, vol. 97(2), pages 245-259, March.

    Lists

    This item is not listed on Wikipedia, on a reading list or among the top items on IDEAS.

    Statistics

    Access and download statistics

    Corrections

    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).

    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.

    If references are entirely missing, you can add them using this form.

    If the full references list an item that is present in RePEc, but the system did not link to it, you can help with 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 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.