Heurística Basada en Generación de Columnas para el Problema de Ruteo de Vehículos con Ventanas de Tiempo y Flota Homogénea. Caso: Cervecerías Chile S. A.

Abstract

En este trabajo se presenta una heurística que mejora los resultados operacionales en el despacho de pedidos de cerveza. Este trabajo está, especializado en las características de CERVECERÍAS CHILE S.A., empresa dedicada a la elaboración y transporte de cervezas a lo largo de todo Chile. La problemática diaria que se aborda en este proyecto consiste en la asignación de 400 clientes, en promedio, a rutas específicas de entrega, tomando en cuenta una flota homogénea de vehículos y restricciones horarias en la entrega de los pedidos. Se considera que la demanda de los productos es conocida y que los productos están disponibles para la entrega. Es importante notar que en este problema no existe una limitante en el número de vehículos disponibles para la entrega del producto, debido a que la empresa tiene una gran variedad de proveedores de transporte que facilitan el arrendamiento de vehículos. La formulación de la heurística desarrollada asegura el cumplimiento de las restricciones temporales en la entrega de productos y además minimiza los costos asociados al transporte diario de los productos para satisfacer la demanda de los clientes. La solución del problema se enfrentó con la técnica de Generación de Columnas. La base de esta metodología es dividir el problema en dos etapas: La primera etapa considera la generación de rutas factibles conocida como Sub Problema, y una segunda etapa la formulación de un problema de programación lineal que escoge mediante un modelo de optimización las soluciones que serán consideradas como rutas factibles para el despacho de los pedidos. Estas rutas corresponden a aquellas que tienen un costo reducido negativo para mejorar la función objetivo. El modelo decide qué cliente es asignado a cada viaje y horarios en que se realiza dicho viaje. El modelo se aplicó a datos que representan situaciones reales analizando principalmente el comportamiento de los resultados entregados por la heurística respecto a la configuración de rutas generadas y a la naturaleza de las rutas factibles generadas. El resultado final de la heurística utilizada contempla un aumento en el nivel de servicio, dado que logra entregar los pedidos cumpliendo las restricciones horarias de los clientes. Lo anterior refleja también una mejora de un 50% aproximadamente en las utilidades de los pedidos diarios.