Submitted by Automa??o e Estat?stica (sst@bczm.ufrn.br) on 2017-11-01T21:17:49Z No. of bitstreams: 1 EmersonBezerraDeCarvalho_DISSERT.pdf: 1150853 bytes, checksum: f0f5998d8f74eb082da1133fbcf4b27a (MD5) / Approved for entry into archive by Arlan Eloi Leite Silva (eloihistoriador@yahoo.com.br) on 2017-11-07T21:35:18Z (GMT) No. of bitstreams: 1 EmersonBezerraDeCarvalho_DISSERT.pdf: 1150853 bytes, checksum: f0f5998d8f74eb082da1133fbcf4b27a (MD5) / Made available in DSpace on 2017-11-07T21:35:18Z (GMT). No. of bitstreams: 1 EmersonBezerraDeCarvalho_DISSERT.pdf: 1150853 bytes, checksum: f0f5998d8f74eb082da1133fbcf4b27a (MD5) Previous issue date: 2017-07-24 / A heur?stica de Lin e Kernighan (LK) ? um dos m?todos mais eficientes para o Problema do Caixeiro Viajante (PCV). Devido a este fato, diferentes implementa??es para a LK foram propostas na literatura e esta heur?stica ? tamb?m usada como parte de diversos algoritmos meta-heur?sticos. A heur?stica LK tem sido utilizada no contexto do PCV multiobjetivo (PCVM) conforme proposta originalmente por seus autores, isto ?, com o foco mono-objetivo. Este trabalho investiga a extens?o da heur?stica LK no contexto multiobjetivo. ? investigado o potencial de extens?es da LK combinadas com outras t?cnicas meta-heur?sticas. Resultados de um experimento computacional para inst?ncias do PCVM com 2, 3 e 4 objetivos s?o reportados. / The Lin and Kernighan?s heuristic (LK) is one of the most effective methods for the Traveling Salesman Problem (TSP). Due to this fact, different implementations for the LK were proposed in literature and this heuristic is also used as part of various meta-heuristic algorithms. LK has been used in the context of the multi-objective TSP (MTSP) as originally proposed by its authors, i.e., with a single objective focus. This study investigates variants of the LK heuristic in the multi-objective context. We investigate the potential of LK extensions combined with other metaheuristic techniques. Results of a computational experimental are reported for MTSP instances with 2, 3 and 4 objectives.

Memoria para optar al título de Ingeniera Civil Eléctrica / El presente trabajo tiene como objetivo conocer los aportes de los sistemas de almacenamiento a la resiliencia de los sistemas de distribución, ante un evento de baja probabilidad y alto impacto, en términos de profundidad y duración de la falla. Para lo cual, se ha escogido utilizar baterías conectadas a transformadores de distribución, evaluando su desempeño en la recuperación de suministro eléctrico, a través de las metodologías relacionadas con el manejo de cuadrillas de recuperación del sistema. Todas comienzan con la modelación del evento (en este caso sismos), utilizando una medida de aceleración sísmica (Peak Ground Aceleration o PGA) para evaluar el grado de afectación de los elementos de la red. Una vez calculado el PGA se evalúa el estado de daño de las estructuras del sistema a través de las curvas de fragilidad, lo que a su vez introduce la necesidad de realizar múltiples simulaciones, para lograr capturar la naturaleza estocástica del estado de daño de cada elemento. Para evaluar el aporte del almacenamiento al sistema de distribución, se utiliza un modelo aproximado de la red de Santiago, el cual, actualmente no cuenta con dichos sistemas, por lo tanto, se realiza el supuesto de que existen 2.000 sistemas de almacenamiento distribuidos, con una energía promedio almacenada de 12 horas y ubicados de manera aleatoria en la red. La memoria considera el estudio de tres metodologías, la primera es la metodología del Caso Base, la cual realiza el ruteo de cuadrillas utilizando una función de priorización de transformadores, basada en la energía no suministrada, la distancia y el tiempo de restauración según nivel de daño, sin embargo, no considera el uso de la energía almacenada para realizar dicho ruteo, por lo tanto, el aporte de las baterías podría ser ineficiente, cada vez que el algoritmo de ruteo considera reparar transformadores conectados a baterías con energía disponible. La segunda metodología corresponde al Caso 1, la cual, realiza el ruteo de cuadrillas a partir de la función de priorización del caso anterior y además, considera que se debe utilizar toda la energía almacenada en todas las baterías, imponiendo que la posición en el ruteo de los transformadores con baterías, sea inmediatamente después que se les haya agotado la energía, independiente de la distancia a la cual este la cuadrilla. En este caso, los resultados en cuanto a energía no suministrada son considerablemente menores, no así para el tiempo de restauración total del sistema, el cual aumenta en comparación al caso anterior. Finalmente, la metodología del Caso 2, es una combinación entre colocar los transformadores con baterías de manera eficiente en el ruteo, para aprovechar su energía almacenada y considerando las distancias entre transformadores, por tanto, los resultados de este caso son mejores que el Caso 1 en cuanto a tiempo de restauración, en desmedro de una mayor energía no suministrada. La metodología propuesta en el Caso 1, podría mejorar un 25% en promedio la energía no suministrada a cambio de una demora de 7 horas adicionales en corregir el sistema completo. Mientras que el aporte de los sistemas de almacenamiento propiamente tal esta directamente ligado a la capacidad energética de estos, sin embargo, tanto la propuesta del Caso 1, como la del Caso 2 logran ocupar porcentajes importantes de la energía almacenada (cercano al 100% en el Caso 1). Por otro lado, se observa un espacio de mejora relacionado con los algoritmos de clustering que busca que todas las cuadrillas se mantengan activas sin tiempos de inactividad.