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.

The struggle to model and solve Combinatorial Optimization Problems (COPs) has challenged the development of new approaches to deal with COPs. In one of the front lines of such approaches, Operational Research (OR) and Constraint Programming (CP) optimization techniques are beginning to converge, despite their very different origins. More specifically, Mixed Integer Linear Programming (MILP) and Constraint Logic Programming (CLP) are at the confluence of the OR and the CP fields. This thesis summarizes and contrasts the essential characteristics of MILP and CLP, and the ways that they can be fruitfully combined. Chapters 1 to 3 sketch the intellectual background for recent efforts at integration and the main results achieved. In addition, these chapters highlight that CLP is known by its reach modeling framework, and the MILP modeling vocabulary is just based on inequalities, which makes the modeling process hard and error-prone. Therefore, a combined CLP-MILP approach suffers from this MILP inherited drawback. In chapter 4, this issue is addressed, and some "high-level" MILP modeling structures based on logical inference paradigms are proposed. These structures help the formulation of MILP models, and can be seen as a contribution towards a unifying modeling framework for a combined CLP-MILP approach. In addition, chapter 5 presents an MILP formulation addressing a combinatorial problem. This problem is focused on issues regarding the oil industry, more specifically, issues involving the scheduling of operational activities in a multi-product pipeline. Chapter 5 demonstrates the applicability of the high-level MILP modeling structures in a real-world scenario. Furthermore, chapter 6 presents a CLP-MILP formulation addressing the same scheduling problem previously exploited. This chapter demonstrates the applicability of the high-level MILP modeling structures in an integrated CLP-MILP modeling framework. The set of simulations conducted indicates that the combined CLP-MILP model was solved to optimality faster than either the MILP model or the CLP model. Thus, the CLP-MILP framework is a promising alternative to deal with the computational burden of this pipeline-scheduling problem. In essence, this thesis considers the integration of CLP and MILP in a modeling standpoint: it conveys the fundamentals of both techniques and the modeling features that help establish a combined CLP-MILP approach. Herein, the concentration is on the building of MILP and CLP-MILP models rather than on the solution process.

A Inteligência de Enxame (Swarm Intelligence) é uma área de estudos que busca soluções para problemas de otimização utilizando-se de técnicas computacionais inspiradas no comportamento social emergente encontrado na biologia. A metaheurística Particle Swarm Optimization (PSO) é relativamente nova e foi inspirada no comportamento social de bandos de pássaros. PSO tem apresentado bons resultados em alguns trabalhos recentes de otimização discreta, apesar de ter sido concebido originalmente para a otimização de problemas contínuos. Este trabalho trata o Problema de Atribuição de Tarefas - Task Assignment Problem (TAP), e apresenta uma aplicação: o problema de alocação de táxis e clientes, cujo objetivo da otimização está em minimizar a distância percorrida pela frota. Primeiramente, o problema é resolvido em um cenário estático, com duas versões do PSO discreto: a primeira abordagem é baseada em codificação binária e a segunda utiliza permutações para codificar as soluções. Os resultados obtidos mostram que a segunda abordagem é superior à primeira em termos de qualidade das soluções e tempo computacional, e é capaz de encontrar as soluções ótimas para o problema nas instâncias para as quais os valores ótimos são conhecidos. A partir disto, o algoritmo é adaptado para a otimização do problema em um ambiente dinâmico, com a aplicação de diferentes estratégias de resposta às mudanças. Os novos resultados mostram que a combinação de algumas abordagens habilita o algoritmo PSO a obter boas soluções ao longo da ocorrência de mudanças nas variáveis de decisão problema, em todas as instâncias testadas, com diferentes tamanhos e escalas de mudança. / Swarm Intelligence searches for solutions to optimization problems using computational techniques inspired in the emerging social behavior found in biology. The metaheuristic Particle Swarm Optimization (PSO) is relatively new and can be considered a metaphor of bird flocks. PSO has shown good results in some recent works of discrete optimization, despite it has been originally designed for continuous optimization problems. This paper deals with the Task Assignment Problem (TAP), and presents an application: the optimization problem of allocation of taxis and customers, whose goal is to minimize the distance traveled by the fleet. The problem is solved in a static scenario with two versions of the discrete PSO: the first approach that is based on a binary codification and the second one which uses permutations to encode the solution. The obtained results show that the second approach is superior than the first one in terms of quality of the solutions and computational time, and it is capable of achieving the known optimal values in the tested instances of the problem. From this, the algorithm is adapted for the optimization of the problem in a dynamic environment, with the application of different strategies to respond to changes. The new results show that some combination of approaches enables the PSO algorithm to achieve good solutions along the occurrence of changes in decision variables problem, in all instances tested, with different sizes and scales of change.

