IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v288y2020i1d10.1007_s10479-019-03469-8.html
   My bibliography  Save this article

Approximate dynamic programming for the military inventory routing problem

Author

Listed:
  • Rebekah S. McKenna

    (Air Force Institute of Technology)

  • Matthew J. Robbins

    (Air Force Institute of Technology)

  • Brian J. Lunday

    (Air Force Institute of Technology)

  • Ian M. McCormack

    (Air Force Institute of Technology)

Abstract

The United States Army can benefit from effectively utilizing cargo unmanned aerial vehicles (CUAVs) to perform resupply operations in combat environments to reduce the use of manned (ground and aerial) resupply that incurs risk to personnel. We formulate a Markov decision process (MDP) model of an inventory routing problem (IRP) with vehicle loss and direct delivery, which we label the military IRP (MILIRP). The objective of the MILIRP is to determine CUAV dispatching and routing policies for the resupply of geographically dispersed units operating in an austere, combat environment. The large size of the problem instance motivating this research renders dynamic programming algorithms inappropriate, so we utilize approximate dynamic programming (ADP) methods to attain improved policies (relative to a benchmark policy) via an approximate policy iteration algorithmic strategy utilizing least squares temporal differencing for policy evaluation. We examine a representative problem instance motivated by resupply operations experienced by the United States Army in Afghanistan both to demonstrate the applicability of our MDP model and to examine the efficacy of our proposed ADP solution methodology. A designed computational experiment enables the examination of selected problem features and algorithmic features vis-à-vis the quality of solutions attained by our ADP policies. Results indicate that a 4-crew, 8-CUAV unit is able to resupply 57% of the demand from an 800-person organization over a 3-month time horizon when using the ADP policy, a notable improvement over the 18% attained using a benchmark policy. Such results inform the development of procedures governing the design, development, and utilization of CUAV assets for the resupply of dispersed ground combat forces.

