Este trabalho aborda um problema ainda não explorado na literatura denominado 3L-FSMVRPTW (three-dimensional loading fleet sizing and mix vehicle routing problem with time windows), que compreende resolver simultaneamente o roteamento e carregamento tridimensional de veículos considerando frota heterogênea e janela de tempo. Foi desenvolvido um algoritmo específico para resolver o problema, denominado 3DC. Neste algoritmo foram introduzidas algumas inovações, entre elas, um novo operador de busca local (k-IntensiveSwap) e uma nova heurística de carregamento de contêiner. O algoritmo foi comparado aos melhores resultados disponíveis na literatura para problemas particulares ao apresentado. Houve bom desempenho no caso do CLP (container loading problem), bom resultado na redução do tamanho de frota no caso do 3L-VRP (threedimensional loading vehicle routing problem) e desempenho superior ao problema mais complexo estudado, o 3L-VRPTW (three-dimensional loading vehicle routing problem with time windows). Finalmente, apresentou-se um conjunto de avaliação, instâncias e soluções, para o problema completo com frota heterogênea e janela de tempo. / This work presents a problem not treated yet on the literature referenced as 3L-FSMVRPTW (three-dimensional loading fleet sizing and mix vehicle routing problem with time windows), which deals simultaneously with vehicle routing and its three-dimensional loading considering heterogeneous fleet and time windows. The algorithm developed for the specific problem is called 3DC. This algorithm introduces a new local search operator called k-IntensiveSwap and a new container loading heuristic. The results are compared with the best-known results from literature for particular problems embeeded on the general problem presented. The quality of solution was good in comparison other methods for CLP (container loading problem), it has good results in terms of reduction fleet sizing in the case of 3L-VRP (three-dimensional loading vehicle routing problem) and as for 3L-VRPTW (threedimensional loading vehicle routing problem with time windows) the performance was very superior. Finally, it is presented a solution set as benchmark for future comparison with the general problem, with heterogeneous fleet.

