Approximation Algorithms for Integrated Distribution Network Design Problems

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 l...

Full description

Saved in:
Bibliographic Details
Published in:INFORMS journal on computing 2013-06, Vol.25 (3), p.572-584
Main Authors: Li, Yu, Shu, Jia, Wang, Xi, Xiu, Naihua, Xu, Dachuan, Zhang, Jiawei
Format: Article
Language:English
Subjects:
Algorithms
Approximation
approximation algorithm
Approximation theory
Costs
Distributed network protocols
facility location
Industrial locations
Inventory
Linear programming
Methods
Stochastic models
Studies
supply chain network design
Supply chains
Traffic flow
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1091-9856
1526-5528
1091-9856
DOI:10.1287/ijoc.1120.0522