INVESTIGADOR(ES) PRINCIPAL(ES):

Ramon Alfonso Gallego Rendón

13 horas

CODIGO CIE

6-16-3

Antonio Hernando Escobar Zuluaga

Coinvestigador

4 Horas

John Fredy Franco Baquero

Estudiante

0 Horas

David Escobar Vargas

Estudiante

0 Horas

Eliana Mirledy Toro Ocampo

Coinvestigador

13 Horas

Manuela Del Pilar Gómez Suta

Estudiante

0 Horas

Luis Fernando Galindres Guancha

Coinvestigador

0 Horas

Lisbeth Carolina Pava García

Estudiante

0 Horas

TIPO DE CONVOCATORIA

2015. Novena Convocatoria

TIPO DE PROYECTO

Investigación Aplicada

OBJETIVO(S)

Objetivo General: Proponer un modelo general de solución para el problema de ruteo atendido con flota propia y subcontratada que resuelva el CVRPCC, MDVRPCC y CLRPCC. Objetivos específicos : -Realizar una revisión del estado del arte de los problemas CVRP, MDVRP, CLRP y OVRP. - Realizar una revisión del estado del arte de los problemas CVRPCC, MDVRPCC y CLRPCC. - Plantear un modelo matemático general que resuelva las variantes de VRP: CVRP, MDVRP, CLRP, OVRP, CVRPCC, MDVRPCC y CLRPCC. - Implementar en lenguaje AMPL el modelo propuesto. - Validar el modelo matemático con instancias de prueba de la literatura especializada - Presentar metodologías y resultados a la comunidad académica y sector productivo.

RESUMEN

Inicialmente fue realizada una revisión del estado del arte de los problemas CVRP, MDVRP, CLRP, OVRP, MDOVRP y OLRP. Posteriormente a los problemas CVRPCC, MDVRPCC y CLRPCC y cuyo objetivo en estos últimos era identificar vacíos en el estudio de estos problemas. En el estudio del problema de ruteo, se pueden identificar vacíos en alguno de los siguientes aspectos: el modelo matemático, el método de solución o la metodología de solución, que considera tanto el modelo como el método de solución. La búsqueda fue realizada en bases de datos reconocidas, identificando revistas que tratan el problema de transporte. En la revisión se encontraron pocas publicaciones en el problema CVRPCC, las cuales fueron verificadas con instancias de baja complejidad matemática. Para los problemas MDVRPPC y CLRPCC, no se encontraron evidencias de publicaciones. Generalmente este problema ha sido resuelto en dos etapas de manera independiente, en la primera se resuelve el problema con vehículos propios y en una segunda etapa, con los clientes que no hayan sido atendidos, se resuelve el problema con vehículos subcontratados. Posteriormente, fue planteado un modelo matemático que resuelve el problema de ruteo de vehículos con flota propia y el mismo fue adecuado para la solución del problema con flota subcontratada. Seguidamente son combinados los modelos que resuelven el problema con flota propia y subcontratada y planteado el modelo matemático de los problemas CVRPCC, MDVRPCC y CLRPCC. Entre las características del modelo está el uso de dos grafos independientes, uno para flota propia y el segundo para la subcontratada. La duplicación del grafo incrementa de manera ostensible la complejidad matemática del problema. Una segunda característica es la restricción del número de vehículos de la flota propia y un pago único por el uso de vehículos subcontratados, el cual es establecido en el uso del arco. En la etapa de validación son estudiados los modelos matemáticos que consideran flota propia y subcontratada de manera independiente, usando el método de optimización exacto Branch and cut, para lo cual se usó el software comercial CPLEX. Para el análisis de los modelos se emplearon instancias de la literatura. Posteriormente fueron validadas los modelos con vehículos subcontratados y por ultimo son validadas instancias de la literatura especializada, para los problemas CVRPCC, MDVRPCC y CLRPCC. Para el CVRPCC se encontraron algunas instancias que sirvieron como referencia, obteniendo resultados que muestran que se trata de un modelo con un buen desempeño. Para los problemas MDVRPCC y CLRPCC, no se encontraron sistemas de prueba que sirvieran como referencia, así que se optó por instancias usadas en la solución de los problemas MDVRP y CLRP. Estas instancias fueron adecuadas al nuevo modelo propuesto, ya que en este, los problemas de vehículos propios y subcontratados, se resuelven de manera simultánea. Entre las nuevas consideraciones están la restricción de la flota propia de vehículos y costo de desplazamiento en los arcos para la flota subcontratada. Finalmente el modelo CVRPPC fue implementado usando la meta heurística ILS. Los resultados obtenidos fueron comparados con los del método exacto descrito anteriormente, validando la eficiencia de la metaheurística. En la siguiente etapa fueron estudiadas instancias de mediana y gran complejidad matemática, obteniendo resultados de buena calidad. Los resultados muestran un desempeño aceptable del modelo planteado para los problemas CVRPCC, MDVRPCC y CLRPCC. El modelo es general y con capacidad para resolver los tres problemas usando un método exacto de solución. El problema CVRPPC resuelto con la metaheuristica ILS, obtiene soluciones de alta calidad en instancias de gran complejidad matemática.

ESTADO

Concluido

FECHA DE INICIO

18/01/2016

FECHA DE FINALIZACION

18/01/2018

PRODUCTOS

Revisión del estado del arte del problema de ruteo abierto (OVRP)

Pregrado

Escuela Latinoamericana de Verano de Investigación de Operaciones - ELAVIO 2016

Ponencia en evento especializado

Green open location-routing problem considering economic and environmental costs

Artículos en revista A1 ó A2

Introducing radiality constraints in capacitated location-routing problems

Artículos en revista A1 ó A2

Mathematical Model for Capacitated Location Routing Problem with Private Fleet and Common Carrier

Artículos en revista A1 ó A2

Metaheurística ILS-VNS para la solución del problema de ruteo de vehículos con flota propia y subcontratada VRPC

Maestría o Especialidad clínica

Specialized Genetic Algorithm Combined with an Efficient Binary Linear Programming Method Aplied to the Capacitated Vechicle Routing Problem (CVPR)'

Ponencia en evento especializado