Orientador: Rubén Augusto Romero Lázaro / Banca: Antonio Padilha Feltrin / Banca: Eduardo Nobuhiro Asada / Resumo: O Problema de Alocação Ótima de Bancos de Capacitores em sistema de distribuição radial consiste em determinar os tipos, tamanhos, localizações e esquema de controle dos bancos alocados nos alimentadores primários dos sistemas de distribuição. Para a solução deste problema são consideradas restrições de tensão e tamanho de bancos de capacitores alocados nas barras do sistema de modo a se minimizar as perdas de potência e energia, ao longo de um período de planejamento considerado, e manter o perfil de tensão das barras do sistema dentro da faixa adequada, exigida pela legislação do setor elétrico nacional. Por se tratar de um problema de difícil solução, uma vez que ele é tratado como sendo um problema de programação não-linear inteiro misto, e por apresentar explosão combinatorial à medida que a dimensão do problema cresce, propõe-se, neste trabalho, a utilização da metaheurística Particle Swarm como método de solução para o problema analisado. Além disso, é realizada uma análise da influência dos parâmetros e da topologia de vizinhança do algoritmo Particle Swarm sobre o processo de convergência do problema estudado para soluções de boa qualidade. Um algoritmo híbrido, composto pelo algoritmo Particle Swarm e pelo operador de mutação, que é freqüentemente usado em algoritmos genéticos... (Resumo completo, clicar acesso eletrônico abaixo) / Abstract: The Optimal Capacitor Placement Problem for radial distribution networks aims to determine capacitor types, locations and control scheme on primary distribution feeders. To the solution of this problem are considered voltage constraint and size constraint of placement capacitor on primary distribution network in a manner to minimize the power and energy losses along of period of planning considered and maintain the voltage profile of distribution network is inside of adequate range of according to the requirement of the national electrical sector legislation. The problem is of difficult solution, because the problem is formulated as a mixed integer nonlinear program, and presents combinatorial explosion when the dimension of the problem grow up. It proposes in this work to use the Particle Swarm meta-heuristic to solve the problem. Moreover, it is done an analysis of influence of the parameters and of the neighborhood topology of Particle Swarm algorithm over the convergence process to good solutions. A hybrid algorithm, composed for Particle Swarm algorithm and mutation process often used in genetic algorithm, is used to solve the problem above. Another important thing relative to this work is about the maintenance of profile voltage inside adequate range voltage although it is considered a high peak load level, being... (Complete abstract click electronic access below) / Mestre

