Tabu Search Based Tspr Heuristic Algorithm For The Vertex P-center Problem

The P-center problem is a classical NP-hard problem proposed by Hakami in 1964 which has wide application in the communications industry,public service, the logist ics industry, the Internet especially in public services, such as the siting of hospitals, courier service points, police station, fire station.The P-center problem has been gained comprehensive attention by the international scholars.NP-hard problem has the characteristics of multiple constraints, large-scale, mult iobjective and uncertainty and so on. There are three kinds of algorithms for this problem: accurate algorithm, approximation algorithm and heuristic algorithm.The complexity of the NP-hard problem is exponential, and accurate algorithm is fit for smal-scale problems.The P-center problem is a large-scale problem which can not be solved in polynomial time by accurate algorithm. Approximate algorithm can guarantee a solution in polynomial time which has a certain distance with the optimal solution, But it has been proven for NP- hard problem that the computing performance of heuristic algorithm is superior to the approximate algorithm for large-scale instances.On the basis of the PBS- 1 algorithm proposed by Pullan,I propose a TSPR algorit hm based on Tabu Search algorithm and Path Relinking algorithm. The core of the tabu search algorithm is double tabu algorithm. The experimental results show that this way of tabu search for the vast majority of small-scale instances have good effect in computing time and calculation result. Path Relinking algorithm is a kind of genetic algorithm which through the solution of two parents to establish a path, and then select a child from the path to start a new process of local search. To test the performance of TSPR algorithm, the test instances include two kinds of size which are large and small. Large-scale instances have three groups, each group has 15 examples respectively.Small-scale instances have 40 ORLIB instances and 11 sets of TSP instances. The experimental results compared with the most advanced algorithm for the P-center problem prove that TSPR have higher performance.