Seminario de investigación : algunos métodos de solución para el cvrp
No Thumbnail Available
Date
2010
Advisors
Evaluators
Journal Title
Journal ISSN
Volume Title
Publisher
Universidad Industrial de Santander
Abstract
En este proyecto se presentan los conceptos básicos y la formulación matemática del problema del agente viajero, el problema del agente viajero múltiple y el problema de ruteo de vehículos con capacidad, seguidos del estudio del método exacto Branch and Bound, y las metaheurísticas Algoritmos genéticos y Colonia de hormigas como métodos de solución al problema de ruteo de vehículos con capacidad (CVRP). Para el desarrollo de este trabajo se llevó a cabo una extensa revisión bibliográfica con la que se estableció el estado del arte del CVRP y las técnicas de solución mencionadas para resolverlo. El estudio de cada una de las técnicas se realizó con la explicación de conceptos básicos generales y posteriormente enfocados a la solución de ejercicios específicos del CVRP. Se muestran las relajaciones básicas y las relajaciones avanzadas propuestas para encontrar una solución con la aplicación del método exacto en GAMS utilizando CPLEX como optimizador. Se explica detalladamente el algoritmo genético y el algoritmo colonia de hormigas junto con el desarrollo de un ejemplo del CVRP con solución en Matlab. Estos temas fueron recopilados en un libro, anexo de este documento. Para mayor claridad se realizó un tutorial de GAMS que muestra el contenido de los temas desarrollados en el documento con la aplicación de diversos ejercicios. La herramienta de algoritmos genéticos de MatLab (Genetic Algorithm Tool) es ilustrada mediante la implementación de una instacia del CVRP, así como desarrollo de un algoritmo específico; de manera similar se explica el desarrollo de cada elemento del algoritmo Colonia de Hormigas. Los documentos pretenden guiar a los lectores en el manejo de estos programas/herramientas y sobre sus funciones principales. Finalmente, el libro describe la metodología de trabajo utilizada por el grupo para el desarrollo del tema mediante la modalidad de seminario de investigación.
Description
Keywords
Ruteo De Vehículos, Branch And Bound, Optmización Combinatoria, Algoritmos Genéticos, Colonia De Hormigas.