Algoritmo hibrido combinando un sistema evolutivo colonia de hormigas con busqueda tabu para la solución del problema de ruteo de vehiculos con ventanas de tiempo duras
No Thumbnail Available
Date
2014
Advisors
Evaluators
Journal Title
Journal ISSN
Volume Title
Publisher
Universidad Industrial de Santander
Abstract
En el presente trabajo se aborda la problemática de la planificación de rutas de transporte para el reparto de mercancías donde se contempla la ventana de tiempo en el cual el cliente debe ser visitado, este tipo de problema es conocido en la literatura como el Problema de Ruteo de Vehículos con Ventanas de Tiempo (VRPTW por sus siglas en inglés). El VRPTW aporta mayor realismo al problema de ruteo de vehículos. La complejidad de gran parte de los problemas de ruteo de vehículos hace que no se puedan resolver instancias en tiempo de cómputo razonable, es por ello que este tipo de problemas es considerado como NP-duros. Para su solución, se han desarrollado técnicas aproximadas. Entre las herramientas de optimización, se encuentran los métodos metaheurísticos, que buscan soluciones en tiempo moderado. Se propone un algoritmo híbrido entre dos metaheurísticas: algoritmo colonia de hormigas y algoritmo búsqueda tabú, apoyándose en las heurísticas Vecino más cercano e Inserción I1. El algoritmo busca minimizar tanto vehículos como distancias, para ello trabaja con dos colonias de hormigas, VEI y TIME, cada una dedicada a un objetivo. Los resultados obtenidos son comparados con el conjunto de problemas tipo de Solomon (1987) y con otros encontrados en la literatura.
Description
Keywords
Optimización Combinatoria, Ruteo De Vehículos Con Ventanas Horarias, Colonia De Hormigas, Búsqueda Tabú, Heurística, Metaheurística