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

Orientador: Rubén Augusto Romero Lázaro / Banca: Jose Roberto Sanches Mantovani / Banca: Sergio Azevedo de Oliveira / Banca: Antônio César Baleeiro Alves / Banca: Eduardo Nobuhiro Asada / Resumo: O problema de planejamento de sistemas de transmissão é um problema de programação não-linear inteira mista (PNLIM) quando é usado o modelo DC. Praticamente todos os algoritmos usados para resolver este problema utilizam uma subrotina de programação linear (PL) para resolver problemas de PL resultantes do algoritmo de solução do problema de planejamento. Às vezes a resolução desses problemas de PL representa o maior esforço computacional dos algoritmos de planejamento. A particularidade desses problemas de PL é que, na solução ótima, apenas algumas restrições de desigualdade estão ativas. Este trabalho considera a formulação e a implementação computacional de vários algoritmos de PL resultantes, ou seja, os algoritmos propostos fazem modificações nos problemas de PL resultantes dos modelos de transportes e DC de maneira que apresentam uma única restrição de igualdade, a equação de balanço de potência ativa, e muitas restrições de desigualdade. É usado um algoritmo dual simplex canalizado e uma estratégia de relaxação para resolver esses problemas de PL que inicia o processo de otimização com uma única restrição de igualdade e, em cada passo, é adicionada a restrição mais violada. Portanto, a lógica de trabalho é parecida com a proposta apresentada por Brian Stott para o planejamento da operação de sistemas elétricos. Os resultados encontrados mostram um desempenho superior do algoritmo quando comparados com métodos do tipo primal simplex. / Abstract: The transmission network planning problem is a non linear integer mixed programming problem (NLIMP) which used the DC model. Most of the algorithms used to solve this problem use a linear programming subroutine (LP) to solve LP problems resulting from planning algorithms. Sometimes the resolution of these LP problems represents a major computational effort of planning algorithms. The particularity of these LP problems in optimal solution is that only some inequality constraints are binding. This work considers the formulation and the computational implementation of algorithms several of the LP problems resulting, i.e., the proposed algorithms make modifications in the LP problems resulting of the transports and DC models so that present an only equality constraint, only one equality constraint, the power flow equation, and many inequality constraints. It is used a dual simplex algorithm and a relaxation strategy to solve these LP problems_ which start the optimization process with only one equality constraint and, in each step, the most unfeasible constraint is added. Then, the logic used is similar to the proposal presented in Brian Stott for electric systems operation planning. The results show a higher performance of the algorithm when compared to primal simplex methods. / Doutor

Orientador: Fernando Augusto Silva Marins / Coorientador: Aneirson Francisco da Silva / Banca: Valério Antonio Pamplona Salomon / Banca: Fabrício Maciel Gomes / Resumo: Esta dissertação trata da construção de um modelo matemático para a elaboração do quadro de horários dos cursos de graduação do CBV/IFRR. A programação de horários é um problema de otimização combinatória estudado há anos pela Pesquisa Operacional e, em termos de complexidade computacional, é tido como NP-Completo, sendo assim, é um problema que exige grande capacidade de processamento. A elaboração do quadro de horários em qualquer instituição de ensino é complexa e demanda tempo para os responsáveis por essa atividade, pois as necessidades dos professores e alunos devem ser atendidas e devem-se evitar conflitos nos horários dos professores. A instituição estudada nesta dissertação assim como outras instituições, possui particularidades institucionais, dessa forma, uma formulação geral do problema acaba não lhe sendo útil. O CBV/IFRR realiza a elaboração dos horários de forma manual, por meio de planilha eletrônica e realização de reuniões entre os gestores, o que torna difícil encontrar uma solução factível. Sendo assim, foi necessária a realização de pesquisa científica para encontrar métodos que poderiam ser aplicados ao problema. Assim, este trabalho teve como objetivo desenvolver um modelo de Programação Matemática que permitisse a elaboração dos horários para cursos de graduação do CBV/IFRR. Utilizou-se entrevistas com as Coordenações de Cursos para obtenção das informações acerca do problema tratado, tais como restrições e prioridades a serem atendidas com a programaç... (Resumo completo, clicar acesso eletrônico abaixo) / Abstract: This dissertation deals with the construction of a mathematical model for the elaboration of the timetable of the undergraduate courses of the CBV/IFRR. Time scheduling is a combinatorial optimization problem that has been studied for years by Operational Research and, in terms of computational complexity, is considered as NP-Complete, so it is a problem that requires large processing capacity. The elaboration of the timetable in any educational institution is complex and takes time for those responsible for this activity, because the needs of teachers and students must be met and avoid conflicts in the schedules of teachers. The institution studied in this dissertation as well as other institutions, has institutional features, so a general formulation of the problem ends up being of no use to it. The CBV/IFRR performs the elaboration of the schedules manually, through a spreadsheet and holding meetings between managers, which makes it difficult to find a feasible solution. Thus, it was necessary to carry out scientific research to find methods that could be applied to the problem. Thus, this work had the objective of developing a Mathematical Programming model that allowed the elaboration of the schedules for the undergraduate courses of the CBV/IFRR. We used interviews with the Course Coordinators to obtain information about the problem, such as constraints and priorities to be met with the programming of classes for teachers. This information was the basis for the construction of the conceptual model, which was used to elaborate the final mathematical model, which was implemented in the GAMS® high-level language and solved by the CPLEX® solver. The tests of the model were performed optimizing an instance with real data of the studied institution. The results obtained from the optimization were satisfactory, since it was possible to find an ... (Complete abstract click electronic access below) / Mestre

