Análisis del rendimiento del algoritmo OptQuest para optimización en simulación.
Loading...
Date
2014
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
La simulación computacional es una herramienta que permite modelar sistemas complejos que son difíciles de representar fielmente mediante técnicas matemáticas tradicionales. En este contexto, se han desarrollado diversas herramientas de optimización en simulación, ocupando distintos enfoques: algoritmos basados en técnicas tradicionales, algoritmos basados en conceptos de búsqueda aleatoria y metaheurísticas, que son la base de la gran mayoría de los software comerciales de optimización en simulación. En este trabajo se presenta un estudio detallado del rendimiento del algoritmo comercial OptQuest aplicado a problemas reales de optimización en simulación. El objetivo de esto es encontrar debilidades y fortalezas del algoritmo, para luego proponer recomendaciones para los usuarios de OptQuest y para desarrollos científicos futuros como la elaboración de nuevos algoritmos basados en los principios de OptQuest o la realización de mejoras en el motor actual de OptQuest.
La metodología de esta tesis consiste en aplicar el algoritmo a tres problemas reales de optimización en simulación: asignación de horarios de trabajo en un supermercado para minimizar el tiempo de espera en las cajas de un supermercado; definición de dotación de trabajadores en un centro de distribución para mejorar los tiempos de los procesos que ocurren dentro de éste; definición de dotación de mecánicos e inventario de repuestos en una faena minera para maximizar las ganancias. Los resultados obtenidos muestran que OptQuest mejora de forma rápida, alcanzando buenas soluciones en pocas iteraciones. A pesar de esto, también se observó que el algoritmo no logra ocupar la diversidad entre las soluciones probadas de forma eficiente para mejorar la búsqueda. Por otro lado, el algoritmo presenta dificultades al enfrentar problemas con restricciones aleatorias ya que encuentra pocas soluciones factibles durante la búsqueda. Entre las recomendaciones se plantea el uso de buenas soluciones en la población inicial para aumentar la velocidad de convergencia y métodos alternativos de diversidad que buscan generar soluciones diversas de buena calidad.
Description
Tesis (Magíster en Ciencias de la Ingeniería)--Pontificia Universidad Católica de Chile, 2014