运筹与管理2018，Vol.27Issue(4)：35-38,4.DOI:10.12005/orms.2018.0082
软容量约束带随机需求的设施选址问题的近似算法
Approximation Algorithm for the Facility Location Problem with Soft Capacities and Stochastic Demands
摘要
Abstract
In this paper,we consider the facility location problem with soft capacities and stochastic demands.In this problem,given the facility set and client set, each client has a stochastic demand, and each facility has a capacity but can be open more than once.The opening cost of each facility is fixed,and the connection cost be-tween each client and facility is also given.The objective is to open some facilities and connect each client to an open facility whose capacity can not be exceeded such that the total cost is minimized.For the facility location problem with soft capacities and stochastic demands,we design an approximation algorithm.First,we construct the corresponding uncapacitated facility location problem with stochastic demands for each capacity case.Sec-ond,We solve the uncapacitated facility location problem with stochastic demands and obtain a feasible solution. Third, we construct a feasible solution to the original problem.Finally, we analyze the running time of the algorithm.We prove that the approximation factor for the algorithm is 6.关键词
软容量约束带随机需求/近似算法/近似比Key words
soft capacities and stochastic demands/approximation algorithm/approximation factor分类
数理科学引用本文复制引用
王星,徐大川..软容量约束带随机需求的设施选址问题的近似算法[J].运筹与管理,2018,27(4):35-38,4.基金项目
国家自然科学基金项目(11531014) （11531014）