Esta dissertação apresenta a aplicação de uma nova abordagem utilizando Algoritmo Genético na resolução do Problema de Corte Unidimensional na minimização de dois objetivos, geralmente conflitantes, o número de objetos processados e o setup, simultaneamente. O problema de corte consiste, basicamente, em encontrar a melhor maneira de obter peças de tamanhos distintos (itens) a partir do corte de peças maiores (objetos) com o objetivo de minimizar alguma espécie de custo ou maximizar o lucro. A disposição dos itens no objeto para a realização de cortes durante sua produção é denominada padrão de corte. E o setup é o tempo de preparação de máquina. O modelo do problema, a função objetivo e o método proposto denominado SingleGA, bem como os passos utilizados para sua resolução, também são apresentados. Os resultados obtidos pelo SingleGA são comparados com os métodos SHP, Kombi234, ANLCP300 e Symbio, encontrados na literatura, a fim de verificar a capacidade de encontrar soluções viáveis e competitivas. Os resultados computacionais mostram que o método proposto, o qual utiliza apenas um algoritmo genético para resolver esses dois objetivos inversamente relacionados, proporciona bons resultados.

Esta tese apresenta um estudo sobre modelagem computacional onde são aplicadas meta-heurísticas de otimização na solução de problemas inversos de transferência radiativa em meios unidimensionais com albedo dependente da variável óptica, e meios unidimensionais de duas camadas onde o problema inverso é tratado como um problema de otimização. O trabalho aplica uma meta-heurística baseada em comportamentos da natureza conhecida como algoritmo dos vagalumes. Inicialmente, foram feitos estudos comparativos de desempenho com dois outros algoritmos estocásticos clássicos. Os resultados encontrados indicaram que a escolha do algoritmo dos vagalumes era apropriada. Em seguida, foram propostas outras estratégias que foram inseridas no algoritmo dos vagalumes canônico. Foi proposto um caso onde se testou e investigou todas as potenciais estratégias. As que apresentaram os melhores resultados foram, então, testadas em mais dois casos distintos. Todos os três casos testados foram em um ambiente de uma camada, com albedo de espalhamento dependente da posição espacial. As estratégias que apresentaram os resultados mais competitivos foram testadas em um meio de duas camadas. Para este novo cenário foram propostos cinco novos casos de testes. Os resultados obtidos, pelas novas variantes do algoritmo dos vagalumes, foram criticamente analisados. / This thesis presents a study on computational modeling where optimization metaheuristics are applied to the solution of inverse radiative transfer problems in heterogeneous media: in one-layer media with space-dependent single scattering albedo, and two-layer media, where the inverse problem is formulated as an optimization problem. It is applied a metaheuristic based on the natural behavior of fireflies, known as the firefly algorithm. Initially, comparative studies of performance were made with two other classic stochastic algorithms. The results indicated that the choice of the firefly algorithm was appropriate. Then, it was proposed other strategies that have been inserted into the original firefly algorithm. A first case was proposed where all the strategies were investigated and tested. The strategies with the best results were investigated in other two different cases. All the three proposed cases involved one-layer media with space-dependent scattering albedo. The strategies have been tested and evaluated, and those which presented the best competitive results were then implemented for radiative problems in two-layer media. For this new scenario five test cases were investigated, and the results obtained with the new strategies developed in this work were critically analyzed.

