Volume List  / Volume 11 (2)

Article

FILTERED VARIABLE NEIGHBORHOOD SEARCH METHOD FOR THE P-NEXT CENTER PROBLEM

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


11 / 2 / 294-309 Pages

Author(s)

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 -


Abstract

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: 135


Acknowledgements:

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


References:

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