Introduccion. Un aspecto emergente en los sistemas de distribucion comercial es reducir el impacto ambiental encontrando las mejores rutas de los vehiculos con el fin de minimizar el tiempo o la distancia total del recorrido y, por ende, el consumo de combustible. La teoria de grafos es una herramienta importante para la solucion de problemas de ruteo de vehiculos con restricciones de capacidad (Capacitated Vehicle Routing Problem, CVRP). Objetivo. Aplicar una herramienta informatica basada en la teoria de grafos para analizar y resolver un CVRP en una empresa de transporte de carga de cubrimiento nacional. Materiales y metodos. El analisis se realizo en una flotilla de 13 vehiculos con las mismas especificaciones tecnicas y capacidad de carga similar (15 toneladas). El origen escogido fue Medellin y los municipios de su area metropolitana. Los destinos se concentraron en 4 ciudades: Cartagena, Bogota, Buenaventura y Cucuta. Resultados. Se obtuvieron dos rutas optimas. La primera ruta es cubierta por un vehiculo con un recorrido de 2.347 Km. La segunda ruta es cubierta por un vehiculo con un recorrido de 1.761 Km. Conclusiones. Se puede obtener un ahorro de 21.9% en el consumo de combustible dado que las rutas pueden ser cubiertas usando 2 vehiculos menos. Es necesario complementar la solucion teorica obtenida con una adecuada planeacion de rutas para evitar desplazamientos vacios de los vehiculos.