Browsing by Author "Escobar Riquelme, Claudia Andrea"
Now showing 1 - 1 of 1
- Results Per Page
- Sort Options
Thesis IMPLEMENTACIÓN DE METAHEURÍSTICAS PARA LA RESOLUCIÓN DEL PROBLEMA DE RUTEO DE VEHÍCULOS CON CAPACIDAD LIMITADA Y VENTANAS DE TIEMPO(2017-11) Escobar Riquelme, Claudia Andrea; Riff, María Cristina; Universidad Tecnica Federico Santa Maria UTFSM INFORMATICA; Montero, ElizabethEl presente trabajo muestra tres soluciones algorítmicas para Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) el cual corresponde a un problema NP-hard con un enfoque multi-objetivo que busca la optimización del tiempo/distancia total de las rutas (D), la cantidad de vehículos (K) y balancear el tiempo/distancia de las rutas (RB). Se trabajó con el Solomon’s Benchmark para CVRPTW de 25, 50 y 100 clientes. Las técnicas implementadas corresponden a metaheurísticas poblacionales basadas en la naturaleza: un Algoritmo Inmune Artificial de Selección Clonal (AIS), un Sistema de Colonia de Hormigas con Búsqueda Local (ANT) y un híbrido de ambas (ALL). Se utilizó ParamILS para sintonizar los parámetros asociados a cada algoritmo y para potenciar su desempeño. De esto se desprende que en comparación AIS tiene un buen desempeño en instancias pequeñas de 25 y 50 clientes pero al aumentar a 100 clientes no logra obtener soluciones al nivel de otras técnicas. Por último los resultados de ANT son buenos y se mantienen estables para todotipo de instancias comparativamente aunque no es el mejor. Por otro lado la versión híbrida ALL logra malos resultados en instancias pequeñas pero en 100 clientes logra superar en casi todas las ejecuciones a las otras versiones principalmente en el objetivo D. Además se calculó el aporte en hipervolumen de cada frente agregado para comparar desempeño de las técnicas entre sí en términos de calidad general de los resultados para todas las instancias.
Política de Privacidad 
