[pt] A Cerveja Heineken está presente em onze países da América Latina. Alguns têm sua demanda suprida por plantas industriais localizadas no próprio território, outros pela importação a partir de plantas localizadas em outros países da região e ainda há aqueles que dependem do fornecimento de cerveja da matriz da empresa localizada na Holanda. Considerando os mercados latino-americanos que são supridos regularmente por plantas industriais localizadas no exterior, apresentam-se três fornecedores (sources) distintos: Holanda, Argentina e Chile. Motivada pelo grande volume de cerveja importado da Heineken Holanda, pelos custos gerados por estas importações e ainda pelos problemas ocasionados pela dificuldade de algumas plantas cervejeiras locais em atender a demanda externa – entende-se por locais aquelas localizadas na região da América Latina -, esta dissertação se desenvolve. Assim, o intuito desse estudo é analisar a dinâmica da rede de distribuição de Cerveja Heineken para os países da América Latina, com vistas a identificar potenciais novas bases e propor uma melhor organização do fluxo de exportação. O objetivo é otimizar esse fluxo, reduzindo custos através da regionalização das chamadas sources, que nada mais são do que as plantas industriais cervejeiras que exportam e suprem os diversos países latinoamericanos. Para atender a este propósito, serão testadas potenciais sources e avaliados, por meio de ferramentas logísticas, os cenários que poderão suprir de forma mais eficaz os mercados da região. / [en] The Heineken Beer is present in eleven Latin-American countries. Some of them have their demand supplied by breweries located in their own countries, others by the importation from breweries located in other countries of the region and there are still those that depend on the beer exported from the headquarters of the company, in The Netherlands. Considering the Latin-American markets that have their demand regularly supplied by breweries located abroad, we identify three different origins: Holland, Argentina and Chile. Motivated by the large volume of beer imported from Heineken in The Netherlands, by the costs generated by such importations and also by the problems brought about by the difficulties found by some local breweries in order to meet their foreign demand - by local I mean located in the region of Latin America -, this dissertation is developed. The aim of this study is to analyze the dynamics of the distribution network of Heineken Beer throughout Latin-America, in order to identify potential new export bases and propose a better organization of the export flow. The objective is to optimize such flow, reducing costs through the regionalization of the so-called sources, which are nothing other than breweries exporting to and supplying the Latin-American countries. In order to fulfill this purpose, potential sources will be tested and, by making use of logistics tools, the scenarios that meet the demand of the region in a more effective way will be evaluated.

[pt] Descreve-se uma metodologia para planejamento da expansão da capacidade de ponta em sistemas interligados de usinas hidroelétricas. O objetivo é determinar os geradores e linhas de transmissão a serem instalados no sistema existente, de forma a suprir a carga prevista da maneira mais econômica possível, satisfazendo restrições de confiabilidade. A solução é baseada no método de decomposição de Benders, sendo o problema mestre um problema de programação inteira e o subproblema um problema estocástico de fluxo em redes. / [en] This thesis describes a methodology for peak capacity expansion of interconnected hydroelectric generating systems. The objective is to minimize investments in generators and transmission lines, subject to contraints on supply reliability. The solution approach is based on Benders decomposition, in which the master problem is an integer programming problem and the subploblem is a stochastic network flow problem.