Orientadora: Profª. Drª. Deise M. Bertholdi Costa / Co-orientador: Prof. Dr. Luiz Fernando Nunes / Dissertação (mestrado) - Universidade Federal do Paraná, Setor de Tecnologia, Programa de Pós-Graduaçao em Métodos Numéricos em Engenharia. Defesa: Curitiba, 25/11/2011 / Inclui bibliografias / Resumo: O transporte, em geral, representa nos dias atuais, o maior percentual de custos do na atividade logística. Por isso, muitas empresas estão repensando seus processos para redução dos mesmos. A otimização da distribuição de produtos é um problema estudado há muito tempo por pesquisadores da área de matemática, pesquisa operacional e da computação. Este tipo de problema é dado como um típico problema de otimização combinatória. O Problema do Caixeiro Viajante (PCV) é um clássico deste tipo de problema. Assim, como o Problema de Roteamento de Veículos (PRV), o qual busca o menor caminho dentre N lugares de destino. Na literatura podem ser encontrados trabalhos e abordagens propostos, que utilizam formulações exatas, algoritmos heurísticos e metaheurísticos. O objetivo deste trabalho foi realizar um estudo de caso que envolvesse um número significativo de pontos visitados por algum tipo de veículo, visando analisar e comparar, em termos de desempenho computacional e qualidade das soluções obtidas, as Heurísticas de Construção e Melhoria de Rota e das Metaheurísticas Ant System, Simulated Annealing e Algoritmos Genéticos para o PCV. Também foi aplicado o algoritmo 2- opt para melhoria das rotas geradas. As técnicas foram aplicadas tendo em vista que a otimização das visitas e distribuição dos produtos pode reduzir custos e principalmente os atrasos nas entregas. Para implementação foram utilizados dados reais de uma distribuidora de produtos para uma determinada região da cidade de Curitiba (PR), Brasil. Através do aplicativo online, Google Earth foram obtidas as coordenadas geográficas dos pontos de visitação, que foram então convertidas para coordenadas cartesianas, para a utilização nos algoritmos. Os resultados obtidos foram comparados com as rotas reais praticadas na época por um dos representantes da referida distribuidora. / Abstract: Transport, in general, on average absorbs the highest percentage of costs than any other logistics activity, so many companies are rethinking their processes to reduce them. The optimization of the distribution of products is a problem that is studied for a long time by researchers in mathematics, operational research and computing. This type of problem is given as a typical combinatorial optimization problem. The Traveling Salesman Problem (TSP) is a classic of this, as well as the Vehicle Routing Problem (VRP), where it briefly conceptualizes in finding the shortest path from N places of destination. In the literature there are many jobs and proposed approaches, and some of these heuristics and metaheuristics will be studied and analyzed. The objective of this work was to perform a case study involving a significant number of points visited by some kind of vehicle in order to analyze and compare in terms of computational performance and quality of the solutions obtained, the Construction and Improvement Heuristics and Route Ant System metaheuristics, Simulated Annealing and Genetic Algorithms for the TSP, and has also applied the 2-opt algorithm for improving the routes generated, with a view that the optimization of the visits and distribuition product will reduce costs and above all, the delivery delays. We used real data from a distributor of products in a specific region of Curitiba (PR), Brazil. Using Google Earth has picked the geographical coordinates of points of visitation, which were converted to Cartesian coordinates, for application of the algorithms used. The results were compared with the true routes that are being used by a particular representative of that distributor.

Resumo: O Particle Swarm Optimization (PSO) pertence a uma classe de algoritmos inspirados em comportamentos sociais naturais inteligentes, chamada Swarm Intelligence (SI). O algoritmo PSO tem sido aplicado com sucesso na resolução de problemas de otimização contínua, no entanto, o seu potencial em problemas discretos não foi suficientemente explorado. Trabalhos recentes têm proposto a implementação de PSO usando algoritmos de busca local e Path relinking com resultados promissores. Este trabalho tem como objetivo apresentar um algoritmo PSO como um meta-modelo que utiliza internamente busca local e Path relinking, mas diferentemente das abordagens anteriores, o algoritmo proposto mantém o conceito principal de PSO para a atualização da velocidade da partícula. O trabalho descreve o algoritmo proposto como uma plataforma geral para problemas combinatórios. Tal proposta é validada em duas implementações: uma aplicada ao Problema do Caixeiro Viajante e outra ao Problema da Mochila. As peculiaridades e uma série de experimentos de calibragem de ambos os algoritmos são relatados. Finalmente, a qualidade do algoritmo proposto é testada na comparação com outros PSO discretos da literatura recente e também com outro conhecido algoritmo de metaheurística: o Ant Colony Optimization (ACO). Os resultados são encorajadores e reforçam a idéia de que o algoritmo PSO também pode ser competitivo em espaço de busca discreto, assim como levam a crer que a utilização de métodos dependentes do problema pode ser uma excelente alternativa na aplicação de PSO a este tipo de problema.