Made available in DSpace on 2014-06-11T19:30:52Z (GMT). No. of bitstreams: 0 Previous issue date: 2005-04-29Bitstream added on 2014-06-13T19:00:51Z : No. of bitstreams: 1 hashimoto_shm_dr_ilha.pdf: 3505990 bytes, checksum: 86eb5da27160760afefec6614a16a090 (MD5) / Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP) / O problema de planejamento de sistemas de transmissão é um problema de programação não-linear inteira mista (PNLIM) quando é usado o modelo DC. Praticamente todos os algoritmos usados para resolver este problema utilizam uma subrotina de programação linear (PL) para resolver problemas de PL resultantes do algoritmo de solução do problema de planejamento. Às vezes a resolução desses problemas de PL representa o maior esforço computacional dos algoritmos de planejamento. A particularidade desses problemas de PL é que, na solução ótima, apenas algumas restrições de desigualdade estão ativas. Este trabalho considera a formulação e a implementação computacional de vários algoritmos de PL resultantes, ou seja, os algoritmos propostos fazem modificações nos problemas de PL resultantes dos modelos de transportes e DC de maneira que apresentam uma única restrição de igualdade, a equação de balanço de potência ativa, e muitas restrições de desigualdade. É usado um algoritmo dual simplex canalizado e uma estratégia de relaxação para resolver esses problemas de PL que inicia o processo de otimização com uma única restrição de igualdade e, em cada passo, é adicionada a restrição mais violada. Portanto, a lógica de trabalho é parecida com a proposta apresentada por Brian Stott para o planejamento da operação de sistemas elétricos. Os resultados encontrados mostram um desempenho superior do algoritmo quando comparados com métodos do tipo primal simplex. / The transmission network planning problem is a non linear integer mixed programming problem (NLIMP) which used the DC model. Most of the algorithms used to solve this problem use a linear programming subroutine (LP) to solve LP problems resulting from planning algorithms. Sometimes the resolution of these LP problems represents a major computational effort of planning algorithms. The particularity of these LP problems in optimal solution is that only some inequality constraints are binding. This work considers the formulation and the computational implementation of algorithms several of the LP problems resulting, i.e., the proposed algorithms make modifications in the LP problems resulting of the transports and DC models so that present an only equality constraint, only one equality constraint, the power flow equation, and many inequality constraints. It is used a dual simplex algorithm and a relaxation strategy to solve these LP problems_ which start the optimization process with only one equality constraint and, in each step, the most unfeasible constraint is added. Then, the logic used is similar to the proposal presented in Brian Stott for electric systems operation planning. The results show a higher performance of the algorithm when compared to primal simplex methods.

Tese (doutorado) - Universidade Federal de Santa Catarina, Centro Tecnológico. Programa de Pós-Graduação em Engenharia de Produção. / Made available in DSpace on 2013-07-15T23:34:21Z (GMT). No. of bitstreams: 1 213308.pdf: 1767196 bytes, checksum: 35f6a544210e481c8ff2120e3be71f91 (MD5) / Este trabalho tem foco no plano de operação de empresas de transporte rodoviário regional de passageiros, visando à alocação da frota e dos condutores. Tem por objetivo desenvolver um modelo dinâmico, que permita corrigir os desvios ocorridos durante a execução do plano ao longo do horizonte de planejamento em tempo computacional razoável. Ambos os modelos, o de programação da frota e o de condutores, se resolvem através de um processo seqüencial de aplicação do algoritmo húngaro, e os resultados obtidos são comparados com limites inferiores, calculados pela relaxação de algumas restrições do problema. O modelo desenvolvido foi aplicado aos dados de uma empresa que atua nos estados de Santa Catarina e Rio Grande do Sul e os resultados obtidos são analisados.