Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

A comparison of stochastic programming and bi-objective optimisation approaches to robust airline crew scheduling

  • Regular Article
  • Published:
OR Spectrum Aims and scope Submit manuscript

Abstract

A prominent problem in airline crew scheduling is the pairings or Tour-of-Duty planning problem. The objective is to determine a set of pairings (or Tours-of-Duty) for a crew group to minimise the planned cost of operating a schedule of flights. However, due to unforeseen events the performance in operation can differ considerably from planning, sometimes causing significant additional recovery costs. In recent years there has been a growing interest in robust crew scheduling. Here, the aim is to find solutions that are “cheap” in terms of planned cost as well as being robust, meaning that they are less likely to be disrupted in case of delays. Taking the stochastic nature of delays into account, Yen and Birge (Transp Sci 40:3–14, 2006) formulate the problem as a two-stage stochastic integer programme and develop an algorithm to solve this problem. Based on the contradictory nature of the goals, Ehrgott and Ryan (J Multi-Criteria Decis Anal 11:139–150, 2002) formulate a bi-objective set partitioning model and employ elastic constraint scalarisation to enable the solution by set partitioning algorithms commercially used in crew scheduling software. In this study, we compare the two solution approaches. We improve the algorithm of Yen and Birge (Transp Sci 40:3–14, 2006) and implement both methods with a commercial crew scheduling software. The results of both methods are compared with respect to characteristics of robust solutions, such as the number of aircraft changes for crew. We also conduct experiments to simulate the performance of the obtained solutions. All experiments are performed using actual schedule data from Air New Zealand.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Anbil R, Forrest J, Pulleyblank W (1998) Column generation and the airline crew pairing problem. Doc Math Extra volume ICM III: 677–686

    Google Scholar 

  • Barnhart C, Johnson EL, Savelsbergh MWP, Vance PH (1998) Branch-and-price: column generation for solving huge integer programs. Oper Res 46: 316–329

    Article  Google Scholar 

  • Barnhart C, Cohn A, Johnson E, Klabjan D, Nemhauser G, Vance P (2003) Airline crew scheduling. In: Hall R(eds) Handbook of transportation science.. Kluwer, Dordrecht, pp 493–521

    Google Scholar 

  • Ehrgott M, Ryan D (2002) Constructing robust crew schedules with bicriteria optimization. J Multi-Criteria Decis Anal 11: 139–150

    Article  Google Scholar 

  • Ehrgott M, Ryan D (2003) The method of elastic constraints for multiobjective combinatorial optimization and its application in airline crew scheduling. In: Tanino T, Tanaka T, Inuiguchi M(eds) Multi-objective programming and goal-programming.. Springer, Berlin, pp 117–122

    Google Scholar 

  • Rosenberger JM, Schaefer AJ, Goldsman D, Johnson EL, Kleywegt A, Nemhauser GL (2000) Simair: a stochastic model of airline operations. In: Joines J, Barton P, Fishwick P, Kang K (eds) Proceedings of the 2000 winter simulation conference, pp 1118–1122

  • Rosenberger JM, Schaefer AJ, Goldsman D, Johnson EL, Kleywegt A, Nemhauser GL (2002) A stochastic model of airline operations. Transp Sci 36: 357–377

    Article  Google Scholar 

  • Ryan DM, Falkner J (1988) On the integer properties of scheduling set partitioning models. Eur J Oper Res 35: 442–456

    Article  Google Scholar 

  • Ryan DM, Foster BA (1981) An integer programming approach to scheduling. In: Wren A(eds) Computer scheduling of public transport.. North-Holland, Amsterdam, pp 269–280

    Google Scholar 

  • Schaefer AJ, Johnson EL, Kelywegt AJ, Nemhauser GL (2005) Airline crew scheduling under uncertainty. Transp Sci 39: 340–348

    Article  Google Scholar 

  • Shebalov S, Klabjan D (2006) Robust airline crew pairing: move-up crews. Transp Sci 40: 300–312

    Article  Google Scholar 

  • US Department of Transportation (2007) Airline on-time performance data. Bureau of Transportation Statistics. http://www.transtats.bts.gov

  • Yen JW, Birge JR (2006) A stochastic programming approach to the airline crew scheduling problem. Transp Sci 40: 3–14

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Engineering Science, The University of Auckland, Private Bag 92019, Auckland, New Zealand

    Bassy Tam, Matthias Ehrgott, David Ryan & Golbon Zakeri

Authors
  1. Bassy Tam
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Matthias Ehrgott
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. David Ryan
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Golbon Zakeri
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Bassy Tam.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Tam, B., Ehrgott, M., Ryan, D. et al. A comparison of stochastic programming and bi-objective optimisation approaches to robust airline crew scheduling. OR Spectrum 33, 49–75 (2011). https://doi.org/10.1007/s00291-009-0164-9

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00291-009-0164-9

Keywords

Search

Navigation