IDEAS home Printed from https://ideas.repec.org/a/eee/transb/v114y2018icp39-67.html
   My bibliography  Save this article

Multi-stage airline scheduling problem with stochastic passenger demand and non-cruise times

Author

Listed:
  • Şafak, Özge
  • Çavuş, Özlem
  • Selim Aktürk, M.

Abstract

We propose a three-stage stochastic programming model which determines flight timing, fleeting and routing decisions while considering the randomness of demand and non-cruise times. Our model differs from the existing two-stage stochastic models by considering not only flight timing and potential passenger demand, but also expected operational expenses, such as fuel burn and carbon emission costs. We include aircraft cruise speed decisions to compensate for non-cruise time variability so as to satisfy the time requirements of the passenger connections. We handle nonlinear functions of fuel and emission costs associated with cruise speed adjustments by utilizing mixed integer second order cone programming. Because the three-stage stochastic model leads to a large decision tree and can be very time-consuming to solve optimally, we suggest a scenario group-wise decomposition algorithm to obtain lower and upper bounds for the optimal value of the proposed model. The lower and upper bounds are obtained by solving a number of group subproblems, which are similar to proposed multi-stage stochastic model defined over a reduced number of scenarios. We suggest a cutting plane algorithm, along with improvements, to efficiently solve each group subproblem. In the numerical experiments, we provide a significant cost savings over two-stage stochastic programming and deterministic approaches.

