Enfoque híbrido para ruteo de vehículos con múltiples viajes, costos dependientes del tiempo y cola en la bodega

Abstract

Esta tesis tiene como objetivo desarrollar una metodología híbrida para resolver un problema de ruteo de vehículos repartidores de mercadería motivado por un caso práctico de una cadena de supermercados que ofrece un servicio de e-commerce. La formulación considera una primera etapa heurística en la que se genera un conjunto diversificado de rutas y una segunda etapa en donde, con un modelo exacto, se selecciona el subconjunto de rutas que minimiza el costo total de ejecución de las rutas. La modelación considera ventanas de tiempo duras para las visitas a los clientes, duración de los viajes dependientes del tiempo, cola en las zonas de carga de la bodega y múltiples viajes por vehículo. La primera etapa consiste en una heurística greedy basada en la propuesta de Ioannou et al. (2001), según la ponderación de tres parámetros, se selecciona el cliente a insertar junto a su posición dentro de la ruta en construcción. Estos parámetros buscan representar el impacto de una inserción tanto en los clientes aún no ruteados, así como sobre los clientes de la ruta en donde se realiza la inserción y el propio impacto para el cliente a insertar. Se emplean diversas estrategias de diversificación para obtener un conjunto variado de rutas. La segunda etapa, consiste en un modelo exacto con una formulación que emplea como variables las rutas previamente construidas. Dicho modelo considera el proceso de cola que se origina en la bodega cuando más de un vehículo debe ser cargado simultáneamente para realizar un nuevo viaje; este planteamiento supone un máximo de dos viajes por vehículo y una única bodega. Se realiza también una generalización del modelo anterior en el que se permite que los vehículos realicen n viajes y que existan múltiples bodegas. Para definir una cota inferior al problema resuelto se propone una formulación basada en generación de columnas para resolver el problema con máximo dos viajes y bodega única. Se plantea un esquema de simulación para definir la calidad de servicio ofrecida a los clientes en caso de emplear la metodología formulada. Los resultados obtenidos con el modelo mixto presentan ahorros, en comparación a emplear la heurística por sí sola, en gran parte debido a la minimización de la flota. Calculando un promedio de todos los escenarios estudiados, un 75,5% del costo total de la solución se debe a los costos correspondientes al uso de la flota. De aquí la importancia de emplear un modelo que considere todos los procesos involucrados al momento de definir la flota requerida para servir un conjunto de clientes.