Approximate dynamic programming for the military inventory routing problem

被引:9
|
作者
McKenna, Rebekah S. [1 ]
Robbins, Matthew J. [1 ]
Lunday, Brian J. [1 ]
McCormack, Ian M. [1 ]
机构
[1] Air Force Inst Technol, Dept Operat Sci, 2950 Hobson Way, Wright Patterson AFB, OH 45433 USA
关键词
Inventory routing problem; Markov decision processes; Approximate dynamic programming; Least squares temporal differences; Military;
D O I
10.1007/s10479-019-03469-8
中图分类号
C93 [管理学]; O22 [运筹学];
学科分类号
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要
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-a-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.
引用
收藏
页码:391 / 416
页数:26
相关论文
共 50 条
  • [41] Markov decision process and approximate dynamic programming for a patient assignment scheduling problem
    O'Reilly, Malgorzata M.
    Krasnicki, Sebastian
    Montgomery, James
    Heydar, Mojtaba
    Turner, Richard
    Van Dam, Pieter
    Maree, Peter
    ANNALS OF OPERATIONS RESEARCH, 2025,
  • [42] Approximate dynamic programming for an energy-efficient parallel machine scheduling problem
    Heydar, Mojtaba
    Mardaneh, Elham
    Loxton, Ryan
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2022, 302 (01) : 363 - 380
  • [43] A Matheuristic Algorithm for the Inventory Routing Problem
    Su, Zhouxing
    Lu, Zhipeng
    Wang, Zhuo
    Qi, Yanmin
    Benlic, Una
    TRANSPORTATION SCIENCE, 2020, 54 (02) : 330 - 354
  • [44] The Inventory Routing Problem with Demand Moves
    Baller A.C.
    Dabia S.
    Desaulniers G.
    Dullaert W.E.H.
    Operations Research Forum, 2 (1)
  • [45] CAR: heuristics for the inventory routing problem
    Ramkumar Nambirajan
    Abraham Mendoza
    Subramanian Pazhani
    T. T. Narendran
    K. Ganesh
    Wireless Networks, 2020, 26 : 5783 - 5808
  • [46] The inventory-routing problem with transshipment
    Coelho, Leandro C.
    Cordeau, Jean-Francois
    Laporte, Gilbert
    COMPUTERS & OPERATIONS RESEARCH, 2012, 39 (11) : 2537 - 2548
  • [47] Inventory Routing Problem with Facility Location
    Jiao, Yang
    Ravi, R.
    ALGORITHMS AND DATA STRUCTURES, WADS 2019, 2019, 11646 : 452 - 465
  • [48] A memetic algorithm for the inventory routing problem
    Sakhri, Mohamed Salim Amri
    Tlili, Mounira
    Korbaa, Ouajdi
    JOURNAL OF HEURISTICS, 2022, 28 (03) : 351 - 375
  • [49] Evolutionary Approach in Inventory Routing Problem
    Simic, Dragan
    Simic, Svetlana
    ADVANCES IN COMPUTATIONAL INTELLIGENCE, PT II, 2013, 7903 : 395 - +
  • [50] A memetic algorithm for the inventory routing problem
    Mohamed Salim Amri Sakhri
    Mounira Tlili
    Ouajdi Korbaa
    Journal of Heuristics, 2022, 28 : 351 - 375