Orientador: Edilaine Martins Soler / Coorientadora: Maristela Oliveira dos Santos / Banca: Andrea Gonçalves Vianna / Banca: Marcos Mansano Furlan / Resumo: Os sistemas de abastecimento de água são de fundamental importância pois são responsáveis por levar água de qualidade a população. No Brasil, para as empresas de saneamento, o custo da energia elétrica é cobrado de acordo com a hora do dia, sendo o horário compreendido entre as 18h e as 21h chamado de horário de pico, onde a energia elétrica é mais cara. Grande parte dos gastos com energia elétrica nos sistemas de abastecimento de água são atribuídos as bombas hidráulicas, que, no geral, são acionadas quando os níveis dos tanques chegam ao mínimo, permanecendo ligadas até que se atinjam seus níveis máximos, sem levar em consideração o horário em que esta operação é feita. Diante disto, este trabalho propõe um modelo matemático para a otimização energética mais próximo da realidade dos sistemas de abastecimento de água. Testes numéricos foram realizados através da implementação do modelo no software GAMS e resolvido pelo pacote de otimização CPLEX para diferentes instâncias, afim de validar o modelo proposto e a comprovar à eficiência do planejamento da operação das bombas hidráulicas em relação a operação feita na prática nos sistemas de abastecimento de água. / Abstract: Water supply systems are of fundamental importance once they are responsible for providing quality water to the population. In Brazil, for sanitation companies, the cost of electricity is charged according to the period of the day, with the period between 6 and 9 p.m. known as the peak hours, during which electricity is more expensive. The majority of costs with electricity in the water supply systems are due to the hydraulic pumps, which are, usually, activated when tank levels reach the minimum level and then they remain on until their maximum levels are reached, without taking into account the period during which this operation is performed. With this in mind, this study proposes a mathematical model for the electricity usage optimization closer to the reality in water supply systems. Numerical tests were performed through the implementation of the GAMS software model and solved by the CPLEX optimization package for different instances, in order to validate the proposed model and to prove the efficiency of the planning of the operation of hydraulic pumps about the operation made in practice in water supply systems. / Mestre

Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico. Programa de Pós-Graduação em Ciência da Computação. / Made available in DSpace on 2012-10-20T07:26:10Z (GMT). No. of bitstreams: 1 186337.pdf: 495102 bytes, checksum: 2077bc80ca3d164d6934ab5544ad87c6 (MD5) / A busca de soluções para problemas de otimização das informações nas organizações por meio do computador constituiu a base deste trabalho. No que tange à Ciência da Computação, essa busca certamente requer a construção de algoritmos eficientes e exatos, mas nem sempre encontram-se boas soluções para muitos problemas de ordem prática, principalmente no que diz respeito ao tempo de execução. Existem problemas, dentre os quais estão os de otimização combinatorial, que diferem dos outros porque apresentam uma grande dificuldade para se obter soluções exatas, num tempo computacional aceitável. Existem técnicas, especialmente as metaheurísticas, tais como Tabu Search, Simulated Annealing, Algoritmos Genéticos e Redes Neurais, que vêm conseguindo sucesso na solução de problemas de otimização combinatorial e, mesmo não apresentando soluções exatas, têm mostrado bastante eficiência com suas soluções aproximadas. Este trabalho propõe um novo método, baseado no algoritmo Simulated Annealing (SA), modificado para trabalhar com múltiplas faixas de temperatura, de forma que os processos são executados de forma paralela, trocando informações de seus melhores resultados entre os processos existentes a cada início de uma nova faixa. Os experimentos são executados com instâncias euclidianas do Problema Caixeiro Viajante, que é um problema de otimização combinatorial de difícil solução, apresentando resultados bastante satisfatórios quando comparado com o SA de múltiplas faixas, executado de forma seqüencial

Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico. Programa de Pós-Graduação em Ciência da Computação. / Made available in DSpace on 2012-10-18T13:35:55Z (GMT). No. of bitstreams: 1 225675.pdf: 796704 bytes, checksum: 892abc8468e4e7c6715b6c3f2de50e51 (MD5) / A busca por soluções de problemas por meio do computador é o tema central da ciência da computação, relevante para grande parte da ciência e de suas aplicações tecnológicas. Essa busca, certamente, vai na direção de algoritmos eficientes e exatos mas que nem sempre boas soluções podem ser encontradas para muitos problemas de ordem prática, principalmente, no que diz respeito a tempo de execução. Existem problemas, dentre estes, os de otimização combinatorial que apresentam uma peculiaridade com relação aos outros, que é a grande dificuldade de se obter soluções exatas num tempo computacional aceitável. Atualmente, as novas técnicas, especialmente as metaheurísticas, tais como: Tabu Search, Simulated Annealing, Algoritmos Genéticos e Redes Neurais, vêm conseguindo sucesso na solução de problemas de otimização combinatorial, que mesmo não apresentando soluções exatas têm mostrado bastante eficiência com suas soluções aproximadas. Este trabalho propõe um novo método baseado no algoritmo Simulated Annealing (SA) através de mudanças bruscas nos valores da temperatura que são retiradas de múltiplas faixas, ao contrário do SA básico, onde esses valores são obtidos de uma faixa única, ou seja, num SA básico, os valores assumidos pela temperatura saem de um intervalo, partindo de um valor inicial, e vão diminuindo até um valor final. Tais mudanças bruscas acontecem exatamente no momento da mudança de faixa, pois o valor da temperatura que no final de uma faixa é pequeno, assume um valor correspondente a temperatura inicial da faixa seguinte, normalmente, bem maior. Posto a prova, com instâncias euclidianas do Problema Caixeiro Viajante, que é um problema de otimização combinatorial de difícil solução, o método apresenta resultados bastante satisfatórios quando comparado com o SA básico.