Orientador: Ariovaldo Verandio Garcia, Ruben Augusto Romero Lazaro / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-06T06:56:43Z (GMT). No. of bitstreams: 1 RiderFlores_MarcosJulio_D.pdf: 1021887 bytes, checksum: 6000961c2f5457b410ac691912476270 (MD5) Previous issue date: 2006 / Resumo: Neste trabalho são propostos modelos matemáticos e técnicas de solução para resolver o problema de planejamento da expansão de sistemas de transmissão através de três enfoques. a) Usando o modelo de corrente alternada do sistema de transmissão e um algoritmo heurístico construtivo especializado para resolver o problema de planejamento, e, ainda, realiza-se uma primeira tentativa de alocação de fontes de potência reativas; b) Usando o modelo de corrente contínua e técnicas de programação não-linear especializadas. Nesse caso emprega-se uma versão relaxada do problema de planejamento da expansão de sistemas de transmissão usando o modelo de corrente contínua, onde a integralidade das variáveis de investimento é desprezada. Resolve-se o problema de programação não-linear, modelado de forma matricial com um algoritmo de otimização especializado e, além disso, um algoritmo heurístico construtivo especializado é utilizado para resolver o problema de planejamento. c) Usando o modelo de corrente contínua e um algoritmo Branch and Bound (B&B) sem empregar técnicas de decomposição. Para isso foram redefinidos os chamados testes de sondagem no algoritmo B&B e em cada nó da árvore de B&B tem-se um problema de programação não-linear que são resolvidos usando a metodologia desenvolvida no item (b). Os ítens (a), (b) e (c) requerem a solução de problemas de programação não-linear diferenciados. Uma revisão das características principais da resolução iterativa dos métodos de pontos interiores é apresentada. Foi desenvolvida uma técnica baseada em uma combinação de métodos de pontos interiores de alta ordem (MPI-AO) para resolver os problemas de programação não-linear de forma rápida, eficiente e robusta. Essa combinação dos MPI-AO tem como objetivo colocar num único método as características particulares de cada um dos MPI-AO e melhorar o desempenho computacional comparado com os MPI-AO de forma individual / Abstract: In this work mathematical models and solution techniques are proposed to solve the power system transmission expansion planning problem through three approaches: a) Using the nonlinear model ofthe transmission system (AC model) and a specialized constructive heuristic algorithm to solve the problem and, yet, a first attempt to allocate reactive power sources is also considered; b) Using the direct-current (DC) model and specialized techniques of nonlinear programming. In this case a version of the power system transmission expansion planning problem using the DC model where the integrality of the investment variables is relaxed is used. The nonlinear programming problem is solved with a specialized optimization algorithm and, moreover, a constructive heuristic algorithm is employed to solve the planning problem. c) Using the DC model and Branch and Bound (B&B) algorithm without the use of decomposition techniques. The so called fathoming tests of the B&B were redefined and at each node of the tree a nonlinear programming problem is solved using the method developed in b). Items a), b) and c) require the solution of distinct problems of nonlinear programming. A revision of the main characteristics of the iterative solution of the interior points methods is presented. An optimization technique based on a combination of the higher order interior point methods (HO-IPM) had been developed to solve the nonlinear programming problems in a fast, efficient and robust way. This combination of the HO-IPM has as objective to explore the particular characteristics of each method in a single one and to improve the comparative computational performance with the HO-IPM of individual form / Doutorado / Energia Eletrica / Doutor em Engenharia Elétrica

