带次模惩罚和随机需求的设施选址问题

运筹学学报 ›› 2013, Vol. 17 ›› Issue (2): 1-9.

• 运筹学 • 下一篇

带次模惩罚和随机需求的设施选址问题

王星¹，徐大川^2,*

1. 杭州电子科技大学理学院，杭州 310018 2. 北京工业大学数理学院，北京 100124

收稿日期:2012-05-10 出版日期:2013-06-15 发布日期:2013-06-15
通讯作者: 徐大川 E-mail:xudc@bjut.edu.cn

Facility location problem with submodular penalties and stochastic demands

WANG Xing¹, XU Dachuan^2,*

1. School of Science, Hangzhou Dianzi University, Hangzhou 310018, China 2. Department of Applied Mathematics, Beijing University of Technology, Beijing 100124, China

Received:2012-05-10 Online:2013-06-15 Published:2013-06-15
Supported by:
北京市教育委员会科技计划面上项目 (No. KM201210005033)

摘要/Abstract

摘要： 考虑带次模惩罚和随机需求的设施选址问题，目的是开设设施集合的一个子集，把客户连接到开设的设施上并对没有连接的客户进行惩罚，使得开设费用、连接费用、库存费用、管理费用和惩罚费用之和达到最小. 根据该问题的特殊结构，给出原始对偶3-近似算法. 在算法的第一步，构造了一组对偶可行解；在第二步中构造了对应的一组原始整数可行解，这组原始整数可行解给出了最后开设的设施集合和被惩罚的客户集合. 最后，证明了算法在多项式时间内可以完成，并且算法所给的整数解不会超过最优解的3倍.

关键词: 次模惩罚, 随机需求, 近似算法, 原始对偶算法

Abstract: In this paper, we consider the facility location problem with submodular penalties and stochastic demands. The objective is to open a subset of facilities, to connect a subset of clients to open facilities, and to penalize the remaining clients such that the total cost of opening cost, connection cost, inventory cost, handling cost and penalty cost is minimized. Based on the special structure of the problem, we propose a primal-dual 3-approximation algorithm. In the algorithm, we construct a dual feasible solution in the first step followed by constructing the corresponding primal integer feasible solution in the second step. This primal integer feasible solution indicates the final opening facility set and penalty client set. We prove that the proposed algorithm can be implemented in polynomial time and the cost of the incurred primal integer feasible solution is no more than 3 times of the optimal value.

Key words: submodular penalties, stochastic demands, approximation algorithm, primal-dual algorithm

中图分类号:

O221.7

王星，徐大川. 带次模惩罚和随机需求的设施选址问题[J]. 运筹学学报, 2013, 17(2): 1-9.

WANG Xing, XU Dachuan. Facility location problem with submodular penalties and stochastic demands[J]. Operations Research Transactions, 2013, 17(2): 1-9.

参考文献