Orientadora : Profª. Ph.D. Aurora Pozo / Dissertação (mestrado) - Universidade Federal do Paraná, Setor de Ciências Exatas, Programa de Pós-Graduação em Informática. Defesa: Curitiba, 29/02/2016 / Inclui referências : f. 81-87 / Resumo: O algoritmo de Otimização por Enxame de Partículas (PSO) e uma meta-heurística inspirada no comportamento de bandos de aves a procura de alimento. Os bons resultados obtidos por esta técnica na otimização de problemas mono-objetivo incentivaram o estudo de variações para problemas multi- objetivo (MOPSO), que também alcançaram bons resultados. Para a adaptação do PSO para problemas multi-objetivo algumas modificações foram necessárias, tais como o uso de um operador para seleção de líder e a aplicação de um operador de arquivamento. Entretanto, a qualidade do algoritmo diminui conforme o aumento do numero de objetivos. Encontrar, dentre os diferentes operadores de selecao de líder e de arquivamento, propostos na literatura, os mais apropriado para determinada instância de um problema permite amenizar esta perda de qualidade. Porem esta tarefa não é uma tarefa trivial. Em trabalhos anteriores o uso de hiper-heurística para a seleção de uma combinação apropriada destes operadores e proposta. Hiper-heurísticas são técnicas para a seleção, ou geração, de heurísticas para problemas de busca. Estas técnicas visam a seleção, ou geração, de uma heurística apropriada para determinada instancia de um problema ou estágio da busca. Neste trabalho foi abordada a hipótese de que, o uso de métodos de seleção mais avançados poderiam melhorar desempenho do MOPSO baseado em Hiper-heurística (H-MOPSO). Para investigar esta hipótese quatro métodos de seleção foram avaliados e comparados a um algoritmo multi-objetivo estado da arte. Nos resultados apresentados o H-MOPSO obteve melhores resultados na maioria dos problemas. / Abstract: Multi-objective Particle Swarm Optimization (MOPSO) is a promising meta-heuristic to solve Many-Objective Problems (MaOPs), however, its performance decreases as the number of objective functions increases. Selecting a good combination of leader and archiving methods helps the algorithm to deal with the challenges caused by this increase in the number of objectives, but finding the most appropriate combination for a given problem is a hard task. To deal with this issue, previous works proposed the use of a simple hyper-heuristic to select dynamically a good combination of leader and archiving methods and achieved promising results. In this work, we hypothesize that by using more advanced heuristic selection methods we could further improve the performance of the algorithm. To investigate this hypothesis we conducted experimental studies comparing four heuristic selection methods. After selecting the best performing variant from this study, we conducted a second empirical study to compare this variant to a state-of-the- art optimizer, where the resulting algorithm outperformed it in most of the problems investigated.

Orientador: Edson Luiz França Senne / Banca: Galeno José de Sena / Banca: José Roberto Dale Luche / Banca: Anibal Tavares de Azevedo / Banca: Kelly Cristina Poldi / Resumo : A presente pesquisa trata do desenvolvimento de um método de solução do problema de construção de linhas de trabalho para a área de escalonamento de pessoal. Foram investigados diversos artigos da área de programação de pessoal com o objetivo de escolher precisamente o tema da pesquisa. Este tema escolhido foi o da construção de linhas de trabalho para empresas de ônibus interurbanos no Brasil. De posse do tema escolhido, foram analisados os métodos usados para formular e resolver o problema. Como resultado foi decidido o uso de uma formulação de cobertura de conjuntos não unicusto para representar o problema em estudo e o uso de um método heurístico para resolver o mesmo. Esta heurística divide a solução do problema em duas fases. A primeira é a fase construtiva, em que o espaço de solução é montado e linhas de trabalho são investigadas e aquelas viáveis são agrupadas formando um conjunto de linhas viáveis e qualificadas. A segunda é a fase de otimização ou de busca local em que um algoritmo evolutivo, baseado em algoritmo genético, irá procurar a melhor solução dentro desse subconjunto de linhas viáveis e qualificadas obtidas na primeira fase. Estes dois procedimentos se repetem até que um critério de parada seja atingido. Testes computacionais foram realizados no sentido de demonstrar a eficácia e eficiência do método proposto. Em seguida, o problema da programação de dias de expediente e de folga, neste trabalho denominado problema de padrões de folga, é formulado e resolvido. Algumas propostas para integrar a solução do problema de criação de linhas de trabalho à do problema de padrões de folga são apresentadas e discutidas / Abstract: This thesis deals with the development of a method for solving the problem of construction of lines of work for the application area of personnel scheduling. Several articles were analyzed in order to matching precisely the subject of the research. An in-depth review of the processes used for formulating and solving such a kind of problem in the literature was conducted. As a result, it was decided to formulating the problem as a non unicost set covering problem and to use a heuristic method to solve it. The proposed heuristic is a twofold algorithm. The first is the construction phase, in which the solution space is scanned and working lines are investigated and those feasible are grouped together forming a set of feasible and qualified lines. The second phase is the optimization or local search in which an evolutionary algorithm based on genetic algorithm will search for the best solution within this set of feasible and qualified lines obtained in the first phase. These two phases are repeated until a stop criterion is reached. Computational tests were performed to demonstrate the effectiveness and efficiency of the proposed method. Then, the tour scheduling problem is addressed in the context of finding shifts of work-days and days-off scheduling. Its resolved by deterministic techniques. Some methods are then discussed on how to integrating both of the solutions of the lines of work and the tour scheduling problems / Doutor

