In:
INFORMS Journal on Computing, Institute for Operations Research and the Management Sciences (INFORMS), Vol. 25, No. 3 ( 2013-08), p. 572-584
Abstract:
In this paper, we study approximation algorithms for two supply chain network design problems, namely, the warehouse-retailer network design problem (WRND) and the stochastic transportation-inventory network design problem (STIND). These two problems generalize the classical uncapacitated facility location problem by incorporating, respectively, the warehouse-retailer echelon inventory cost and the warehouse cycle inventory together with the safety stock costs. The WRND and the STIND were initially studied, respectively, by Teo and Shu (Teo CP, Shu J (2004) Warehouse-retailer network design problem. Oper. Res. 52(3):396–408) and Shu et al. (Shu J, Teo CP, Shen ZJM (2005) Stochastic transportation-inventory network design problem. Oper. Res. 53(1):48–60), where they are formulated as set-covering problems, and column-generation algorithms were used to solve their linear programming relaxations. Both problems can be regarded as special cases of the so-called facility location with submodular facility costs proposed by Svitkina and Tardos (Svitkina Z, Tardos É (2010) Facility location with hierarchical facility costs. ACM Trans. Algorithms 6(2), Article No. 37), for which only a logarithmic-factor approximation algorithm is known. Our main contribution is to obtain efficient constant-factor approximation algorithms for the WRND and the STIND, which are capable of solving large-scale instances of these problems efficiently.
Type of Medium:
Online Resource
ISSN:
1091-9856
,
1526-5528
DOI:
10.1287/ijoc.1120.0522
Language:
English
Publisher:
Institute for Operations Research and the Management Sciences (INFORMS)
Publication Date:
2013
detail.hit.zdb_id:
2070411-2
detail.hit.zdb_id:
2004082-9
SSG:
3,2
Permalink
