IDEAS home Printed from https://ideas.repec.org/a/inm/ortrsc/v48y2014i3p351-372.html
   My bibliography  Save this article

The Recoverable Robust Tail Assignment Problem

Author

Listed:
  • Gary Froyland

    (School of Mathematics and Statistics, University of New South Wales, Sydney NSW 2052, Australia)

  • Stephen J. Maher

    (School of Mathematics and Statistics, University of New South Wales, Sydney NSW 2052, Australia)

  • Cheng-Lung Wu

    (School of Aviation, University of New South Wales, Sydney NSW 2052, Australia)

Abstract

Schedule disruptions are commonplace in the airline industry with many flight-delaying events occurring each day. Recently there has been a focus on introducing robustness into airline planning stages to reduce the effect of these disruptions. We propose a recoverable robustness technique as an alternative to robust optimisation to reduce the effect of disruptions and the cost of recovery. We formulate the recoverable robust tail assignment problem (RRTAP) as a stochastic program, solved using column generation in the master and subproblems of the Benders' decomposition. We implement a two-phase algorithm for the Benders' decomposition and identify pareto-optimal cuts. The RRTAP includes costs due to flight delays, cancellation, and passenger rerouting, and the recovery stage includes cancellation, delay, and swapping options. To highlight the benefits of simultaneously solving planning and recovery problems in the RRTAP we compare our tail assignment solution against current approaches from the literature. Using airline data we demonstrate that by developing a better tail assignment plan via the RRTAP framework, one can reduce recovery costs in the event of a disruption.

