IDEAS home Printed from https://ideas.repec.org/a/eee/jaitra/v90y2021ics0969699720305226.html
   My bibliography  Save this article

A matheuristic approach to the air-cargo recovery problem under demand disruption

Author

Listed:
  • Delgado, Felipe
  • Mora, Julio

Abstract

Air cargo transport is subject to unpredictable changes in expected demand, necessitating adjustments to itinerary planning to recover from such disruptions. We study a flight rescheduling problem to react to cargo demand disruptions in the short run. To increase flexibility, we consider two different cargo assignment policies. We propose a matheuristic approach to solve the problem that provides high-quality solutions in a short computational time, based on column generation in which each subproblem is solved using an ad-hoc heuristic. The approach is tested on demand disruption instances containing up to 75 air cargo orders with different penalty levels. The results show that the proposed method improves profit by 54% over the solution generated by a commercial MIP solver within a 1-h time limit, and by 15% over the solution with the routes fixed as in the original flight planning that only allows cargo to be re-routed. We also show that there exist incremental benefits in the range of 3–5% by allowing cargo for a given order to be transported by various aircraft.

Suggested Citation

  • 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).
  • Handle: RePEc:eee:jaitra:v:90:y:2021:i:c:s0969699720305226
    DOI: 10.1016/j.jairtraman.2020.101939
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0969699720305226
    Download Restriction: Full text for ScienceDirect subscribers only

    File URL: https://libkey.io/10.1016/j.jairtraman.2020.101939?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. Dumas, Yvan & Desrosiers, Jacques & Soumis, Francois, 1991. "The pickup and delivery problem with time windows," European Journal of Operational Research, Elsevier, vol. 54(1), pages 7-22, September.
    2. Maximilian M. Etschmaier & Dennis F. X. Mathaisel, 1985. "Airline Scheduling: An Overview," Transportation Science, INFORMS, vol. 19(2), pages 127-138, May.
    3. Chunhua Gao & Ellis Johnson & Barry Smith, 2009. "Integrated Airline Fleet and Crew Robust Planning," Transportation Science, INFORMS, vol. 43(1), pages 2-16, February.
    4. Stefan Ropke & David Pisinger, 2006. "An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows," Transportation Science, INFORMS, vol. 40(4), pages 455-472, November.
    5. Brian Rexing & Cynthia Barnhart & Tim Kniker & Ahmad Jarrah & Nirup Krishnamurthy, 2000. "Airline Fleet Assignment with Time Windows," Transportation Science, INFORMS, vol. 34(1), pages 1-20, February.
    6. Tiaojun Xiao & Jia Luo & Jiao Jin, 2009. "Coordination of a Supply Chain with Demand Stimulation and Random Demand Disruption," International Journal of Information Systems and Supply Chain Management (IJISSCM), IGI Global, vol. 2(1), pages 1-15, January.
    7. Matthew E. Berge & Craig A. Hopperstad, 1993. "Demand Driven Dispatch: A Method for Dynamic Aircraft Capacity Assignment, Models and Algorithms," Operations Research, INFORMS, vol. 41(1), pages 153-168, February.
    8. Stefan Ropke & Jean-François Cordeau, 2009. "Branch and Cut and Price for the Pickup and Delivery Problem with Time Windows," Transportation Science, INFORMS, vol. 43(3), pages 267-286, August.
    9. Qi, Xiangtong & Bard, Jonathan F. & Yu, Gang, 2004. "Supply chain coordination with demand disruptions," Omega, Elsevier, vol. 32(4), pages 301-312, August.
    10. George B. Dantzig & Philip Wolfe, 1960. "Decomposition Principle for Linear Programs," Operations Research, INFORMS, vol. 8(1), pages 101-111, February.
    11. Roy E. Marsten & Michael R. Muller, 1980. "A Mixed-Integer Programming Approach to Air Cargo Fleet Planning," Management Science, INFORMS, vol. 26(11), pages 1096-1107, November.
    12. Xiao, Tiaojun & Qi, Xiangtong & Yu, Gang, 2007. "Coordination of supply chain after demand disruptions when retailers compete," International Journal of Production Economics, Elsevier, vol. 109(1-2), pages 162-179, September.
    13. Mikkel Sigurd & David Pisinger & Michael Sig, 2004. "Scheduling Transportation of Live Animals to Avoid the Spread of Diseases," Transportation Science, INFORMS, vol. 38(2), pages 197-209, May.
    14. Tang, Ching-Hui & Yan, Shangyao & Chen, Yu-Hsuan, 2008. "An integrated model and solution algorithms for passenger, cargo, and combi flight scheduling," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 44(6), pages 1004-1024, November.
    15. Yan, Shangyao & Chen, Shin-Chin & Chen, Chia-Hung, 2006. "Air cargo fleet routing and timetable setting with multiple on-time demands," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 42(5), pages 409-430, September.
    16. Amos Levin, 1971. "Scheduling and Fleet Routing Models for Transportation Systems," Transportation Science, INFORMS, vol. 5(3), pages 232-255, August.
    17. João P. Pita & Cynthia Barnhart & António P. Antunes, 2013. "Integrated Flight Scheduling and Fleet Assignment Under Airport Congestion," Transportation Science, INFORMS, vol. 47(4), pages 477-492, November.
    18. Cynthia Barnhart & Peter Belobaba & Amedeo R. Odoni, 2003. "Applications of Operations Research in the Air Transport Industry," Transportation Science, INFORMS, vol. 37(4), pages 368-391, November.
    19. Delgado, Felipe & Sirhan, Cristóbal & Katscher, Mathias & Larrain, Homero, 2020. "Recovering from demand disruptions on an air cargo network," Journal of Air Transport Management, Elsevier, vol. 85(C).
    20. 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.
    21. Ulrich Derigs & Stefan Friederichs & Simon Schäfer, 2009. "A New Approach for Air Cargo Network Planning," Transportation Science, INFORMS, vol. 43(3), pages 370-380, August.
    22. Manoj Lohatepanont & Cynthia Barnhart, 2004. "Airline Schedule Planning: Integrated Models and Algorithms for Schedule Design and Fleet Assignment," Transportation Science, INFORMS, vol. 38(1), pages 19-32, February.
    23. Zhang, Dong & Yu, Chuhang & Desai, Jitamitra & Lau, H.Y.K. Henry, 2016. "A math-heuristic algorithm for the integrated air service recovery," Transportation Research Part B: Methodological, Elsevier, vol. 84(C), pages 211-236.
    24. Jean-François Cordeau, 2006. "A Branch-and-Cut Algorithm for the Dial-a-Ride Problem," Operations Research, INFORMS, vol. 54(3), pages 573-586, June.
    25. Lin, Cheng-Chang & Chen, Yin-Chieh, 2003. "The integration of Taiwanese and Chinese air networks for direct air cargo services," Transportation Research Part A: Policy and Practice, Elsevier, vol. 37(7), pages 629-647, August.
    26. Jamili, Amin, 2017. "A robust mathematical model and heuristic algorithms for integrated aircraft routing and scheduling, with consideration of fleet assignment problem," Journal of Air Transport Management, Elsevier, vol. 58(C), pages 21-30.
    27. Hu, Yuzhen & Song, Yan & Zhao, Kang & Xu, Baoguang, 2016. "Integrated recovery of aircraft and passengers after airline operation disruption based on a GRASP algorithm," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 87(C), pages 97-112.
    28. Jay M. Rosenberger & Ellis L. Johnson & George L. Nemhauser, 2003. "Rerouting Aircraft for Airline Recovery," Transportation Science, INFORMS, vol. 37(4), pages 408-421, November.
    29. 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.
    30. Masato Wada & Felipe Delgado & Bernardo K. Pagnoncelli, 2017. "A risk averse approach to the capacity allocation problem in the airline cargo industry," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 68(6), pages 643-651, June.
    31. Cynthia Barnhart & Ellis L. Johnson & George L. Nemhauser & Martin W. P. Savelsbergh & Pamela H. Vance, 1998. "Branch-and-Price: Column Generation for Solving Huge Integer Programs," Operations Research, INFORMS, vol. 46(3), pages 316-329, June.
    32. Chen, Kebing & Xiao, Tiaojun, 2009. "Demand disruption and coordination of the supply chain with a dominant retailer," European Journal of Operational Research, Elsevier, vol. 197(1), pages 225-234, August.
    33. 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.
    34. N Jozefowiez & C Mancel & F Mora-Camino, 2013. "A heuristic approach based on shortest path problems for integrated flight, aircraft, and passenger rescheduling under disruptions," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 64(3), pages 384-395, March.
    35. M. W. P. Savelsbergh & M. Sol, 1995. "The General Pickup and Delivery Problem," Transportation Science, INFORMS, vol. 29(1), pages 17-29, February.
    36. Rivi Sandhu & Diego Klabjan, 2006. "Fleeting with Passenger and Cargo Origin-Destination Booking Control," Transportation Science, INFORMS, vol. 40(4), pages 517-528, November.
    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. 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.
    2. Huang, Lei & Xiao, Fan & Zhou, Jing & Duan, Zhenya & Zhang, Hua & Liang, Zhe, 2023. "A machine learning based column-and-row generation approach for integrated air cargo recovery problem," Transportation Research Part B: Methodological, Elsevier, vol. 178(C).
    3. Ku, Edward C.S., 2022. "Developing business process agility: Evidence from inter-organizational information systems of airlines and travel agencies," Journal of Air Transport Management, Elsevier, vol. 103(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. Delgado, Felipe & Sirhan, Cristóbal & Katscher, Mathias & Larrain, Homero, 2020. "Recovering from demand disruptions on an air cargo network," Journal of Air Transport Management, Elsevier, vol. 85(C).
    2. 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.
    3. João P. Pita & Cynthia Barnhart & António P. Antunes, 2013. "Integrated Flight Scheduling and Fleet Assignment Under Airport Congestion," Transportation Science, INFORMS, vol. 47(4), pages 477-492, November.
    4. Huang, Lei & Xiao, Fan & Zhou, Jing & Duan, Zhenya & Zhang, Hua & Liang, Zhe, 2023. "A machine learning based column-and-row generation approach for integrated air cargo recovery problem," Transportation Research Part B: Methodological, Elsevier, vol. 178(C).
    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. Liu, Ran & Xie, Xiaolan & Augusto, Vincent & Rodriguez, Carlos, 2013. "Heuristic algorithms for a vehicle routing problem with simultaneous delivery and pickup and time windows in home health care," European Journal of Operational Research, Elsevier, vol. 230(3), pages 475-486.
    7. 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.
    8. Stefan Ropke & Jean-François Cordeau, 2009. "Branch and Cut and Price for the Pickup and Delivery Problem with Time Windows," Transportation Science, INFORMS, vol. 43(3), pages 267-286, August.
    9. 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.
    10. Delgado, Felipe & Trincado, Ricardo & Pagnoncelli, Bernardo K., 2019. "A multistage stochastic programming model for the network air cargo allocation under capacity uncertainty," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 131(C), pages 292-307.
    11. Birolini, Sebastian & Antunes, António Pais & Cattaneo, Mattia & Malighetti, Paolo & Paleari, Stefano, 2021. "Integrated flight scheduling and fleet assignment with improved supply-demand interactions," Transportation Research Part B: Methodological, Elsevier, vol. 149(C), pages 162-180.
    12. 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.
    13. Liu, Mengyang & Luo, Zhixing & Lim, Andrew, 2015. "A branch-and-cut algorithm for a realistic dial-a-ride problem," Transportation Research Part B: Methodological, Elsevier, vol. 81(P1), pages 267-288.
    14. Xue, Li & Luo, Zhixing & Lim, Andrew, 2016. "Exact approaches for the pickup and delivery problem with loading cost," Omega, Elsevier, vol. 59(PB), pages 131-145.
    15. 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.
    16. Hou, Liwen & Li, Dong & Zhang, Dali, 2018. "Ride-matching and routing optimisation: Models and a large neighbourhood search heuristic," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 118(C), pages 143-162.
    17. Veaceslav Ghilas & Jean-François Cordeau & Emrah Demir & Tom Van Woensel, 2018. "Branch-and-Price for the Pickup and Delivery Problem with Time Windows and Scheduled Lines," Transportation Science, INFORMS, vol. 52(5), pages 1191-1210, October.
    18. Schaumann, Sarah K. & Bergmann, Felix M. & Wagner, Stephan M. & Winkenbach, Matthias, 2023. "Route efficiency implications of time windows and vehicle capacities in first- and last-mile logistics," European Journal of Operational Research, Elsevier, vol. 311(1), pages 88-111.
    19. Hua, Shijia & Zeng, Wenjia & Liu, Xinglu & Qi, Mingyao, 2022. "Optimality-guaranteed algorithms on the dynamic shared-taxi problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 164(C).
    20. Yuan Qu & Jonathan F. Bard, 2015. "A Branch-and-Price-and-Cut Algorithm for Heterogeneous Pickup and Delivery Problems with Configurable Vehicle Capacity," Transportation Science, INFORMS, vol. 49(2), pages 254-270, May.

    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:jaitra:v:90:y:2021:i:c:s0969699720305226. 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.journals.elsevier.com/journal-of-air-transport-management/ .

    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.