Made available in DSpace on 2016-01-13T13:27:34Z (GMT). No. of bitstreams: 0 Previous issue date: 2015-10-23. Added 1 bitstream(s) on 2016-01-13T13:33:02Z : No. of bitstreams: 1 000855212.pdf: 2111250 bytes, checksum: 7eb42c51ea96f1616ea18b419052b97c (MD5) / 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... / 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

Orientadora : Profª. Drª. Neida Maria Patias Volpi / 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, 05/04/2011 / Inclui referências / Resumo: O problema de roteamento de veículos (PRV) é um dos mais estudados nas áreas de logística e otimização combinatória e consiste em determinar rotas de custo mínimo para uma frota de veículos, atendendo à demanda de um conjunto de clientes. Devido à complexidade computacional dos problemas de roteamento, torna-se inviável resolvê-los de forma exata, e em virtude disso, na maioria das vezes, a solução é obtida através de heurísticas. Mesmo sendo amplamente estudado o PRV carece de implementações práticas e nem sempre as soluções disponíveis resolvem satisfatoriamente os problemas das empresas, daí a necessidade de buscar soluções customizadas para cada problema. Dessa forma, o objetivo desse trabalho é desenvolver uma ferramenta que auxilie no processo de elaboração de roteiros de entrega de refeições feitas pela ASSEMCO - Associação dos Servidores Municipais de Colombo, localizada na região metropolitana de Curitiba, Paraná. A configuração atual dos roteiros de entrega não contempla todas as particularidades do problema, pois os clientes atendidos pela ASSEMCO possuem demanda variável e alguns destes precisam ser atendidos em horário fixo. Para resolução desse problema este trabalho apresenta duas abordagens: um programa computacional para o planejamento de rotasde entrega e um modelo estocástico que descreve o problema. Na abordagem determinística foi desenvolvido um programa em Visual Basic 6.0 que gera os roteiros de entrega através de métodos heurísticos de agrupamento e roteirização. Na odelagem estocástica do problema foram considerados a probabilidade de presença dos clientes, a probabilidade do veículo fazer o trajeto e o tempo de viagem entre os clientes, baseado na probabilidade de presença destes. Este modelo foi resolvido através do software Lingo 9.0 e através da meta-heurística Ant Colony System. Em relação à abordagem determinística, observou-se que os roteiros obtidos com a utilização do programa mostraram-se melhores em comparação com os roteiros normalmente praticados pela empresa. Em relação à abordagem estocástica, observou-seque o modelo proposto se adequou ao problema. Além disso, a meta-heurística Ant Colony System implementada para a resolução do modelo mostrou-se eficiente, visto que apresentou soluções de boa qualidade em tempo computacional viável. / Abstract: The vehicle routing problem (VRP) is one of the most studied in logistics and combinatorial optimization and it consists in determining minimum cost routes for a fleet of vehicles, in order to serve the demand of a set of customers. Due to the computational complexity of routing problems, it becomes impossible to solve them optimally, so in most cases, th solution is achieved by heuristics implementation. Even widely studied, PRV lacks practical implementation and not always available solutions solve satisfactorily companies problems, hence the necessity of seeking customized solutions for each problem. Thus, the purpose of this research is to assist in the meal delivery routes process made by ASSEMCO - Colombo Municipal Servers Association, great Curitiba, in Paraná. The current configuration of delivery routes does not include all the details of the problem because the customers served by ASSEMCO have variable demand and some of them need to be attendend at fixed times. To solve this problem this research presents two approaches: a software for planning delivery routes and a stochastic model that describes the problem. In a deterministic approach, it was developed a program in Visual Basic 6.0 that generates the delivery route through heuristic methods for clustering and routing. In the stochastic modeling, based on customers presence probability, vehicle probability traversing the path, and the travel time between customers were considered. This model was solved by Lingo 9.0 software and through the meta-heuristic Ant Colony System. Concerning deterministic approach, it was observed that obtained routes by the program proved to be better compared to the route normally adopted by the company. Concerning stochastic approach, it was observed that the proposed model is suitable to the problem. n addition, the metaheuristic Ant Colony System implemented for solving the model proved to be useful, because it produced good quality solutions in reasonable computational time.

