Simposio “Transferencia de Conocimiento en Tecnologías de la Información”

Demand allocation approaches for the capacitated maximal covering location problem

Abstract

The maximal covering location problem seeks to locate a limited number of facilities to maximize the covered demand. Commonly facilities are modeled with unlimited capacity, but this is not realistic, and in many situations, facilities have workload limits. A limited capacity means that it is also necessary to find the best allocation of customers to the facilities. This paper presents six demand node allocation procedures for the capacitated maximal coverage location problem. Performed experiments show that the descending allocation of the demand nodes to the closest facility nodes with available capacity obtains the best results, achieving a 3% improvement over the worst allocation procedure resulted from the experiments.

Resumen

El problema de localización de máxima cobertura busca ubicar un número limitado de instalaciones que maximice la cobertura sobre un conjunto de demandas. Frecuentemente las instalaciones son modeladas sin límite de capacidad, pero en muchas situaciones las instalaciones tienen una capacidad limitada. La limitación de la capacidad de las instalaciones implica que sea necesario encontrar la mejor asignación de nodos de demanda para aprovechar la capacidad y que maximice la utilidad de las instalaciones. En este artículo, un conjunto de procedimientos para la asignación de nodos de demanda para el problema de localización de máxima cobertura capacitado es propuesto. Un análisis experimental empleando búsqueda local es presentado con el objetivo de conocer el mejor procedimiento de asignación. Los resultados obtenidos muestran que la asignación descendente de nodos de demanda a la instalación más cercana con capacidad disponible obtiene los mejores resultados, obteniéndose una mejora de un 3% sobre el peor criterio de asignación resultante de los experimentos.