Tesis Pre-grado
Un algoritmo de Planos Cortantes para Resolver el Problema de la p-Mediana con Capacidad
Un algoritmo de planos cortantes para resolver el problema de la p-mediana con capacidad
Autor
Obreque-Niñez, Carlos Enrique
Cornejo-Zúñiga, Oscar
UNIVERSIDAD CATOLICA DE LA SANTISIMA CONCEPCION
Institución
Resumen
El problema de la p-mediana capacitada es una extensión del conocido problema de la p-mediana, que considera una demanda asociada a cada cliente y una capacidad asociada a cada servidor candidato. El objetivo de este problema es localizar p servidores y asignar los clientes a los servidores más cercanos sin exceder la capacidad disponible de cada servidor, de modo que se minimice la distancia total que recorren los clientes para alcanzar su servidor asignado.
En este proyecto se presenta un algoritmo de planos cortantes para resolver el problema de la p-mediana con capacidad. El procedimiento incorpora desigualdades válidas en el nodo inicial del árbol de búsqueda, con el objetivo de mejorar la cota inferior de la relajación lineal. Cuando no se encuentran más cortes, el proceso continúa utilizando el método branch and cut, hasta encontrar la solución óptima o hasta que se satisfaga el tiempo límite de proceso. Además, se presentan dos nuevas formulaciones del problema, basadas en el concepto de flujo entero.
Para evaluar la efectividad del algoritmo, se utilizan cuatro clases de instancias obtenidas de la literatura y se compara su desempeño con respecto al branch and cut de CPLEX, revelando que el algoritmo propuesto es competitivo para instancias de gran tamaño.