Resumen

El Problema Probabilístico de Localización-Alocalización de Máxima Cobertura (PPLAMC) consiste en localizar instalaciones, maximizando la población atendida y proporcionando un buen nivel de servicio a toda la población, es decir, se debe garantizar que un usuario, al llegar a un centro, no espere más de un tiempo máximo permitido o no encuentre una cola de atención con un número de usuarios superior a un valor máximo. Estos dos parámetros dependen del ritmo de llegada de los usuarios y de la asistencia, ambos probabilísticos. Debido a las dificultades intrínsecas del problema, en este trabajo se discuten los límites lagrangeanos para el PPLAMC obtenidos con la relajación lagrangeana con clusters (LagClus). En su propuesta inicial, LagClus utilizaba un grafo de conflicto, pero en este trabajo se aplica esta relajación a un grafo especial denominado grafo de cobertura.

1. INTRODUCCIÓN

Los problemas de localización tienen como objetivo ubicar instalaciones para dar servicio a usuarios que están distribuidos espacialmente. Las instalaciones son centros que prestan algún tipo de servicio. Por ejemplo, se pueden citar los hospitales que prestan servicios médicos a sus pacientes y los bancos que gestionan las cuentas de sus clientes.

Muchos de estos problemas son combinatorios, e incluso con aplicaciones sofisticadas como CPLEX (ILOG, http://www.ilog.com) y XPRESS (DASH OPTIMIZATION, http://www.dashoptimization.com), puede resultar difícil encontrar soluciones óptimas. Por ello, muchos investigadores recurren a heurísticas, metaheurísticas, métodos de descomposición y relajaciones para obtener soluciones primarias de buena calidad o incluso límites duales interesantes que permitan evaluar soluciones factibles.

El Problema de Localización de Cobertura Máxima (MCPL) ha sido considerablemente tratado en la literatura desde su formulación por Church y ReVelle (1974). Este problema busca obtener la configuración para localizar una cantidad predefinida de instalaciones que atienda al mayor número de individuos de una población, considerando una distancia dada o un tiempo estándar desde el punto de demanda. Este modelo no pretende atender a toda la población, sino ofrecer el máximo servicio, teniendo en cuenta los recursos disponibles. La figura 1 muestra tres instalaciones localizadas que dan servicio a varios puntos de demanda, pero nótese que algunos puntos no están cubiertos por los centros. Habitualmente, en la bibliografía se considera que un punto está cubierto si se encuentra a una distancia o un tiempo determinados del centro.

• Materias:Diseño de servicios Arquitectura orientada a servicios Calidad de servicio Servicios de atención
• Subjects:Service design Service-oriented architecture Quality of service Care services
• Palabras claves:Relajación Lagrangeana; Relajación Lagrangeana con Clusters; Problemas de localización; Cobertura máxima
• Keywords:Lagrangean Relaxation; Lagrangean Relaxation with Clusters; Location Problems; Maximal Covering