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

A Novel Model and Decomposition Approach for the Integrated Airline Fleet Assignment, Aircraft Routing, and Crew Pairing Problem

Author

Listed:
  • Shengzhi Shao

    (Grado Department of Industrial and Systems Engineering, Virginia Tech, Blacksburg, Virginia 24061)

  • Hanif D. Sherali

    (Grado Department of Industrial and Systems Engineering, Virginia Tech, Blacksburg, Virginia 24061)

  • Mohamed Haouari

    (Department of Mechanical and Industrial Engineering, Qatar University, Doha, Qatar)

Abstract

Given a daily flight schedule and a set of aircraft fleets, the airline scheduling problem assigns individual aircraft and groups of crew to each flight based on specific considerations of aircraft maintenance requirements and crew work rules, respectively. Traditionally, this problem has been sequentially broken down into several stages, where the fleet assignment problem, which is solved first, partitions the entire flight network into subnetworks according to fleet types, followed by respectively solving the aircraft routing and crew pairing problems to generate suitable aircraft and crew rotations. However, this sequential approach ignores the interdependencies among the stages, leading to suboptimal, or even infeasible, solutions. In this paper, we propose an integrated model and solution approach that incorporates the fleet assignment (with itinerary-based demands), aircraft routing, and crew pairing problems within a single framework. We solve the resulting formulation of the problem by using a Benders decomposition approach, along with several acceleration strategies. Computational results obtained by using real-life data from a major U.S. airline demonstrate the benefits of the integrated approach.

