? 带路径重连的GRASP算法求解p-center问题
Journal of Computer Science and Technology
Quick Search in JCST
 Advanced Search 
      Home | PrePrint | SiteMap | Contact Us | Help
 
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 << Previous Articles | >>
带路径重连的GRASP算法求解p-center问题
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
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

摘要
参考文献
相关文章
Download: [PDF 825KB]  
摘要 p-center问题是在无向图的顶点集合中选择一个子集作为设备点,其余点为客户点,使得客户点与其最近的设备点的最大距离最小化。本文提出带路径重连的GRASP算法(GRASP/PR)来求解p-center问题。该方法结合了GRASP和路径重连。GRASP/PR的每次迭代过程由随机贪心的构造算法和禁忌算法组成。得到的解与优质解集中的一个解进行路径重连,用来搜素路径中的高质量的解。实验结果表明,GRASP/PR和当前文献中的优秀算法在解的质量和效率上具有可比性。特别是,它改进了40个大算例中的10个算例的已知最好解,并与其它的算例的最好解持平。
关键词p-center问题   禁忌搜索   路径重连   设备选址     
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.
Keywordsp-center problem   tabu search   path-relinking   facility location     
Received 2016-08-29;
本文基金:

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

通讯作者: 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.
引用本文:   
Ai-Hua Yin, Tao-Qing Zhou, Jun-Wen Ding, Qing-Jie Zhao, Zhi-Peng Lv.带路径重连的GRASP算法求解p-center问题[J]  Journal of Computer Science and Technology , 2017,V32(6): 1319-1333
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
链接本文:  
http://jcst.ict.ac.cn:8080/jcst/CN/10.1007/s11390-017-1802-3
Copyright 2010 by Journal of Computer Science and Technology