摘要
文考虑了软容量约束带随机需求的设施选址问题,根据此问题构造出一个无容量约束带随机需求的设施选址问题,通过求解无容量约束情形给出软容量情形的一个可行解,分析出近似比为6。
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.
作者
王星
徐大川
WANG Xing;XU Da-chuan(School of Science, Hangzhou Dianzi University, Hangzhou 310018, China;Department of Applied Mathematics, Beifing University of Technology, Beijing 100124, China)
出处
《运筹与管理》
CSSCI
CSCD
北大核心
2018年第4期35-38,共4页
Operations Research and Management Science
基金
国家自然科学基金项目(11531014)
关键词
软容量约束带随机需求
近似算法
近似比
soft capacities and stochastic demands
approximation algorithm
approximation factor