A utilização de genótipos de soja tolerantes é uma alternativa muito promissora no manejo da ferrugem asiática da soja (FAS), uma vez que a resistência qualitativa mostra-se instável devido à grande variabilidade do patógeno. Este estudo objetivou avaliar o potencial de populações formadas por 64 cruzamentos biparentais (gerações F2, F3 e F4) de um dialelo parcial 8 x 8 para produtividade de grãos (PG) e tolerância à ferrugem. Quinze genitores compreenderam linhagens experimentais desenvolvidas pelo Departamento de Genética/ESALQ/USP e um genitor envolveu uma cultivar comercial. Em 2012/13, dois experimentos foram conduzidos: o primeiro com as populações dos 64 cruzamentos (geração F2) e três testemunhas comuns, enquanto que o segundo envolveu os 16 genitores e as mesmas três testemunhas comuns. Em 2013/14 e 2014/15, a fim de se estimar o efeito ferrugem (EF), ou seja, o nível de tolerância dos genótipos, por meio da diferença entre as médias ajustadas de PG e peso de cem sementes (PCS), foram conduzidos quatro experimentos, sendo dois com as populações dos 64 cruzamentos (gerações F3 e F4) e outros dois com os 16 genitores; cada dupla de experimentos compreendeu dois manejos distintos de doenças com fungicidas. No manejo O&P foram feitas duas aplicações sucessivas de Opera e uma de Priori Xtra, para o controle da ferrugem e outras doenças de fim de ciclo (DFC); no manejo D foram feitas aplicações de Derosal para controle de DFC, exceto a ferrugem. No estádio R5, cinco plantas competitivas de cada parcela foram avaliadas para a severidade, enquanto que no estádio R8, cada parcela foi avaliada para caracteres agronômicos. Os dados obtidos foram analisados (programas computacionais R e Genes). A análise dialélica apresentou significância (p<0,001) dos quadrados médios de CGC e CEC. Para PG, considerando os parâmetros genéticos (heterose, herdabilidade, depressão por endogamia, CGC e CEC), os melhores genitores foram USP 02-16.122 (2), USP 04-17.027 (4), USP 04-17.039 (5), USP 231-4124-04 (6), USP 04-17.011 (10), USP 231-2228-01 (11), USP 231-2224-12 (13) e USP 231-2222-12 (16); tais genitores devem possuir maiores quantidades de genes favoráveis e com complementações genéticas apropriadas, com destaque de USP 04-17.027 (4). Oito (12,5%) cruzamentos sobressaíram com alto desempenho agronômico. A avaliação da severidade foi mais eficiente com o aumento da infecção (NF2). Os genitores USP 04-18.092 (1) e TMG INOX (9) foram resistentes à ferrugem. Com base nas perdas de PG e PCS, os genitores mais tolerantes foram USP 02-16.122 (2), USP 02-16.045 (3), USP 04-17.027 (4), USP 231-2132-04 (12), USP 231-1228-09 (15) e USP 231-2222-12 (16). Ao considerar em conjunto PG e PCS, quinze (23%) cruzamentos revelaram-se tolerantes ou resistentes de acordo com o contraste entre EF e NF2, respectivamente. Concluiu-se que houve forte associação entre CGC e CEC para os destaques reportados; a tolerância estimada pelo PCS e PG apresentaram baixa correlação entre si; assim, a combinação dos dois parâmetros melhorou a eficiência da seleção para tolerância. Ganhos adicionais em PG e tolerância à ferrugem poderão ser obtidos com a seleção entre e dentro de cruzamentos a partir da geração F5. / The use of tolerant soybean genotypes is a very promising alternative for the management of Asian soybean rust (FAS), since qualitative resistance proves to be unstable due to the high variability of the pathogen. This study aimed evaluate the potential of populations composed of 64 two-parental crosses (F2, F3 and F4 generations) of a partial diallel 8 x 8 to seed yield (PG) and tolerance to rust . Fifteen parents understood experimental lines developed by the Department of Genetics / ESALQ / USP and one parent involved a commercial cultivar. In 2012/13, two experiments were conducted: the first with the populations of the 64 crosses (F2) and three common checks, while the second involved 16 parents and the same three common checks. In 2013/14 and 2014/15, it was estimated the rust effect (EF), or the tolerance level of the genotypes using the difference between the adjusted mean of seed yield (PG) and one hundred-seeds weight (PCS), four experiments were conducted, two with populations of 64 crosses (generations F3 and F4) and two with 16 parents; each pair of experiments comprised two different managements of diseases with fungicides. In the management O&P has been made two successive applications of Opera and Priori Xtra in order to control rust and other late season leaf diseases (DFC). In the management D, applications of Derosal were made to control DFC, except rust. In R5 stage, five competitive plants from each plot were evaluated for rust severity, while at the R8 stage, each plot was evaluated for agronomic traits. The data were analyzed through the software R and Genes. The diallel analysis showed significance (p <0.001) of mean squares of GCA (general combining ability) and SCA (specific combining ability). For PG, considering the genetic parameters (heterosis, heritability, inbreeding depression, GCA and SCA), the best parents were USP 02-16.122 (2), USP 04-17.027 (4), USP 04-17.039 (5), USP 231-4124-04 (6), USP 04-17.011 (10), USP 231-2228-01 (11), USP 231-2224-12 (13) and USP 231-2222-12 (16); these parents must have larger amounts of favorable genes and appropriate genetic complementation, particularly USP 04-17.027 (4). Eight (12.5%) crosses stood out with high agronomic performance. The assessment of severity was more efficient with the increase of infection (NF2). The parents USP 04-18.092 (1) and TMG INOX (9) were resistant to FAS. Based on PG and PCS losses, the most tolerant parents were USP 04-18.092 (1), USP 02-16.122 (2), USP 02-16.045 (3), USP 04-17.027 (4), USP 231-3225-11 (7), USP 231-2132-04 (12) e USP 231-1228-09 (15). By considering together PG and PCS, fifteen (23%) crosses revealed tolerance or resistance to rust, according to the estimates of the EF and NF2, respectively. It was found a strong association between GCA and SCA for the reported genotypes. The estimated tolerance by PCS and PG showed low correlation between each other; thus, the combination of the two parameters improved selection efficiency for tolerance. Further gains in PG and rust tolerance may be obtained from the selection among and within crosses in the generation F5.

