[1]王晓峰,华盈盈,王军霞,等.k-center问题的算法研究综述[J].郑州大学学报(工学版),2025,46(01):42-50.[doi:10.13705/j.issn.1671-6833.2024.01.009]
　WANG Xiaofeng,HUA Yingying,WANG Junxia,et al.The Survey of Algorithms for k-center Problem[J].Journal of Zhengzhou University (Engineering Science),2025,46(01):42-50.[doi:10.13705/j.issn.1671-6833.2024.01.009]
点击复制

k-center问题的算法研究综述()
分享到：

《郑州大学学报(工学版)》[ISSN:1671-6833/CN:41-1339/T]

卷:
46
期数:
2025年01期
页码:
42-50
栏目:
出版日期:
2024-12-23

文章信息/Info

Title:
The Survey of Algorithms for k-center Problem
文章编号:
1671-6833(2025)01-0042-09
作者:
王晓峰1; 2;  华盈盈1;  王军霞1;  彭庆媛1;  何　飞1
1.北方民族大学 计算机科学与工程学院,宁夏 银川 750021;2.北方民族大学 图像图形智能处理国家民委重点实验室,宁夏 银川 750021
Author(s):
WANG Xiaofeng1; 2;  HUA Yingying1;  WANG Junxia1;  PENG Qingyuan1;  HE Fei1
1.School of Computer Science and Engineering, North Minzu University, Yinchuan 750021, China; 2.The Key Laboratory of Images and Graphics Intelligent Processing of State Ethnic Affairs Commission, North Minzu University, Yinchuan 750021, China
关键词:
k-center问题;  精确算法;  近似算法;  蜂群优化;  遗传算法
Keywords:
k-center problem;  exact algorithm;  approximation algorithm;  bee colony optimization algorithm;  genetic algorithm
分类号:
TP301
DOI:
10.13705/j.issn.1671-6833.2024.01.009
文献标志码:
A
摘要:
k-center问题是设施选址的基础问题,同样是NP难问题,在分配、紧急服务等领域也有着实际的应用。随着问题规模的扩大,原有的算法已不再适用,需要进一步优化或者改进。为了找到求解该问题的高效算法,对现有算法进行研究。对各类求解k-center问题的算法进行梳理,将求解算法划分为精确算法、启发式算法、元启发式算法、近似算法等,从算法原理、改进思路、性能和精度等方面进行对比综述。精确算法在求解小规模k-center问题时可在多项式时间内得到最优解,但是算法效率低,不适用于大规模问题;启发式算法可以在多项式时间内给出相对最优解,但是没有理论保证,无法衡量与最优解的关系;元启发式算法可对目前存在的智能优化算法进行改进,给出相对最优解,但是解的质量无法保证;利用近似算法得到的解具有近似比保证,有较大的理论研究价值,但是实用价值较弱。目前求解k-center问题的元启发式算法已取得一定的研究成果,但是在求解时间、求解规模、算法效率等方面仍待突破,这将是未来k-center问题的研究重点。
Abstract:
The k-center problem is fundamental in facility siting, and is also an NP-hard problem with practical applications in the fields of distribution, emergency services, etc. However, with the expansion of the problem scale, the original algorithms were no longer applicable and should be further optimized or improved. In order to find an efficient algorithm to solve the problem, the existing algorithms were studied. The algorithms for the k-center problem were classified into exact algorithms, heuristic algorithms, meta-heuristic algorithms, approximation algorithms, etc. The algorithms were compared in terms of their principles, ideas for improvement, performance, accuracy, etc. The exact algorithm obtained the optimal solution in polynomial time when solving small-scale k-center problems, but was inefficient and not applicable to large-scale problems. The heuristic algorithm could give the relative optimal solution in polynomial time, but there was no theoretical guarantee to measure the relationship with the most optimal solution. The meta-heuristic algorithm could be improved according to the existing intelligent optimization algorithms to give the relative optimal solution, but the quality of the solution could not be guaranteed. The solution obtained by using the approximation algorithm had the guarantee of the approximation ratio, which was of greater theoretical research value, but the practical value was weaker. At present, the meta-heuristic algorithm for solving the k-center problem achieved certain research results, but there were still breakthroughs in the solution time, solution scale and algorithm efficiency, which could be the focus of the future research on the k-center problem.

参考文献/References:

[1]KARIV O, HAKIMI S L. An algorithmic approach to network location problems. I: the p-centers[J]. SIAM Journal on Applied Mathematics, 1979, 37(3): 513-538. 

