GRASP heuristic for p-median problem applied to the location of concentrators
DOI:
https://doi.org/10.5935/1809-2667.20110023Keywords:
p-median, Combinatory optimization, GRASP, HeuristicAbstract
Several real practical situations, such as location of depots, hospitals and telecommunications devices (hubs, cellular towers, etc.), can be seen as a p-median problem. This paper presents a proposal for solving the p-median problem based on the backbone network of computers that will be installed at the Federal Fluminense Institute (IFF). This type of problem is known in literature as a problem of locating concentrators. To solve the problem cited was proposed a GRASP heuristic. Computational tests performed show that the heuristic developed in this work has reached satisfactory results.Downloads
References
ASSUNÇÃO, R.M.; LAGE, J.P.; A.REIS, E.; SILVA, P.L.N. Análise de conglomerados espaciais via árvore geradora mínima. Revista Brasileira de Estatística, v.63, p.7-24, 2004.
CHIYOSHI, F.; GALVÃO, R.D. A statistical analysis of simulated annealing applied to the p-median problem. Annals and Operations Research, v.96, p.61-74, 2000.
DRUMMMOND, L.M.A.; OCHI, L.S.; VIANNA, D.S. An asynchronous parallel metaheuristic for the period vehicle routing problem. Future Generation Computer Systems, v.17, n.4, p.379-386, 2001.
ERKUT E.; BOZKAYA, B.; ZHANG, J. An effective genetic algorithm for the p-median problem. Alberta: University of Alberta, 1997. 23 p
FEO, T.A. AND RESENDE, M.G.C. Greedy randomized adaptive search procedures. Journal of Global Optimization, v.6, p.109-133, 1995.
GOLDMAN, A.J. Optimal location for centers in a network. Transportation Science, v.3, p.352–360, 1969.
HANSEN, P.; MLADENOVIC, N.; PEREZ-BRITO. Variable neighborhood decomposition search. Journal of Heuristics, v.7, p.335-350, 2001.
HOSAGE, C.M.; GOODCHILD, M.F. Discrete space location-allocation solutions from genetic algorithms. Annals of Operations Research, v.6, p.657-682, 1986.
MARQUES, T.B.; ARROYO, J.E.C. ; VIANNA, D.S. Heurísticas para o problema de alocação de antenas de transmissão. In: SIMPÓSIO BRASILEIRO DE PESQUISA OPERACIONAL, 2007, Fortaleza. p. 1-12.
O’KELLY, M.E. A quadratic integer program for the location of interacting hub facilities. European Journal of Operational Research, v.32, p.393–404, 1987.
RESENDE, M.G.C. Greedy Randomized Adaptive Search Procedures (GRASP). AT&T Labs Research Technical Report, v.98.41.1, 1998.
RESENDE, M. G. C.; RIBEIRO, C. C. Greedy randomized adaptive search procedures. In: GLOVER, F. ; KOCHENBERGER, G. (Eds.). Handbook of metaheuristics. England: Kluwer, 2003. p.219-249.
RESENDE, M.G.C.; WERNECK, R.F. A Hybrid Heuristic for p-Median Problem. Journal of Heuristics, v.10, p.59-88, 2004.
RIBEIRO, C.C.; VIANNA, D.S. A hybrid genetic algorithm for the phylogeny problem using path-relinking as a progressive crossover strategy. International Transactions in Operational Research, v.16, p.641-657, 2009.
ROLLAND, E.; SCHILLING, D.A.; CURRENT, J.R. An efficient tabu search procedure for the pmedian problem. European Journal of Operational Research, v.96, n.2, p.329-342, 1996.
VOSS, S. A reverse elimination approach for the p-median problem. Studies in Locational Analysis, v.8, p.49-58, 1996.
Downloads
Issue
Section
License
The authors of the manuscript submitted to Vértices, hereby represented by the corresponding author, agree to the following terms:
The authors retain the copyright and grant Vértices the right of first publication.
At the same time the work is licensed under the Creative Commons Attribution 4.0 International License, allowing third parties to copy and redistribute the material in any medium or format and to remix, transform, and build upon its content for any legal purpose, even commercially, provided the original work is properly cited.
Authors will not receive any material reward for the manuscript and Essentia Editora will make it available online in Open Access mode, through its own system or other databases.
Authors are authorized to enter into additional contracts separately for non-exclusive distribution of the version of the work published in Vértices (eg, publish in institutional repository or as book chapter), with acknowledgment of authorship and initial publication in this journal.
Authors are permitted and encouraged to disseminate and distribute the post-print (ie final draft post-refereeing) or publisher's version/PDF at online information sources (eg, in institutional repositories or on their personal page) at any time after the first publication of the article by Vértices.
Essentia Editora may make normative, orthographic and grammatical changes in the originals in order to maintain the standard language, with the final consent of the authors.
The content and opinions expressed in the manuscript are the sole responsibility of the author (s).
How to Cite
1.png)
