Study On Warehouse Location With Submodularity

The thesis investigates a series of warehouse location problems with submodular-ity, including warehouse location problem with submodular operation cost, warehouse location problem with submodular penalty cost and warehouse location problem with submodular operation cost and penalty cost. We disign approximation algorithms for those problems respectively and the approximation ratios of our algorithms for all the problems we studied are the best so far.In Chapter1, we introduce some related basic knowledge, specific issues, relative backgrounds of the research and our results.In Chapter2, we study two warehouse location problems with submodular oper-ation cost, namely, the warehouse-retailer network design (WRND) problem and the stochastic transportation-inventory network design (STIND) problem. These two prob-lems generalize the classical uncapacitated facility location problem by incorporating, respectively, the warehouse-retailer echelon inventory cost and the warehouse cycle in-ventory together with the safety stock costs. Our main contribution is to obtain two3-approximation algorithms for the WRND and the STIND, which are capable of solv-ing large-scale instances of these problems efficiently.In Chapter3, we study warehouse location problem with submodular penalties (WLPSP) and introduce a general algorithmic framework that leverages existing approximation re-sults for the traditional models to obtain corresponding results for their counterpart mod-els with submodular penalties. More specifically, any rounding-based a-approximation for the traditional model can be leveraged to a (1-e-1/α)-approximation algorithm for the counterpart model with submodular penalties. With exploiting the special prop-erties, for WLPSP we can improve the approximation ratio from2.044to2, and for the more special case——warehouse location problem with linear penalties (WLPLP), we present a1.5148-approximation algorithm, which offer the currently best approximation ratios, respectively.In Chapter4, we continued to study WLPSP and offer the a combinatorial approxi-mation algorithm with currently best approximation ratio2.375, which improves not only the previous best combinatorial ratio3, but also the previous best non-combinatorial ra-tio2.488. We achieve this improved ratio by combining the primal-dual scheme with the greedy augmentation technique.In Chapter5, we propose and study the warehoues-retailer network design problem with submodular penalties (WRNDSP). In this problem, we might not choose to serve some retailers at the cost of paying a penalty cost which is assumed to be a non-decreasing nonnegative submodular function. We propose a primal-dual approximation algorithm with a performance factor of3for this problem.