Orientadores: Antonio Carlos Moretti, Margarida Pinheiro Mello / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-11T15:01:14Z (GMT). No. of bitstreams: 1 Oliveira_WashingtonAlvesde_M.pdf: 1986709 bytes, checksum: fa0dfb8c33d0fe5dd13eeced37d3b4ee (MD5) Previous issue date: 2008 / Resumo: Nesta dissertação estudamos um aspecto do problema de planejamento do pratulhamento urbano preventivo: a construção de rotas a serem percorridas pelos veículos da força policial no patrulhamento preventivo. De modo geral, a elaboração de rotas visa garantir uma boa visibilidade para o patrulhamento, de modo a proporcionar sensação de segurança para a população, permitir o atendimento rápido em caso de ocorrências, fazer vigilância de determinados estabelecimentos (hospitais, escolas, etc.). O planejamento deve levar em conta os recursos disponíveis, normalmente o número de veículos, visar agilidade e uma distribuição equânime de trabalho. O produto final é um módulo computacional capaz de automaticamente gerar rotas atendendo um dado conjunto de especificações, que possa ser utilizado pelos departamentos responsáveis pela segurança pública. Para tanto, fizemos uma adaptação do modelo para o Problema de Rotas de Cobertura multi-veículo (m-PRC). Este modelo consiste em um programa linear inteiro cujo tamanho e complexidade torna inviável a aplicação de métodos exatos para sua solução. Soluções subótimas são obtidas aplicando-se as heurísticas propostas por M. Hachicha et. al. (2000), e outras contribuídas por nós. Neste modelo alguns pontos geográficos devem ser obrigatoriamente visitados, enquanto outros devem ficar suficientemente próximos das rotas traçadas. Procuramos gerar rotas de tamanho menor possível, para que cada circuito seja percorrido um maior número de vezes durante o turno de serviço. As heurísticas foram implementadas em MATLAB e sua validação, assim como a do modelo, foi feita através da resolução de problemas gerados aleatoriamente. Além disso, obtivemos dados relativos à cidade de Vinhedo, S.P., e formulamos rotas para patrulhamento preventivo pela Guarda Civil Municipal. Os resultados são promissores, e a análise das soluções obtidas será utilizada para aprimorar o modelo / Abstract: In this text we study one aspect of the urban community policing: routine patrol route planning. We seek routes that guarantee visibility, as this has a sizable impact on the community's perceived safety and allows for quick emergency responses, and that provide surveillance of public buildings (e.g., hospitals, schools). The planning is restricted to the availability of vehides and strives to achieve balanced and short routes. We construct a computerized module, capable of automatic generation of routes for a given vehide fieet and lists of sites that must be visited. Such a module could be of interest to Police, Public Safety Departments, Municipal Service Agencies. The module implements an adaptation of the model for the multi-vehicle covering tour problem. It constitutes an integer program whose size and complexity makes the use of an exact method impractical. Suboptimal solutions are obtained with several heuristics, some by M. Hachicha et. al. (2000), and others of our own devising. In this model a set of locations must be visited, whereas another subset must be close enough to the planned routes. The heuristics aim to construct short routes so that one could make several rounds during a work shift. The implementation was done in MATLAB and its validation, as well as the model's, was based on the solution of randomly generated problems. Furthermore, data from the city of Vinhedo, SP, was obtained and tentative routes planned for the patroling of a choice of locations by the Municipal Guard. Their appraisal by the personnel in charge of the route planning will, without a doubt, help us improve the model and heuristics / Mestrado / Pesquisa Operacional / Mestre em Matemática Aplicada

Made available in DSpace on 2014-07-29T14:57:46Z (GMT). No. of bitstreams: 1 dissertacao_jean.pdf: 321149 bytes, checksum: 11c9f94be02284e8412d026b60b596d0 (MD5) Previous issue date: 2010-08-16 / The Course Scheduling is a hard resolution problem, found in most of the learning institutions. Just like the others timetabling problems, the Course Scheduling have a strong associative characteristic, that means that its resolution is made of associations between events and resources. In the educational case, the lectures are events, while the teachers workload are resources. Techniques and methods have being used on the solution of these kind of problems, however is small the number of universities using software based solutions. This work is a starting point to software based solutions applied to the Federal University of Goiás. / O Agendamento Semanal de Aulas é um problema de difícil resolução enfrentado em grande maioria das instituições de ensino. Assim como os demais problemas de timetabling, possui como característica principal a sua natureza associativa, ou seja, sua resolução envolve a associação entre uma certa quantidade de recursos e eventos que utilizarão tais recursos. Especificamente em relação ao problema em questão, as aulas a serem ministradas podem ser caracterizadas como eventos, enquanto que a carga horária dos professores envolvidos podem ser vistas como recursos disponíveis (Programação de Horários de Aulas). Técnicas e métodos de grande relevância na ciência da computação estão relacionados na pesquisa e na solução destes tipos de problemas, contudo, a utilização de tais tecnologias no cotidiano de escolas e universidades ainda é pequena. Neste contexto, propõe-se uma abordagem para a resolução de Problemas de Programação de Horários, incluindo o Problema de Alocação de Professores a Disciplinas, e utiliza-se o Instituto de Informática da Universidade Federal de Goiás como um estudo de caso para tal.

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.

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: 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