Made available in DSpace on 2016-12-23T14:33:44Z (GMT). No. of bitstreams: 1 Dissertacao de Danuza Prada de Faria Alckmin.pdf: 676333 bytes, checksum: 0f5968628437ef878dc7f703ce48b8bf (MD5) Previous issue date: 2009-08-31 / Agrupamento de dados é uma tarefa que divide um conjunto de dados em subconjuntos de forma que elementos associados a um mesmo grupo sejam mais similares entre si do que em relação a elementos de outros grupos. Ao organizar os dados em grupos é possível identificar similaridades e diferenças entre eles, extrair informações relevantes e inferir conclusões úteis a respeito das características dos dados. O problema de agrupamento de dados pode ser considerado como uma tarefa de otimização, uma vez que se pretende encontrar a melhor combinação de partições dentre todas as combinações possíveis. Uma abordagem que pode ser aplicada para resolver o problema de agrupamento é o uso de metaheurísticas, que são procedimentos capazes de escapar de ótimos locais, pois o uso de métodos exatos se torna computacionalmente inviável. Entretanto, a maioria das metaheurísticas aplicadas ao problema de agrupamento não são escalonáveis para bases reais e comerciais, são mais efetivas nos casos em que a instância do problema é menor. O custo computacional necessário para calcular as soluções se torna maior em instâncias maiores do problema. Por esse motivo, procedimentos híbridos que exploram a combinação de metaheurísticas representam uma abordagem promissora para a resolução do problema de agrupamento. Este trabalho apresenta uma proposta de Algoritmo Genético Híbrido de Agrupamento que associa ao processo de busca global uma heurística de busca local e cuja população inicial é gerada por técnicas de agrupamento. Tais melhorias têm como objetivo direcionar a busca para soluções mais próximas do ótimo global. É realizada uma avaliação experimental em bases de dados reais e sintéticas com o objetivo de verificar se a abordagem proposta apresenta uma melhoria em relação aos algoritmos avaliados. O resultado dessa análise mostra que o algoritmo proposto apresenta um desempenho melhor do que quatro entre os seis algoritmos avaliados. Para complementar a análise é realizada uma avaliação do tempo de execução, cujo objetivo é quantificar a diferença entre a abordagem proposta e os demais algoritmos avaliados. O resultado mostra que o tempo de execução da abordagem proposta é viável, porém é consideravelmente maior do que os tempos de execução dos algoritmos considerados de rápida convergência / Clustering is a task that divides a data set in subgroups aiming that elements associated to one exactly group are more similar between themselves than elements of other groups. Organizing data in groups make it possible to identify similarities and differences between them, to extract useful information and conclusions regarding the data features. Clustering may be considered an optimization problem because it is intended to find the best combination of partitions among all possible combinations. An approach that can be applied to solve the clustering problem is the use of metaheuristics, which are procedures capable of escaping from local optima, once the use of exact methods is computationally infeasible. However, the majority of the metaheurísticas applied to clustering problem is not scalable for real or commercial bases. They are more effective for smaller instances of the problem trated. The computational cost necessary to calculate the solutions becomes greater in larger instances of the problem. For this reason, hybrid procedures that explore the combination of metaheuristics represent a promising approach for solving the clustering problem. This work shows a proposal of a Hybrid Genetic Clustering Algorithm that associates the process of global search to a local search heuristic and also initializes the population by different grouping techniques. Such improvements aim to direct the search for solutions next to the global optimal one. An experimental evaluation with real and synthetic databases is performed aiming to verify if the proposed approach presents an improvement in relation to the other evaluated algorithms. The result of this analysis shows that the proposed algorithm presents a better performance in four among the six evaluated algorithms. In addition, an analysis of the execution time shows that the execution time of our proposal is feasible, even though it is considerably longer than the execution times of the fast convergence algorithms

