鲁棒动态设施选址问题的近似算法

doi:10.12005/orms.2020.0119

运筹与管理 ›› 2020, Vol. 29 ›› Issue (5): 61-66.DOI: 10.12005/orms.2020.0119

鲁棒动态设施选址问题的近似算法

吴晨晨^1,2, 王丽³, 徐春明², 徐大川³

1.南开大学商学院,天津 300371;
2.天津理工大学理学院,天津 300384;
3.北京工业大学数学学院,北京 100124

收稿日期:2020-01-13 出版日期:2020-05-25
作者简介:吴晨晨(1986-),女,安徽人,博士后,副教授,研究方向:组合优化,近似算法等;王丽(1996-),女,山东人,硕士研究生,研究方向:组合优化,近似算法等;徐春明(1980-),男,满族,河北人,博士,讲师,研究方向:物流与供应链管理、库存模型及其优化等,通讯作者;徐大川(1969-),男,山东人,博士,教授,北京工业大学,博士生导师,研究方向:组合优化,近似算法等。
基金资助:
国家自然科学基金资助项目(11971349,11871081);教育部人文社会科学研究基金(19YJC630188)

Approximation Algorithm for the Robust Dynamic Facility Location Problem

WU Chen-chen^1,2, WANG Li³, XU Chun-ming², XU Da-chuan³

1. Business School, Nankai University, Tianjin, 30007, China;
2. College of Science, Tianjin University of Technology,Tianjin 300384, China;
3. College of Mathematics, Beijing University of Technology, Beijing 100124, China

Received:2020-01-13 Online:2020-05-25

摘要/Abstract

摘要： 设施选址问题是组合优化中重要问题之一。动态设施选址问题是传统设施选址问题的推广,其中度量空间中设施的开设费用和顾客的需求均随着时间的变化而变化。更多地,经典设施选址问题假设所有的顾客都需要被服务。在这个模型假设下,所有的顾客都需要服务。但事实上,有时为服务距离较远的顾客,需要单独开设设施,导致了资源的浪费。因此,在模型设置中,可以允许一些固定数目的顾客不被服务 (带异常点的设施选址问题),此外也可以通过支付一些顾客的惩罚费用以达到不服务的目的 (带惩罚的设施选址问题)。本文将综合以上两种鲁棒设置考虑同时带有异常点和惩罚的动态设施选址问题,通过原始-对偶框架得到近似比为3的近似算法。

关键词: 动态设施选址问题, 近似算法, 原始对偶算法

Abstract: The facility location problem is one of the important problems in combinatorial optimization. The dynamic facility location problem is a generalization of the classic facility location problem in which the open cost of the facilities and the demand of the clients change over time. Moreover, the classic facility location problem always assumes that all clients need to be served. A shortcoming of the model is that it does not consider a few very distant clients. To serve these clients, some facilities need to be open to serve them only. This is not good for using the facilities resource. Thus, in the setting of the model, it is allowable that a constant number of clients can be not served (which is called the facility location problem with outliers). On the other hand, it is also allowable to pay penalty cost for not serving some clients (which is called the facility location problem with penalties). In this paper, we combine the above robust setting to consider the facility location problem with penalties and outliers for which we propose a 3-approximation algorithm.

Key words: dynamic facility location problem, approximation algorithm, primal-dual algorithm

中图分类号:

O221.7

吴晨晨, 王丽, 徐春明, 徐大川. 鲁棒动态设施选址问题的近似算法[J]. 运筹与管理, 2020, 29(5): 61-66.

WU Chen-chen, WANG Li, XU Chun-ming, XU Da-chuan. Approximation Algorithm for the Robust Dynamic Facility Location Problem[J]. Operations Research and Management Science, 2020, 29(5): 61-66.

参考文献

