Premium
Decomposition‐based approximation algorithms for the one‐warehouse multi‐retailer problem with concave batch order costs
Author(s) -
Hu Weihong,
Yu Zhuoting,
Toriello Alejandro,
Dessouky Maged M.
Publication year - 2020
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/nav.21927
Subject(s) - subadditivity , mathematical optimization , piecewise linear function , logarithm , constant (computer programming) , order (exchange) , concave function , piecewise , function (biology) , decomposition , mathematics , holding cost , approximation algorithm , computer science , economics , combinatorics , mathematical analysis , ecology , geometry , finance , regular polygon , evolutionary biology , biology , programming language
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.