File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Approximation algorithms for general one-warehouse multi-retailer systems

TitleApproximation algorithms for general one-warehouse multi-retailer systems
Authors
KeywordsInventory planning
Network flow
Approximation algorithms
Issue Date2009
Citation
Naval Research Logistics, 2009, v. 56, n. 7, p. 642-658 How to Cite?
AbstractLogistical 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.
Persistent Identifierhttp://hdl.handle.net/10722/296054
ISSN
2021 Impact Factor: 1.806
2020 SCImago Journal Rankings: 0.665
ISI Accession Number ID

 

DC FieldValueLanguage
dc.contributor.authorShen, Zuo Jun Max-
dc.contributor.authorShu, Jia-
dc.contributor.authorSimchi-Levi, David-
dc.contributor.authorTeo, Chung Piaw-
dc.contributor.authorZhang, Jiawei-
dc.date.accessioned2021-02-11T04:52:44Z-
dc.date.available2021-02-11T04:52:44Z-
dc.date.issued2009-
dc.identifier.citationNaval Research Logistics, 2009, v. 56, n. 7, p. 642-658-
dc.identifier.issn0894-069X-
dc.identifier.urihttp://hdl.handle.net/10722/296054-
dc.description.abstractLogistical 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.-
dc.languageeng-
dc.relation.ispartofNaval Research Logistics-
dc.subjectInventory planning-
dc.subjectNetwork flow-
dc.subjectApproximation algorithms-
dc.titleApproximation algorithms for general one-warehouse multi-retailer systems-
dc.typeArticle-
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1002/nav.20367-
dc.identifier.scopuseid_2-s2.0-70349604128-
dc.identifier.volume56-
dc.identifier.issue7-
dc.identifier.spage642-
dc.identifier.epage658-
dc.identifier.eissn1520-6750-
dc.identifier.isiWOS:000270263200004-
dc.identifier.issnl0894-069X-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats