Metodología para la solución de un problema de ruteo de vehículos con múltiples depósitos, ventanas de tiempo y flota heterogénea

Abstract

El problema de ruteo de vehículos con múltiples depósitos con flota heterogénea y ventanas de tiempo de servicio se ajusta a la realidad de múltiples compañías que cuentan con diferentes centros de distribución y vehículos de diferentes características para atender a sus clientes cumpliendo con las demandas y las franjas horarias de atención establecidas. Este tipo de problema está clasificado en la categoría Np-hard dadas sus características de complejidad combinatoria. En este trabajo se aborda el caso específico de una compañía real en la ciudad de Medellín, al cual se le da solución mediante dos enfoques de generación de rutas. En primera instancia, se construye y se soluciona el modelo de diseño de rutas en un software comercial con buenas características en cuanto a practicidad, flexibilidad y rápida respuesta computacional. El segundo enfoque, consiste en la aplicación de un algoritmo de optimización de tres fases disponible en la literatura, que combina técnicas heurísticas con programación lineal entera mixta (MILP) para obtener soluciones factibles y eficientes en términos de costos. En los primeros capítulos de este trabajo se presenta la descripción del problema y la revisión de literatura, luego se presenta un análisis estadístico de demanda y tiempos de atención como parámetros de entrada importantes para los modelos de optimización, posteriormente se desarrolla la metodología con los enfoques de optimización descritos y, en el capítulo final, se plantean las conclusiones y recomendaciones de este estudio.

Abstract: The Multi-Depot Heterogeneous Fleet Vehicle Routing Problem with Time Windows (MDHVRPTW) addresses the reality of multiple companies’ distribution problems in the last mile delivery. Those problems contemplate operations with multiple distribution centers and vehicles that have different characteristics to serve customers demands meeting their established time windows. This problem is classified −given its ombinatorial complexity. This paper presents a specific case of a real company in Medellin (Colombia) in the food industry. This real instance is solved by two different methodologies of routes design: the first one, constructs and solves the model with a commercial software with good characteristics in terms of flexibility and computational response for real life decisions. The second approach the use of a three-phase optimization algorithm available in the literature for the MDHVRPTW which combines heuristic techniques with mixed integer linear programming (MILP) to obtain feasible and efficient solutions in terms of costs. The paper is organized as follows: the description of the problem and the literature review are resented in the first chapters. Then a statistical analysis of customer’s demand and customer’s attention times is introdu ced to show the importance of these input parameters for the optimization models. Later, both optimization solution methodologies are described and developed with their results, allowing the presentation of conclusions and recommendations in the final chapter.