Heurística para la generación de zonas de distribución postal

Abstract

En este trabajo, se logró conceptualizar un modelo matemático para resolver el problema del distritaje de códigos postales y la generación de zonas de distribución postal para la Empresa de Correos de Chile. El modelo aborda dificultades regulares en la conformación de distritos: compacidad, conexidad y balance de cargas entre distritos, donde las cargas de los códigos postales se distribuyen heterogéneamente en la cartografía. Pero sobretodo, tiene foco en diseñar los distritos "más compactos posibles", puesto que este tipo de resultados se percibe como una mejor solución, logra mayor aceptación y genera menor necesidad de modificaciones posteriores.

La formulación de este problema se basó en un modelo de optimización lineal entera sobre un grafo, el cual tiene como función objetivo minimizar la distancia de cada nodo de un distrito al centro de este último, cumpliendo restricciones de balance de carga y conexidad. El propósito fundamental de este modelo reside en la posibilidad de establecer un benchmark del tipo de soluciones que se desean obtener.

Este modelo resultó extremadamente complejo de resolver en instancias del tamaño de la operación regular de Correos, las cuales rondan los 4000 nodos. Por esta razón, frente a la imposibilidad de utilizar este modelo de optimización en problemas operacionales, se propone una metodología heurística que, tras análisis empíricos, consigue obtener soluciones muy cercanas al óptimo (GAP promedio de $5\%$) en tiempos funcionales para la operación regular (menos de una hora).

El procedimiento se aplicó a un caso de estudio real, representado por la generación de cuarteles de distribución postal en la comuna de Recoleta, y fue comparado contra otros distritajes realizados en la empresa. Los distritos obtenidos por la metodología propuesta logran excelente balance y presentan una elevado nivel de compacidad, muy superior a las alternativas. Además, este resultado se obtuvo en tiempos por debajo de los márgenes de espera establecidos, lo cual habilita este procedimiento para ser usado operacionalmente.

De manera que, el procedimiento presentado en este trabajo, se puede considerar como una alternativa que genera resultados con mejores índices de aceptación que la actual metodología usada para generar zonas de distribución postal.