INVESTIGADOR(ES) PRINCIPAL(ES):

Mauricio Granada Echeverri

13 horas

CODIGO CIE

6-19-5

Eliana Mirledy Toro Ocampo

Coinvestigador

13 Horas

Ricardo Alberto Hincapié Isaza

Coinvestigador

13 Horas

Ramon Alfonso Gallego Rendón

Coinvestigador

13 Horas

TIPO DE CONVOCATORIA

2018. Décimosegunda Convocatoria

TIPO DE PROYECTO

Desarrollo Experimental

OBJETIVO(S)

Implementar una herramienta computacional que permita transitar desde el modelo simple del TSP hasta el OLRP, pasando por el MTSP, CVRP y MCVRP para resolver de forma óptima la programación de rutas para entrega de mercancía en cada escenario.

RESUMEN

Entre los procesos claves de toda empresa dedicada a ofrecer servicios logísticos se encuentra uno de gran importancia conocido como ¿cadena de suministro¿, cuyo objetivo fundamental es distribuir un producto o servicio desde un proveedor hasta un cliente. En el contexto de transporte de productos, este proceso de distribución ha sido uno de los aspectos que más ha evolucionado en los últimos años, propendiendo el mejoramiento de los costos de transporte, impacto ambiental, tiempo de entrega y distancias recorridas, entre otros. Sin embargo, esta creciente evolución ha derivado inexorablemente en un incremento de la complejidad de las operaciones de transporte y distribución, así como de los modelos matemáticos y técnicas de solución. Esto, a su vez, ha originado un creciente interés por herramientas computacionales que permitan, de forma simple, una gestión logística óptima dentro de las empresas de transporte de diferentes tipos y estrategias de distribución de productos. Muchos de los problemas de optimización de rutas estudiados y definidos en la literatura especializada intentan representar diferentes estrategias o escenarios de distribución de bienes que, en el contexto del alcance del presente proyecto, se pueden clasificar de menor a mayor según su nivel de complejidad, utilizando problemas bien conocidos y definidos en la literatura especializada, tales como: 1) Problema del agente viajero, (TSP, Travelling Salesman Problem): este problema existe cuando un vehículo, con suficiente capacidad, sale desde un punto de acopio (depósito), realiza la entrega de productos a todos los clientes y regresa al depósito. Esta ruta recibe el nombre de circuito Hamiltoniano. 2) Problema de múltiples agentes viajeros (MTSP): en este problema existe una flota de n vehículos con capacidad suficiente, que deben distribuir sus productos de forma que se generan n circuitos. 3) Problema de ruteo de vehículos con capacidad (CVRP, Capacitated Vehicle Routing Problem): este problema es similar al MTSP pero se considera una flota de vehículos homogénea (iguales) con capacidad de carga limitada. 4) CVRP con múltiples depósitos (MCVRP, Multi-Depot CVRP): es el mismo CVRP considerando varios depósitos de acopio de productos. Estos depósitos ya existen, por lo cual el problema consiste en planear las rutas óptimas de la flota de vehículos saliendo y regresando a los diferentes depósitos. 5) Problema abierto de ubicación y ruteo de vehículos (OLRP, Open Location Routing Problem.): en este problema se considera la ubicación de múltiples depósitos. Por lo tanto se deben ubicar de forma óptima y posteriormente se deben planificar las rutas de distribución. La característica del ¿problema abierto¿ implica que las rutas no regresan al depósito, sino que terminan en un cliente. Existen muchos otros problemas de ruteo de vehículos, sin embargo los mencionados anteriormente conforman un bloque interesante de estrategias de distribución típicas existentes en la mayoría de empresas logísticas. Por lo tanto, en este proyecto se propone desarrollar un aplicativo computacional que integre eficientemente estas cinco estrategias y que permita obtener el conjunto de rutas óptimas en cada una, usando una técnica exacta de optimización matemática. El objetivo de esta herramienta computacional es contribuir al mejoramiento de la competitividad del sector de transporte de bienes y apoyar los actuales procesos de asignación y planeación asociados a la generación de rutas óptimas de distribución de productos. Esta temática es de interés actual tanto en la comunidad académica como en el sector de transporte. La efectividad de la herramienta propuesta será determinada a través de comparaciones con casos existentes en la literatura especializada.

SÍNTESIS DEL PROYECTO

In the open location¿routing problem (OLRP), one has a set of candidate depots to be installed and the vehicles start from the depot, visit all customers, and are not required to return to the depot after completing their service. Thus, the OLRP involves the problems of facility location and open vehicle routing. In this paper, a new mixed integer programming formulation for the OLRP is presented by proposing a set of constraints to obtain valid solutions formed by a graph consisting of a spanning tree in each connected component of the graph. This approach results in an alternative way of avoiding generating subtours, which significantly simplifies the set of constraints associated with the connectivity of the solution and the vehicle capacity requirements. The computational results show that the proposed formulation is competitive against state of¿the¿art methods for this type of problems

ESTADO

Concluye Parcialmente

FECHA DE INICIO

28/01/2019

FECHA DE FINALIZACION

28/01/2021

PRODUCTOS

Integrated Methodology for the Planning of Electrical Distribution System Considering the Continuity of the Service and the Reduction of Technical Losses

Circulación de conocimiento especializado

A specialized genetic algorithm for the fuel consumption heterogeneous fleet vehicle routing problem with bidimensional packing constraints

Demás tipos de producción bibliográfica

URL

Modelos matemáticos para la programación óptima de rutas: formulación e implementación

Libro resultante de investigación

URL