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

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

【期刊名称】《计算机科学技术学报（英文版）》 【年(卷),期】2017(032)006

【摘要】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. 【总页数】16页(1319-1334) 【关键词】

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

【作者单位】School of Software and Communication Engineering, Jiangxi University of Finance and Economics Nanchang 330013, China;School of Computer Science and Technology, Huazhong University

of

Science

and

Technology,

Wuhan

430074,

China;Department of Computer Science, School of Information Engineering, Zhejiang Agriculture and Forestry University Hangzhou 311300, China;School of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan 430074, China;School of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan 430074, China;School of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan 430074, China 【正文语种】英文 【中图分类】 【文献来源】

https://www.zhangqiaokeyan.com/academic-journal-cn_journal-computer-science-technology_thesis/0201241194841.html 【相关文献】

1.Solving the constrained shortest path problem using random search strategy [J],

2.Optimized quantum random-walk search algorithm for multi-solution search [J], 张宇超; 鲍皖苏; 汪翔; 付向群

3.Toward path reliability by using adaptive multi-path routing mechanism for multimedia service in mobile Ad-hoc network [J], ZHEN Yan; WU Mu-qing; WU Da-peng; ZHANG Qin-juan; XU Chun-xiu 4.Meta-Path-Based Search and Mining in Heterogeneous Information Networks [J], Yizhou Sun; Jiawei Han

5.Molecular path for ligand search [J], Tao Lu; Yuan Yuan Qiao; Pan Wen Shen

以上内容为文献基本信息，获取文献全文请下载