Orientador: Antônio Carlos Moretti / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica / Made available in DSpace on 2018-08-17T07:59:31Z (GMT). No. of bitstreams: 1 Pinto_LuisFrancodeCampos_M.pdf: 11074962 bytes, checksum: 1a81559fbea90f37c92a435180da70b3 (MD5) Previous issue date: 2010 / Resumo: Neste trabalho, foi desenvolvida uma aplicação prática de técnicas da pesquisa operacional para a resolução de um problema real de esquematização ou programação de máquinas. Este problema deriva de um flexible job shop scheduling, porém apresentando diversas características próprias, impossibilitando a aplicação de modelos disponíveis na literatura. O desempenho da utilização da combinação de um modelo de programação linear inteira mista com uma heurística de construção e uma heurística de melhoramento foi avaliado diante de cenários reais obtidos da indústria de produção de frascos plásticos. Estas técnicas provaram ser eficientes para a resolução dos casos propostos / Abstract: In this work, a practical application of operational research techniques was developed to solve a real machine scheduling or programming problem. This problem derives from a flexible job shop scheduling framework, but presents several unique characteristics, which makes it impossible to apply models available in literature. The performance of using a combination of a mixed integer programming model with a construction heuristic and a improvement heuristic was evaluated using real world scenarios obtained from the plastic bottle production industry. Theses techniques were proven efficient in resolving the proposed cases / Mestrado / Pesquisa Operacional / Mestre em Matemática Aplicada

Orientador: Antonio Carlos Moretti / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica / Made available in DSpace on 2018-08-19T06:41:26Z (GMT). No. of bitstreams: 1 AraujoNeto_JoseEvangelista_M.pdf: 2884766 bytes, checksum: c57ca36e07463336bdf238ea6b35e234 (MD5) Previous issue date: 2011 / Resumo: Uma empresa de energia elétrica tem por obrigação garantir a continuidade e a qualidade do serviço prestado. A fim de incentivar a qualidade do serviço, a ANEEL introduziu penalidades nos contratos com as concessionárias de serviços públicos de transmissão de energia elétrica caso as instalações de transmissão sejam desligadas, por acidente, falha de equipamento ou manutenção programada. Abordagens tradicionais de manutenção em sistemas de transmissão de energia elétrica se baseiam em ações realizadas periodicamente, ou programadas, de acordo com uma análise de necessidades. Embora essas abordagens tenham o objetivo de melhorar o desempenho destes sistemas, geralmente não há uma avaliação precisa do impacto das ações de manutenção na confiabilidade dos mesmos relacionada aos recursos empregados, bem como penalidades legais decorrentes. O objeto assim formulado caracteriza-se como um problema de otimização combinatória com o objetivo de encontrar o encadeamento das ações de manutenções que minimizem os recursos utilizados em manutenções e garanta um nível de confiabilidade desejado para o Sistema Elétrico. Este trabalho propõe uma abordagem para enfrentar este problema baseada na relação confiabilidade/custo com a perspectiva de encontrar as melhores estratégias para a realização de manutenções em equipamentos (ativos) de transmissão de energia elétrica, apresentando um modelo matemático para a confecção de um calendário viável (que respeite às restrições do Sistema Elétrico) para programação de manutenção nestes ativos e metodologia de otimização para encontrar as melhores soluções em um determinado horizonte de planejamento / Abstract: A eletric power company is required to ensure continuity and quality of the provided service. To promote the quality of service, ANEEL introduced penalties in contracts with the electric power companies if transmission facilities are turned off by accident, equipment failure or programmed maintenance. Traditional approaches to maintenance of electric energy transmission systems are based on actions performed periodically, or programmed, in agreement with an analysis of needs. Although these approaches have the goal of improving the performance of these systems, generally there is not an accurate assessment of the impact of maintenance actions on the reliability of those actions related to the employed resources, as well as current legal penalties. The object thus formulated is characterized as a combinatorial optimization problem with the objective to find the sequence of maintenance actions that minimize the resources used in maintenance, ensuring a level of reliability desired for the Electric System. This work proposes an approach to address this problem based on the relationship reliability/ cost with the prospect of finding the best strategies for performing maintenance on equipment (assets) of electricity transmission, presenting a mathematical model for finding a feasible schedule (which respects the constraints of the Electric System) maintenance programming for these assets and optimization methodology to find the best solutions in a given planning horizon / Mestrado / Matematica Aplicada / Mestre em Matemática Aplicada