[pt] A importância do planejamento em logística ferroviária cresce a cada dia devido ao alto custo dos investimentos para o aumento da sua capacidade. Entretanto, planejar é uma atividade que exige uma representação suficientemente precisa da realidade estudada. Neste contexto, os modelos de programação matemática apresentam-se cada vez mais adequados. Isto decorre dos recentes avanços nos algoritmos e computadores disponíveis para sua resolução. Esta dissertação apresenta modelos e algoritmos para o planejamento ferroviário tático e estratégico, isto é feito estudando o Problema de Planejamento de Atendimento (PPA). Primeiramente este problema é considerado assumindo que toda a estrutura ferroviária está definida: a malha, a tração e os vagões disponíveis, os pátios para carga, descarga e transbordo, suas respectivas taxas de carga e descarga e as demandas previstas. Em seguida, a questão adicional de determinar os pátios onde paradas podem ser efetuadas é considerada. Finalmente, em uma terceira etapa, introduz-se a capacidade de se analisar os efeitos do congestionamento de trechos da malha e seu impacto nos tempos de circulação e na capacidade da estrutura logística. Modelos são apresentados para cada um dos níveis de complexidade do PPA. Algoritmos exatos e heurísticos e técnicas de pré- processamento, foram desenvolvidos para os tratamentos dos casos obtidos. Em todos os casos, foi possível resolver de maneira ótima ou quase ótima em tempo razoável, tanto em termos acadêmicos, como para a utilização prática. Resultados computacionais sobre um amplo conjunto de instâncias reais são apresentados. / [en] Planning in Railway Logistic is an activity with growing importance. This is due to the high costs of investment to increase the railway capacity. Nevertheless, planning in this context is a cumbersome task, since a precise representation is necessary to consider most relevant points in this activity. Mathematical programming is becoming one of the best ways derive precise representations and to solve them. This is due to the recent advances on algorithms and computers used in the resolution of mathematical programming problems. This dissertation presents models and algorithms for tactical and strategical railway planning what is done by studying a demand planning problem (PPA). First, this problem is considered assuming that all the railway structure is defined: the network, the locomotives and wagons available, the yards for loading and unloading with their respective rates, and the forecast of demands. Next, the question of deciding the yards to stop is considered. Finally, in a third step, the effect of congestion in parts of the network is introduced to the models. This allows analyzing the variation in the travel times and its consequence in the logistic structure capacity. Models are presented for all cases of the PPA. Exact and heuristic algorithms, as well as pre-processing techniques, are described for the problem resolution. In all cases, the resulting approach allowed to solve the problems optimally or quasioptimally in a reasonable computing time. Computational results are presented on a wide set of real world instances.

[pt] Problemas de transporte de cargas fracionadas são grandes candidatos para a aplicação de técnicas de otimização como forma de obter um melhor aproveitamento de recursos. Nesta dissertação, são apresentados modelos de programação inteira e os algoritmos desenvolvidos para a resolução adequada dos problemas estudados neste contexto. O foco é o planejamento da movimentação dos veículos para o atendimento das demandas ao longo de um período pré-definido. Diferentes formas de contratação dos veículos são consideradas, demandas possuem janelas de tempo para serem atendidas e podem compartilhar um mesmo veículo em um ou mais trechos do seu caminho até o destino. Conexões são permitidas, ou seja, uma demanda pode utilizar mais de um veículo para o seu atendimento, respeitando as capacidades operacionais dos centros de distribuição e coleta. Os objetivos abrangem o dimensionamento da frota, que possui um custo fixo, e o planejamento da operação ao longo do período. Este deve determinar quais demandas são transportadas por quais veículos em que instantes e em que trechos. O método de resolução proposto utiliza algoritmos para a construção e pré-processamento de grafos que representam o problema e permitem que a formulação como programa inteiro tenha uma resolução mais efciente. Além disso, o algoritmo correspondente resolve uma sequência de programas inteiros para obter soluções viáveis de qualidade para as diferentes versões do problema aqui considerado. Melhorias nos limites inferiores obtidos também são propostas. O código resultante foi testado em um conjunto de instâncias baseadas na operação de uma transportadora brasileira de grande porte. Resultados foram obtidos tanto para condições de utilização reais, isto é, com o tempo de execução limitado, como para testar os limites do método proposto. Em ambos os casos pôde-se obter soluções de alta qualidade comprovada. / [en] Less-than-truckload transportation problems are great candidates for the application of optimization techniques as a form to obtain a better exploitation of resources. This thesis introduces integer programming models and the developed algorithms for the proper resolution of the studied problems in this context. The focal point is the vehicle's dislocation planning for the ideal attendance of the demands during a certain time period. Different forms of vehicle contract are considered. There are time windows for the attendances and demands can share a same vehicle in one or more parts of its route until his destination. Connections are allowed, that is, demands can use more than one vehicle for its attendance, respecting the operational capacities of the centers (collection and distribution stations). The goals embraces the sizing of the proper fleet which has a fixed cost, and the operation's planning during the period. This one should determine which demands are transported by which vehicles in what instants and where on routes. The resolution's method proposed uses algorithms for the graph's construction and pre-processing which represents the problem and allows that the formulation, as an integer program, to have a resolution more efficient. Furthermore, the corresponding algorithm solves a sequence of integer programs to obtain feasible quality solutions for the differents versions of the considered problem. Improvements on the lower bounds gotten are also proposed. The resulting code was tested in a set of proposed instances that were based on the operation of an important brazilian trucking company . Results were acquired such for conditions of real utilization, in other words, with a limited time of execution, as to test the limits of the proposed method. In both cases, solutions of comproved high quality were obtained.