Submitted by Renata Lopes (renatasil82@gmail.com) on 2016-06-09T11:41:20Z No. of bitstreams: 1 isabelamirandademendonca.pdf: 1432328 bytes, checksum: 68aebf134272c7d3ee8daad48baf21cd (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2016-07-13T13:30:43Z (GMT) No. of bitstreams: 1 isabelamirandademendonca.pdf: 1432328 bytes, checksum: 68aebf134272c7d3ee8daad48baf21cd (MD5) / Made available in DSpace on 2016-07-13T13:30:43Z (GMT). No. of bitstreams: 1 isabelamirandademendonca.pdf: 1432328 bytes, checksum: 68aebf134272c7d3ee8daad48baf21cd (MD5) Previous issue date: 2012-08-02 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Esta dissertação tem por objetivo a realização do planejamento estático da expansão de sistemas de transmissão de energia elétrica via otimização por Enxame de Partículas (EP). A metodologia proposta faz uso de um Algoritmo Heurístico Construtivo (AHC) que tem a finalidade de pré-selecionar as linhas candidatas à expansão mais relevantes, de modo a reduzir o espaço de busca e consequentemente, aumentar a eficiência do processo de otimização bioinspirado. Desta forma, a metodologia proposta pode ser dividida em duas etapas: (i) Obtenção do conjunto reduzido de rotas através do AHC, com o objetivo de identificar os caminhos relevantes à expansão e, assim, diminuir o espaço de busca; (ii) Utilização da otimização por enxame de partículas e das informações heurísticas advindas da primeira etapa, com o objetivo de encontrar o custo mínimo de expansão através de um número reduzidos de partículas. Em ambas as etapas a rede de transmissão é representada pelo modelo linearizado de fluxo de carga, onde as decisões de expansão são incorporadas ao problema através das equações originais do modelo CC. O critério de seleção da expansão é realizado através de heurística, de modo a evitar a explosão combinatória referente às alternativas de investimento. A metodologia proposta é aplicada ao sistema Garver e a dois sistemas reais equivalentes a região Sul e Sudeste do Brasil. / This dissertation aims at the realization of the static transmission network expansion planning (STNEP) of electric power systems using the Particle Swarm Optimization (PSO) method. The proposed methodology uses a Constructive Heuristic Algorithm (CHA) in order to pre-select the most relevant candidates lines for expansion, so as to reduce the search space and thereby increasing efficiency of the bioinspired optimization process. Thus, the proposed methodology can be divided into two steps: (i) Obtaining the reduced set of routes through the CHA, in order to identify relevant routes for expansion and thus reduce the search space; (ii) Using the Particle Swarm Optimization and heuristic information provided by the first stage, in order to find the minimum expansion cost using a reduced number of particles. In both stages the transmission network is represented by a linearized load flow model, where the expansion decisions are incorporated into the optimization problem using the original equations of the model DC. The selection of expansion criterion is done through heuristic in order to avoid combinatorial explosion associated with expansion alternatives. The proposed methodology is applied to the Garver system and two real equivalent South and Southeastern Brazilian systems.

Orientadores: Takaaki Ohishi, Anibal Tavares de Azevedo / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação / Made available in DSpace on 2018-08-25T04:07:17Z (GMT). No. of bitstreams: 1 Milanez_AnaPaula_D.pdf: 14663161 bytes, checksum: b19e5018faa8a4e7653560273b6f88fc (MD5) Previous issue date: 2014 / Resumo: A cadeia de exportação da soja tem alta participação no desempenho econômico do país. No entanto, as principais áreas produtoras são expostas a diversos problemas logísticos decorrentes da falta de planejamento e de investimentos em infraestrutura. Como resultado, os produtores são onerados pelos custos diminuindo seu capital disponível para investimentos, o que compromete as safras futuras e a projeção econômica do país. Diante desta realidade o governo brasileiro tem tomado medidas e realizando investimentos para sanar estes problemas. Os investimentos realizados em infraestrutura devem ser planejados para o longo prazo. Deste modo, este trabalho propõe a análise de um modelo capacitado de design de rede de hubs e, posteriormente, com base no mesmo, desenvolve três de modelos matemáticos que descrevem a cadeia exportação da soja e suas especificidades a fim de, criar uma ferramenta de análise para definir a localização de facilidades, armazenadoras/ consolidadoras/ redirecionadoras de fluxo, as rotas a serem utilizadas e a utilização dos portos para otimizar esta cadeia. Para aplicar os modelos, o Estado do Mato Grosso foi selecionado como foco do estudo., e com base no qual, foi realizado um extenso levantamento de dados da soja. Considerando que o Estado do Mato Grosso é dividido em 22 microrregiões foram esti-madas a quantidade de soja produzida, identificada a quantidade de soja exportada e a capacidade estática de cada microrregião. Também foram identificados os principais países importadores da soja brasileira e os principais portos de exportação, além das quantidades de soja exportada para cada país, a utilização atual dos portos e identificação das rotas terrestres e marítimas utilizadas no transporte / Abstract: The soybean exporter chain has high participation in the economic performance of the country. However, the main producing areas are exposed to several logistical problems arising from lack of planning and investment in infrastructure. As a result, producers are burdened by the costs and have an available capital decrease to future investments, which reduce futures crops and future economic potential of the country. Faced with this reality, the Brazilian government has taken measures and investing to solve these problems. Investments in infrastructure should be planned for the long term. Thus, this paper proposes the analysis of a capacitated model design of network hubs and then, based on it, develops three mathematical models that describe the soybeans exporter chain, in order to create an analysis tool to define the location of facilities, as storage / switching / transshipment facilities, define routes and ports that should be utilized to optimize the use of the chain. In order to apply the model, the state of Mato Grosso was selected as the focus of this study and, based on which, an extensive survey data of soybeans was realized. Whereas that the State of Mato Grosso is divided into 22 micro regions it was estimated their soybeans production, identified the amount of soybeans exported and the static capacity to each one. The main importer¿s countries of Brazilian soybeans and the major export ports it was also identified, in addition, the amounts of soybeans exported by each country and ports, and identification of routes and sea routes used to transport / Doutorado / Automação / Doutora em Engenharia Elétrica

Orientador: Flávio Keidi Miyazawa / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-25T12:28:53Z (GMT). No. of bitstreams: 1 Lopes_MauroCardoso_M.pdf: 3797752 bytes, checksum: c82bee131ad99d747e42150908135190 (MD5) Previous issue date: 2014 / Resumo: Investigamos uma variante do problema de localização e roteamento com relação de muitos-para-muitos concentradores que consiste em particionar o conjunto de vértices de um grafo em ciclos contendo exatamente um concentrador cada e determinar um ciclo adicional interligando todos os concentradores. Qualquer vértice do grafo pode ser um concentrador; faz parte do problema determinar quais vértices devem ser concentradores. Esse problema tem aplicações práticas relevantes em áreas como transporte urbano e redes de computadores. Desenvolvemos uma heurística baseada em busca local com operações de inserção, remoção e troca de vértices. Soluções iniciais são geradas de maneira aleatória, e suas vizinhanças são exploradas a fim de obter melhores soluções. Além disso, elaboramos um algoritmo exato com estrutura de branch-and-cut para a formulação em Programação Linear Inteira proposta. Restrições de capacidade e eliminação de caminhos são adicionadas como planos de corte, com algoritmos de separação baseados em árvores de corte mínimo e nas componentes conexas de um grafo suporte. Diversos experimentos computacionais mostram a capacidade de resolução do algoritmo exato para instâncias pequenas e da heurística para instâncias pequenas e médias. São comparados também os desempenhos para outras variantes do problema / Abstract: We investigate a variant of the many-to-many hub location-routing problem which consists in partitioning the set of vertices of a graph into cycles containing exactly one hub each and determining an extra cycle interconnecting all hubs. Any vertex of the graph can be a hub; it is part of the problem to determine which vertices should be hubs. This problem has relevant practical applications in areas such as urban transportation and computer networks. A local search based heuristic that considers add/remove and swap operations is developed. Initial solutions can be generated at random, and their neighborhoods are explored in order to get better solutions. Also a branch-and-cut approach that solves an integer formulation is investigated. Capacity and path elimination constraints are added in a cutting plane way, so the separation algorithms are based on the computation of min-cut trees and in the connected components of a support graph. Many computational experiments over several instances adapted from literature show the problem-solving capability of the exact algorithm for small instances and of the heuristic for small to medium-sized instances. We also compare the performance of other variants of the problem / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

Orientador: Fernando José Von Zuben / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação / Made available in DSpace on 2018-08-25T22:55:48Z (GMT). No. of bitstreams: 1 Raimundo_MarcosMedeiros_M.pdf: 764820 bytes, checksum: 80ad4c20c482ad09b06c3e07d1b2c240 (MD5) Previous issue date: 2014 / Resumo: O gerenciamento de cadeias de suprimento no mundo corporativo é de grande relevância prática e uma de suas versões é conhecida como problema de roteamento e estoque. Este trabalho propõe uma formulação linear-inteira genérica e flexível para este problema de otimização, assim como uma metodologia de solução. Nesta nova formulação proposta, algumas peculiaridades da rede de suprimentos podem ser especificadas como parâmetros de entrada, permitindo assim que o usuário seja capaz de realizar modificações na estrutura, na hierarquia e no elenco de restrições da cadeia de suprimentos, sem precisar refazer a formulação matemática associada. Com isso, é possível resolver uma grande diversidade de configurações do problema, sem a necessidade de adaptações junto à metodologia de solução. A natureza genérica e flexível da formulação linear-inteira se deve às seguintes propriedades, todas elas passíveis de serem definidas como parâmetros de entrada: (1) Todo nó da rede pode produzir ou consumir produtos; (2) Todo nó da rede pode enviar e receber produtos; (3) Decorrente das propriedades (1) e (2), a hierarquia de entrega fica generalizada, com o produto podendo passar por vários nós antes de ser consumido; (4) Restrições presentes na formulação garantem consistência, por exemplo, entre quantidade de produto entregue pelos fornecedores e recebida pelos consumidores; (5) Restrições presentes na formulação estão associadas a especificações que podem ser ativadas, como intervalo de tempo entre entregas. Os resultados experimentais contemplam soluções para múltiplas configurações do problema, todas representáveis pela formulação proposta e, portanto, todas resolvidas pela mesma metodologia de solução. Essas múltiplas configurações trabalhadas nos experimentos evidenciam os benefícios do emprego de uma formulação estendida para o problema de roteamento e estoque. Além disso, visando comparação com propostas alternativas disponíveis na literatura, tomou-se uma configuração específica e bem-estabelecida do problema, para a qual existe uma formulação própria e uma metodologia de solução dedicada. Neste experimento comparativo, chegou-se às mesmas soluções e, em algumas parametrizações, até a soluções de melhor qualidade / Abstract: Managing supply chains in the corporate world is of great practical relevance and one of its versions is named inventory routing problem. This work proposes a more generic and flexible linear-integer formulation for this optimization problem, together with a solution methodology. In the novel formulation proposed here, some peculiarities of the supply network can be specified as input parameters, thus allowing the user to make modifications to the structure, the hierarchy and the set of constraints in the supply chain, without having to rebuild the associated mathematical formulation. Therefore, it is possible to solve a wide variety of configurations of the problem without the need for adjustments in the solution methodology. The generic and flexible nature of the linear-integer formulation is due to the following properties, all of them being definable as input parameters: (1) Every node of the network can produce or consume products; (2) Every node of the network can send and receive products; (3) Due to properties (1) and (2), the hierarchy of delivery is generalized, with the product being able to pass through several nodes before being consumed; (4) Some restrictions of the formulation ensure consistency, for example, between the amount of product delivered by the suppliers and received by the consumers; (5) Some restrictions of the formulation are associated with specifications that can be activated, as the time interval between deliveries. The experimental results include solutions for multiple configurations of the problem, all representable by the proposed formulation and, as a consequence, all able to be solved by the same solution methodology. Those multiple configurations considered in the experiments highlight the benefits of employing an extended formulation for the inventory routing problem. Aiming at comparing to alternative proposals available in the literature, it was considered a specific and well-established configuration of the problem, for which there are a proper formulation and a dedicated solution methodology. In this comparative experiment, we came to the same solutions and, in some parameterizations, even better solutions / Mestrado / Engenharia de Computação / Mestre em Engenharia Elétrica

Orientador: José Plínio de Oliveira Santos / 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-22T15:43:28Z (GMT). No. of bitstreams: 1 Rodrigues_ChristianeBuffo_M.pdf: 948322 bytes, checksum: be5636b0d15a131df52736cd4f4782d0 (MD5) Previous issue date: 2013 / Resumo: Este trabalho trata da aplicação do Método Simbólico na resolução de problemas de Combinatória. A vantagem desta técnica é o cálculo direto de uma expressão fechada para a Função Geradora F(z) do problema escrito como uma Série de Potências. Consequentemente garantimos a facilidade na enumeração da sequência que queremos a partir do coeficiente de zn de F(z). O desenvolvimento de nosso estudo foi feito aplicando-se o método a dois tipos de Classes: Rotuladas e não Rotuladas, apontando as diferenças básicas entre elas através de exemplos e resultados teóricos. Ao final, concluímos que a enumeração independe do tipo de modelagem feita para o problema / Abstract: This work deals with the application of the Symbolic Method in the solutions of combinatorial problems. The advantage of this technique is the direct calculus for the exact expression of the Generating Function F(z) of the problem, written as a Power Series. Consequently, we ensure the enumeration of the desired sequence, from the coefficient of zn of F(z). Our study was developed by applying the method in two types of Classes: Labeled and unlabelled, pointing the basic differences between them through examples and theoretical results. Finally, we concluded that the enumeration does not depend of the type of the model chosen for the problem / Mestrado / Matematica Aplicada / Mestra em Matemática Aplicada

Orientador: Eduardo Candido Xavier / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-23T15:26:56Z (GMT). No. of bitstreams: 1 Silveira_Tiago_M.pdf: 2498154 bytes, checksum: 4bbdff83ad5a399e1c436ffdbeb89a92 (MD5) Previous issue date: 2013 / Resumo: O resumo poderá ser visualizado no texto completo da tese digital / Abstract: The complete abstract is available with the full electronic document / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

Orientador: Cid Carvalho de Souza / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-19T18:36:28Z (GMT). No. of bitstreams: 1 Marini_BrunoConti_M.pdf: 1252984 bytes, checksum: 40439ec279501ea9ca594d950e42a229 (MD5) Previous issue date: 2011 / Resumo: Uma das formas mais econômicas e, em relação ao meio ambiente, mais seguras de se transportar combustíveis é bombeá-los através de redes de dutos. Contudo, as diversas restrições operacionais que precisam ser consideradas fazem com que o planejamento das atividades de bombeamento se transforme em um grande desafio. Dentre os diversos cenários em que o problema se apresenta, investiga-se nessa dissertação o caso de uma rede composta de um único duto onde diversos produtos são bombeados unidirecionalmente. Trata-se de uma situação real enfrentada pela Petrobras no gerenciamento da rede OSBRA. Na literatura existem propostas de vários modelos matemáticos para tratar esta instância particular do problema. Contudo, no melhor do nosso conhecimento, não existem comparações efetivas entre estes modelos e os algoritmos usados para computá-los. Nessa dissertação faz-se uma comparação aprofundada entre três desses modelos, a qual se baseia em uma metodologia sugerida pelos técnicos da Petrobras. Neste trabalho são destacadas não só as dificuldades envolvendo a implementação dos modelos, bem como as deficiências encontradas na aplicação da metodologia de comparação usada pela empresa. Propostas são feitas nessa dissertação no intuito de superar estes obstáculos / Abstract: One of the most economical and, with respect to the environment, safest ways to transport fuel is to pump them through pipeline networks. However, the several operational constraints that have to be considered turn the planning of these activities into a major challenge. Among the several cenarios in which the problem arises, in this dissertation we investigate the case of a network composed of a single pipeline through which several products are pumped unidirectionally. This is a real situation faced by Petrobras in the management of the OSBRA network. In the literature there are proposals of various mathematical models to tackle this particular instance of the problem. However, to the best of our knowledge, there are no effective comparisons of these models and of the algorithms used to compute them. In this dissertation an in-depth comparison is made between three of these models, which is based on a methodology suggested by the technical staff of Petrobras. In this work we highlight not only the difficulties involving the implementation of the models but also the deficiencies encountered in the application of the comparison methodology used by the company. Proposals are made in this dissertation in an attempt to overcome these obstacles / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

Orientador: Cid Carvalho de Souza / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-20T15:20:18Z (GMT). No. of bitstreams: 1 Oliveira_Lucasde_M.pdf: 1308997 bytes, checksum: cc147cd3d3c9f50c61a48d83579b6c49 (MD5) Previous issue date: 2012 / Resumo: Esta dissertação tem como foco a investigação experimental de algoritmos exatos, aproximativos e heurísticos aplicados na resolução do chamado problema do corredor de comprimento mínimo (PCCM). No PCCM recebemos um polígono retilinear P e um conjunto de polígonos retilineares menores formando uma subdivisão S planar conexa de P. Uma solução para este problema, também chamada de corredor, é formada por um conjunto conexo de arestas de S, e tal que cada face interna em S possui pelo menos um ponto em sua borda que pertence a alguma aresta deste conjunto. O objetivo então é encontrar um corredor tal que a soma total dos comprimentos das arestas seja a menor possível. Trata-se de um problema NP-difícil com aplicações em áreas diversas, tais como telecomunicações, engenharia civil e projeto de circuitos VLSI. O PCCM pode ser reduzido polinomialmente a um problema em grafos denominado problema da árvore de Steiner com grupos (PASG). Considerando esta transformação, estudamos e implementamos dois métodos aproximativos, um método exato de branch-and-cut, e um método heurístico baseado na metaheurística GRASP combinada com um evolutionary path relinking (GRASP+EPR). Além disso, propomos três heurísticas de busca local que visam melhorar a qualidade de soluções do PASG. Instâncias do PCCM foram geradas aleatoriamente, nas quais aplicamos os métodos implementados. Analisamos os resultados, e apresentamos as situações onde é interessante utilizar cada método. Verificamos que o método branch-and-cut foi capaz de encontrar soluções ótimas para instâncias que julgamos ser de grande porte em tempos computacionalmente aceitáveis. O melhor algoritmo aproximativo obteve corredores que na média têm comprimento 17% maior que o comprimento ótimo. Se combinarmos este algoritmo com as heurísticas de melhoria propostas este percentual cai para a média de 3,5%. Finalmente, o GRASP+EPR consome mais tempo que este algoritmo aproximativo, entretanto, o comprimento dos corredores obtidos por ele é em média 0,9% maior que o comprimento ótimo / Abstract: This dissertation focuses on the experimental investigation of exact, approximation and heuristic algorithms applied to solve the so-called minimum length corridor problem (MLCP). In the MLCP we receive a rectilinear polygon P and a set of minor rectilinear polygons forming a connected planar subdivision S of P. A solution for this problem, also called corridor, is formed by a set of connected edges of S, and such that each inner face of S has at least one point on its your border which belongs to an edge in this set. The goal is to find a corridor such that the sum of lengths of the edges is as small as possible. This is an NP-hard problem with applications in several areas such as telecommunications, civil engineering and design of VLSI circuits. The MLCP can be polynomially reduced to a graph problem known as group Steiner tree problem (GSTP). Based on this transformation, we studied and implemented two approximation methods, an exact branch-and-cut method, and a heuristic method based on the metaheuristic GRASP combined with an evolutionary path relinking (GRASP+EPR). Furthermore, we propose three local search heuristics to improve the quality of GSTP solutions. MLCP instances were randomly generated, in which we apply the methods implemented. We analyzed the results, and present situations where it is interesting to use each method. We found that the branch-and-cut has been able to find optimal solutions for instances that we consider to be large in acceptable computational times. The best approximation algorithm obtained corridors having average length 17% higher than the optimum length. If we combine this algorithm with the improvement heuristics proposed this percentage drops to an average of 3.5%. Finally, the GRASP+EPR spent more time than this approximation algorithm, however, the length of the corridors obtained by the method is, on average, 0.9% higher than the optimum length / Mestrado / Ciência da Computação / Mestre em Ciência da Computação