Orientadores: André Luiz Morelato França, Paulo Morelato França / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação / Made available in DSpace on 2018-08-20T08:47:23Z (GMT). No. of bitstreams: 1 Usberti_FabioLuiz_D.pdf: 2207082 bytes, checksum: 83078a448a40f75c373b989f9af006fb (MD5) Previous issue date: 2012 / Resumo:O problema de roteamento em arcos capacitado e aberto (open capacitated arc routing problem, OCARP) é um problema de otimização combinatorial NP-difícil em que, dado um grafo não-direcionado, o objetivo consiste em encontrar um conjunto de rotas de custo mínimo para veículos com capacidade restrita que atendam a demanda de um subconjunto de arestas. O OCARP está relacionado com o problema de roteamento em arcos capacitado (capacitated arc routing problem, CARP), mas difere deste pois o OCARP não possui um nó depósito e as rotas não estão restritas a ciclos. Aplicações da literatura para o OCARP são discutidas. Uma formula ção de programação linear inteira é fornecida junto com propriedades do problema. Uma metaheurística GRASP (greedy randomized adaptive search procedure) com reconexão por caminhos (path-relinking) é proposta e comparada com outras metaheurísticas bem-sucedidas da literatura. Algumas características do GRASP são: (i) ajuste reativo de parâmetros, cujos valores são estocasticamente selecionados com viés 'aqueles valores que produziram, em média, as melhores soluções; (ii) um filtro estatístico que descarta soluções iniciais caso estas tenham baixa probabilidade de superar a melhor solução incumbente; (iii) uma busca local infactível que gera soluções de baixo custo utilizadas para explorar fronteiras factíveis/infactíveis do espaço de soluções; (iv) a reconexão por caminhos evolutiva aprimora progressivamente um conjunto de soluções de elevada qualidade (soluções elites). Testes computacionais foram conduzidos com instâncias CARP e OCARP e os resultados mostram que o GRASP é bastante competitivo, atingindo os melhores desvios entre os custos das soluções e limitantes inferiores conhecidos. Este trabalho também propõe um algoritmo exato para o OCARP que se baseia no paradigma branch-and-bound. Três limitantes inferiores são propostos e um deles utiliza o método dos subgradientes para resolver uma relaxação lagrangeana. Testes computacionais comparam o algoritmo branch-and-bound com o CPLEX resolvendo um modelo reduzido OCARP de programa ção linear inteira. Os resultados revelam que o algoritmo branch-and-bound apresentou resultados melhores que o CPLEX no que diz respeito aos desvios entre limitantes e ao número de melhores soluções / Abstract: The Open Capacitated Arc Routing Problem (OCARP) is an NP-hard combinatorial optimization problem where, given an undirected graph, the objective is to find a minimum cost set of tours that services a subset of edges with positive demand under capacity constraints. This problem is related to the Capacitated Arc Routing Problem (CARP) but differs from it since OCARP does not consider a depot, and tours are not constrained to form cycles. Applications to OCARP from literature are discussed. An integer linear programming formulation is given, followed by some properties of the problem. A Greedy Randomized Adaptive Search Procedure (GRASP) with path-relinking (PR) solution method is proposed and compared with other successful metaheuristics. Some features of this GRASP with PR are (i) reactive parameter tuning, where the metaheuristic parameters values are stochastically selected biased in favor of those values which produced the best solutions in average; (ii) a statistical filter, which discards initial solutions if they are unlikely to improve the incumbent best solution; (iii) infeasible local search, where high-quality solutions, though infeasible, are used to explore the feasible/infeasible boundaries of the solution space; (iv) evolutionary PR, a recent trend in which a pool of elite solutions is progressively improved by relinking pairs of elite solutions. Computational tests were conducted for both CARP and OCARP instances, and results reveal that the GRASP with PR is very competitive, achieving the best overall deviation from lower bounds. This work also proposes an exact algorithm for OCARP, based on the branch-and-bound paradigm. Three lower bounds are proposed, one of them uses a subgradient method to solve a Lagrangian relaxation. The computational tests compared the proposed branch-and-bound with a commercial state-of-the-art ILP solver. Results reveal that the branch-and-bound outperformed CPLEX in the overall average deviation from lower bounds / Doutorado / Automação / Doutor em Engenharia Elétrica

