The k-center problem is fundamental in facility siting,and is also an NP-hard problem with practical ap-plications 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 prob-lem were classified into exact algorithms,heuristic algorithms,meta-heuristic algorithms,approximation algo-rithms,etc. The algorithms were compared in terms of their principles,ideas for improvement,performance,accu-racy,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 opti-mization 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 prob-lem.
万方数据
维普
