Resumen

Los modelos de optimización discreta juegan en la actualidad un rol muy importante en muchas aplicaciones prácticas tales como logística, producción, economía, ingeniería, transportes, telecomunicaciones e informática. Para algunas clases de problemas de optimización discreta se han desarrollado métodos de solución efectivos, pero todavía no existe una metodología general que se pueda aplicar para resolver todos los tipos de problemas de manera eficiente. Dado que para un gran número de problemas de optimización discreta, los métodos exactos siguen siendo ineficientes, en los últimos años se ha realizado un gran esfuerzo por desarrollar métodos aproximados que proporcionen soluciones de buena calidad con un esfuerzo razonable.

Por otro lado, el avance en la tecnología computacional ha permitido resolver problemas que en el pasado simplemente no habrían sido considerados. Esto ha dado origen a la búsqueda de métodos de solución eficientes para problemas de optimización discreta que han permitido el desarrollo de nuevas metodologías tales como los métodos meta heurísticos, los cuales han sido aplicados con éxito a un gran número de problemas. Entre estos problemas se tienen los problemas de localización discreta, que consideran situaciones en donde el proceso de toma de decisión consiste en ubicar instalaciones, dentro de un conjunto discreto de posibles localizaciones, en relación con un conjunto de clientes que serán atendidos por la instalaciones a ubicar, de una manera óptima con respecto a una función objetivo.

El problema que se aborda en este estudio es el problema de p-centro por vértices que es uno de los problemas clásicos de localización. Considera la ubicación de un número fijo de instalaciones de manera tal que se minimice la máxima distancia entre cualquier nodo de demanda y la instalación más cercana a dicho nodo. El trabajo actual propone un método meta heurístico basado en la metodología GRASP "Greedy Randomized Adaptive Search Procedure" para encontrar soluciones factibles para el problema de p-centro. Este algoritmo será evaluado con diferentes problemas disponibles en la literatura.

Palabras clave: GRASP, Localización Instalaciones, P-CENTRO

Esta tesis sólo puede ser consultada por miembros de la Comunidad Universitaria. (ir al índice de contenido)

Aguilar Gochicoa, J. S. 2004. Diseño e implementación de un algoritmo heurístico para el problema de localización p-centro por vértices. Tesis Licenciatura. Ingeniería Industrial. Departamento de Ingeniería Industrial y Textil, Escuela de Ingeniería, Universidad de las Américas Puebla. Mayo. Derechos Reservados © 2004.