Solución de problemas de ruteo de vehículos con restricciones de capacidad usando la teoría de grafos

La teoría de grafos es una herramienta para la solución de problemas de ruteo de vehículos con restricciones de capacidad (Capacitated Vehicle Routing Problem, CVRP). En este artículo se muestra la aplicación de una herramienta informática basada en la teoría de grafos para analizar y resolver un un problema CVRP en una empresa de transporte de carga a nivel nacional. El análisis se realizó en una flotilla de 13 vehículos con las mismas especificaciones técnicas y capacidad de carga similar (15 Toneladas). El origen escogido fue Medellín y los municipios de su área metropolitana. Los destinos se concentraron en 4 ciudades: Cartagena, Bogotá, Buenaventura y Cúcuta. Se obtuvieron dos rutas óptimas: la primera ruta es cubierta por un vehículo con un recorrido de 2,347 Km y la segunda ruta es cubierta por un vehículo con un recorrido de 1,761 Km. Es posible obtener un ahorro de 21.9% en los recursos utilizados dado que las rutas pueden ser cubiertas usando 2 vehículos menos.