Orientadora : Profª. Drª. Aurora Pozo / Co-orientador : Prof. Dr. Richard Aderbal Gonçalves / Dissertação (mestrado) - Universidade Federal do Paraná, Setor de Ciências Exatas, Programa de Pós-Graduação em Informática. Defesa: Curitiba, 26/02/2016 / Inclui referências : f. 64-70 / Resumo: Muitos problemas de otimização do mundo real são complexos e possuem muitas variáveis e restrições. Por esta causa, o uso de meta-heurísticas tornou-se a principal maneira de resolver problemas com essas características. Uma das principais desvantagens do uso de meta-heurísticas e que são geralmente desenvolvidas utilizando características do domínio fazendo com que sejam atreladas a ele dificultando sua utilização em outros problemas. Em buscas de algoritmos mais adaptáveis o conceito de hiper-heurísticas surgiu. Hiper- heurísticas são métodos de busca que visam solucionar problemas de otimização selecionando ou gerando heurísticas. Hiper-heurísticas de seleção escolhem uma boa heurística para ser aplicada a partir de um conjunto de heurísticas. O método de seleção e a principal peca de uma hiper-heurística de seleção tendo impacto fundamental em sua performance. Apesar de existirem vários trabalhos sobre hiper-heurísticas de seleção, ainda não existe consenso sobre como uma boa estratégia de seleção deve ser definida. Em busca de uma estratégia de seleção, algoritmos inspirados nos conceitos do problema Multi-Armed Bandit (MAB) serão estudados. Estes algoritmos foram aplicados ao contexto da Seleção Adaptativa de Operadores obtendo resultados promissores. Entretanto, ainda existem poucas abordagens para o contexto de hiper-heurísticas. Nesta dissertação propomos uma hiper-heurística que utiliza algoritmos MAB como sua estratégia de seleção. A abordagem proposta e desenvolvida utilizando o framework HyFlex, que foi proposto para facilitar a implementação e comparação de novas Hiper- heurísticas. Os parâmetros foram configurados através de um estudo empírico, e a melhor configuração encontrada foi comparada com os 10 primeiros colocados da competição CHeSC 2011. Os resultados obtidos foram bons e comparáveis com os das melhores abordagens da literatura. O algoritmo proposto alcançou a quarta colocação. Apesar dos bons resultados, os experimentos demonstram que a abordagem proposta sofre grande influencia dos parâmetros. Trabalhos futuros irão investigar formas de amenizar esta influência. / Abstract: Many real word optimization problems are very complex with many variables and constraints, and cannot be solved by exact methods in a reasonable computational time. As an alternative, meta-heuristics emerged as an efficient way to solve this type of problems even though they cannot ensure optimal values. The main issue of meta-heuristics is that they are built using domain-specific knowledge, therefore they require a great effort to be used in a new domain. In order to solve this problem, the concept of Hyper-heuristics were proposed. Hyper-heuristics are search methods that aim to solve optimization problems by selecting or generating heuristics. Selection hyper-heuristics choose from a pool of heuristics a good one to be applied at the current stage of the optimization process. The selection mechanism is the main part of a selection hyper-heuristic and has a great impact on its performance. Although there are several works focused on selection hyperheuristics, there is no unanimity about which is the best way to define a selection strategy. In this dissertation, a deterministic selection strategy based on the concepts of the MultiArmed Bandit (MAB) problem is proposed to cross-domain optimization. Multi-armed bandit approaches define a selection function with two components, the first is based on the performance of an operator and the second based on the number of times that the operator was used. These approaches had showed a promising performance over the Adaptive Operator Selection context. However, there are few works on literature that aim the hyper-heuristic context, as proposed here. The proposed approach is integrated into the HyFlex framework, that was developed to facilitate the implementation and comparison of hyper-heuristics. An empirical parameter configuration was performed and the best setup was compared to the top ten CHeSC 2011 algorithms using the same methodology adopted during the competition. The results obtained were good comparable to those attained by the literature. Moreover, it was concluded that the behavior of MAB selection is heavily affected by its parameters. As this is not a desirable behavior to hyper-heuristics, future research will investigate ways to better deal with the parameter setting.