[2]DASKIN M. Network and discrete location: models, algorithms and applications[J]. Journal of the Operational Research Society, 1997, 48(7): 763-764. 
[3]ZHANG F Z, HE Y C, OUYANG H B, et al. A fast and efficient discrete evolutionary algorithm for the uncapacitated facility location problem[J]. Expert Systems with Applications, 2023, 213: 118978. 
[4]KAVEH A, NASR H. Solving the conditional and unconditional-center problem with modified harmony search: a real case study[J]. Scientia Iranica, 2011, 18(4): 867-877. 
[5]CONTARDO C, IORI M, KRAMER R. A scalable exact algorithm for the vertex p-center problem[J]. Computers & Operations Research, 2019, 103: 211-220. 
[6]GUI Z P, SUN Y Z, YANG L, et al. LSI-LSTM: an attention-aware LSTM for real-time driving destination prediction by considering location semantics and location importance of trajectory points[J]. Neurocomputing, 2021, 440: 72-88. 
[7]WANG S H, GAO S, FENG X, et al. A context-based geoprocessing framework for optimizing meetup location of multiple moving objects along road networks[J]. International Journal of Geographical Information Science, 2018, 32(7): 1368-1390. 
[8]ZHOU L, WANG S H, XU Z B. A multi-factor spatial optimization approach for emergency medical facilities in Beijing[J]. ISPRS International Journal of Geo-Information, 2020, 9(6): 361. 
[9]ZHU Y S, DU Q Y, TIAN F, et al. Location optimization using a hierarchical location-allocation model for trauma centers in Shenzhen, China[J]. ISPRS International Journal of Geo-Information, 2016, 5(10): 190. 
[10] HAN B, HU M X, ZHENG J M, et al. Site selection of fire stations in large cities based on actual spatiotemporal demands: a case study of Nanjing city[J]. ISPRS International Journal of Geo-Information, 2021, 10(8): 542. 
[11] FARAHANI R Z, HEKMATFAR M. Facility location: concepts, models, algorithms and case studies[M]. Heidelberg: Physica-Verlag HD, 2009. 
[12] HOCHBAUM D S, SHMOYS D B. A best possible heuristic for the k-center problem[J]. Mathematics of Operations Research, 1985, 10(2): 180-184. 
[13] DYER M E, FRIEZE A M. A simple heuristic for the pcentre problem[J]. Operations Research Letters, 1985, 3(6): 285-288. 
[14] PANIGRAHY R, VISHWANATHAN S. An O(log∗n) approximation algorithm for the asymmetric p-center problem[J]. Journal of Algorithms, 1998, 27(2): 259-268. 
[15] KHULLER S, SUSSMANN Y J. The capacitated K-center problem[J]. SIAM Journal on Discrete Mathematics, 2000, 13(3): 403-418. 
[16] BRASS P, KNAUER C, NA H S, et al. The aligned kcenter problem[J]. International Journal of Computational Geometry & Applications, 2011, 21(2): 157-178. 
[17] KHULLER S, PLESS R, SUSSMANN Y J. Fault tolerant K-center problems[J]. Theoretical Computer Science, 2000, 242(1/2): 237-245.
[18] LIM A, RODRIGUES B, WANG F, et al. k-center problems with minimum coverage[J]. Theoretical Computer Science, 2005, 332(1/2/3): 1-17. 
[19] XU Y, PENG J G, XU Y F. The mixed center location problem[J]. Journal of Combinatorial Optimization, 2018, 36(4): 1128-1144. 
[20] MINIEKA E. The m-center problem[J]. SIAM Review, 1970, 12(1): 138-139.
[21] DASKIN M S. A new approach to solving the vertex pcenter problem to optimality: algorithm and computational results[J]. Communications of the Operations Research Society of Japan, 2000, 45(9): 428-436. 
[22] ILHAN T, PINAR M C. An efficient exact algorithm for the vertex p-center problem[EB/OL]. (2001-09-27) [2023-12-30]. https:∥optimization-online. org/2001/09/376/ . 
[23] AL-KHEDHAIRI A, SALHI S. Enhancements to two exact algorithms for solving the vertex P-center problem [J]. Journal of Mathematical Modelling and Algorithms, 2005, 4(2): 129-147. 
[24] MLADENOVIC’ N, LABBÉ M, HANSEN P. Solving the p-center problem with tabu search and variable neighborhood search[J]. Networks, 2003, 42(1): 48-64. 
[25] PACHECO J A, CASADO S. Solving two location models with few facilities by using a hybrid heuristic: a real health resources case[J]. Computers & Operations Research, 2005, 32(12): 3075-3091. 
[26] GLOVER F. Future paths for integer programming and links to artificial intelligence[J]. Computers & Operations Research, 1986, 13(5): 533-549. 
[27] GLOVER F, LAGUNA M. Tabu search[M]. New York: Springer Science+Business Media, 1997. 
[28] LAGUNA M, MARTÍ R. Scatter search: methodology and implementations in C[J]. Interfaces, 2006, 36(6): 610-612. 
[29]蒋建林, 徐进澎, 文杰. 基于单亲遗传模拟退火算法的顶点p-中心问题[J]. 系统工程学报, 2011, 26 (3): 414-420. 
JIANG J L, XU J P, WEN J. Solving the vertex p-center problem with a partheno-genetic simulated annealing algorithm[J]. Journal of Systems Engineering, 2011, 26 (3): 414-420. 
[30] DAVIDOVIC’ T, RAMLJAK D, ŠELMIC’ M, et al. Bee colony optimization for the p-center problem[J]. Computers & Operations Research, 2011, 38(10): 1367-1376. 
[31] YURTKURAN A, EMEL E. A modified artificial bee colony algorithm for p-center problems[J]. The Scientific World Journal, 2014, 2014: 824196. 
[32]包敏泽, 胡秀婷, 谢玉莹, 等. 基于人工蜂群算法的p-center问题求解算法[J]. 计算机工程与科学, 2020, 42(6): 1127-1133. 
BAO M Z, HU X T, XIE Y Y, et al. A p-center problem solving algorithm based on artificial bee colony algorithm [J]. Computer Engineering and Science, 2020, 42(6): 1127-1133. 
[33] LUˇ CIC’ P, TEODOROVIC’ D. Bee system: modeling combinatorial optimization transportation engineering problems by swarm intelligence[C]∥The TRISTAN IV Triennial Symposium on Transportation Analysis. Sao Miguel: TRISTAN, 2001: 441-445. 
[34] LUˇ CIC’ P, TEODOROVIC’ D. Transportation modeling: an artificial life approach[C]∥14th IEEE International Conference on Tools with Artificial Intelligence(ICTAI 2002). Piscataway: IEEE, 2003: 216-223. 
[35] LUˇ CIC’ P, TEODOROVIC’ D. Computing with bees: attacking complex transportation engineering problems[J]. International Journal on Artificial Intelligence Tools, 2003, 12(3): 375-394. 
[36]王守娜, 刘弘, 高开周. 一种应用于函数优化问题的多种群人工蜂群算法[J]. 郑州大学学报(工学版), 2018, 39(6):30-35. 
WANG S N, LIU H, GAO K Z. A multi-swarm artificial bee colony algorithm for function optimization[J]. Journal of Zhengzhou University (Engineering Science), 2018, 39(6):30-35. 
[37]何尧, 刘建华, 杨荣华. 人工蜂群算法研究综述[J]. 计算机应用研究, 2018, 35(5): 1281-1286. 
HE Y, LIU J H, YANG R H. Survey on artificial bee colony algorithm[J]. Application Research of Computers, 2018, 35(5): 1281-1286. 
[38] RANA R, GARG D. The analytical study of k-center problem solving techniques[J]. International Journal of Information Technology and Knowledge Management, 2008, 1(2): 527-535. 
[39] SHMOYS D B. Computing near-optimal solutions to combinatorial optimization problems[M]∥DIMACS Series in Discrete Mathematics and Theoretical Computer Science. Providence: American Mathematical Society, 1995: 355397. 
[40] PLESNÍK J. A heuristic for the p-center problems in graphs[J]. Discrete Applied Mathematics, 1987, 17 (3): 263-268. 
[41] GONZALEZ T F. Clustering to minimize the maximum intercluster distance[J]. Theoretical Computer Science, 1985, 38: 293-306. 
[42] GARCIA-DIAZ J, SANCHEZ-HERNANDEZ J, MENCHACA-MENDEZ R, et al. When a worse approximation factor gives better performance: a 3-approximation algorithm for the vertex k-center problem[J]. Journal of Heuristics, 2017, 23(5): 349-366. 
[43] MIHELI ˇ C J, ROBI ˇ C B. Solving the k-center problem efficiently with a dominating set algorithm[J]. Journal of Computing and Information Technology, 2005, 13(3): 225-233.
[44] BEASLEY J E. OR-library: distributing test problems by electronic mail[J]. Journal of the Operational Research Society, 1990, 41(11): 1069-1072. 
[45] REINELT G. TSPLIB—A traveling salesman problem library[J]. ORSA Journal on Computing, 1991, 3(4): 376-384. 
[46] GARCIA-DIAZ J, MENCHACA-MENDEZ R, MENCHACA-MENDEZ R, et al. Approximation algorithms for the vertex k-center problem: survey and experimental evaluation[J]. IEEE Access, 2019, 7: 109228-109245.

更新日期/Last Update: 2024-12-30