Dans cette thèse, nous traitons essentiellement des problèmes de lot sizing en désassemblage avec une structure de produits à désassembler à deux niveaux sans composants communs. Nous traitons deux problèmes différents. Dans le premier problème, nous considérons un seul produit et la contribution porte sur le développement de deux modèles de programmation en nombres entiers. Le premier modèle est considéré sans ventes perdues où toutes les demandes doivent être satisfaites, et le deuxième est considéré avec ventes perdues où les demandes peuvent ne pas être satisfaites. Pour la résolution de ce problème, nous développons d’abord une approche analytique permettant de calculer les stocks de surplus (avant la résolution du problème) à la fin de l’horizon de planification. Ensuite, nous adaptons trois heuristiques connues pour leurs performances et largement utilisées dans le problème lot sizing en production « Silver Meal, Part Period Balancing et Least Unit Cost ». Dans le deuxième problème, nous considérons plusieurs produits avec contrainte de capacité et la contribution porte sur l’extension des deux modèles précédents. Le premier est également considéré sans ventes perdues et le deuxième avec ventes perdues. En ce qui concerne la résolution de ce problème et compte tenu de sa complexité, un algorithme génétique est d’abord proposé. Ensuite, afin d’améliorer cet algorithme, nous intégrons une heuristique Fix-and-Optimize dans ce dernier tout en proposant une approche hybride. Finalement, des tests sont effectués sur de nombreuses instances de la littérature afin de montrer l’efficacité et les limites de chaque approche de résolution / In this thesis, we mainly deal with lot sizing problems by disassembling with a structure of products to disassemble with two levels and without commonality components. We treat two different problems. In the first problem, we consider a single product whose contribution focuses on developing the two programming models integers. The first model is considered without lost sales where all demands must be satisfied, and the second one is considered with lost sales where demands may not be met. To solve this problem, we first develop an analytical approach to calculate the surplus stocks (before solving the problem) at the end of the planning horizon. Then we adapt three heuristics known for their performance and widely used in the lot sizing problem of production "Silver Meal, Part Period Balancing and Least Unit Cost". In the second problem, we consider a number of products with capacity constraint, and the contribution relates to the extension of the two previous models. The first is considered without lost sales and the second with lost sales. Regarding the resolution of this problem and given its complexity, a genetic algorithm is first proposed. Then, to improve this algorithm, we integrate a Fix-and-Optimize heuristic in the latter while offering a hybrid approach. Finally, various tests are performed on different literature instances to demonstrate the effectiveness and limitations of each solving approach

In this thesis we focus on Stochastic combinatorial Optimization Problems (SCOPs), a wide class of combinatorial optimization problems under uncertainty, where part of the information about the problem data is unknown at the planning stage, but some knowledge about its probability distribution is assumed.<p><p>Optimization problems under uncertainty are complex and difficult, and often classical algorithmic approaches based on mathematical and dynamic programming are able to solve only very small problem instances. For this reason, in recent years metaheuristic algorithms such as Ant Colony Optimization, Evolutionary Computation, Simulated Annealing, Tabu Search and others, are emerging as successful alternatives to classical approaches.<p><p>In this thesis, metaheuristics that have been applied so far to SCOPs are introduced and the related literature is thoroughly reviewed. In particular, two properties of metaheuristics emerge from the survey: they are a valid alternative to exact classical methods for addressing real-sized SCOPs, and they are flexible, since they can be quite easily adapted to solve different SCOPs formulations, both static and dynamic. On the base of the current literature, we identify the following as the key open issues in solving SCOPs via metaheuristics: <p>(1) the design and integration of ad hoc, fast and effective objective function approximations inside the optimization algorithm;<p>(2) the estimation of the objective function by sampling when no closed-form expression for the objective function is available, and the study of methods to reduce the time complexity and noise inherent to this type of estimation;<p>(3) the characterization of the efficiency of metaheuristic variants with respect to different levels of stochasticity in the problem instances. <p><p>We investigate the above issues by focusing in particular on a SCOP belonging to the class of vehicle routing problems: the Probabilistic Traveling Salesman Problem (PTSP). For the PTSP, we consider the Ant Colony Optimization metaheuristic and we design efficient local search algorithms that can enhance its performance. We obtain state-of-the-art algorithms, but we show that they are effective only for instances above a certain level of stochasticity, otherwise it is more convenient to solve the problem as if it were deterministic.<p>The algorithmic variants based on an estimation of the objective function by sampling obtain worse results, but qualitatively have the same behavior of the algorithms based on the exact objective function, with respect to the level of stochasticity. Moreover, we show that the performance of algorithmic variants based on ad hoc approximations is strongly correlated with the absolute error of the approximation, and that the effect on local search of ad hoc approximations can be very degrading.<p><p>Finally, we briefly address another SCOP belonging to the class of vehicle routing problems: the Vehicle Routing Problem with Stochastic Demands (VRPSD). For this problem, we have implemented and tested several metaheuristics, and we have studied the impact of integrating in them different ad hoc approximations.<p> / Doctorat en sciences appliquées / info:eu-repo/semantics/nonPublished