Suggested Citation

  • Şafak, Özge & Çavuş, Özlem & Selim Aktürk, M., 2018. "Multi-stage airline scheduling problem with stochastic passenger demand and non-cruise times," Transportation Research Part B: Methodological, Elsevier, vol. 114(C), pages 39-67.
    • Handle: RePEc:eee:transb:v:114:y:2018:i:c:p:39-67
    DOI: 10.1016/j.trb.2018.05.012
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0191261517310202
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.trb.2018.05.012?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Bektas, Tolga & Laporte, Gilbert, 2011. "The Pollution-Routing Problem," Transportation Research Part B: Methodological, Elsevier, vol. 45(8), pages 1232-1250, September.
    2. Ovidiu Listes & Rommert Dekker, 2005. "A Scenario Aggregation–Based Approach for Determining a Robust Airline Fleet Composition for Dynamic Capacity Allocation," Transportation Science, INFORMS, vol. 39(3), pages 367-382, August.
    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. Hanif D. Sherali & Raymond W. Staats & Antonio A. Trani, 2006. "An Airspace-Planning and Collaborative Decision-Making Model: Part II---Cost Model, Data Considerations, and Computations," Transportation Science, INFORMS, vol. 40(2), pages 147-164, May.
    5. Hanif Sherali & Brian Lunday, 2013. "On generating maximal nondominated Benders cuts," Annals of Operations Research, Springer, vol. 210(1), pages 57-72, November.
    6. Yan, Shangyao & Tang, Ching-Hui & Fu, Tseng-Chih, 2008. "An airline scheduling model and solution algorithms under stochastic demands," European Journal of Operational Research, Elsevier, vol. 190(1), pages 22-39, October.
    7. Haahr, Jørgen Thorlund & Pisinger, David & Sabbaghian, Mohammad, 2017. "A dynamic programming approach for optimizing train speed profiles with speed restrictions and passage points," Transportation Research Part B: Methodological, Elsevier, vol. 99(C), pages 167-182.
    8. Cook, Andrew & Tanner, Graham & Williams, Victoria & Meise, Gerhard, 2009. "Dynamic cost indexing – Managing airline delay costs," Journal of Air Transport Management, Elsevier, vol. 15(1), pages 26-35.
    9. Yang, Xin & Chen, Anthony & Ning, Bin & Tang, Tao, 2016. "A stochastic model for the integrated optimization on metro timetable and speed profile with uncertain train mass," Transportation Research Part B: Methodological, Elsevier, vol. 91(C), pages 424-445.
    10. Milind Sohoni & Yu-Ching Lee & Diego Klabjan, 2011. "Robust Airline Scheduling Under Block-Time Uncertainty," Transportation Science, INFORMS, vol. 45(4), pages 451-464, November.
    11. 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.
    12. 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.
    13. Shervin AhmadBeygi & Amy Cohn & Marcial Lapp, 2010. "Decreasing airline delay propagation by re-allocating scheduled slack," IISE Transactions, Taylor & Francis Journals, vol. 42(7), pages 478-489.
    14. Hanif D. Sherali & Xiaomei Zhu, 2008. "Two-Stage Fleet Assignment Model Considering Stochastic Passenger Demands," Operations Research, INFORMS, vol. 56(2), pages 383-399, April.
    15. 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.
    16. He, Qie & Zhang, Xiaochen & Nip, Kameng, 2017. "Speed optimization over a path with heterogeneous arc costs," Transportation Research Part B: Methodological, Elsevier, vol. 104(C), pages 198-214.
    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. Şafak, Özge & Çavuş, Özlem & Aktürk, M. Seli̇m, 2022. "A two-stage decision dependent stochastic approach for airline flight network expansion," Transportation Research Part B: Methodological, Elsevier, vol. 158(C), pages 78-101.
    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. Naz Yeti̇moğlu, Yücel & Selim Aktürk, M., 2021. "Aircraft and passenger recovery during an aircraft’s unexpected unavailability," Journal of Air Transport Management, Elsevier, vol. 91(C).
    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. Rajendran, Suchithra & Zack, Joshua, 2019. "Insights on strategic air taxi network infrastructure locations using an iterative constrained clustering approach," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 128(C), pages 470-505.
    6. Birolini, Sebastian & Jacquillat, Alexandre & Cattaneo, Mattia & Antunes, António Pais, 2021. "Airline Network Planning: Mixed-integer non-convex optimization with demand–supply interactions," Transportation Research Part B: Methodological, Elsevier, vol. 154(C), pages 100-124.
    7. Xiaoqian Sun & Sebastian Wandelt, 2021. "Robustness of Air Transportation as Complex Networks:Systematic Review of 15 Years of Research and Outlook into the Future," Sustainability, MDPI, vol. 13(11), pages 1-19, June.
    8. Ming Liu & Yueyu Ding & Lihua Sun & Runchun Zhang & Yue Dong & Zihan Zhao & Yiting Wang & Chaoran Liu, 2023. "Green Airline-Fleet Assignment with Uncertain Passenger Demand and Fuel Price," Sustainability, MDPI, vol. 15(2), pages 1-22, January.
    9. 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. 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.
    2. 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.
    3. 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.
    4. Keji Wei & Vikrant Vaze, 2020. "Airline Timetable Development and Fleet Assignment Incorporating Passenger Choice," Transportation Science, INFORMS, vol. 54(1), pages 139-163, January.
    5. 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.
    6. Kenan, Nabil & Jebali, Aida & Diabat, Ali, 2018. "The integrated aircraft routing problem with optional flights and delay considerations," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 118(C), pages 355-375.
    7. Aakil M. Caunhye & Xiaofeng Nie, 2018. "A Stochastic Programming Model for Casualty Response Planning During Catastrophic Health Events," Transportation Science, INFORMS, vol. 52(2), pages 437-453, March.
    8. Ming Liu & Yueyu Ding & Lihua Sun & Runchun Zhang & Yue Dong & Zihan Zhao & Yiting Wang & Chaoran Liu, 2023. "Green Airline-Fleet Assignment with Uncertain Passenger Demand and Fuel Price," Sustainability, MDPI, vol. 15(2), pages 1-22, January.
    9. Pilla, Venkata L. & Rosenberger, Jay M. & Chen, Victoria & Engsuwan, Narakorn & Siddappa, Sheela, 2012. "A multivariate adaptive regression splines cutting plane approach for solving a two-stage stochastic programming fleet assignment model," European Journal of Operational Research, Elsevier, vol. 216(1), pages 162-171.
    10. René Brandenberg & Paul Stursberg, 2021. "Refined cut selection for benders decomposition: applied to network capacity expansion problems," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 94(3), pages 383-412, December.
    11. 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.
    12. M. Selim Aktürk & Alper Atamtürk & Sinan Gürel, 2014. "Aircraft Rescheduling with Cruise Speed Control," Operations Research, INFORMS, vol. 62(4), pages 829-845, August.
    13. 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.
    14. Nathan Sudermann‐Merx & Steffen Rebennack & Christian Timpe, 2021. "Crossing Minimal Edge‐Constrained Layout Planning using Benders Decomposition," Production and Operations Management, Production and Operations Management Society, vol. 30(10), pages 3429-3447, October.
    15. N. Beheshti Asl & S. A. MirHassani, 2019. "Accelerating benders decomposition: multiple cuts via multiple solutions," Journal of Combinatorial Optimization, Springer, vol. 37(3), pages 806-826, April.
    16. Abdelghany, Ahmed & Guzhva, Vitaly S. & Abdelghany, Khaled, 2023. "The limitation of machine-learning based models in predicting airline flight block time," Journal of Air Transport Management, Elsevier, vol. 107(C).
    17. Wei Zhang & Kai Wang & Alexandre Jacquillat & Shuaian Wang, 2023. "Optimized Scenario Reduction: Solving Large-Scale Stochastic Programs with Quality Guarantees," INFORMS Journal on Computing, INFORMS, vol. 35(4), pages 886-908, July.
    18. Brueckner, Jan K. & Czerny, Achim I. & Gaggero, Alberto A., 2022. "Airline delay propagation: A simple method for measuring its extent and determinants," Transportation Research Part B: Methodological, Elsevier, vol. 162(C), pages 55-71.
    19. 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.
    20. Saldanha-da-Gama, Francisco, 2022. "Facility Location in Logistics and Transportation: An enduring relationship," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 166(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:eee:transb:v:114:y:2018:i:c:p:39-67. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/wps/find/journaldescription.cws_home/548/description#description .

    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.