Greedy Randomized Adaptive Search Procedure with Path-Relinking for the Vertex p-Center Problem  

作　　者：Ai-Hua Yin Tao-Qing Zhou Jun-Wen Ding Qing-Jie Zhao Zhi-Peng Lv 

机构地区：[1]School of Software and Communication Engineering, Jiangxi University of Finance and Economics Nanchang 330013, China [2]School of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan 430074, China [3]Department of Computer Science, School of Information Engineering, Zhejiang Agriculture and Forestry University Hangzhou 311300, China

出　　处：《Journal of Computer Science & Technology》2017年第6期1319-1334,共16页计算机科学技术学报（英文版）

基　　金：The research was supported by the National Natural Science Foundation of China under Grant Nos. 61370183 and 61262011.

摘　　要：The p-center problem consists of choosing a subset of vertices in an undirected graph as facilities in order to minimize the maximum distance between a client and its closest facility. This paper presents a greedy randomized adaptive search procedure with path-relinking （GRASP/PR） algorithm for the p-center problem, which combines both GRASP and path-relinking. Each iteration of GRASP/PR consists of the construction of a randomized greedy solution, followed by a tabu search procedure. The resulting solution is combined with one of the elite solutions by path-relinking, which consists in exploring trajectories that connect high-quality solutions. Experiments show that GRASP/PR is competitive with the state-of-the-art algorithms in the literature in terms of both solution quality and computational efficiency. Specifically, it virtually improves the previous best known results for 10 out of 40 large instances while matching the best known results for others.The p-center problem consists of choosing a subset of vertices in an undirected graph as facilities in order to minimize the maximum distance between a client and its closest facility. This paper presents a greedy randomized adaptive search procedure with path-relinking （GRASP/PR） algorithm for the p-center problem, which combines both GRASP and path-relinking. Each iteration of GRASP/PR consists of the construction of a randomized greedy solution, followed by a tabu search procedure. The resulting solution is combined with one of the elite solutions by path-relinking, which consists in exploring trajectories that connect high-quality solutions. Experiments show that GRASP/PR is competitive with the state-of-the-art algorithms in the literature in terms of both solution quality and computational efficiency. Specifically, it virtually improves the previous best known results for 10 out of 40 large instances while matching the best known results for others.

关 键 词：p-center problem tabu search PATH-RELINKING facility location 

分 类 号：TP0[自动化与计算机技术]