<p>A metaheuristic is a generic algorithmic template that, once properly instantiated, can be used for finding high quality solutions of combinatorial optimization problems.<p>For obtaining a fully functioning algorithm, a metaheuristic needs to be configured: typically some modules need to be instantiated and some parameters need to be tuned. For the sake of precision, we use the expression <em>parametric tuning</em> for referring to the tuning of numerical parameters, either continuous or discrete but in any case ordinal. <p>On the other hand, we use the expression <em>structural tuning</em> for referring to the problem of defining which modules should be included and, in general, to the problem of tuning parameters that are either boolean or categorical. Finally, with <em>tuning</em> we refer to the composite <em>structural and parametric tuning</em>.</p><p><p><p>Tuning metaheuristics is a very sensitive issue both in practical applications and in academic studies. Nevertheless, a precise definition of the tuning problem is missing in the literature. In this thesis, we argue that the problem of tuning a metaheuristic can be profitably described and solved as a machine learning problem.</p><p><p><p>Indeed, looking at the problem of tuning metaheuristics from a machine learning perspective, we are in the position of giving a formal statement of the tuning problem and to propose an algorithm, called F-Race, for tackling the problem itself. Moreover, always from this standpoint, we are able to highlight and discuss some catches and faults in the current research methodology in the metaheuristics field, and to propose some guidelines.</p><p><p><p>The thesis contains experimental results on the use of F-Race and some examples of practical applications. Among others, we present a feasibility study carried out by the German-based software company <em>SAP</em>, that concerned the possible use of F-Race for tuning a commercial computer program for vehicle routing and scheduling problems. Moreover, we discuss the successful use of F-Race for tuning the best performing algorithm submitted to the <em>International Timetabling Competition</em> organized in 2003 by the <em>Metaheuristics Network</em> and sponsored by <em>PATAT</em>, the international series of conferences on the <em>Practice and Theory of Automated Timetabling</em>.</p> / Doctorat en sciences appliquées / info:eu-repo/semantics/nonPublished

The Web Based Query Optimization Simulator (WBQOS) is a software tool designed to enhance understanding of query optimization with a Relational Database Management System (RDBMS). WBQOS allows the user to visualize and participate in query optimization, which enhances the learning process.

