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 -
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.
Number of downloads: 513
Keywords:
variable neighborhood search;
heuristic algorithms;
p-next center problem;
combinatorial optimization;
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
There is no quoted studies.
Related Keywords
There is no related studies.