Approximation Algorithms For Stochastic Multi-level Facility Location Problem With Soft Capacities

Facility location problem is a classical combinatorial optimization problem,which has important research value in many fields,such as network design,communication technology,data mining,and so on.It also has been widely applied in our real life.For example,the construction of the fifth-generation communication base station,the location selection of "mobile cabin hospital" and the location decision-making of industrial park can be solved by the facility location model.It is a NP-Hard problem so there is no effective way to find the exact optimal solution in polynomial time.Therefore,we usually solve this kind of problem with the help of approximation algorithms.In recent years,the research on approximation algorithms for location problem has become an important research direction in the field of combinatorial optimization.In this thesis,we mainly study the stochastic multi-level facility location problem with soft capacities(SMLFLPSC),which is a kind of comprehensive deformation of facility location problem under the condition of limited facility service resources,complex customer demand and uncertain information.Among them,soft capacity means that there is an upper bound on the service resources that each facility can provide,but each facility can acquire multiple capacities by paying multiple opening cost;Multi-level means that customers need to be assigned to a path which is consisted of multi-level opening facilities.The stochastic setting means that the customer demand information is uncertain before locating,which leads to the whole location process is stochastic.Comparing with the classical facility location problem,assumptions for this problem are more consistent with actual situation,so researching on this problem has more important practical significance.Firstly,we introduce the stochastic multi-level facility location problem with soft capacities and give its linear programming model.In this case,we reduce the SMLFLPSC to the stochastic multi-level facility location problem(SMLFLP)by the bi-factor reduction technique,and obtain the relationship of approximation ratios between these two problems.Then,we propose a simple {1/?,1+(4/(1-2?))}-approximation algorithm with setting the parameter ??{0,1/2}for SMLFLP based on the LP-rounding technique.By combining this algorithm with the reduction process,the 10.0105-approximation algorithm for the SMLFLPSC is obtained.Finally,we also conduct numerical experimentation to show the validity and feasibility of the approximation algorithm.