Heurística GRASP para o problema de p-medianas aplicado à localização de concentradores
DOI:
https://doi.org/10.5935/1809-2667.20110023Palabras clave:
p-mediana, Otimização combinatória, GRASP, HeurísticaResumen
Várias situações práticas reais, tais como localizações de depósitos, hospitais e dispositivos de telecomunicações (concentradores, torres de celulares, etc), podem ser vistas como um problema de p-medianas. Este trabalho apresenta uma proposta para a solução do problema de p-medianas baseado no backbone da rede de computadores que será instalado no Instituto Federal Fluminense (IFF). Esse tipo de ocorrência é conhecida na literatura como problema de localização de concentradores. Para resolver a questão citada foi proposta uma heurística GRASP. Testes computacionais realizados, mostram que a heurística elaborada neste trabalho atingiu resultados satisfatórios.Descargas
Referencias
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.
Descargas
Número
Sección
Licencia
Los autores del manuscrito enviado a la revista Vértices, representados aquí por el autor correspondiente, aceptan los siguientes términos:
Los autores conservan los derechos de autor y otorgan a la revista Vértices el derecho de primera publicación.
Al mismo tiempo, el trabajo está licenciado bajo la Licencia Creative Commons Atribución 4.0 Internacional (CC BY 4.0), que permite a terceros copiar y redistribuir el material en cualquier medio o formato y mezclar, transformar y construir sobre su contenido para cualquier propósito legal, incluso comercial, siempre que el trabajo original se cite correctamente.
Los autores no recibirán ningún pago material por su manuscrito y la Essentia Editora lo pondrá a disposición en línea en modo de acceso abierto, a través de su propio sistema o de otras bases de datos.
Los autores están autorizados a celebrar contratos adicionales por separado para la distribución no exclusiva de la versión del trabajo publicado en la revista Vértices (por ejemplo, publicar en un repositorio institucional o como capítulo de libro), con reconocimiento de autoría y publicación inicial en esta revista.
Se permite y se alienta a los autores a difundir y distribuir en línea la versión posterior a la publicación (es decir, la versión final posterior al arbitraje) o la versión PDF del editor en distintas fuentes de información (por ejemplo, en repositorios institucionales, temáticos o páginas web personales) en cualquier momento después de la primera publicación del artículo por la revista Vértices.
La Essentia Editora puede realizar cambios normativos, ortográficos y gramaticales en los originales con el fin de mantener el estándar culto de la lengua, con el consentimiento final de los autores.
Las opiniones expresadas en el manuscrito son responsabilidad exclusiva de los autores.
Cómo citar
1.png)