No description available.

Resumo: Os sistemas gerenciadores de bancos de dados (SGBDs) relacionais proporcionam atualmente uma ambiente bastante produtivo para a manipulação de informações. A partir de uma linguagem de alto nível, tais sistemas permitem que seus usuários descrevam consultas de uma maneira simples e rápida, sem definir com isso detalhes relacionados ao seu processamento. Tais detalhes são de responsabilidade do próprio SGBD, o qual deve escolher, através de um sofisticado processo de otimização e planejamento, uma alternativa eficiente para a obtenção dessas informações. A otimização de junções é uma das mais importantes e complexas dentre todas as fases que compõem este processo. A definição da melhor ordem de junções somente pode ser realizada em condições relativamente simples, através do uso de algoritmos de busca exaustiva fortemente baseados na programação dinâmica. Para os demais casos, espera-se que apenas uma aproximação desta melhor ordem seja encontrada, utilizando para isso técnicas não exaustivas de busca. Este estudo concentra-se na avaliação de dois algoritmos não exaustivos de otimização de junções implementados para o SGBD de código aberto PostgreSQL: o enetic Queri Optimization (GEQO) e o Two Phase Optimization (2PO). Através de um esquema de testes multidimensional, este estudo apresenta diversos dados relevantes sobre o comportamento desses algoritmos. Estes resultados servem tanto para o processo de melhoria dos algoritmos avaliados como para a elaboração de novas abordagens de otimização de junções.

Made available in DSpace on 2014-06-11T19:35:40Z (GMT). No. of bitstreams: 0 Previous issue date: 2014-02-28Bitstream added on 2014-06-13T20:07:10Z : No. of bitstreams: 1 000757731.pdf: 2807037 bytes, checksum: 5aa196a9569db15583f96a6a1fbce2c8 (MD5) / 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 / 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

Orientador: Fernando Luiz Pio dos Santos / Resumo: Neste trabalho, apresentamos uma estratégia para estimação de parâmetros de um modelo matemático não-linear de equações diferenciais ordinárias, que descreve a dinâmica populacional de mosquitos da Dengue, para o qual há dados disponíveis para as fases aquática e alada. Para estimar um conjunto de parâmetros biológicos desconhecidos, uma função custo envolvendo tais parâmetros é minimizada por meio do método Levenberg −Marquardt (LM). O principal interesse foi ajustar o modelo aos dados levando em conta os parâmetros estimados. Os resultados das simulações numéricas mostram a eficácia da técnica de estimação de parâmetros acoplada ao LM. A comparação entre a solução numérica e os dados comprova a eficiência do código no ajuste dos dados, consonante com estimativas apresentadas na literatura. / Mestre