Orientador: José Manoel Balthazar / Co-orientador: Edilaine Martins Soler / Banca: Diego Colon / Banca: Atila Madureira Bueno / Resumo: Este trabalho abrange o estudo de um sistema de controle na sua forma mais simples, ou seja, controlador e processo. A otimização de uma função objetivo definida por um determinado índice de desempenho, que tem como variáveis o estado do sistema e os sinais de controle, busca atingir o controle ótimo que minimiza este índice. A pesquisa levantou os principais conceitos afetos à teoria do controle ótimo e algumas das principais técnicas de solução do que consistiu o conceito central da teoria, o Problema de Controle Ótimo, ou PCO. Em especial, foi possível implementar a técnica de otimização dinâmica por pontos de colocação, aplicada em um ambiente integrado constituído de ferramentas de modelagem, JModelica e de otimização, IPOPT. Como principal referência foi utilizado o PCO um modelo matemático da transmissão da dengue, com auxílio do qual alguns pesquisadores tentaram calcular, em função dos custos relativos de cada técnica de combate à doença, inseticidas e liberação no ambiente de machos estéreis, as melhores estratégias para diminuir a população de fêmeas fertilizadas, diretamente relacionadas aos casos da doença. Os trabalhos originais que pesquisaram o mesmo problema abordaram a questão pela formulação de um PCO com solução pelo Princípio do Máximo de Pontryagin, em procedimento sequencial e aproximado. Outros utilizaram algoritmos genéticos e otimização multiobjetivo. Os resultados desta pesquisa que podem ser destacados são inicialmente a própria revisão da teoria de controle ótimo, a instalação e a operação do referido ambiente integrado de modelagem, simulação e otimização, onde diversos PCO foram e podem ser solucionados, bem como o programa em linguagem Python que solucionou estes PCO e, finalmente, as considerações teóricas sobre o PCO do modelo de transmissão da dengue, permitindo sugerir alterações no cálculo de função objetivo para melhor utilização dos... / Abstract: This work comprises the study of a control system in its most simple format, that is, a controller and a process oer a plant. The optmization of a cost function, with the system state as variables, aims to achieve the optimal control. Starting from the concepts presented in the previous works, we studied alternatives optimization techniques suited to the optmal control. We used as experimental basement a mathemtical model of dengue disease's transmission, the same model adopted by some researchers to help to assess the best strategies to vanish the fertilized females, an index that is direclty related to the illness cases, as function of the relative costs of each technique available to combat the disease: the use of insecticides and the release of sterile males to the environment. The original researches that studies the same problem approached the matter by the formulation of an optimal control problem solved by Pontryagin Maximum Principle, in a sequential and approximated procedure. Others adopted genetic algorithm and multi-objective optimization. This research shows the results of the approach by dynamic optimization with collocation points in a integrated enviornment with modeling and simulation, JModelica, and optimization, IPOPT, tools. The application of the dynamic optimization with collocation points technique to the studied model allowed, by better observation of control signals and the assessment of the cost function, to suggest changes to a more efficient control / Mestre

