Por favor, use este identificador para citar o enlazar este ítem:
http://cicese.repositorioinstitucional.mx/jspui/handle/1007/415| Diseño de algoritmos bioinspirados para el problema multiobjetivo p-mediana bajo incertidumbre A multi-objective evolutive algorithm approach for the multiobjective p-Median problem under uncertainty | |
| Francisco López Monzalvo | |
| Carlos Alberto Brizuela Rodríguez | |
| Acceso Abierto | |
| Atribución | |
| Algoritmos evolutivos,Problema p-Mediana,Multi-Objetivo,Teoría de confiabilidad,Teoría de robustez,Teoría de incertidumbre,NSGA-II | |
| El problema de localización de instalaciones bajo ambientes de incertidumbre es un problema importante y desa?ante. Su objetivo es la ubicación óptima de las instalaciones o centros de distribución que sirven a un conjunto de nodos o clientes que se encuentran distribuidos en una región determinada. Una forma de resolver este problema es modelando la incertidumbre por medio de escenarios para optimizar algún criterio de robustez, tal como el lamento promedio o el máximo lamento sobre todos esos escenarios. Se propone entonces emplear una metodología de solución y análisis aproximado de problemas multiobjetivo basada en algoritmos evolutivos para resolver un problema de localización de instalaciones (p-mediana) multiobjetivo bajo incertidumbre. Para ello, el estudio se divide en dos partes: en la primera se modela el problema de diseño robusto como uno de optimización del lamento promedio y máximo lamento, el cual se resuelve por medio de un algoritmo evolutivo, el NSGA-II. Con este mismo algoritmo se analiza el efecto de las variaciones en el cambio de los parámetros del problema y del algoritmo evolutivo sobre la calidad de las soluciones obtenidas. En la segunda parte se propone modelar el diseño robusto-con?able como un problema de optimización de tres objetivos: lamento promedio, máximo lamento y con?abilidad. Los resultados experimentales muestran que: i) El algoritmo evolutivo propuesto resuelve, con buena aproximación al frente Pareto, tanto el diseño robusto como el robusto-con?able. ii) Los frentes no dominados más robustos se obtienen cuando la cota inferior de la función objetivo del producto demanda-distancia entre nodos minoristas y centros de distribución es más cercana al óptimo. iii) Cuando el número de centros de distribución se aproxima al número de nodos, se obtienen soluciones no dominadas más robustas, sin embargo hay casos donde es posible obtener, con un número menor de centros de distribución, un frente Pareto que domina a otro obtenido con un número mayor de centros de distribución, como se muestra en la comparación de un caso de 3 centros de distribución contra uno de 5. iv) La evidencia experimental no permite de?nir una regla de comportamiento general para la robustez en el caso en el que se deja ?jo el número de centros de distribución y se varía el número de clientes. v) Con respecto a los resultados del modelo robusto-con?able, más que generar conclusiones de?nitivas, nos motiva a plantear preguntas interesantes, tales como, ¿cuánto tiempo adicional necesita invertir el algoritmo para conseguir, con tres funciones objetivo, la misma calidad de solución obtenida al optimizar dos funciones objetivo?, ¿cuál es la relación entre el costo computacional al optimizar al mismo tiempo tres funciones objetivo y el costo al optimizar dos para distintos valores del tercer objetivo?. Facility location problem under uncertain environments is an important and challenging problem that deals with the optimal location of facilities, or distribution centres, that serve a set of spatially distributed retailers nodes. One way to deal with this problem is by modelling uncertainty by means of scenarios, while some robustness criteria, such as average and maximum regrets, are optimised over them. We propose to use a solution methodology for multi-objective problems based on evolutionary algorithms, in order to solve a multi-objective facility location problem (p-median) under uncertainty. Therefore, this study is divided into two parts: ?rst, we model the robust design as an optimization problem that seeks to minimize the average and maximum regrets, we then analyse the e?ects of variations in the problem parameters on the quality of the Pareto solutions. In the second part, we propose to model the robust and reliable design as an optimization problem considering three objective functions: average regret, maximum regret, and reliability. The experimental results show that: i) The proposed evolutionary algorithm solves, with good approximation to the Pareto front both, the robust and the robust and reliable facility location model. ii) Solutions with higher robustness are obtained when the lower bound of the objective function, related to the demand-distance product between retailer nodes and distribution centres, is closer to the optimum. iii) When the distribution centres number is close to the retailer nodes number, the most robust non-dominated fronts are obtained, however, there are cases where it is possible to ?nd, with a smaller number of distribution centres, a Pareto front which dominates another one that is obtained with a larger number of distribution centres. iv) The experimental evidences do not allow us to state a general behaviour rule for the robustness in the case where the number of distribution centres is ?xed and the number of retailer nodes is varied. v) In the case of the robust and reliable model, the experimental results motivate us to formulate a set of interesting questions such as, how much additional time does the algorithm need to invest in order to achieve, with three objective functions, the same quality of solution obtained while optimizing two objective functions?, in terms of computation time, what is the relationship between optimizing simultaneously three objective functions, compared to optimizing two of them for di?erent values of the third one? | |
| CICESE | |
| 2013 | |
| Tesis de doctorado | |
| Español | |
| López Monzalvo,F.2013.Diseño de algoritmos bioinspirados para el problema multiobjetivo p-mediana bajo incertidumbre.Tesis de Doctorado en Ciencias. Centro de Investigación Científica y de Educación Superior de Ensenada, Baja California.xiv, 140 pp. | |
| CIENCIA DE LOS ORDENADORES | |
| Aparece en las colecciones: | Tesis - Ciencias de la Computación |
Cargar archivos:
| Fichero | Descripción | Tamaño | Formato | |
|---|---|---|---|---|
| 232611.pdf | Versión completa de la tesis | 2.73 MB | Adobe PDF | Visualizar/Abrir |