[pt] Os sistemas ferroviários são grandes candidatos à aplicação de técnicas de otimização para o melhor aproveitamento dos seus recursos. Neste trabalho são apresentados dois modelos de programação inteira para problemas nesta área,o Problema de Planejamento de Atendimento -PPA- e o Problema de Fluxo de Vagões -PFV-. Ambos foram resolvidos de maneira ótima ou quase ótima em tempo razoável, tanto em termos acadêmicos como para sua utilização prática.São apresentados os problemas, as formulações dos modelos, as técnicas de préprocessamento utilizadas, assim como resultados computacionais de instâncias reais. / [en] Railroad systems are major candidates for the use of optimization techniques to obtain a more efficient use of resources. In this research we present two integer programming models for freight railroad problems, the Demand Fulfillment Problem and the Car Flow Problem. Both problems were solved to optimality or near-optimality in a reasonable time, either for academic or practical purposes. We present the descriptions of the problems, the mathematical formulations,the preprocessing techniques used, as well as computational results for real instances.

[pt] Esta dissertação de mestrado apresenta a utilização do novo paradigma de desenvolvimento de software, a programação orientada a objetos (OOP), na modelagem em redes de transportes. A utilização da OOP visa, através de suas características: herança, polimorfismo e encapsulamento, aumentar a flexibilidade, produtividade e eficiência dos softwares desenvolvidos segundo seus princípios. O programa desenvolvido, visa servir como uma ferramenta de auxílio a tomada de decisão, a nível estratégico, no planejamento de redes de transportes urbanos. O software faz a alocação de fluxos em redes buscando minimizar o custo do usuário, ou seja, segundo o primeiro princípio de Wardrop. Este estudo foi baseado no método Fusion, que propõe uma abordagem sistemática para o desenvolvimento de software orientado a objetos. O método também está voltado para requisitos de desenvolvimento para e com reutilização. Será feita uma abordagem a nível de análise, projeto e implementação. / [en] This Master thesis presents the utilization in transport modeling the new paradigm in software development, the Object Oriented Program (OOP). The using of OOP seeks improve the flexibility, productivity and efficiency in software developed under such principles. This will be done thought its characteristics: inheritance, polymorphism and encapsulation. The application of the OOP principles has been done adjusting the software TRAFFIC, developed in the University of Montreal. The model will be used like a decision making tool for the urban network transportation planning, ai a strategic level. The software assigns vehicle flows on road networks in order to minimize the user cost, following the first Wardrop`s principle. This research has been based on the Fusion method, that presents a systematic approach for development of object oriented software. The method also is directed toward the requirements of development with and for reutilization. The study will be developed at the level of analysis, project and implementation. / [es] Esta disertación de mestrado presenta la utilización del nuevo paradigma de desarrollo de software, la programación orientada a objetos (OOP), en la modelaje de redes de transportes. La utilización de la OOP tiene como objetivo, a través de sus características (herencia, polimorfismo y encapsulamiento) aumentar la flexibilidad, productividad y eficiencia de los softwares desarrollados según sus principios. El programa desarrollado sirve como herramienta de auxilio a la toma de decisión, a nivel estratégico, en la planificación de redes de transportes urbanos. El software configura los flujos en redes buscando minimizar el costo del usuario, o sea, según el primer princípio de Wardrop. Este estudio está basado en el método Fusión, que propone una abordaje sistemática para el desarrollo de software orientado a objetos. El método también considera requisitos de desarrollo para y con reutilización. Se realiza una abordaje a nível de análise, proyecto e implementación.

[pt] Problemas de multifluxos surgem como modelos básicos no contexto de várias aplicações de fluxos em redes, tais como redes de telecomunicações, redes de transporte e logística. Em tais aplicações, os fluxos que atravessam a rede compartilham simultaneamente os mesmos recursos disponíveis e são definidos por suas próprias restrições. A cada uma das arestas ligando os pontos da rede está associado um custo, fixo ou proporcional à sua utilização. Este trabalho trata problemas de projeto de redes multifluxos, em que os custos estão associados às capacidades instaladas nas arestas. Particularmente, será estudado o caso em que a função de custo nas arestas possui o comportamento de uma função escada crescente e descontínua, para o qual métodos exatos de resolução são ineficientes. Métodos heurísticos são propostos para a resolução aproximada do problema e sintetizados em um algoritmo de multi-partida com memória adaptativa. Um mecanismo de intensificação, conhecido na literatura como construção de vocabulário, é também explorado e aplicado. Finalmente, experimentos computacionais são realizados e o método de resolução proposto é analisado quanto aos seus resultados e os resultados obtidos pelo método de resolução proposto são analisados. O método obtém as melhores soluções conhecidas para algumas instâncias da literatura. / [en] Multicommodity flow problems arise widely as basic models in the context of network flows applications such as telecommunication networks, transportation problems, and logistic. In these applicatons, the flows that cross the networks share the same avaiable resources simultaneously and are defined by their own constraints. Each edge connecting two nodes in the network has an associated cost that is either fixed or proportional to its use. This work focuses on a network design problem in which the cost are associated with the capacities installed in the edges. Particularly, the network design problem studied has discrete and step increasing cost functions on the edges, for which exact methods are inefficient. Heuristics are proposed for the approximate memory algorithm. An intensification mechanism, known in the literature as vocabulary building, is also explored and applied. Finally, computational experiments are performed and the results obtained with the proposed solution method are evaluated. The method obtains the best known solutions for some instances in the literature.

[pt] Os sistemas rodoviários são grandes candidatos à aplicação de técnicas de otimização para a redução dos custos operacionais. Neste trabalho são apresentados dois modelos de programação inteira para problemas nesta área, o Problema de Transferência de Cargas (PTC) e o Problema de Alocação de Cargas (PAC). Ambos foram resolvidos de maneira ótima ou quase ótima em tempo razoável, tanto em termos acadêmicos como para sua utilização prática. São apresentados os problemas, as formulações dos modelos, as técnicas de pré-processamento utilizadas, assim como resultados computacionais de instâncias reais. / [en] Road systems are major candidates for the use of optimization techniques to obtain operational reduction costs. In this research we present two integer programming models for road problems, the Load Transference Problem and the Load Scheduling Problem. Both problems were solved to optimality or near-optimality in a reasonable time, either for academic or practical purposes. We present the descriptions of the problems, the mathematical formulations, the preprocessing techniques used, as well as computational results for real instances.

[pt] Calcular o valor do fluxo máximo entre um nó origem e um nó destino em uma rede é um problema clássico no contexto de Fluxos em Redes. Sua extensão, chamada de problema do fluxo máximo multiterminal, consiste em achar os valores dos fluxos máximos entre todos os pares de nós de uma rede não direcionada. Estes problemas possuem diversas aplicações, especialmente nos campos de transporte, logística, telecomunicações e energia. Neste trabalho, apreciamos a recente teoria da análise de sensibilidade, em que se estuda a influência da variação de capacidade de arestas nos fluxos máximos multiterminais, e estendemos a computação dinâmica dos fluxos multiterminais para o caso de mais de uma aresta com capacidade variável. Através dessa teoria, relacionamos também nós de corte e fluxos multiterminais, o que permitiu desenvolver um método competitivo para solucionar o problema do fluxo máximo multiterminal, quando a rede possui nós de corte. Os resultados dos experimentos computacionais conduzidos com o método proposto são apresentados e comparados com os de um algoritmo clássico, fazendo uso de instâncias geradas e outras conhecidas da literatura. Por último, aplicamos a teoria apresentada em um problema de identificação de complexos de proteínas em redes de interação proteína-proteína. Através da generalização de um algoritmo e de um resultado teórico sobre exclusão de cortes mínimos, foi possível reduzir o número de cálculos de fluxo máximo necessários para identificar tais complexos. / [en] Computing the maximum flow value between a source and a terminal nodes in a given network is a classic problem in the context of network flows. Its extension, namely the multi-terminal maximum flow problem, consists of finding the maximum flow values between the all pairs of nodes in a given undirected network. These problems have several applications, especially in the fields of transports, logistics, telecommunications and energy. In this work, we study the recent theory of sensitivity analysis, which examines the influence of edges capacity variation on the multi-terminals maximum flows, and we extend the dynamic computation of multi-terminals flows to the case of more than one edge with variable capacity. Based on this theory, we also relate cut nodes and multiterminals flows, allowing us to develop a competitive method to solve the multiterminal maximum flow problem, when the network has cut nodes. The results of the computational experiments conducted with the proposed method are presented and compared with the results of a classical algorithm, using generated and wellknown instances of the literature. Finally, we apply the presented theory on a problem of identifying protein complexes in protein-protein interaction networks. Through the generalization of an algorithm and a theoretical result about exclusion of minimum cuts, it was possible to reduce the number of maximum flow computations necessary to identify such complexes.

Submitted by SBI Biblioteca Digital (sbi.bibliotecadigital@puc-campinas.edu.br) on 2017-03-23T14:50:03Z No. of bitstreams: 1 ADOLFO BLENGINI NETO.pdf: 3955942 bytes, checksum: 45ddc01c026b2c6b88359672fba01257 (MD5) / Made available in DSpace on 2017-03-23T14:50:03Z (GMT). No. of bitstreams: 1 ADOLFO BLENGINI NETO.pdf: 3955942 bytes, checksum: 45ddc01c026b2c6b88359672fba01257 (MD5) Previous issue date: 2017-02-16 / Pontif?cia Universidade Cat?lica de Campinas ? PUC Campinas / This study proposes the development of an environment for optimization of the operations of electrical distribution systems. The environment is proposed for the modern electrical distribution networks considering the possibility of inclusion of distributed generation and mesh topology. The environment is divided into three modules. The first module consists of standardizing the input and organization data of the network in memory using techniques of object-oriented software engineering. This approach simplifies the processes of nodal analysis of the circuits, improves the performance of the solution and allows reusing the objects and operations in other implementations. The second module is responsible for analyzing and represents network characteristics: topology, load model and distributed generation points. The third consists of the BFS, FW and OCF methods to perform the current flow calculation and allows the user to choose the desired algorithm, being able to present the currents and voltages in each iteration. The choice of different methods in the optimization environment allows the use of the most adherent method to the different network topologies, the types of load, the flexibility in the use of capacity constraints of the elements of the network and the inclusion of generation limits and voltage limits. In order to verify the adhesion and the efficiency of the environment, simulations were carried out on balanced three-phase circuits of primary distribution of 11, 33 and 400 buses with different load models, radial or mesh topology, with and without distributed generation. / Esta pesquisa prop?e-se ao desenvolvimento de um ambiente para otimiza??o da opera??o de sistemas de distribui??o de energia. O ambiente ? aderente ?s modernas redes de distribui??o de energia por considerar a possibilidade de inclus?o de gera??o distribu?da e topologia em malha. O ambiente est? dividido em tr?s m?dulos. O primeiro m?dulo consiste na padroniza??o dos dados de entrada e organiza??o da rede em mem?ria no formato de grafo utilizando t?cnicas de engenharia de software orientada a objetos. Este enfoque simplifica os processos de an?lises nodais dos circuitos, melhora o desempenho da solu??o e permite reaproveitar os objetos e opera??es em outras implementa??es. O segundo m?dulo ? respons?vel pela an?lise e representa??o das caracter?sticas da rede: topologia, modelo de cargas e pontos de gera??o distribu?da. O terceiro consiste dos m?todos BFS, FW e OCF para a execu??o do c?lculo do fluxo de corrente e d? a op??o ao usu?rio de escolha do enfoque desejado, podendo apresentar as correntes e tens?es em cada itera??o. A op??o de escolha de diferentes m?todos no ambiente de otimiza??o possibilita o uso do m?todo mais aderentes ?s diferentes topologias de rede, aos tipos modelos de carga, a flexibilidade no uso de restri??es de capacidade dos elementos da rede e a inclus?o de limites de gera??o e limites de tens?o. Com a finalidade de comprovar a ader?ncia e efici?ncia do ambiente foram realizadas simula??es em circuitos trif?sicos equilibrados de distribui??o prim?ria com 11, 33 e 400 barras com modelos de carga constante, topologia radial, anel, com e sem gera??o distribu?da.