En los problemas de optimización combinatoria se estudian colecciones finitas de objetos que satisfacen unos criterios específicos y se persigue determinar si cierto objeto ``óptimo'' existe. En la mayoría de las ocasiones, a pesar de que el dominio de búsqueda es finito, éste puede ser de dimensiones exponenciales. En la actualidad es posible solucionar un gran número de problemas combinatorios presentes en la vida real empleando técnicas basadas en programación entera. Sin embargo, en numerosas ocasiones no es posible resolverlos de forma exacta debido a la gran dificultad que presentan algunos problemas de optimización combinatoria y sólo es posible encontrar soluciones cercanas al óptimo. Para estas ocasiones, los esfuerzos de investigación se han centrado en la aplicación de técnicas meta-heurísticas. En este último caso se enmarca el presente trabajo, es decir, en la resolución de problemas combinatorios complejos, de grandes dimensiones, donde explorar todas las posibilidades a fin de encontrar el óptimo es inabordable, ya sea por motivos económicos (probar cada combinación sea caro) o por motivos computacionales (temporalmente sea intratable). En concreto, en esta tesis se propone una arquitectura de búsqueda independiente del dominio de aplicación y capaz de abordar problemas combinatorios de grandes dimensiones, de los que se disponga de poca información de partida. Esta arquitectura está basada en técnicas Soft Computing, pues combina un algoritmo genético basado en codificación real con modelos basados en redes neuronales, concretamente en perceptrones multicapa. Así, el algoritmo genético emplea, en los casos en los que sea necesario, modelos aproximados de las funciones de aptitud mediante perceptrones diseñados para tal fin. El sistema obtenido ofrece la flexibilidad y versatilidad requeridas para poder adaptarse a los requisitos propios de cada problema combinatorio a tratar, sea cual sea su dominio. / Valero Cubas, S. (2010). Arquitectura de búsqueda basada en técnicas soft computing para la resolución de problemas combinatorios en diferentes dominios de aplicación [Tesis doctoral no publicada]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/8329 / Palancia

La presente tesis doctoral tiene como principal objetivo el estudio de catalizadores heterogéneos para la obtención de productos de química fina. Gracias a la aplicación simultánea de metodologías combinatorias avanzadas, dispositivos experimentales de alta capacidad (tecnología High-Throughput) y técnicas de caracterización fundamental de los materiales, ha sido posible el desarrollo y optimización de nuevos catalizadores heterogéneos en diferentes procesos de interés industrial. Concretamente, se han investigado tres líneas para la obtención de intermedios orgánicos, basadas en reacciones de acoplamiento carbono-carbono (catalizadores de Pd), epoxidación de olefinas (titano-silicatos) e hidrogenación quimiselectiva de grupos nitro (catalizadores de oro, platino, rutenio y níquel). El control de las propiedades de los materiales a nivel atómico (química de nanopartículas soportadas) ha permitido proponer nuevos sistemas catalíticos altamente activos y selectivos para llevar a cabo estas transformaciones, ofreciendo soluciones limpias y eficientes para una producción sostenible de multiples compuestos químicos. / Serna Merino, PM. (2008). Catálisis combinatoria para procesos de química fina [Tesis doctoral no publicada]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/3902 / Palancia

Magíster en Gestión de Operaciones / Ingeniero Civil Industrial / En la presente Tesis, se propone una metodología para enfrentar el Problema Dinámico de Ruteo de Técnicos con Ventanas de Tiempo. La naturaleza dinámica del problema está comprendida en los clientes que aparecen dinámicamente y deben ser asignados a la mejor ruta posible mediante algún criterio. La metodología propuesta puede ser resumida en tres pasos: - Usar información histórica para crear nodos ficticios, los que sirven como puntos de espera (y de covering) para los vehículos que han terminado sus tareas en agenda. - Resolver el problema de ruteo estático, que comprende los nodos reales y los puntos de espera, mediante Generación de Columnas. - Añadir las llamadas entrantes usando la heurística Generación de Columnas Dinámica. La Generación de Columnas Dinámica es una heurística que se basa en la propuesta de Chen, la cual genera nuevas columnas usando la información de los nuevos nodos junto con un subconjunto de las columnas generadas anteriormente en la resolución del problema estático. Mientras se generan nuevas columnas, estas pueden ser añadidas al conjunto total de columnas y resolver el nuevo problema de optimización. Esta heurística permite encontrar nuevas soluciones muy rápido, por lo cual corresponde a una buena opción para resolver problemas dinámicos donde las decisiones son tomadas en tiempo real. En cuanto a los resultados numéricos, el método propuesto (SCTTP-DCG), obtiene mejores resultados que la implementación dinámica más intuitiva realizable: el ruteo estático de nodos más la agregación Greedy de llamados dinámicos (TTP-Greedy). Por otra parte, el ruteo estático de nodos con la agregación de nodos dinámicos por medio de Generación de Columnas Dinámico (TTP-DCG) obtiene mejores resultados en comparación SCTTP-DCG. La explicación a este fenómeno tiene que ver con dos efectos: TTP-DCG gana las bondades de la inserción por medio de DCG y, además, ahorra en tiempos de desplazamiento pues no tiene que viajar a los nodos ficticios. Si bien era lógico que este fenómeno existiera, se esperaba que el SCTTP-DCG lograra recuperar los costos extra de transporte por medio de menor desplazamiento gracias a la buena ubicación frente a los llamados venideros.