Shmoys D B, Tardos E, Aardal K I. Approximation algorithms for facility location problems [C]//Proceedings of STOC, New York: Association for Computing Machinery, 1997, 265-274.
Li S. A 1. 488-approximation algorithm for the uncapacitated facility location problem [J]. Information and Computation, 2013, 222: 45-58.
Guha S, Khuller S. Greedy strike back: improved facility location algorithms [J]. Journal of Algorithms, 1999, 31: 228-248.
Charikar M, Khuller S, Mount D M, et al. Algorithms for facility location problems with outliers [C]//Proceedings of SODA, 2001, 642-651.
Xu G, Xu J. An LP rounding algorithm for approximating uncapacitated facility location problem with penalties [J]. Information Processing Letters, 2005, 94: 119-123.
Xu G, Xu J. An improved approximation algorithm for uncapacitated facility location problem with penalties [J]. Journal of Combinatorial Optimization, 2009, 17: 424-436.
Hayrapetyan A, Swamy C, Tardos E. Network design for information networks [C]//Proceedings of SODA, 2005, 933-942.
Chudak F A, Nagano K. Efficient solutions to relaxations of combinatorial problems with submodular penalties via the Lovasz extension and non-smooth covex optimization [C]//Proceedings of SODA, 2007, 79-88.
Du D, Lu R, Xu D. A primal-dual approximation algorithm for the facility location problem with submodular penalties [J]. Algorithmica, 2012, 63: 191-200.
Daskin M S, Coullard C R, Max Shen Z J. An inventory-location model: formulation, solution algorithm and computational results [J]. Annals of Operations Research, 2002, 110: 83-106.
Max Shen Z J, Coullard C R, Daskin M S. A joint location-inventory model [J]. Transportation Science, 2003, 37: 40-55.
Shu J, Teo C P, Max Shen Z J. Stochastic transportation-inventory network design problem [J]. Operations Research, 2005, 53: 48-60.
Li Y, Shu J, Wang X, Xiu N, Xu D, Zhang J. Approximation algorithms for integrated distribution network design problems [J]. INFORMS Journal on Computing, DOI: 10.1287/ijoc.1120.0522.
Jain K, Vazirani V V. Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation [J]. Journal of the ACM, 2001, 48: 274-296.
Fujishige S. Submodular functions and optimization (2nd ed.) [M]. Amsterdam: Elsevier, 2005.

[1]	张玉忠. 工件可拒绝排序问题综述[J]. 运筹学学报, 2020, 24(2): 111-130.
[2]	刘晓霞, 余山杉, 罗文昌. 工作有到达时间且拒绝工件总个数受限的单机平行分批排序问题的近似算法[J]. 运筹学学报, 2020, 24(1): 131-139.
[3]	王翼展, 张安, 陈永, 陈光亭. 堆取料机调度问题的一个近似算法[J]. 运筹学学报, 2020, 24(1): 147-154.
[4]	张国川, 陈林. 负载均衡问题[J]. 运筹学学报, 2019, 23(3): 1-14.
[5]	姜燕君, 徐大川, 张冬梅. 平方度量动态设施选址问题的近似算法[J]. 运筹学学报, 2018, 22(3): 49-58.
[6]	余善恩, 徐文洋, 刘光宇. 圆形区域分散布局问题研究[J]. 运筹学学报, 2018, 22(3): 132-138.
[7]	王一水, 徐大川, 吴晨晨. 关联聚类问题的半定规划舍入算法[J]. 运筹学学报, 2018, 22(1): 67-76.
[8]	陈光亭, 陈蕾, 张安, 陈永. 可转包两台流水作业机排序的近似算法[J]. 运筹学学报, 2016, 20(4): 109-114.
[9]	仲维亚, 马晓茹. 带有运输且加工具有灵活性的无等待流水作业排序问题[J]. 运筹学学报, 2016, 20(4): 93-101.
[10]	孙婷, 李改弟, 徐文青. 最大割问题和最大平分割问题基于半定规划松弛的近似算法[J]. 运筹学学报, 2016, 20(3): 21-32.
[11]	方芮, 罗文昌. 带惩罚的容错设施布局问题的近似算法[J]. 运筹学学报, 2016, 20(2): 69-78.
[12]	闫林成, 肖汉, 赵红娟, 孙小淇. 关于可靠性设施布局问题的近似算法[J]. 运筹学学报, 2015, 19(4): 14-24.
[13]	范静, 张峰. 具有多个不可用时间段的单机供应链排序问题[J]. 运筹学学报, 2015, 19(3): 116-122.
[14]	王颖, 王凤敏, 徐大川, 徐文青. 带次模惩罚的优先设施选址问题的近似算法[J]. 运筹学学报, 2015, 19(2): 1-14.
[15]	徐大川, 万玮, 吴晨晨, 徐文青. 随机容错设施选址问题的原始-对偶近似算法[J]. 运筹学学报, 2014, 18(2): 17-28.

带次模惩罚和随机需求的设施选址问题

Facility location problem with submodular penalties and stochastic demands

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价