Please use this identifier to cite or link to this item:
|Title:||Approximation algorithms for general one-warehouse multi-retailer systems|
|Source:||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. https://doi.org/10.1002/nav.20367|
|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|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Mar 7, 2018
WEB OF SCIENCETM
checked on Jan 31, 2018
checked on Mar 11, 2018
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.