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 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 (2004) and Shu et al. (2005), 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 (2010) 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.