Un problema de dispersión con capacidades
Los problemas de dispersión y diversidad surgen de la inquietud de encontrar las mejores ubicaciones para instalaciones no deseadas, administración de personal y en el contexto de las redes sociales, entre otros. Maximizar la diversidad se ocupa, en términos generales, de seleccionar un subconjunto...
| Autor Principal: | Jiménez Hidalgo, Iris Marina |
|---|---|
| Formato: | Tesis |
| Idioma: | Español |
| Publicado: |
2020
|
| Materias: | |
| Acceso en línea: |
http://up-rid.up.ac.pa/3184/ http://up-rid.up.ac.pa/3184/1/iris_jimenez.pdf |
| Sumario: |
Los problemas de dispersión y diversidad surgen de la inquietud de encontrar las mejores ubicaciones para instalaciones no deseadas, administración de personal y en el contexto de las redes sociales, entre otros. Maximizar la diversidad se ocupa, en términos generales, de seleccionar un subconjunto de elementos de un conjunto dado de tal manera que se maximice la distancia entre los elementos seleccionados. En este trabajo presentamos una variante del problema de la Dispersión con restricciones de capacidad y costos dado por Rosenkrantz, Tayi y Ravi (1999), que muestra una heurística con garantía de desempeño de 2, lo que significa que, en todos los casos, el valor de la solución óptima dividido por el valor de su solución es inferior o igual a 2. Para realizar esta variante, investigamos la adaptación de las metodologías de búsqueda adaptativa aleatoria codificada (GRASP) y la búsqueda de entornos variables (VNS) al problema de dispersión con capacidades (CDP), con el objetivo de proponer una hibridación entre GRASP y VNS que se implementará mediante un procedimiento de oscilación estratégica, que nos ayudará a encontrar un método competitivo en la búsqueda de soluciones de alta calidad al problema (CDP). Para evaluar el rendimiento de nuestra propuesta, realizamos una extensa experimentación para establecer primero los parámetros clave de búsqueda de la heurística y luego compararlos con el método anterior. Además, proponemos un modelo matemático para obtener soluciones óptimas para instancias de pequeño tamaño y comparar nuestras soluciones con el conocido software Local-Solver. |
|---|