Suggested Citation

  • Shengzhi Shao & Hanif D. Sherali & Mohamed Haouari, 2017. "A Novel Model and Decomposition Approach for the Integrated Airline Fleet Assignment, Aircraft Routing, and Crew Pairing Problem," Transportation Science, INFORMS, vol. 51(1), pages 233-249, February.
    • Handle: RePEc:inm:ortrsc:v:51:y:2017:i:1:p:233-249
    DOI: 10.1287/trsc.2015.0623
    as

    Download full text from publisher

    File URL: https://doi.org/10.1287/trsc.2015.0623
    Download Restriction: no
    File URL: https://libkey.io/10.1287/trsc.2015.0623?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. Cynthia Barnhart & Timothy S. Kniker & Manoj Lohatepanont, 2002. "Itinerary-Based Airline Fleet Assignment," Transportation Science, INFORMS, vol. 36(2), pages 199-217, May.
    2. Mohamed Haouari & Shengzhi Shao & Hanif D. Sherali, 2013. "A Lifted Compact Formulation for the Daily Aircraft Maintenance Routing Problem," Transportation Science, INFORMS, vol. 47(4), pages 508-525, November.
    3. Diego Klabjan, 2005. "Large-Scale Models in the Airline Industry," Springer Books, in: Guy Desaulniers & Jacques Desrosiers & Marius M. Solomon (ed.), Column Generation, chapter 0, pages 163-195, Springer.
    4. L. W. Clarke & C. A. Hane & E. L. Johnson & G. L. Nemhauser, 1996. "Maintenance and Crew Considerations in Fleet Assignment," Transportation Science, INFORMS, vol. 30(3), pages 249-260, August.
    5. 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.
    6. Shivaram Subramanian & Hanif D. Sherali, 2008. "An Effective Deflected Subgradient Optimization Scheme for Implementing Column Generation for Large-Scale Airline Crew Scheduling Problems," INFORMS Journal on Computing, INFORMS, vol. 20(4), pages 565-578, November.
    7. Hanif D. Sherali & Ki-Hwan Bae & Mohamed Haouari, 2010. "Integrated Airline Schedule Design and Fleet Assignment: Polyhedral Analysis and Benders' Decomposition Approach," INFORMS Journal on Computing, INFORMS, vol. 22(4), pages 500-513, November.
    8. 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.
    9. A. M. Geoffrion & G. W. Graves, 1974. "Multicommodity Distribution System Design by Benders Decomposition," Management Science, INFORMS, vol. 20(5), pages 822-844, January.
    10. 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.
    11. 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.
    12. Haouari, Mohamed & Aissaoui, Najla & Mansour, Farah Zeghal, 2009. "Network flow-based approaches for integrated aircraft fleeting and routing," European Journal of Operational Research, Elsevier, vol. 193(2), pages 591-599, March.
    13. 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.
    14. Martin Desrochers & François Soumis, 1989. "A Column Generation Approach to the Urban Transit Crew Scheduling Problem," Transportation Science, INFORMS, vol. 23(1), pages 1-13, February.
    15. Anne Mercier, 2008. "A Theoretical Comparison of Feasibility Cuts for the Integrated Aircraft-Routing and Crew-Pairing Problem," Transportation Science, INFORMS, vol. 42(1), pages 87-104, February.
    16. Hanif Sherali & Brian Lunday, 2013. "On generating maximal nondominated Benders cuts," Annals of Operations Research, Springer, vol. 210(1), pages 57-72, November.
    17. Rivi Sandhu & Diego Klabjan, 2007. "Integrated Airline Fleeting and Crew-Pairing Decisions," Operations Research, INFORMS, vol. 55(3), pages 439-456, June.
    18. Hanif D. Sherali & Warren P. Adams & Patrick J. Driscoll, 1998. "Exploiting Special Structures in Constructing a Hierarchy of Relaxations for 0-1 Mixed Integer Problems," Operations Research, INFORMS, vol. 46(3), pages 396-405, June.
    19. Dale McDaniel & Mike Devine, 1977. "A Modified Benders' Partitioning Algorithm for Mixed Integer Programming," Management Science, INFORMS, vol. 24(3), pages 312-319, November.
    20. Amy Mainville Cohn & Cynthia Barnhart, 2003. "Improving Crew Scheduling by Incorporating Key Maintenance Routing Decisions," Operations Research, INFORMS, vol. 51(3), pages 387-396, June.
    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. Mohamed Haouari & Farah Zeghal Mansour & Hanif D. Sherali, 2019. "A New Compact Formulation for the Daily Crew Pairing Problem," Transportation Science, INFORMS, vol. 53(3), pages 811-828, May.
    2. 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.
    3. Glomb, Lukas & Liers, Frauke & Rösel, Florian, 2022. "A rolling-horizon approach for multi-period optimization," European Journal of Operational Research, Elsevier, vol. 300(1), pages 189-206.
    4. Wen, Xin & Ma, Hoi-Lam & Chung, Sai-Ho & Khan, Waqar Ahmed, 2020. "Robust airline crew scheduling with flight flying time variability," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 144(C).
    5. Ben Ahmed, Mohamed & Zeghal Mansour, Farah & Haouari, Mohamed, 2018. "Robust integrated maintenance aircraft routing and crew pairing," Journal of Air Transport Management, Elsevier, vol. 73(C), pages 15-31.

    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. Okan Örsan Özener & Melda Örmeci Matoğlu & Güneş Erdoğan & Mohamed Haouari & Hasan Sözer, 2017. "Solving a large-scale integrated fleet assignment and crew pairing problem," Annals of Operations Research, Springer, vol. 253(1), pages 477-500, June.
    2. 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.
    3. Oliver Faust & Jochen Gönsch & Robert Klein, 2017. "Demand-Oriented Integrated Scheduling for Point-to-Point Airlines," Transportation Science, INFORMS, vol. 51(1), pages 196-213, February.
    4. Mohamed Haouari & Shengzhi Shao & Hanif D. Sherali, 2013. "A Lifted Compact Formulation for the Daily Aircraft Maintenance Routing Problem," Transportation Science, INFORMS, vol. 47(4), pages 508-525, November.
    5. Zhe Liang & Wanpracha Art Chaovalitwongse, 2013. "A Network-Based Model for the Integrated Weekly Aircraft Maintenance Routing and Fleet Assignment Problem," Transportation Science, INFORMS, vol. 47(4), pages 493-507, November.
    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. 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.
    8. Rahmaniani, Ragheb & Crainic, Teodor Gabriel & Gendreau, Michel & Rei, Walter, 2017. "The Benders decomposition algorithm: A literature review," European Journal of Operational Research, Elsevier, vol. 259(3), pages 801-817.
    9. F M Zeghal & M Haouari & H D Sherali & N Aissaoui, 2011. "Flexible aircraft fleeting and routing at TunisAir," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 62(2), pages 368-380, February.
    10. Vedat Bayram & Hande Yaman, 2018. "Shelter Location and Evacuation Route Assignment Under Uncertainty: A Benders Decomposition Approach," Transportation Science, INFORMS, vol. 52(2), pages 416-436, March.
    11. Başdere, Mehmet & Bilge, Ümit, 2014. "Operational aircraft maintenance routing problem with remaining time consideration," European Journal of Operational Research, Elsevier, vol. 235(1), pages 315-328.
    12. Mohammed Saddoune & Guy Desaulniers & Issmail Elhallaoui & François Soumis, 2012. "Integrated Airline Crew Pairing and Crew Assignment by Dynamic Constraint Aggregation," Transportation Science, INFORMS, vol. 46(1), pages 39-55, February.
    13. Ragheb Rahmaniani & Shabbir Ahmed & Teodor Gabriel Crainic & Michel Gendreau & Walter Rei, 2020. "The Benders Dual Decomposition Method," Operations Research, INFORMS, vol. 68(3), pages 878-895, May.
    14. Atoosa Kasirzadeh & Mohammed Saddoune & François Soumis, 2017. "Airline crew scheduling: models, algorithms, and data sets," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 6(2), pages 111-137, June.
    15. Teodor Gabriel Crainic & Mike Hewitt & Francesca Maggioni & Walter Rei, 2021. "Partial Benders Decomposition: General Methodology and Application to Stochastic Network Design," Transportation Science, INFORMS, vol. 55(2), pages 414-435, March.
    16. Zhe Liang & Wanpracha Art Chaovalitwongse & Huei Chuen Huang & Ellis L. Johnson, 2011. "On a New Rotation Tour Network Model for Aircraft Maintenance Routing Problem," Transportation Science, INFORMS, vol. 45(1), pages 109-120, February.
    17. Ben Ahmed, Mohamed & Zeghal Mansour, Farah & Haouari, Mohamed, 2018. "Robust integrated maintenance aircraft routing and crew pairing," Journal of Air Transport Management, Elsevier, vol. 73(C), pages 15-31.
    18. Hanif D. Sherali & Ki-Hwan Bae & Mohamed Haouari, 2010. "Integrated Airline Schedule Design and Fleet Assignment: Polyhedral Analysis and Benders' Decomposition Approach," INFORMS Journal on Computing, INFORMS, vol. 22(4), pages 500-513, November.
    19. Jeihoonian, Mohammad & Kazemi Zanjani, Masoumeh & Gendreau, Michel, 2016. "Accelerating Benders decomposition for closed-loop supply chain network design: Case of used durable products with different quality levels," European Journal of Operational Research, Elsevier, vol. 251(3), pages 830-845.
    20. M. Jenabi & S. M. T. Fatemi Ghomi & S. A. Torabi & Moeen Sammak Jalali, 2022. "An accelerated Benders decomposition algorithm for stochastic power system expansion planning using sample average approximation," OPSEARCH, Springer;Operational Research Society of India, vol. 59(4), pages 1304-1336, December.

    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:51:y:2017:i:1:p:233-249. 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.