Resumen en español

El objetivo de este trabajo es diseñar un programa periódico de rutas para la recolección de material reciclable que permita la disminución de la distancia recorrida lo que corresponde a un problema periódico de enrutamiento de arco capacitado PCARP. Para el desarrollo del trabajo se establecieron 3 fases: la primera consiste en la caracterización del proceso, donde se identificaron los materiales recolectados, los vehículos utilizados, los recorridos, la demanda por calle y la frecuencia de recolección en un horizonte de tiempo de una semana. En la segunda fase se simplifico el problema PCARP al problema de enrutamiento de vehículos capacitados sobre arcos para un periodo CARP, debido a que la frecuencia de recolección en el horizonte de una semana es igual a uno para cada ruta, siendo así, se formuló el modelo matemático con base al realizado por Golden (1981) que nos da como resultado los nodos a recorrer buscando minimizar la distancia total recorrida por los dos vehículos teniendo en cuenta que se debe salir y regresar al depósito y no se debe exceder la capacidad del vehículo. Sin embargo, como el tamaño del problema caso de estudio lo hace intratable, se diseñó una heurística en el lenguaje de programación Python, como estrategia de solución que divide el problema en dos fases: la primera fase con el propósito de abordar las limitaciones de capacidad de los vehículos y la periodicidad en la recolección por medio del algoritmo KMeans, y la segunda fase con el fin de encontrar los recorridos para cada ruta a través del algoritmo del cartero chino CPP el cual a su vez se basa en dos algoritmos como Dijkstra y Fleury para determinar la secuencia de los nodos que conforman el circuito euleriano con sus respectivas distancia. Por último, para demostrar que tan efectivos eran los resultados de la heurística propuesta a comparación de cómo la empresa lo realiza se hizo una comparación de las distancias recorridas logrando una disminución de 5,65 kilómetros por semana. Para efectos comparativos entre el modelo exacto del CARP y la fase 2 de la heurística propuesta con respecto a la secuencia del recorrido y la distancia total obtenida, se resolvieron ambos modelos en una instancia pequeña del problema abordado obteniendo un porcentaje del 0% de desviación (GAP) de la solución obtenida por la heurística con respecto a la obtenida por el CARP.