Tabu Search Based GRASP Algorithm For The Vertex P-center Problem

As a classic NP hard problem put forward by Hakami in 1964, P-center problem has broad application prospects in the logistics facilities planning, communication network design, and location of the police station, hospital, fire station and other industries which have public service standards. Especially as the foundation of e-commerce, with the development of e-commerce the logistics industry, the P-center problem became more and more important. The facility location problem, which is the core of the logistics industry got widely studied by international scholars. As the basis of each type of location problem, p-center problem is a challenging topic and have great research value.There are three kinds of algorithm to solve a NP hard problem: the exact algorithm, the approximation algorithm and the heuristic algorithm. The exact algorithm can always give the optimal solution. But for the esponential complexity of the NP hard problem, it is almost not probably to get the optimal solution in a limited time for the exact algorithm when it comes to instance of big scale. Though approximation algorithm can limit the error between the worst solution and the optimal one in a certain range, but its efficiency can not always be satisfactory.The heuristic algorithm can always make a balance on the solution precision and the solution time, so it has become a popular algorithm which is widely researched by scholars. In this article, based on the local search in PBS-1 presented by Pullan, we proposed the tabu search based GRASP algorithm — TS&GRASP. In order to evaluate the effectiveness of the TS&GRASP, we do experiment on 148 standard benchmarks. The result shows that the TS&GRASP can get a better solution on 11 instances, and it can at least reach the previous solution got by PBS-1 on other instances. It worth to point that compared with PBS-1, our TS&GRASP has obvious improvement on solution time. The experimental results show that, compared to the best algorithm in the world,TS&GRASP is quite competitive on the solution of P-center problem.