IDEAS home Printed from https://ideas.repec.org/a/spr/orspec/v42y2020i1d10.1007_s00291-019-00571-y.html
   My bibliography  Save this article

Enhancing Benders decomposition algorithm to solve a combat logistics problem

Author

Listed:
  • Mohammad Marufuzzaman

    (Mississippi State University)

  • Farjana Nur

    (Mississippi State University)

  • Amy E. Bednar

    (U.S. Army Engineer Research and Development Center)

  • Mark Cowan

    (U.S. Army Engineer Research and Development Center)

Abstract

This paper proposes a multi-time period, two-stage stochastic programming model for the design and management of a typical combat logistics problem. The design shall minimize the total path setup cost, commodity preposition and processing costs, and expected transportation, storage, and shortage costs across all possible path failure scenarios. Due to the complexity associated with solving the model, we propose an accelerated Benders decomposition algorithm to solve the model in a realistic-size network problem within a reasonable amount of time. The Benders decomposition algorithm incorporates several algorithmic improvements such as pareto-optimal cuts, multi-cuts, knapsack inequalities, integer cuts, input ordering, mean-value cuts, and the rolling horizon heuristic. Computational experiments are performed to assess the efficiency of different enhancement techniques within the Benders decomposition algorithm.

Suggested Citation

  • Mohammad Marufuzzaman & Farjana Nur & Amy E. Bednar & Mark Cowan, 2020. "Enhancing Benders decomposition algorithm to solve a combat logistics problem," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 42(1), pages 161-198, March.
    • Handle: RePEc:spr:orspec:v:42:y:2020:i:1:d:10.1007_s00291-019-00571-y
    DOI: 10.1007/s00291-019-00571-y
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s00291-019-00571-y
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s00291-019-00571-y?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. Schütz, Peter & Tomasgard, Asgeir & Ahmed, Shabbir, 2009. "Supply chain design under uncertainty using sample average approximation and dual decomposition," European Journal of Operational Research, Elsevier, vol. 199(2), pages 409-419, December.
    2. 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.
    3. Gerald G. Brown & W. Matthew Carlyle, 2008. "Optimizing the US Navy's combat logistics force," Naval Research Logistics (NRL), John Wiley & Sons, vol. 55(8), pages 800-810, December.
    4. Georgiadis, Michael C. & Tsiakis, Panagiotis & Longinidis, Pantelis & Sofioglou, Maria K., 2011. "Optimal design of supply chain networks under uncertain transient demand variations," Omega, Elsevier, vol. 39(3), pages 254-272, June.
    5. Crainic, Teodor G. & Rousseau, Jean-Marc, 1986. "Multicommodity, multimode freight transportation: A general modeling and algorithmic framework for the service network design problem," Transportation Research Part B: Methodological, Elsevier, vol. 20(3), pages 225-242, June.
    6. T. L. Magnanti & R. T. Wong, 1984. "Network Design and Transportation Planning: Models and Algorithms," Transportation Science, INFORMS, vol. 18(1), pages 1-55, February.
    7. Rettke, Aaron J. & Robbins, Matthew J. & Lunday, Brian J., 2016. "Approximate dynamic programming for the dispatch of military medical evacuation assets," European Journal of Operational Research, Elsevier, vol. 254(3), pages 824-839.
    8. Overholts II, Dale L. & Bell, John E. & Arostegui, Marvin A., 2009. "A location analysis approach for military maintenance scheduling with geographically dispersed service areas," Omega, Elsevier, vol. 37(4), pages 838-852, August.
    9. Sakine Batun & Brian T. Denton & Todd R. Huschka & Andrew J. Schaefer, 2011. "Operating Room Pooling and Parallel Surgery Processing Under Uncertainty," INFORMS Journal on Computing, INFORMS, vol. 23(2), pages 220-237, May.
    10. Ji Ren & Xiao-lei Zheng & Yue-jin Tan, 2013. "Multi-product Supply Planning for Combat Units in Battlefield Environment," Springer Books, in: Ershi Qi & Jiang Shen & Runliang Dou (ed.), The 19th International Conference on Industrial Engineering and Engineering Management, edition 127, chapter 0, pages 445-453, Springer.
    11. Dmitry Tsadikovich & Eugene Levner & Hanan Tell & Frank Werner, 2016. "Integrated demand-responsive scheduling of maintenance and transportation operations in military supply chains," International Journal of Production Research, Taylor & Francis Journals, vol. 54(19), pages 5798-5810, October.
    12. Santoso, Tjendera & Ahmed, Shabbir & Goetschalckx, Marc & Shapiro, Alexander, 2005. "A stochastic programming approach for supply chain network design under uncertainty," European Journal of Operational Research, Elsevier, vol. 167(1), pages 96-115, November.
    13. Hunkar Toyoglu & Oya Ekin Karasan & Bahar Yetis Kara, 2011. "Distribution network design on the battlefield," Naval Research Logistics (NRL), John Wiley & Sons, vol. 58(3), pages 188-209, April.
    14. Birge, John R. & Louveaux, Francois V., 1988. "A multicut algorithm for two-stage stochastic linear programs," European Journal of Operational Research, Elsevier, vol. 34(3), pages 384-392, March.
    Full references (including those not matched with items on IDEAS)

    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. Aghalari, Amin & Nur, Farjana & Marufuzzaman, Mohammad, 2020. "A Bender’s based nested decomposition algorithm to solve a stochastic inland waterway port management problem considering perishable product," International Journal of Production Economics, Elsevier, vol. 229(C).
    2. Halit Üster & Sung Ook Hwang, 2017. "Closed-Loop Supply Chain Network Design Under Demand and Return Uncertainty," Transportation Science, INFORMS, vol. 51(4), pages 1063-1085, November.
    3. Bhuiyan, Tanveer Hossain & Medal, Hugh R. & Harun, Sarah, 2020. "A stochastic programming model with endogenous and exogenous uncertainty for reliable network design under random disruption," European Journal of Operational Research, Elsevier, vol. 285(2), pages 670-694.
    4. Farahani, Reza Zanjirani & Rezapour, Shabnam & Drezner, Tammy & Fallah, Samira, 2014. "Competitive supply chain network design: An overview of classifications, models, solution techniques and applications," Omega, Elsevier, vol. 45(C), pages 92-118.
    5. Sahling, Florian & Kayser, Ariane, 2016. "Strategic supply network planning with vendor selection under consideration of risk and demand uncertainty," Omega, Elsevier, vol. 59(PB), pages 201-214.
    6. Fattahi, Mohammad & Govindan, Kannan & Keyvanshokooh, Esmaeil, 2017. "Responsive and resilient supply chain network design under operational and disruption risks with delivery lead-time sensitive customers," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 101(C), pages 176-200.
    7. Ben Mohamed, Imen & Klibi, Walid & Sadykov, Ruslan & Şen, Halil & Vanderbeck, François, 2023. "The two-echelon stochastic multi-period capacitated location-routing problem," European Journal of Operational Research, Elsevier, vol. 306(2), pages 645-667.
    8. 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.
    9. Sushil R. Poudel & Md Abdul Quddus & Mohammad Marufuzzaman & Linkan Bian & Reuben F. Burch V, 2019. "Managing congestion in a multi-modal transportation network under biomass supply uncertainty," Annals of Operations Research, Springer, vol. 273(1), pages 739-781, February.
    10. Kiya, Farhad & Davoudpour, Hamid, 2012. "Stochastic programming approach to re-designing a warehouse network under uncertainty," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 48(5), pages 919-936.
    11. Mohammaddust, Faeghe & Rezapour, Shabnam & Farahani, Reza Zanjirani & Mofidfar, Mohammad & Hill, Alex, 2017. "Developing lean and responsive supply chains: A robust model for alternative risk mitigation strategies in supply chain designs," International Journal of Production Economics, Elsevier, vol. 183(PC), pages 632-653.
    12. 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.
    13. Contreras, Ivan & Cordeau, Jean-François & Laporte, Gilbert, 2011. "Stochastic uncapacitated hub location," European Journal of Operational Research, Elsevier, vol. 212(3), pages 518-528, August.
    14. Vahab Vahdat & Mohammad Ali Vahdatzad, 2017. "Accelerated Benders’ Decomposition for Integrated Forward/Reverse Logistics Network Design under Uncertainty," Logistics, MDPI, vol. 1(2), pages 1-21, December.
    15. Poudel, Sushil Raj & Marufuzzaman, Mohammad & Bian, Linkan, 2016. "A hybrid decomposition algorithm for designing a multi-modal transportation network under biomass supply uncertainty," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 94(C), pages 1-25.
    16. Govindan, Kannan & Fattahi, Mohammad, 2017. "Investigating risk and robustness measures for supply chain network design under demand uncertainty: A case study of glass supply chain," International Journal of Production Economics, Elsevier, vol. 183(PC), pages 680-699.
    17. Kabli, Mohannad & Quddus, Md Abdul & Nurre, Sarah G. & Marufuzzaman, Mohammad & Usher, John M., 2020. "A stochastic programming approach for electric vehicle charging station expansion plans," International Journal of Production Economics, Elsevier, vol. 220(C).
    18. Sarmadi, Kamran & Amiri-Aref, Mehdi & Dong, Jing-Xin & Hicks, Christian, 2020. "Integrated strategic and operational planning of dry port container networks in a stochastic environment," Transportation Research Part B: Methodological, Elsevier, vol. 139(C), pages 132-164.
    19. S. Ayca Erdogan & Brian Denton, 2013. "Dynamic Appointment Scheduling of a Stochastic Server with Uncertain Demand," INFORMS Journal on Computing, INFORMS, vol. 25(1), pages 116-132, February.
    20. Baghalian, Atefeh & Rezapour, Shabnam & Farahani, Reza Zanjirani, 2013. "Robust supply chain network design with service level against disruptions and demand uncertainties: A real-life case," European Journal of Operational Research, Elsevier, vol. 227(1), pages 199-215.

    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:spr:orspec:v:42:y:2020:i:1:d:10.1007_s00291-019-00571-y. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.