Orientador: José Marcos Lopes / Banca: Roseli Arbach Fernandes de Oliveira / Banca: Tatiana Bertoldi Carlos / Resumo: Este trabalho apresenta uma proposta de ensino aprendizagem para introdução do conceito de Combinações Simples, através de uma sequência didática utilizando a resolução de problemas como forma metodológica, aplicado em uma série de 2° Ano do Ensino Médio. Trata-se de uma sequência didática em que os problemas apresentam uma ordem crescente de dificuldade. Apresentamos antes uma breve introdução, com conceitos históricos, do uso de problemas como forma metodológica, outra de situação problema e, uma rápida revisão dos conteúdos de Análise Combinatória, estudados durante o Ensino Médio, para organizar e ambientar nosso trabalho. Da mesma forma como já aparece no Caderno do Aluno, fornecido pela Secretaria da Educação do Estado de São Paulo, propomos a utilização da sequência didática, em sala de aula, através do uso da metodologia de resolução de problemas, em que o aluno deve chegar ao conceito matemático por meio de suas descobertas. Aplicamos em sala de aula a sequência didática acima citada, com os alunos em grupos, onde foi apresentado problema por problema, entre eles sempre se colhiam os resultados e discutíamos em plenária para que fosse possível identificar os acertos e transformar os erros em aprendizado. Além de trabalhar Análise Combinatória, que já é um assunto que traz algumas dificuldades para professores e alunos, a principal habilidade necessária para a resolução de problemas também é trabalhada, a leitura e interpretação, pois cada problema era lido e interpretado por cada um dos grupos, trazendo então as discussões e trocas de experiências entre os grupos e o professor que somente mediava as discussões e sistematiza os resultados. Esperamos que o nosso trabalho sirva para desmistificar o conceito e trazer novas práticas que podem ser ajustadas para as nossas salas de aula / Abstract: This paper presents a learning teaching proposal to introduce the concept of simple combinations, through a didactic sequence using problem solving as a methodological way, applied in a 2nd year of high school. This is a didactic sequence in which problems are an increasing degree of difficulty. We presented before a brief introduction with historical concepts, using problems as a methodological way, another problem situation and a quick review of Combinatorial Analysis of content studied during high school to organize and situate our work. As already appears in the Student Notebook, provided by the Secretaria do Estado de São Paulo, we propose the use of didactic sequence in the classroom through the use of Problem-Solving Methodology, in which the student must reach the mathematical concept through their discoveries. We apply in the classroom the Didactic Sequence mentioned here, the students divided into groups, where it was presented issue by issue, among them always reaped the results and discussed in plenary, so that it was possible to identify the successes and turn mistakes into learning. Besides working Combinatorial Analysis, which is already a subject that brings some difficulties for teachers and students, the main skill required for Problem-Solving is also worked, the reading and the interpretation, because each problem was read and interpreted by each group, bringing the discussions and exchanges of experience among the groups, which before, the teacher was the one who only mediated the discussions and systematized the results. We hope our work will serve to demystify the concept and bring new practices that can be adjusted to our classrooms / Mestre