Diseño de heurística de PVRP para repartos en Área Metropolitana

Abstract

Este trabajo nace como un esfuerzo para solucionar el problema de una empresa importante en el rubro de la distribución de alimentos, desde centros de despacho a clientes finales, que busca hallar mejoras en su distribución tanto en distancias como en tiempos de reparto, desde bodegas a clientes, considerando además el costo de contratación de máquinas para realizar dicho transporte y el costo organizacional que representa el ruteo diario, enfrentado desde la calendarización de las visitas a clientes finales con pedidos regulares en una variante del VRP llamado PVRP. El foco principal de esta tesis se concentra en encontrar una manera razonable de separar el problema de asignación de un PVRP del de ruteo (VRP), utilizando aproximaciones al costo de resolver el ruteo de manera inteligente, y aprovechando el estado del arte que permitan incorporar en esta etapa las ventanas de tiempo y la capacidad. Prima el principio de modularidad de la solución para resolver el PVRP a través de ensamblaje con otros algoritmos que permitan resolver problemas de gran escala, ya sea por la cantidad de detenciones como por el tamaño de la flota de vehículos. Puntualmente, el trabajo consta del desarrollo de un algoritmo que permita la resolución de estos problemas de gran escala y posterior validación, tanto a nivel teórico de su rendimiento frente al óptimo del problema como en la aplicación para resolver el problema de la empresa. La asignación diaria incurre en ahorros de distancia entre el 1,53\% y el 11,41\%, ahorros en tiempo de entre 1,75\% y 20,54\% y un impacto difuso en la flota entre 20,54\% de ahorro y 9,09\% de exceso de flota, respecto a un benchmark compuesto por la optimización de la situación inicial cuando no se consideran herramientas que balanceen la solución. En el caso en que efecctivamente se consideran estas herramientas, si bien la distancia se encuentra entre un 4,76\% de ahorro y un 7,65\% de sobrecosto respecto al mismo benchmark, la flota disminuye entre 11,18\% y un 26,57\%, mientras los tiempos entre un 7,20\% y un 11,93\%.