Suggested Citation

  • Gary Froyland & Stephen J. Maher & Cheng-Lung Wu, 2014. "The Recoverable Robust Tail Assignment Problem," Transportation Science, INFORMS, vol. 48(3), pages 351-372, August.
  • Handle: RePEc:inm:ortrsc:v:48:y:2014:i:3:p:351-372
    DOI: 10.1287/trsc.2013.0463
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/trsc.2013.0463
    Download Restriction: no

    File URL: https://libkey.io/10.1287/trsc.2013.0463?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Chunhua Gao & Ellis Johnson & Barry Smith, 2009. "Integrated Airline Fleet and Crew Robust Planning," Transportation Science, INFORMS, vol. 43(1), pages 2-16, February.
    2. Jean-François Cordeau & Goran Stojković & François Soumis & Jacques Desrosiers, 2001. "Benders Decomposition for Simultaneous Aircraft Routing and Crew Scheduling," Transportation Science, INFORMS, vol. 35(4), pages 375-388, November.
    3. T. L. Magnanti & R. T. Wong, 1981. "Accelerating Benders Decomposition: Algorithmic Enhancement and Model Selection Criteria," Operations Research, INFORMS, vol. 29(3), pages 464-484, June.
    4. Michelle Dunbar & Gary Froyland & Cheng-Lung Wu, 2012. "Robust Airline Schedule Planning: Minimizing Propagated Delay in an Integrated Routing and Crewing Framework," Transportation Science, INFORMS, vol. 46(2), pages 204-216, May.
    5. Barry C. Smith & Ellis L. Johnson, 2006. "Robust Airline Fleet Assignment: Imposing Station Purity Using Station Decomposition," Transportation Science, INFORMS, vol. 40(4), pages 497-516, November.
    6. Cynthia Barnhart & Natashia L. Boland & Lloyd W. Clarke & Ellis L. Johnson & George L. Nemhauser & Rajesh G. Shenoi, 1998. "Flight String Models for Aircraft Fleeting and Routing," Transportation Science, INFORMS, vol. 32(3), pages 208-220, August.
    7. Shan Lan & John-Paul Clarke & Cynthia Barnhart, 2006. "Planning for Robust Airline Operations: Optimizing Aircraft Routings and Flight Departure Times to Minimize Passenger Disruptions," Transportation Science, INFORMS, vol. 40(1), pages 15-28, February.
    8. Walter Rei & Jean-François Cordeau & Michel Gendreau & Patrick Soriano, 2009. "Accelerating Benders Decomposition by Local Branching," INFORMS Journal on Computing, INFORMS, vol. 21(2), pages 333-345, May.
    9. Cynthia Barnhart & Christopher A. Hane & Pamela H. Vance, 2000. "Using Branch-and-Price-and-Cut to Solve Origin-Destination Integer Multicommodity Flow Problems," Operations Research, INFORMS, vol. 48(2), pages 318-326, April.
    10. Kohl, Niklas & Larsen, Allan & Larsen, Jesper & Ross, Alex & Tiourine, Sergey, 2007. "Airline disruption management—Perspectives, experiences and outlook," Journal of Air Transport Management, Elsevier, vol. 13(3), pages 149-162.
    11. Joyce W. Yen & John R. Birge, 2006. "A Stochastic Programming Approach to the Airline Crew Scheduling Problem," Transportation Science, INFORMS, vol. 40(1), pages 3-14, February.
    12. Jay M. Rosenberger & Ellis L. Johnson & George L. Nemhauser, 2004. "A Robust Fleet-Assignment Model with Hub Isolation and Short Cycles," Transportation Science, INFORMS, vol. 38(3), pages 357-368, August.
    Full references (including those not matched with items on IDEAS)

    Citations

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


    Cited by:

    1. Maher, Stephen J. & Desaulniers, Guy & Soumis, François, 2018. "The daily tail assignment problem under operational uncertainty using look-ahead maintenance constraints," European Journal of Operational Research, Elsevier, vol. 264(2), pages 534-547.
    2. Maher, Stephen J., 2021. "Implementing the branch-and-cut approach for a general purpose Benders’ decomposition framework," European Journal of Operational Research, Elsevier, vol. 290(2), pages 479-498.
    3. Birolini, Sebastian & Jacquillat, Alexandre, 2023. "Day-ahead aircraft routing with data-driven primary delay predictions," European Journal of Operational Research, Elsevier, vol. 310(1), pages 379-396.
    4. Huang, Zhouchun & Luo, Xiaodong & Jin, Xianfei & Karichery, Sureshan, 2022. "An iterative cost-driven copy generation approach for aircraft recovery problem," European Journal of Operational Research, Elsevier, vol. 301(1), pages 334-348.
    5. Delgado, Felipe & Mora, Julio, 2021. "A matheuristic approach to the air-cargo recovery problem under demand disruption," Journal of Air Transport Management, Elsevier, vol. 90(C).
    6. Chiwei Yan & Jerry Kung, 2018. "Robust Aircraft Routing," Transportation Science, INFORMS, vol. 52(1), pages 118-133, January.
    7. Xiao, Fan & Guo, Siqi & Huang, Lin & Huang, Lei & Liang, Zhe, 2022. "Integrated aircraft tail assignment and cargo routing problem with through cargo consideration," Transportation Research Part B: Methodological, Elsevier, vol. 162(C), pages 328-351.
    8. Stephen J. Maher, 2016. "Solving the Integrated Airline Recovery Problem Using Column-and-Row Generation," Transportation Science, INFORMS, vol. 50(1), pages 216-239, February.
    9. Valentina Cacchiani & Juan-José Salazar-González, 2017. "Optimal Solutions to a Real-World Integrated Airline Scheduling Problem," Transportation Science, INFORMS, vol. 51(1), pages 250-268, February.
    10. Zhao, Ai & Bard, Jonathan F. & Bickel, J. Eric, 2023. "A two-stage approach to aircraft recovery under uncertainty," Journal of Air Transport Management, Elsevier, vol. 111(C).

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Liang, Zhe & Feng, Yuan & Zhang, Xiaoning & Wu, Tao & Chaovalitwongse, Wanpracha Art, 2015. "Robust weekly aircraft maintenance routing problem and the extension to the tail assignment problem," Transportation Research Part B: Methodological, Elsevier, vol. 78(C), pages 238-259.
    2. Jon D. Petersen & Gustaf Sölveling & John-Paul Clarke & Ellis L. Johnson & Sergey Shebalov, 2012. "An Optimization Approach to Airline Integrated Recovery," Transportation Science, INFORMS, vol. 46(4), pages 482-500, November.
    3. Michelle Dunbar & Gary Froyland & Cheng-Lung Wu, 2012. "Robust Airline Schedule Planning: Minimizing Propagated Delay in an Integrated Routing and Crewing Framework," Transportation Science, INFORMS, vol. 46(2), pages 204-216, May.
    4. Da Lu & Fatma Gzara, 2015. "The robust crew pairing problem: model and solution methodology," Journal of Global Optimization, Springer, vol. 62(1), pages 29-54, May.
    5. Chunhua Gao & Ellis Johnson & Barry Smith, 2009. "Integrated Airline Fleet and Crew Robust Planning," Transportation Science, INFORMS, vol. 43(1), pages 2-16, February.
    6. Valentina Cacchiani & Juan-José Salazar-González, 2017. "Optimal Solutions to a Real-World Integrated Airline Scheduling Problem," Transportation Science, INFORMS, vol. 51(1), pages 250-268, February.
    7. Xu, Yifan & Wandelt, Sebastian & Sun, Xiaoqian, 2021. "Airline integrated robust scheduling with a variable neighborhood search based heuristic," Transportation Research Part B: Methodological, Elsevier, vol. 149(C), pages 181-203.
    8. Birolini, Sebastian & Jacquillat, Alexandre, 2023. "Day-ahead aircraft routing with data-driven primary delay predictions," European Journal of Operational Research, Elsevier, vol. 310(1), pages 379-396.
    9. Qiang Meng & Shuaian Wang & Henrik Andersson & Kristian Thun, 2014. "Containership Routing and Scheduling in Liner Shipping: Overview and Future Research Directions," Transportation Science, INFORMS, vol. 48(2), pages 265-280, May.
    10. Hanif Sherali & Ki-Hwan Bae & Mohamed Haouari, 2013. "A benders decomposition approach for an integrated airline schedule design and fleet assignment problem with flight retiming, schedule balance, and demand recapture," Annals of Operations Research, Springer, vol. 210(1), pages 213-244, November.
    11. Jane Lee & Lavanya Marla & Alexandre Jacquillat, 2020. "Dynamic Disruption Management in Airline Networks Under Airport Operating Uncertainty," Transportation Science, INFORMS, vol. 54(4), pages 973-997, July.
    12. Chiwei Yan & Jerry Kung, 2018. "Robust Aircraft Routing," Transportation Science, INFORMS, vol. 52(1), pages 118-133, January.
    13. Hanif D. Sherali & Ki-Hwan Bae & Mohamed Haouari, 2013. "An Integrated Approach for Airline Flight Selection and Timing, Fleet Assignment, and Aircraft Routing," Transportation Science, INFORMS, vol. 47(4), pages 455-476, November.
    14. Sujeevraja Sanjeevi & Saravanan Venkatachalam, 2021. "Robust flight schedules with stochastic programming," Annals of Operations Research, Springer, vol. 305(1), pages 403-421, October.
    15. Parmentier, Axel & Meunier, Frédéric, 2020. "Aircraft routing and crew pairing: Updated algorithms at Air France," Omega, Elsevier, vol. 93(C).
    16. Keji Wei & Vikrant Vaze, 2018. "Modeling Crew Itineraries and Delays in the National Air Transportation System," Transportation Science, INFORMS, vol. 52(5), pages 1276-1296, October.
    17. Lim, Gino J. & Bard, Jonathan F., 2016. "Benders decomposition and an IP-based heuristic for selecting IMRT treatment beam anglesAuthor-Name: Lin, Sifeng," European Journal of Operational Research, Elsevier, vol. 251(3), pages 715-726.
    18. Sherali, Hanif D. & Bish, Ebru K. & Zhu, Xiaomei, 2006. "Airline fleet assignment concepts, models, and algorithms," European Journal of Operational Research, Elsevier, vol. 172(1), pages 1-30, July.
    19. Erdem, Furkan & Bilgiç, Taner, 2024. "Airline delay propagation: Estimation and modeling in daily operations," Journal of Air Transport Management, Elsevier, vol. 115(C).
    20. Ding, Chengjin & Chen, Xinyuan & Wu, Weiwei & Wei, Wenbin & Xin, Zelin, 2023. "Game-theoretic analysis of the impact of crew overnight hotel cost on airlines’ fleet assignment and crew pairing," Journal of Air Transport Management, Elsevier, vol. 113(C).

    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:ortrsc:v:48:y:2014:i:3:p:351-372. See general information about how to correct material in RePEc.

    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 CitEc recognized a bibliographic reference but did not link an item in RePEc 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 RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

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

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.