Sejam GI = (VI ,AI) e GM = (VM,AM) dois grafos simples. Um mapeamento de GI para GM é um conjunto de associações, tal que cada vértice de VI está associado a um vértice de VM, e cada aresta de AI está associada a um par de vértices de VM. A cada possível associação é atribuído um custo. O problema de correspondência inexata entre grafos (PCIG) consiste em encontrar um mapeamento de GI para GM, tal que a soma dos custos de suas associações seja mínima. Nesta dissertação, resumimos os resultados encontrados na literatura sobre o PCIG e algumas de suas variações. Os resultados que incluímos aqui tratam sobre a questão de como formular o PCIG e algumas de suas variações, através de programação linear inteira. Provamos alguns resultados de complexidade computacional que relacionam variações do PCIG a problemas clássicos, como isomorfismo e partição de grafos. Fornecemos uma formulação através de programação linear inteira para o PCCA (uma variante do PCIG com conexidade e cobertura de arestas). Mostramos que o PCCA é NP-difícil quando os grafos de entrada são completos ou árvores (chamamos o segundo caso de PCCA para árvores). Apresentamos uma formulação linear inteira e um algoritmo - que é polinomial se o grau máximo dos vértices de VM for limitado por uma constante - para o PCCA para árvores. Mostramos um caso especia em que o PCCA para árvores pode ser resolvido em tempo polinomial. Por último, exibimos alguns resultados experimentais, inclusive com instâncias reais de uma aplicação do problema. / Let GI = (VI ,AI) and GM = (VM,AM) be two simple graphs. A mapping from GI to GM is an association set, such that each vertex in VI is associated to a vertex in VM, and each edge in AI is associated to a pair of vertices of VM. A cost is defined to each possible association. The inexact graph correspondence problem (IGCP) consists in finding a mapping from GI to GM, such that the sum of its associations costs is minimized. In this dissertation, we summarize the results found in the literature about the IGCP and some variations. The results included here address the question of how to formulate the IGCP and some variations, using integer linear programming. We prove some computational complexity results which relate IGCP variations with classical problems, like graph isomorphism and partitioning. We give an integer linear programming formulation to the ICEC (IGCP with connectivity and edges cover). We show that the ICEC is NP-hard when the input graphs are complete or trees (we call the second case ICEC for trees). We introduce an integer linear formulation and an algorithm - which has polynomial running time if the vertices of VM have maximum degree bounded by a constant - to the ICEC for trees. We show a especial case in which the ICEC for trees can be solved in polynomial time. Finally, we present some experimental results, also with instances of a real application of the problem.

Muitas relações min-max em otimização combinatória podem ser demonstradas através de total dual integralidade de sistemas lineares. O conceito algébrico de bases de Hilbert foi originalmente introduzido com o objetivo de melhor compreender a estrutura geral dos sistemas totalmente dual integrais. Resultados apresentados posteriormente mostraram que bases de Hilbert também são relevantes para a otimização combinatória em geral e para a caracterização de certas classes de objetos discretos. Entre tais resultados, foram provadas, a partir dessas bases, versões do teorema de Carathéodory para programação inteira. Nesta dissertação, estudamos aspectos estruturais e computacionais de bases de Hilbert e relações destas com programação inteira e otimização combinatória. Em particular, consideramos versões inteiras do teorema de Carathéodory e conjecturas relacionadas. / There are several min-max relations in combinatorial optimization that can be proved through total dual integrality of linear systems. The algebraic concept of Hilbert basis was originally introduced with the objective of better understanding the general structure of totally dual integral systems. Some results that were proved later have shown that Hilbert basis are also relevant to combinatorial optimization in a general manner and to characterize certain classes of discrete objects. Among such results, there are versions of Carathéodory\'s theorem for integer programming that were proved through those basis. In this dissertation, we study structural and computational aspects of Hilbert basis and their relations to integer programming and combinatorial optimization. In particular, we consider integer versions of Carathéodory\'s theorem and related conjectures.

