Aplicación de la teoría de grafos en la solución de problemas con impacto ambiental

Introduction. An aspect that is emerging in the commercial distribution systems is the reduction of environmental impacts, by finding the best routes for the vehicles to take and aiming to reduce time or distance and, thus, fuel consumption. The graph theory is an important tool to solve routing problems for vehicles with a restricted capacity (Capacitated Vehicle Routing Problem, CVRP). Objective. To apply an informatics tool based on the graph theory to analyze and solve a CVRP in a national cargo transportation company. Materials and methods. A 13 vehicles fleet with the same technical specifications and load capacity (15 tons) were analyzed. The c hosen departure place was Medellín and its surrounding towns. Destinations were concentrated in four cities: Cartagena, Bogotá, Buenaventura and Cúcuta. Results. Two optimal routes were found: The first one is covered by a vehicle with a distance of 2347 Km. The second is covered by a vehicle with a distance of 1761 Km. Conclusions. A 21.9% saving in fuel consumption can be achieved because the routes can be covered by the use of 2 vehicles or less. It is necessary to complement the theoretical solution obtained with an adequate route planning in order to avoid moving empty vehicles.Introdução. Um aspecto emergente nos sistemas de distribuição comercial é reduzir o impacto ambiental encontrando as melhores rotas dos veículos com o fim de minimizar o tempo ou a distância total do percurso e, portanto, o consumo de combustível. A teoria de grafos é uma ferramenta importante para a solução de problemas de roteio de veículos com restrições de capacidade (Capacitated Vehicle Routing Problem, CVRP). Objetivo. Aplicar uma ferramenta informática baseada na teoria de grafos para analisar e resolver um CVRP numa empresa de transporte de carga de cobertura nacional. Materiais e métodos. A análise se realizou numa frota de 13 veículos com as mesmas especificações técnicas e capacidade de carga similar (15 toneladas). A origem escolhida foi Medellín e os municípios de sua área metropolitana. Os destinos se concentraram em 4 cidades: Cartagena, Bogotá, Buenaventura e Cúcuta. Resultados. Obtiveram-se duas rotas ótimas. A primeira rota é coberta por um veículo com um percurso de 2.347 Km. A segunda rota é coberta por um veículo com um percurso de 1.761 Km. Conclusões. Pode-se obter uma poupança de 21.9% no consumo de combustível dado que as rotas podem ser cobertas usando menos 2 veículos. É necessário complementar a solução teórica obtida com um adequado planejamento de rotas para evitar deslocamentos vazios dos veículos.Introducción. Un aspecto emergente en los sistemas de distribución comercial es reducir el impacto ambiental encontrando las mejores rutas de los vehículos con el fin de minimizar el tiempo o la distancia total del recorrido y, por ende, el consumo de combustible. La teoría de grafos es una herramienta importante para la solución de problemas de ruteo de vehículos con restricciones de capacidad (Capacitated Vehicle Routing Problem, CVRP). Objetivo. Aplicar una herramienta informática basada en la teoría de grafos para analizar y resolver un CVRP en una empresa de transporte de carga de cubrimiento nacional. Materiales y métodos. 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. Resultados. Se obtuvieron dos rutas óptimas. La primera ruta es cubierta por un vehículo con un recorrido de 2.347 Km. La segunda ruta es cubierta por un vehículo 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 vehículos menos. Es necesario complementar la solución teórica obtenida con una adecuada planeación de rutas para evitar desplazamientos vacíos de los vehículos