On Vehicle Routing Problem with Service Consistency

Abstract

Esta tesis se enfoca en investigar dos estrategias de ruteo para el problema de logística de última milla para un centro de distribución de una empresa de alimentos. La empresa cuenta con una flota homogénea de vehículos. Cada conductor tiene asignado un conjunto de clientes fijo. Los conjuntos de clientes asignados a diferentes conductores son disjuntos. Cada cliente requiere que sus pedidos se entreguen dentro de una ventana horaria determinada. La empresa conoce la demanda de los clientes con un día de anticipación. Los clientes no realizan pedidos todos los días y la frecuencia con la cual lo hacen es irregular. Además, las cantidades demandas por los clientes no son constantes y cambian entre un pedido y otro. Esto, provoca inconvenientes en el ruteo diario realizado por los conductores impactando negativamente en el nivel de servicio de la empresa. Se estudian estrategias de diseño de rutas que preservan los requerimientos de consistencia del servicio, en la literatura, enmarcadas dentro del Consistent Vehicle Routing Problem (ConVRP). También, se estudian estrategias que permiten que las rutas construidas no se intercepten entre sí, en la literatura, enmarcadas dentro de los problemas de Diseño de Territorios (TD). Finalmente, se evalúa de qué forma impactaría en los resultados de la empresa el uso de estas dos estrategias de solución. Para cada estrategia de ruteo, se proponen un modelo de programación lineal entera mixta (MILP) y una heurística de solución ad-hoc. Comparamos las respectivas soluciones de heurística con las soluciones de MILP en un conjunto de instancias pequeñas. Además, comparamos el plan de ruteo actual de la empresa con los obtenidos a través de las heurísticas en instancias reales de la empresa. Los resultados muestran la efectividad de las heurísticas. Obtenemos importantes mejoras sobre los planes de ruteo utilizados por la empresa, con un menor n ́umero de vehículos y una mayor tasa de pedidos entregados dentro de las ventanas de tiempo establecidas.