? Greedy Randomized Adaptive Search Procedure with Path-Relinking for the Vertex <em>p</em>-Center Problem
Journal of Computer Science and Technology
Quick Search in JCST
 Advanced Search 
      Home | PrePrint | SiteMap | Contact Us | FAQ
 
Indexed by   SCIE, EI ...
Bimonthly    Since 1986
Journal of Computer Science and Technology 2017, Vol. 32 Issue (6) :1319-1333    DOI: 10.1007/s11390-017-1802-3
Regular Paper Current Issue | Archive | Adv Search << Previous Articles | >>
Greedy Randomized Adaptive Search Procedure with Path-Relinking for the Vertex p-Center Problem
Ai-Hua Yin1, Member, CFF, Tao-Qing Zhou2,3, Jun-Wen Ding2,*, Qing-Jie Zhao2, Zhi-Peng Lv2
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

Abstract
Reference
Related Articles
Download: [PDF 825KB]     Export: BibTeX or EndNote (RIS)  
Abstract 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.
Articles by authors
Keywordsp-center problem   tabu search   path-relinking   facility location     
Received 2016-08-29;
Fund:

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

Corresponding Authors: Jun-Wen Ding     Email: dingjunwen@hust.edu.cn
About author: Ai-Hua Yin received his Ph.D.degree in computer science and technology from Huazhong University of Science and Technology,Wuhan,in 2003.Currently,he is a senior researcher at Jiangxi University of Finance and Economics,Nanchang.His research interests include job shop scheduling problem,rectangular packing problem and p-center problem.Dr.Yin is a member of CCF.
Cite this article:   
Ai-Hua Yin, Tao-Qing Zhou, Jun-Wen Ding, Qing-Jie Zhao, Zhi-Peng Lv.Greedy Randomized Adaptive Search Procedure with Path-Relinking for the Vertex p-Center Problem[J]  Journal of Computer Science and Technology, 2017,V32(6): 1319-1333
URL:  
http://jcst.ict.ac.cn:8080/jcst/EN/10.1007/s11390-017-1802-3
Copyright 2010 by Journal of Computer Science and Technology