O estudo tem como finalidade tratar a alocação de recursos no nível operacional com a presença de incertezas. Para isso, foi proposta uma abordagem de otimização usando métodos heurísticos. As soluções de problemas de produção e logística, comumente abordadas em pesquisa operacional, exploram diversos parâmetros dentre os quais o presente estudo considera três como de incerteza: demanda, tempo de execução e indisponibilidade de recursos. Para tal finalidade foi escolhido como estudo de caso a resolução de um problema de logística. O problema consiste na minimização dos custos de operação, na seleção de veículos em uma frota heterogênea, consolidação das cargas para cada cliente e na seleção do tipo de frete utilizado. Quanto ao tipo de frete, são considerados dois, os quais se diferenciam quanto aos ativos envolvidos na produção e ao tipo de prestação de serviço, sendo eles: i) frota da empresa com serviço terceirizado; ii) frota e serviços totalmente terceirizados. O problema original foi decomposto em duas etapas: i) Compartimentalizador e ii) Alocador. As duas etapas são solucionadas via a abordagem de Busca Tabu, sendo que a primeira etapa (Compartimentalizador) gera uma lista dos carregamentos factíveis que atenda pedidos de até três clientes distintos. O Alocador se utiliza da lista dos carregamentos factíveis para definir como e quando cada pedido será atendido. Os resultados indicam a viabilidade da adoção desta abordagem para a solução de problemas reais. / The study aims to address the allocation of resources at the operational level under uncertainties. For this reason, it was proposed an optimization approach based on heuristic methods. The resolutions of production and logistics problems, commonly addressed in operational research, explore various parameters among which the present study considers three variables of uncertainty: demand, operation time and resources availability. For this purpose a logistics problem was chosen as study of case. The problem consists in minimizing cost operation, selection of vehicles in a heterogeneous fleet, consolidation of loads for each client and selecting the type of freight payables. Regarding of freight payables types, there are centered in two different tariffs, mainly due to assets and service negotiation, such as: i) fleet controlled by company and service outsource; ii) fleet and service completely outsource. The resolution of the original problem was broke down in two steps: i) Compartmentalizer and ii) Allocator. Both steps are solved through Tabu Search approach; the first step (Compartmentalizer) generates a list of feasible shipments to fulfill orders up to three different customers. The second step, the allocator uses the list of feasible shipments to define how and when each request will be supplied. The results aim the feasibility of assumes this approach in order to solve real problems.

O estudo tem como finalidade tratar a alocação de recursos no nível operacional com a presença de incertezas. Para isso, foi proposta uma abordagem de otimização usando métodos heurísticos. As soluções de problemas de produção e logística, comumente abordadas em pesquisa operacional, exploram diversos parâmetros dentre os quais o presente estudo considera três como de incerteza: demanda, tempo de execução e indisponibilidade de recursos. Para tal finalidade foi escolhido como estudo de caso a resolução de um problema de logística. O problema consiste na minimização dos custos de operação, na seleção de veículos em uma frota heterogênea, consolidação das cargas para cada cliente e na seleção do tipo de frete utilizado. Quanto ao tipo de frete, são considerados dois, os quais se diferenciam quanto aos ativos envolvidos na produção e ao tipo de prestação de serviço, sendo eles: i) frota da empresa com serviço terceirizado; ii) frota e serviços totalmente terceirizados. O problema original foi decomposto em duas etapas: i) Compartimentalizador e ii) Alocador. As duas etapas são solucionadas via a abordagem de Busca Tabu, sendo que a primeira etapa (Compartimentalizador) gera uma lista dos carregamentos factíveis que atenda pedidos de até três clientes distintos. O Alocador se utiliza da lista dos carregamentos factíveis para definir como e quando cada pedido será atendido. Os resultados indicam a viabilidade da adoção desta abordagem para a solução de problemas reais. / The study aims to address the allocation of resources at the operational level under uncertainties. For this reason, it was proposed an optimization approach based on heuristic methods. The resolutions of production and logistics problems, commonly addressed in operational research, explore various parameters among which the present study considers three variables of uncertainty: demand, operation time and resources availability. For this purpose a logistics problem was chosen as study of case. The problem consists in minimizing cost operation, selection of vehicles in a heterogeneous fleet, consolidation of loads for each client and selecting the type of freight payables. Regarding of freight payables types, there are centered in two different tariffs, mainly due to assets and service negotiation, such as: i) fleet controlled by company and service outsource; ii) fleet and service completely outsource. The resolution of the original problem was broke down in two steps: i) Compartmentalizer and ii) Allocator. Both steps are solved through Tabu Search approach; the first step (Compartmentalizer) generates a list of feasible shipments to fulfill orders up to three different customers. The second step, the allocator uses the list of feasible shipments to define how and when each request will be supplied. The results aim the feasibility of assumes this approach in order to solve real problems.