Metaheurístico basado en multi-space sampling para la solución de problemas de distritación

Abstract

RESUMEN : Los problemas de distritación (PD) buscan agrupar pequeñas áreas geográficas (clientes, manzanas, barrios, etc.), en grupos geográficos de mayor tamaño de manera que estos últimos sean útiles según las características del problema. Las aplicaciones de este problema comprenden desde la zonificación política, diseño de zonas de ventas y distribución, hasta la planeación de cuidado domiciliario, entre otras. Para la solución de los PD se han utilizado en el pasado distintas técnicas, que van desde heurísticos constructivos y de búsqueda local hasta metaheurísticos, y métodos exactos basados en programación entera. En el presente trabajo se desarrolló una solución metaheurística para el problema de distritación general que podría ser aplicado a cualquier necesidad de distritación. La solución implementada está basada en un nuevo método metaheurístico llamado multi-space sampling heuristic (MSH) introducido por Mendoza & Villegas (2013). Este informe ilustra la revisión de la literatura asociada a los problemas de distritación y sus soluciones, la explicación realizada del MSH propuesto, los resultados computacionales al aplicar la solución a un problema particular y el análisis de los resultados obtenidos.

ABSTRACT : Districting problems (DP) seek to group small geographic areas (customers, blocks, neighborhoods, etc.) into larger geographic groups so that the latter are useful according to the characteristics of the problem. The applications of this problem range from political zoning, to the design of sales and distribution areas, to home healthcare planning, among others. Different techniques have been used in the past to solve DPs, ranging from constructive and local search heuristics to metaheuristics and exact methods based on integer programming. In the present work, a metaheuristic solution for the general districting problem was developed that could be applied to any districting application. The implemented solution is based on a new metaheuristic framework called the multi-space sampling heuristic (MSH), introduced by Mendoza & Villegas (2013). This report illustrates the review of the literature associated with districting problems and their solutions; the explanation of the proposed MSH carried out; the computational results when applying the solution to a particular problem; and the analysis of the results obtained.