Suggested Citation

  • Rebekah S. McKenna & Matthew J. Robbins & Brian J. Lunday & Ian M. McCormack, 2020. "Approximate dynamic programming for the military inventory routing problem," Annals of Operations Research, Springer, vol. 288(1), pages 391-416, May.
  • Handle: RePEc:spr:annopr:v:288:y:2020:i:1:d:10.1007_s10479-019-03469-8
    DOI: 10.1007/s10479-019-03469-8
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10479-019-03469-8
    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/s10479-019-03469-8?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. Andrzej Ruszczyński, 2010. "Commentary ---Post-Decision States and Separable Approximations Are Powerful Tools of Approximate Dynamic Programming," INFORMS Journal on Computing, INFORMS, vol. 22(1), pages 20-22, February.
    2. 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.
    3. Davis, Michael T. & Robbins, Matthew J. & Lunday, Brian J., 2017. "Approximate dynamic programming for missile defense interceptor fire control," European Journal of Operational Research, Elsevier, vol. 259(3), pages 873-886.
    4. Anton J. Kleywegt & Vijay S. Nori & Martin W. P. Savelsbergh, 2004. "Dynamic Programming Approximations for a Stochastic Inventory Routing Problem," Transportation Science, INFORMS, vol. 38(1), pages 42-70, February.
    5. Anton J. Kleywegt & Vijay S. Nori & Martin W. P. Savelsbergh, 2002. "The Stochastic Inventory Routing Problem with Direct Deliveries," Transportation Science, INFORMS, vol. 36(1), pages 94-118, February.
    6. Maciejewski, Jan, 2010. "Social Change And Women In The Polish Army. Selected Sociological Aspects," Economic and Regional Studies (Studia Ekonomiczne i Regionalne), John Paul II University of Applied Sciences in Biala Podlaska, vol. 4(2).
    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. Rempel, M. & Cai, J., 2021. "A review of approximate dynamic programming applications within military operations research," Operations Research Perspectives, Elsevier, vol. 8(C).
    2. Liles, Joseph M. & Robbins, Matthew J. & Lunday, Brian J., 2023. "Improving defensive air battle management by solving a stochastic dynamic assignment problem via approximate dynamic programming," European Journal of Operational Research, Elsevier, vol. 305(3), pages 1435-1449.

    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. Jenkins, Phillip R. & Robbins, Matthew J. & Lunday, Brian J., 2021. "Approximate dynamic programming for the military aeromedical evacuation dispatching, preemption-rerouting, and redeployment problem," European Journal of Operational Research, Elsevier, vol. 290(1), pages 132-143.
    2. Cárdenas-Barrón, Leopoldo Eduardo & González-Velarde, José Luis & Treviño-Garza, Gerardo & Garza-Nuñez, Dagoberto, 2019. "Heuristic algorithm based on reduce and optimize approach for a selective and periodic inventory routing problem in a waste vegetable oil collection environment," International Journal of Production Economics, Elsevier, vol. 211(C), pages 44-59.
    3. Chih-Kang Lin & Shangyao Yan & Fei-Yen Hsiao, 2021. "Optimal Inventory Level Control and Replenishment Plan for Retailers," Networks and Spatial Economics, Springer, vol. 21(1), pages 57-83, March.
    4. Yugang Yu & Chengbin Chu & Haoxun Chen & Feng Chu, 2012. "Large scale stochastic inventory routing problems with split delivery and service level constraints," Annals of Operations Research, Springer, vol. 197(1), pages 135-158, August.
    5. Sayarshad, Hamid R. & Gao, H. Oliver, 2018. "A non-myopic dynamic inventory routing and pricing problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 109(C), pages 83-98.
    6. Mirzapour Al-e-hashem, Seyed M.J. & Rekik, Yacine & Mohammadi Hoseinhajlou, Ebrahim, 2019. "A hybrid L-shaped method to solve a bi-objective stochastic transshipment-enabled inventory routing problem," International Journal of Production Economics, Elsevier, vol. 209(C), pages 381-398.
    7. Oğuz Solyalı & Jean-François Cordeau & Gilbert Laporte, 2012. "Robust Inventory Routing Under Demand Uncertainty," Transportation Science, INFORMS, vol. 46(3), pages 327-340, August.
    8. Liles, Joseph M. & Robbins, Matthew J. & Lunday, Brian J., 2023. "Improving defensive air battle management by solving a stochastic dynamic assignment problem via approximate dynamic programming," European Journal of Operational Research, Elsevier, vol. 305(3), pages 1435-1449.
    9. Alejandro Toriello & George Nemhauser & Martin Savelsbergh, 2010. "Decomposing inventory routing problems with approximate value functions," Naval Research Logistics (NRL), John Wiley & Sons, vol. 57(8), pages 718-727, December.
    10. Michelle Blom & Slava Shekh & Don Gossink & Tim Miller & Adrian R Pearce, 2020. "Inventory routing for defense: Moving supplies in adversarial and partially observable environments," The Journal of Defense Modeling and Simulation, , vol. 17(1), pages 55-81, January.
    11. Jeffrey W. Ohlmann & Michael J. Fry & Barrett W. Thomas, 2008. "Route Design for Lean Production Systems," Transportation Science, INFORMS, vol. 42(3), pages 352-370, August.
    12. Bertazzi, Luca & Chua, Geoffrey A. & Laganà, Demetrio & Paradiso, Rosario, 2022. "Analysis of effective sets of routes for the split-delivery periodic inventory routing problem," European Journal of Operational Research, Elsevier, vol. 298(2), pages 463-477.
    13. Song, Ruidian & Zhao, Lei & Van Woensel, Tom & Fransoo, Jan C., 2019. "Coordinated delivery in urban retail," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 126(C), pages 122-148.
    14. Yves Crama & Mahmood Rezaei & Martin Savelsbergh & Tom Van Woensel, 2018. "Stochastic Inventory Routing for Perishable Products," Transportation Science, INFORMS, vol. 52(3), pages 526-546, June.
    15. Lars Magnus Hvattum & Arne Løkketangen & Gilbert Laporte, 2009. "Scenario Tree-Based Heuristics for Stochastic Inventory-Routing Problems," INFORMS Journal on Computing, INFORMS, vol. 21(2), pages 268-285, May.
    16. Daniel Adelman, 2004. "A Price-Directed Approach to Stochastic Inventory/Routing," Operations Research, INFORMS, vol. 52(4), pages 499-514, August.
    17. Ali Ekici & Okan Örsan Özener & Gültekin Kuyzu, 2015. "Cyclic Delivery Schedules for an Inventory Routing Problem," Transportation Science, INFORMS, vol. 49(4), pages 817-829, November.
    18. Markov, Iliya & Bierlaire, Michel & Cordeau, Jean-François & Maknoon, Yousef & Varone, Sacha, 2018. "A unified framework for rich routing problems with stochastic demands," Transportation Research Part B: Methodological, Elsevier, vol. 114(C), pages 213-240.
    19. Leandro C. Coelho & Jean-François Cordeau & Gilbert Laporte, 2014. "Thirty Years of Inventory Routing," Transportation Science, INFORMS, vol. 48(1), pages 1-19, February.
    20. Jin-Hwa Song & Martin Savelsbergh, 2007. "Performance Measurement for Inventory Routing," Transportation Science, INFORMS, vol. 41(1), pages 44-54, February.

    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:annopr:v:288:y:2020:i:1:d:10.1007_s10479-019-03469-8. 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.