Resumen

Este trabajo propone una técnica de partición de clusters para calcular límites superiores mejorados para la solución óptima de problemas de localización de cobertura máxima. Dada una distancia de cobertura, se construye un grafo considerando como vértices las posibles ubicaciones de las instalaciones, y con una arista que conecta cada par de instalaciones que atienden a un mismo cliente. Las restricciones de acoplamiento, correspondientes a algunas aristas de este grafo, se identifican y se relajan a la manera de Lagrange, dando lugar a subgrafos desconectados que representan subproblemas más pequeños que son computacionalmente más fáciles de resolver por métodos exactos. La técnica propuesta se compara con el enfoque clásico, utilizando datos reales e instancias de la literatura disponible.

• Materias:Algoritmos genéticos Optimización matemática Técnica heurística Inventario
• Subjects:Genetic algorithms Mathematical optimization Metaheuristic technique Inventory
• Palabras claves:técnicas de partición de clústeres, soluciones de máximos, par de instalaciones, localización de instalaciones potenciales, límite superior mejorado, subgrafos desconectados, borde, problema de localización, vía lagrangeana, literatura disponible
• Keywords:cluster partitioning techniques, solutions of maximal, pair of facilities, potential facilities location, improved upper bound, disconnected subgraphs, edge, location problem, lagrangean way, available literature