Multi-Depot Multi-Trip Vehicle Routing Problem with Time Windows: A Perishable Good Case Study.

Abstract

El problema de ruteo de vehículos con múltiples depósitos, múltiples viajes y con ventanas de tiempo (MDMTVRPTW, por sus siglas en inglés) nace del problema que enfrenta una panadería. Primero, fue necesario analizar uno de sus componentes, el problema de ruteo con tiempos de salida. El problema de ruteo con tiempos de salida (VRP-Rd, por sus siglas en inglés) es una variante del clásico problema de las rutas de vehículos en el que el pedido de cada cliente tiene una fecha de entrega que indica la hora más temprana en que este está disponible en el depósito para su entrega. Por lo tanto, los pedidos de los clientes se cargan en los vehículos después de sus fechas de liberación, lo que denota un problema bastante común que surge en la logística de la ciudad y en la distribución de última milla. En esta investigación, se presenta una novedosa formulación compacta de dos índices e inecuaciones ajustadas para el VRP-Rd. Utilizando un conjunto de instancias de referencias conocidas, se comparan la formulación propuesta, con y sin inecuaciones ajustadas, con dos formulaciones compactas existentes y un algoritmo del estado de larte reportado en la literatura. Los resultados demuestran que ambas variaciones propuestas superan a las formulaciones existentes, y son competitivas en términos de calidad de la solución con las obtenidas por el algoritmo del estado del arte. Adicionalmente, se lleva a cabo un profundo análisis para acelerar la optimización y esquemas de mejora. Por último, cabe destacar que la formulación con inecuaciones ajustadas resultante puede resolverse eficazmente utilizando solvers comerciales sin implementaciones algorítmicas complicadas.