[1] Arya V, Garg N, Khandekar R, Meyerson A, Munagala K, Pandit V. Local search heuristics for k-median and facility location problems[J]. SIAMJournal on Computing, 2004, 33: 544-562.
[2] Charikar M, Khuller S, Mount D M, Narasimhan G. Algorithms for facility location problems with outliers[ ]. In Proceedings of 12th annual ACM-SIAM Symposium on Discrete Algorithms, 2001. 642-651.
[3] Cohen-Addad V, Klein P, Mathieu C. Local search yields approximation schemes for k-Means and k-median in Euclidean and minor-free metrics[ ]. In Proceedings of 57th IEEE Annual Symposium on Foundations of Computer Science, 2016. 353-364.
[4] 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.
[5] Feng Q, Zhang Z, Huang Z, Xu J, Wang J. Improved Algorithms for Clustering with Outliers. In Proceedings of 30th International Symposium on Algorithms and Computation. 2019, article 61.
[6] Guha S, Khuller S, Greedy strike back: Improved facility location algorithms[J]. Journal of Algorithms, 1999, 31: 228-248.
[7] Gupta S, Kumar R, Lu K, Moseley B, Vassilvitskii S. Local search methods for k-means with outliers[J]. Proceedings of the VLDB Endowment, 2017, 10: 757-768.
[8] Geunes J, Levi R, Romeijn H E, Shmoys D B. Approximation algorithms for supply chain planning and logistics problems with market choice[J]. Mathematical Programming, 2011, 130: 85-106.
[9] Hayrapetyan A, Swamy C, Tardos E. Network design for information networks. In Proceedings of the 16th annual ACM-SIAM Symposium on Discrete Algorithms, 2005. 933-942.
[10] Jain K, Mahdian M, Markakis E, Saberi S, Vazirani V V. Greedy facility location algorithms analyzed using dual fifitting with factor-revealing LP[J]. Journal of the ACM, 2003, 50: 795-824.
[11] 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.
[12] Jiang Y, Xu D, Du D, Zhang D. An approximation algorithm for the dynamic facility location problem with outliers[J]. Optimization Letters, 2019, 13: 561-571.
[13] Jiang C, Xu D. An approximation algorithm for the dynamic facility location problem with penalties[J]. Acta Mathematicae Applicatae Sinica, 2009, 6: 5.
[14] Krishnaswamy R, Li S, Sandeep S. Constant approximation for k-median and k-means with outliers via iterative rounding[J]. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of ComputingJune, 2018. 646-659.
[15] Li S, A 1. 488-approximation algorithm for the uncapacitated facility location problem[J]. Information and Computation, 2013, 222: 45-58.
[16] Li Y, Du D, Xiu N, Xu D. A combinatorial 2.375-approximation algorithm for the facility location problem with submodular penalties[J]. Theoretical Computer Science, 2013, 476: 109-117.
[17] Li Y, Du D, Xiu N, and Xu D. Improved approximation algorithms for the facility location problems with linear/submodular penalty[J]. Algorithmica, 2015, 13: 561-571.
[18] Shmoys D B, Tardos E, Aardal K I, Approximation algorithms for facility location problems[J]. In Proceedings of 29th annual ACM symposium on Theory of computing, 1997. 265-274.
[19] Xu G, Xu J. An LP rounding algorithm for approximating uncapacitated facility location problem with penalties[J]. Information Processing Letters, 2005, 94: 119-123.
[20] Ye Y, Zhang J W, An approximation algorithm for the dynamic facility location problem[J]. In: Cheng, M.X., Li, Y., Du, D-Z. (eds.) Combinatorial Optimization in Communication Networks, Springer, US, 2006. 623-637.
[21] Zanjirani F R, Hekmatfar M. Facility location: concepts, models, algorithms and Case Studies[M]. Physica, Heidelberg, 2009.

鲁棒动态设施选址问题的近似算法

Approximation Algorithm for the Robust Dynamic Facility Location Problem

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 7

编辑推荐

Metrics

[1]	井彩霞, 吴瑞强, 贾兆红. 并行分批排序综述[J]. 运筹与管理, 2020, 29(1): 223-239.
[2]	王星, 徐大川. 软容量约束带随机需求的设施选址问题的近似算法[J]. 运筹与管理, 2018, 27(4): 35-38.
[3]	包晓光, 刘朝晖, 余炜. 线形网络上单台车辆分群调度问题[J]. 运筹与管理, 2017, 26(5): 125-129.
[4]	余海燕, 申成然, 符证菘. 周期性需求的供应商配送排程优化研究[J]. 运筹与管理, 2016, 25(6): 83-90.
[5]	余英, 舒彤, 曾春花. 工件带简单线性恶化函数和共同交货期单机排序问题[J]. 运筹与管理, 2016, 25(1): 154-157.
[6]	苏兵, 张萌, 姬浩. 应急救援物资紧缺的配送车辆路径选择研究[J]. 运筹与管理, 2013, 22(6): 57-64.
[7]	汪磊扬. 考虑常数客户批运输的单机排序问题[J]. 运筹与管理, 2013, 22(5): 29-34.