Muitas relações min-max em otimização combinatória podem ser demonstradas através de total dual integralidade de sistemas lineares. O conceito algébrico de bases de Hilbert foi originalmente introduzido com o objetivo de melhor compreender a estrutura geral dos sistemas totalmente dual integrais. Resultados apresentados posteriormente mostraram que bases de Hilbert também são relevantes para a otimização combinatória em geral e para a caracterização de certas classes de objetos discretos. Entre tais resultados, foram provadas, a partir dessas bases, versões do teorema de Carathéodory para programação inteira. Nesta dissertação, estudamos aspectos estruturais e computacionais de bases de Hilbert e relações destas com programação inteira e otimização combinatória. Em particular, consideramos versões inteiras do teorema de Carathéodory e conjecturas relacionadas. / There are several min-max relations in combinatorial optimization that can be proved through total dual integrality of linear systems. The algebraic concept of Hilbert basis was originally introduced with the objective of better understanding the general structure of totally dual integral systems. Some results that were proved later have shown that Hilbert basis are also relevant to combinatorial optimization in a general manner and to characterize certain classes of discrete objects. Among such results, there are versions of Carathéodory\'s theorem for integer programming that were proved through those basis. In this dissertation, we study structural and computational aspects of Hilbert basis and their relations to integer programming and combinatorial optimization. In particular, we consider integer versions of Carathéodory\'s theorem and related conjectures.

As empresas de manufatura, nos dias atuais, estão incessantemente em busca de redução de custos, motivadas pela concorrência e competição, que são características fortes da globalização. No Sistema Toyota de Produção (OHNO, 1988) é ressaltada a questão dos sete desperdícios que podem existir em um processo e que, consequentemente, geram custos no produto sem, contudo agregar valor ao mesmo. Um dos desperdícios mais comumente encontrados são os do fluxo do produto semiacabado (WIP), matéria-prima ou produto acabado. O estudo de Layout visa otimizar a disposição dos recursos dentro de um processo de modo a minimizar, entre outros, o fluxo de materiais. O presente estudo visa apresentar um caso real de uma grande empresa de autopeças na região de Curitiba, PR, que gasta milhões por ano em mudanças de Layout. O objeto de estudo é a linha de montagem de um determinado componente que esta empresa fabrica. Através do uso de Métodos Heurísticos propõe-se uma abordagem para a otimização do Layout desta linha de montagem. Esta abordagem foi dividida em duas etapas. Na primeira etapa, foi resolvido o problema de formação de células (visando melhorar os tempos computacionais, bem como a qualidade da solução), visando associar as máquinas disponíveis às peças a serem fabricadas. Na segunda etapa, resolve-se o problema de otimização do layout, considerando as associações de máquinas às peças feitas na primeira etapa. Nas duas etapas testou-se o uso de uma abordagem meta-heurística (busca tabu) híbrida, bem como o método exato denominado Branch-and-Bound (este na primeira etapa), para resolver o problema. Os resultados encontrados no arranjo físico das máquinas mostraram-se bastante promissores. / Nowadays, the manufacturing enterprises are constantly looking for costs reduction, driven by rivalry and competition, which are strong globalization characteristics. In the Toyota Production System (OHNO, 1988), are highlighted the seven wastes which can exist in a manufacturing process and that, consequently, generate costs to the product without, however, adding value to it. Some commonly found wastes are the work-in-process (WIP), raw material or finished products flow wastes. The layout study aims to optimize the layout of facilities inside a process to minimize, among others, the materials flow. This study aims to present a real case of a huge auto parts manufacturer enterprise located in Curitiba, PR, which spends millions a year on layout changes. The object of study is the assembly line of a specifical component that this company manufactures. Using Heuristic methods, it proposes an approach for the layout optimizing of this assembly line. This approach was divided in two stages: in the first one, the cell formation problem (in order to improve the computational time, as well as the solution quality) was solved in order to associate machines to parts. In the second stage, the layout optimizing problem is solved, considering the combination of machines to parts (made in first stage). In both stages the hybrid meta-heuristics approach (tabu search), as well as the Exact method so called Branch-and-Bound (this on first stage), were tested to solve this problem. The results found on layout of facilities were quite promising.