3 results
Search Results
Now showing 1 - 3 of 3
Item Heurísticas para el problema del vendedor viajero robusto con incertidumbre intervalarAutores: Mardones Saavedra, Julio AlfredoProfesor Guía: Candia Véjar, Alfredo; Espinoza González, Daniel; Paredes Moraleda, RodrigoEsta tesis aborda el Problema del Vendedor Viajero Robusto con incertidumbre intervalar en los costos, utilizando el criterio de Min-Max Regret.Varios algoritmos son implementados, inclusive uno exacto mediante Descomposición de Benders, pero sólo con propósitos comparativos. En relación a las heurísticas, se desarrolla una nueva llamada n-HU que extrae un número determinado de tours en base al costo robusto considerando el escenario del peor caso, entregando el mejor tour en términos del regret. Se proponen metaheurísticas basadas en Búsqueda Local con diferentes opciones que aprovechan de mejor forma la estructura particular del problema.Se realiza una comparación desde un punto de vista experimental, mostrando un buen desempeño relativo, pues se mejoran los resultados existentes y se hace más evidente la influencia de la complejidad del problema base (TSP) sobre el desempeño de las heurísticas.Palabras clave: Incertidumbre, Min-Max Regret, Problema del Vendedor Viajero./ABSTRACT:This thesis addresses The Robust Traveling Salesman Problem with interval uncertainty in data costs, using the Min-Max Regret criterion. Several algorithms are implemented, including an exact one by Benders Decomposition, but only for comparative purposes. Regarding heuristics, a new approach is developed, it is called n-HU, and extracts a specific number of tours based on robust cost considering the worst case scenario, returning the best tour in terms of regret. Metaheuristics based on Local Search are also implemented with different options to better exploit the structure of the problem. A comparison is made from an experimental point of view; showing a relative good performance, because actual results are improved and it makes evident in a clearer way the influence of the base problem complexity on the heuristics performance. Keywords: Uncertainty, Min-Max Regret, Traveling Salesman Problem.Item Desarrollo de un software para un circuito de molienda convencional incorporando incertidumbre de variables metalúrgicasAutores: Iragüen Laporta, Sebastián IgnacioAutor Institucional: Universidad de TalcaProfesor Guía: Moraga Cruz, Carlos AlejandroEn el contexto desafiante de la industria minera, donde la escasez de agua emerge como un problema central, se anticipa un aumento considerable en los volúmenes de minerales sulfurados a procesar en los próximos años. Este crecimiento conlleva un incremento significativo en la demanda de agua necesaria para el tratamiento de estos minerales. El consumo de agua fresca está intrínsecamente ligado a las propiedades específicas de los minerales a tratar, así como a la cantidad recuperable y recirculable en el proceso. Este estudio se enfoca en la fase crítica de conminución, abordando la molienda convencional y la clasificación de tamaños, resaltando los desafíos operativos y ambientales asociados. Identificando la fuente de incertidumbre en la determinación de variables metalúrgicas y parámetros operacionales, se destaca la posibilidad de estimar estos valores mediante una caracterización precisa, permitiendo conocer el error asociado en su determinación y minimizarlo mediante la aplicación de protocolos específicos. Adoptando un enfoque estocástico, que implica la adaptación de modelos a una simulación de Montecarlo, se busca proporcionar resultados que reflejen la dispersión de valores originada por la incertidumbre de entrada. Los resultados obtenidos revelan tendencias, relaciones entre variables y comparaciones entre niveles de error, contribuyendo así a una visión más completa de las operaciones en la industria minera. La gestión integral de la incertidumbre, destacada como un pilar esencial en la toma de decisiones y diseño de estrategias eficientes en la industria del procesamiento de minerales, se consolida como una herramienta valiosa en este estudio. Al confirmar que la incertidumbre puede ser empleada para evaluar etapas específicas del procesamiento de minerales, el trabajo subraya su importancia para mejorar la comprensión operativa y abordar desafíos no anticipados. La evaluación detallada se centra en la complejidad intrínseca del sistema, considerando tanto variables conocidas como fuentes imprevistas de variabilidad, ampliando así el espectro de resultados posibles y reforzando la adaptabilidad y solidez del sistema.Item Algoritmos para el problema del árbol de expansión robusto con incertidumbre intervalarAutores: Pérez Galarce, Francisco JavierProfesor Guía: Candia Véjar, Alfredo; Paredes Cajas, Fernando; Herrera Leiva, RodrigoEsta tesis aborda el Problema Árbol de Expansión con incertidumbre intervalar en los costos, utilizando el criterio de Min-Max Regret.Varios algoritmos son implementados, tanto exactos como heurísticos. Con respecto a los algoritmos exactos, se implementan Descomposición de Benders y Branch and Cut, ambos incluyen variantes. Branch and Cut logra superar al resto de los algoritmos, incluso obteniendo gaps menores a un 10%, para 100 nodos, en un conjunto de instancias. En relación a las heurísticas, se desarrolla una heurística constructiva, la que utiliza la información de los intervalos, a diferencia de todas las aproximaciones de la literatura. Se proponen metaheurísticas basadas en Búsqueda Local (Mejora iterativa, Simulated Annealing y GRASP), se obtienen gaps de calidad, incluso para las instancias más complejas.Se realiza una comparación desde un punto de vista experimental, mostrando un buen desempeño, pues se igualan o mejoran los resultados existentes.Palabras clave: Incertidumbre, Min-Max Regret, Árbol de expansión./ABSTRACT: This thesis addresses The Robust Spanning Tree Problem with interval uncertainty in data costs, using the Min-Max Regret criterion.Several algorithms are implemented, both exact as heuristic. With respect to exact algorithms are implemented Benders decomposition and Branch and Cut, and both include some variants. Branch and Cut can ourperform the rest of the algorithms, obtaining gaps below 10% for instances with 100 nodes in a set of instances. In relation to heuristics, a constructive heuristic is developed, which uses the information of the intervals, and different to the known approaches from the literature, that only work with scenarios. Metaheuristics based on Local Search (iterative improvement, simulated annealing and GRASP) are proposed and they got quality gap, even for more complex instances . A comparison is made from an experimental point of view, showing a good performance, improving existing results for some group of instances.Key Words: Uncertainty, Min-Max Regret, Spanning Tree.
