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 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.
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
 Kariv O, Hakimi S L. An algorithmic approach to network location problems. I:The p-centers. SIAM Journal on Applied Mathematics, 1979, 37(3):513-538. Kariv O, Hakimi S L. An algorithmic approach to network location problems. Ⅱ:The p-medians. SIAM Journal on Applied Mathematics, 1979, 37(3):539-560. Hakimi S L. Optimum locations of switching centers and the absolute centers and medians of a graph. Operations Research, 1964, 12(3):450-459. Minieka E. The m-center problem. SIAM Review, 1970, 12(1):138-139. Daskin M S. Network and Discrete Location:Models Algorithms and Applications. John Wiley & Sons, 1995. Daskin M S. A new approach to solving the vertex p-center problem to optimality:Algorithm and computational results. Communications of the Operations Research Society of Japan, 2000, 45(9):428-436. Ilhan T, Pinar M C. An efficient exact algorithm for the vertex p-center problem. http://www.optimizationonline.org/DBHTML/2001/09/376.html, June 2017. Elloumi S, Labbé M, Pochet Y. A new formulation and resolution method for the p-center problem. INFORMS Journal on Computing, 2004, 16(1):84-94. Al-Khedhairi A, Salhi S. Enhancements to two exact algorithms for solving the vertex p-center problem. Journal of Mathematical Modelling and Algorithms, 2005, 4(2):129-147. Hochbaum D S, Shmoys D B. A best possible heuristic for the k-center problem. Mathematics of Operations Research, 1985, 10(2):180-184. Martinich J S. A vertex-closing approach to the p-center problem. Naval Research Logistics, 1988, 35(2):185-201. Plesník J. A heuristic for the p-center problems in graphs. Discrete Applied Mathematics, 1987, 17(3):263-268. Mladenovi? N, Labbé M, Hansen P. Solving the p-center problem with tabu search and variable neighborhood search. Networks, 2003, 42(1):48-64. Hassin R, Levin A, Morad D. Lexicographic local search and the p-center problem. European Journal of Operational Research, 2003, 151(2):265-279. Caruso C, Colorni A, Aloi L. Dominant, an algorithm for the p-center problem. European Journal of Operational Research, 2003, 149(1):53-64. Pacheco J A, Casado S. Solving two location models with few facilities by using a hybrid heuristic:A real health resources case. Computers & Operations Research, 2005, 32(12):3075-3091. Davidovi? T, Ramljak D, Šelmi? M, Teodorovi? D. Bee colony optimization for the p-center problem. Computers & Operations Research, 2011, 38(10):1367-1376. Yurtkuran A, Emel E. A modified artificial bee colony algorithm for p-center problems. The Scientific World Journal, 2014, 2014:824196. Scaparra M P, Pallottino S, Scutellà M G. Large-scale local search heuristics for the capacitated vertex p-center problem. Networks, 2004, 43(4):241-255. Cheng T C E, Kang L Y, Ng C T. An improved algorithm for the p-center problem on interval graphs with unit lengths. Computers & Operations Research, 2007, 34(8):2215-2222. Krumke S O. On a generalization of the p-center problem. Information Processing Letters 1995, 56(2):67-71. Arostegui M A Jr, Kadipasaoglu S N, Khumawala B M. An empirical comparison of tabu search, simulated annealing, and genetic algorithms for facilities location problems. International Journal of Production Economics, 2006, 103(2):742-754. Pullan W. A memetic genetic algorithm for the vertex pcenter problem. Evolutionary Computation, 2008, 16(3):417-436. Laguna M, Marti R. GRASP and path relinking for 2-layer straight line crossing minimization. INFORMS Journal on Computing, 1999, 11(1):44-52. Aiex R M, Resende M G C, Pardalos P M, Toraldo G. GRASP with path relinking for three-index assignment. INFORMS Journal on Computing, 2005, 17(2):224-247. Ribeiro C C, Uchoa E, Werneck R F. A hybrid GRASP with perturbations for the steiner problem in graphs. INFORMS Journal on Computing, 2002, 14(3):228-246. Aiex R M, Binato S, Resende M G C. Parallel GRASP with path-relinking for job shop scheduling. Parallel Computing, 2003, 29(4):393-430. Oliveira C A S, Pardalos P M, Resende M G C. GRASP with path-relinking for the quadratic assignment problem. In Proc. the 3rd Int Workshop on Experimental and Efficient Algorithms, May 2004, pp.356-368. Festa P, Pardalos P M, Resende M G C, Ribeiro C C. Randomized heuristics for the max-cut problem. Optimization Methods and Software, 2002, 17(6):1033-1058. Huang W Q, Lv Z P, Shi H. Growth algorithm for finding low energy configurations of simple lattice proteins. Physical Review E, 2005, 72(1):016704. Zou P, Zhou Z, Wan Y Y, Chen G L, Gu J. New metaheuristic for combinatorial optimization problems:Intersection based scaling. Journal of Computer Science and Technology, 2004, 19(6):740-751. Xu H Y, Lv Z, Cheng T C E. Iterated local search for singlemachine scheduling with sequence-dependent setup times to minimize total weighted tardiness. Journal of Scheduling, 2014, 17(3):271-287. Xu H Y, Lv Z P, Yin A H, Shen L J, Buscher U. A study of hybrid evolutionary algorithms for single machine scheduling problem with sequence-dependent setup times. Computers & Operations Research, 2014, 50:47-60. Glover F. Tabu search-part I. ORSA Journal on Computing, 1989, 1(3):190-206. Huang W Q, Zhang D F, Wang H X. An algorithm based on tabu search for satisfiability problem. Journal of Computer Science and Technology, 2002, 17(3):340-346. Lai X J, Lv Z P. Multistart iterated tabu search for bandwidth coloring problem. Computers & Operations Research, 2013, 40(5):1401-1409. Wu J, Rosin P L, Sun X F, Martin R R. Improving shape from shading with interactive tabu search. Journal of Computer Science and Technology, 2016, 31(3):450-462. Glover F. Tabu search and adaptive memory programming-Advances, applications and challenges. In Interfaces in Computer Science and Operations Research. Operations Research/Computer Science Interfaces Series, Barr R S, Helgason R V, Kennington J L (eds.), Springer 1997, pp.1-75. Glover F. Multi-start and strategic oscillation methods-Principles to exploit adaptive memory. In Computing Tools for Modeling Optimization and Simulation Operations Research/Computer Science Interfaces Series, Laguna M, Velarde J L G (eds.), Springer, 2000 pp.1-23. Glover F, Laguna M, Martí R. Fundamentals of scatter search and path relinking. Control and Cybernetics, 2000, 29(3):653-684. Peng B, Lv Z P, Cheng T C E. A tabu search/path relinking algorithm to solve the job shop scheduling problem. Computers & Operations Research, 2015, 53:154-164. Reinelt G. TSPLIB-A traveling salesman problem library. ORSA Journal on Computing, 1991, 3(4):376-384. Floyd R W. Algorithm 97:Shortest path. Communications of the ACM, 1962, 5(6):Article No. 345. Lourenço H R, Martin O C, Stützle T. Iterated local search. In Handbook of Metaheuristics, Glover F, Kochenberger G A (eds.), Springer, 2003, pp.320-353. Boese K D. Cost versus distance in the traveling salesman problem. Technical report TR-950018 UCLA CS Department, 1995. Stützle T, Dorigo M. ACO algorithms for the quadratic assignment problem. In New Ideas in Optimization, Corne D, Dorigo M, Glover F et al. (eds.), McGraw-Hill Ltd., 1999, pp.33-50. Merz P, Freisleben B. Fitness landscapes, memetic algorithms, and greedy operators for graph bipartitioning. Evolutionary Computation, 2000, 8(1):61-91. Misevicius A. An improved hybrid genetic algorithm:New results for the quadratic assignment problem. KnowledgeBased Systems, 2004, 17(2/3/4):65-73. Benlic U, Hao J K. A multilevel memetic approach for improving graph k-partitions. IEEE Trans. Evolutionary Computation, 2011, 15(5):624-642. Geiger M J. On operators and search space topology in multi-objective flow shop scheduling. European Journal of Operational Research, 2007, 181(1):195-206.