›› 2017, Vol. 32 ›› Issue (6): 1319-1333.doi: 10.1007/s11390-017-1802-3

• Regular Paper • 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. 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
  • Received:2016-08-29 Revised:2017-03-28 Online:2017-11-05 Published:2017-11-05
  • Contact: Jun-Wen Ding E-mail: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.
  • Supported by:

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

PDF

814

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.

[1] 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.

[2] 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.

[3] Hakimi S L. Optimum locations of switching centers and the absolute centers and medians of a graph. Operations Research, 1964, 12(3):450-459.

[4] Minieka E. The m-center problem. SIAM Review, 1970, 12(1):138-139.

[5] Daskin M S. Network and Discrete Location:Models Algorithms and Applications. John Wiley & Sons, 1995.

[6] 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.

[7] 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.

[8] 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.

[9] 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.

[10] Hochbaum D S, Shmoys D B. A best possible heuristic for the k-center problem. Mathematics of Operations Research, 1985, 10(2):180-184.

[11] Martinich J S. A vertex-closing approach to the p-center problem. Naval Research Logistics, 1988, 35(2):185-201.

[12] Plesník J. A heuristic for the p-center problems in graphs. Discrete Applied Mathematics, 1987, 17(3):263-268.

[13] Mladenovi? N, Labbé M, Hansen P. Solving the p-center problem with tabu search and variable neighborhood search. Networks, 2003, 42(1):48-64.

[14] Hassin R, Levin A, Morad D. Lexicographic local search and the p-center problem. European Journal of Operational Research, 2003, 151(2):265-279.

[15] Caruso C, Colorni A, Aloi L. Dominant, an algorithm for the p-center problem. European Journal of Operational Research, 2003, 149(1):53-64.

[16] 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.

[17] Davidovi? T, Ramljak D, Šelmi? M, Teodorovi? D. Bee colony optimization for the p-center problem. Computers & Operations Research, 2011, 38(10):1367-1376.

[18] Yurtkuran A, Emel E. A modified artificial bee colony algorithm for p-center problems. The Scientific World Journal, 2014, 2014:824196.

[19] 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.

[20] 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.

[21] Krumke S O. On a generalization of the p-center problem. Information Processing Letters 1995, 56(2):67-71.

[22] 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.

[23] Pullan W. A memetic genetic algorithm for the vertex pcenter problem. Evolutionary Computation, 2008, 16(3):417-436.

[24] Laguna M, Marti R. GRASP and path relinking for 2-layer straight line crossing minimization. INFORMS Journal on Computing, 1999, 11(1):44-52.

[25] 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.

[26] 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.

[27] 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.

[28] 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.

[29] 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.

[30] 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.

[31] 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.

[32] 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.

[33] 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.

[34] Glover F. Tabu search-part I. ORSA Journal on Computing, 1989, 1(3):190-206.

[35] 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.

[36] Lai X J, Lv Z P. Multistart iterated tabu search for bandwidth coloring problem. Computers & Operations Research, 2013, 40(5):1401-1409.

[37] 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.

[38] 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.

[39] 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.

[40] Glover F, Laguna M, Martí R. Fundamentals of scatter search and path relinking. Control and Cybernetics, 2000, 29(3):653-684.

[41] 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.

[42] Reinelt G. TSPLIB-A traveling salesman problem library. ORSA Journal on Computing, 1991, 3(4):376-384.

[43] Floyd R W. Algorithm 97:Shortest path. Communications of the ACM, 1962, 5(6):Article No. 345.

[44] 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.

[45] Boese K D. Cost versus distance in the traveling salesman problem. Technical report TR-950018 UCLA CS Department, 1995.

[46] 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.

[47] Merz P, Freisleben B. Fitness landscapes, memetic algorithms, and greedy operators for graph bipartitioning. Evolutionary Computation, 2000, 8(1):61-91.

[48] Misevicius A. An improved hybrid genetic algorithm:New results for the quadratic assignment problem. KnowledgeBased Systems, 2004, 17(2/3/4):65-73.

[49] Benlic U, Hao J K. A multilevel memetic approach for improving graph k-partitions. IEEE Trans. Evolutionary Computation, 2011, 15(5):624-642.

[50] 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.
No related articles found!
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] Zhang Bo; Zhang Ling;. Statistical Heuristic Search[J]. , 1987, 2(1): 1 -11 .
[2] Meng Liming; Xu Xiaofei; Chang Huiyou; Chen Guangxi; Hu Mingzeng; Li Sheng;. A Tree-Structured Database Machine for Large Relational Database Systems[J]. , 1987, 2(4): 265 -275 .
[3] Lin Qi; Xia Peisu;. The Design and Implementation of a Very Fast Experimental Pipelining Computer[J]. , 1988, 3(1): 1 -6 .
[4] Sun Chengzheng; Tzu Yungui;. A New Method for Describing the AND-OR-Parallel Execution of Logic Programs[J]. , 1988, 3(2): 102 -112 .
[5] Zhang Bo; Zhang Tian; Zhang Jianwei; Zhang Ling;. Motion Planning for Robots with Topological Dimension Reduction Method[J]. , 1990, 5(1): 1 -16 .
[6] Xu Zhiming;. Discrete Interpolation Surface[J]. , 1990, 5(4): 329 -332 .
[7] Wang Dingxing; Zheng Weimin; Du Xiaoli; Guo Yike;. On the Execution Mechanisms of Parallel Graph Reduction[J]. , 1990, 5(4): 333 -346 .
[8] Zhou Quan; Wei Daozheng;. A Complete Critical Path Algorithm for Test Generation of Combinational Circuits[J]. , 1991, 6(1): 74 -82 .
[9] Zhao Jinghai; Liu Shenquan;. An Environment for Rapid Prototyping of Interactive Systems[J]. , 1991, 6(2): 135 -144 .
[10] Shang Lujun; Xu Lihui;. Notes on the Design of an Integrated Object-Oriented DBMS Family[J]. , 1991, 6(4): 389 -394 .

ISSN 1000-9000(Print)

         1860-4749(Online)
CN 11-2296/TP

 Home
Editorial Board
Author Guidelines
Subscription		 Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
Tel.:86-10-62610746
E-mail: jcst@ict.ac.cn
 
  Copyright ©2015 JCST, All Rights Reserved