Please use this identifier to cite or link to this item:
Title: Approximation algorithms for general one-warehouse multi-retailer systems
Authors: Shen, Z.-J.M.
Shu, J.
Simchi-Levi, D.
Teo, C.-P. 
Zhang, J.
Keywords: Approximation algorithms
Inventory planning
Network flow
Issue Date: 2009
Citation: Shen, Z.-J.M., Shu, J., Simchi-Levi, D., Teo, C.-P., Zhang, J. (2009). Approximation algorithms for general one-warehouse multi-retailer systems. Naval Research Logistics 56 (7) : 642-658. ScholarBank@NUS Repository.
Abstract: Logistical planning problems are complicated in practice because planners have to deal with the challenges of demand planning and supply replenishment, while taking into account the issues of (i) inventory perishability and storage charges, (ii) management of backlog and/or lost sales, and (iii) cost saving opportunities due to economies of scale in order replenishment and transportation. It is therefore not surprising that many logistical planning problems are computationally difficult, and finding a good solution to these problems necessitates the development of many ad hoc algorithmic procedures to address various features of the planning problems. In this article, we identify simple conditions and structural properties associated with these logistical planning problems in which the warehouse is managed as a cross-docking facility. Despite the nonlinear cost structures in the problems, we show that a solution that is within ε-optimality can be obtained by solving a related piece-wise linear concave cost multi-commodity network flow problem. An immediate consequence of this result is that certain classes of logistical planning problems can be approximated by a factor of (1 + ε) in polynomial time. This significantly improves upon the results found in literature for these classes of problems. We also show that the piece-wise linear concave cost network flow problem can be approximated to within a logarithmic factor via a large scale linear programming relaxation. We use polymatroidal constraints to capture the piece-wise concavity feature of the cost functions. This gives rise to a unified and generic LP-based approach for a large class of complicated logistical planning problems. © 2009 Wiley Periodicals, Inc.
Source Title: Naval Research Logistics
ISSN: 0894069X
DOI: 10.1002/nav.20367
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.


checked on Mar 30, 2020


checked on Mar 30, 2020

Page view(s)

checked on Mar 31, 2020

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.