Decomposition‐based approximation algorithms for the one‐warehouse multi‐retailer problem with concave batch order costs. (31st July 2020)

• Record Type: Journal Article
• Authors: Hu, Weihong; Yu, Zhuoting; Toriello, Alejandro; Dessouky, Maged M.
• Is Part Of: Naval research logistics. Volume 67:Number 7(2020)
• Page Start: 503
• Page End: 523
• Publication Date: 2020-07-31
• Subjects: decomposition heuristic -- multi‐echelon inventory control -- one‐warehouse multi‐retailer; Logistics, Naval -- Periodicals; Supplies and stores -- Periodicals; 359.07
• DOI: 10.1002/nav.21927
• Languages: English
• ISSNs: 0894-069X

Abstract

Abstract: We study the one‐warehouse multi‐retailer problem under deterministic dynamic demand and concave batch order costs, where order batches have an identical capacity and the order cost function for each facility is concave within the batch. Under appropriate assumptions on holding cost structure, we obtain lower bounds via a decomposition that splits the two‐echelon problem into single‐facility subproblems, then propose approximation algorithms by judiciously recombining the subproblem solutions. For piecewise linear concave batch order costs with a constant number of slopes we obtain a constant‐factor approximation, while for general concave batch costs we propose an approximation within a logarithmic factor of optimality. We also extend some results to subadditive order and/or holding costs.