Volume List  / Volume 11 (2)



DOI: 10.7708/ijtte.2021.11(2).09

11 / 2 / 294-309 Pages


Dalibor Ristić - School of Computing, Union University, Belgrade, Serbia -

Nenad Mladenović - Khalifa University, Abu Dhabi, United Arab Emirates -

Raca Todosijević - Polytechnic University of Hauts-de-France, Valenciennes, France -

Dragan Urosević - School of Computing, Union University, Belgrade, Serbia & Mathematical Institute, University of Belgrade, Belgrade, Serbia -


The p-center problem has been the subject of interest in the operational research for a long time. It has been well-known since the middle of the previous century. During the last decade, an extension of the problem, known as the p-next center problem, has been defined in order to handle unexpected incidents that can disable the centers. There are only a few papers and algorithms that address the aforementioned problem and therefore we introduce a new algorithm for solving the p-next center problem based on the Variable Neighborhood Search Method. The proposed algorithm was tested on a set of test instances already known in the literature, and the results show that it returns an optimal or at least near-optimal solution to the problem in a reasonable amount of time. Compared to existing algorithms, it has been shown that the proposed algorithm finds the best known or better solutions.

Download Article

Number of downloads: 455


This work was partially supported by the Ministry of Education, Science and Technological Development of the Republic of Serbia, through Mathematical Institute of the Serbian Academy of Sciences and Arts [grant number OI 174010].


Albareda-Sambola, M.; Hinojosa, Y.; Marin, A.; Puerto, J. 2015. When centers can fail: a close second opportunity, Computers & Operations Research 62: 145–156.


Beasley, J.E. 1990. OR-Library: distributing test problems by electronic mail, Journal of the operational research society 41(11): 1069–1072.


Calik, H.; Tansel, B.C. 2013. Double bound method for solving the p-center location problem, Computers & operations research 40(12): 2991–2999.


Daskin, M.S. 2013. Network and discrete location: models, algorithms, and applications, 2nd edn. Wiley, Hoboken. 520p.


Davidovic, T.; Ramljak, D.; Selmic, M.; Teodorovic, D. 2011. Bee colony optimization for the p-center problem, Computers & Operations Research 38: 1367-1376. doi: 10.1016 / j.cor.2010.12.002.


Elloumi, S.; Labbé, M.; Pochet, Y. 2004. A new formulation and resolution method for the p-center problem, INFORMS Journal on Computing 16(1): 84–94.


Feo, T.A.; Resende, M.G.C. 1989. A probabilistic heuristic for a computationally difficult set covering problem, Operations Research Letters 8(2): 67–71.


Hakimi, S.L. 1965. Optimum distribution of switching centers in a communication network and some related graph theoretic problems, Operations Research 13(3): 462–475.


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


Ilhan, T.; Pınar, M.C. 2001. An efficient exact algorithm for the vertex p-center problem. Technical report, Department of Industrial Engineering, Bilkent University.


Kariv, O.; Hakimi, S.L. 1979. An algorithmic approach to network location problems. Part 1: The p-Centers, SIAM Journal on Applied Mathematics 37(3): 513-538.


Lopez, A.; Sánchez-Oro Calvo, J.; Hernández-Díaz, A. 2018. GRASP and VNS for solving the p-next center problem, Computers & Operations Research 104: 295-303. doi: 10.1016 / j.cor.2018.12.017.


Minieka, E. 1970. The m-center problem, SIAM Rev 12:138–139.


Mladenovic, N.; Hansen, P. 1997. Variable neighborhood search, Comput. Operator. Res. 24 (11): 1097–1100.


Mladenovic, N.; Labbé, M.; Hansen, P. 2003. Solving the p-center problem with tabu search and variable neighborhood search, Networks 42 (1): 48–64.


Pullan, W. 2008. A memetic genetic algorithm for the vertex p-center problem, Evol Comput 16:417–436.

Quoted IJTTE Works

Related Keywords