The two-dimensional irregular cutting and packing problems (aka nesting problems) have been studied over the past six decades and consist in cutting (packing) convex and non-convex small pieces from (in) large boards without overlapping. There are several variants of this problem that are defined according to the board shapes and the objective of each problem. There are a number of heuristics proposed in the literature to solve irregular cutting and packing problems, but only few mixed-integer programming models. Specifically, these models were developed for the irregular strip packing problem, that consists in packing pieces into a single board with fixed width and length to be minimized. For the other problem variants, there is no exact methods presented in the literature. The main difficulty in solving irregular cutting and packing problems is how to handle with the geometric constraints. These constraints depend on the type of placement of the pieces on the board that can be continuous or discrete. In this thesis, we present two mixed-integer programming models for the irregular strip packing problem in which the pieces can be continuously placed on the board. These models do not demand complex structures to be built. We also present a new dot data structure to store the information on the placement of the pieces and overlapping positions bringing flexibility and efficiency to discrete approaches. Using this structure, a matheuristic is proposed, combining the advantages of the models with discrete and continuous placement positions for the pieces on the board. Furthermore, constraint programming models for several variants of irregular cutting and packing problems are exploited. For some variants, these models are the first modelling representation. A new global constraint is developed to eliminate the overlap among pieces. Computational experiments were conducted to evaluate the developed approaches. / Os problemas de corte e empacotamento de peças irregulares bidimensionais vêm sendo estudados há décadas e consistem em cortar (empacotar) peças menores, convexas e não convexas, a partir de (em) placas maiores de forma a não se sobreporem. Existem diversas variantes deste problema, definidas de acordo com o formato da placa e objetivo de cada problema. Na literatura, muitas heurísticas foram propostas para a resolução dos problemas de corte e empacotamento de peças irregulares, porém, poucos modelos de programação inteira mista podem ser encontrados. Especificamente, estes modelos foram desenvolvidos para o problema de empacotamento em faixa, que consiste em empacotar as peças em uma placa de largura fixa e comprimento a ser minimizado. Para as demais variantes do problema, não existem métodos exatos propostos na literatura. A principal dificuldade na resolução dos problemas de corte e empacotamento de peças irregulares está na manipulação das restrições geométricas. Estas restrições dependem do tipo de posicionamento das peças na placa, que pode ser discreto ou contínuo. Nesta tese, apresentamos dois modelos de programação inteira mista para o problema de empacotamento de peças em faixa, no qual cada peça pode ser alocada de forma contínua na placa. Estes modelos não demandam estruturas complexas para serem construídos. Também apresentamos uma nova estrutura de dados para armazenar informações sobre o posicionamento das peças e as posições de sobreposição, trazendo flexibilidade e eficiência para abordagens discretas. Utilizando esta estrutura, uma matheuristica foi proposta, combinando as vantagens dos modelos com alocação discreta e contínua das peças na placa. Além disso, modelos de programação por restrições para diversas variantes dos problemas de corte e empacotamento de peças irregulares foram explorados. Para algumas variantes, estes modelos são a primeira representação via modelagem. Uma nova restrição global foi desenvolvida para eliminar a sobreposição entre as peças. Experimentos computacionais foram realizados para avaliar as abordagens propostas.

Orientadores: Arnaldo Vieira Moura, Cid Carvalho de Souza / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-16T11:05:11Z (GMT). No. of bitstreams: 1 Lopes_TonyMinoruTamura_M.pdf: 1334472 bytes, checksum: c53fc4d807764c31b73609102203a039 (MD5) Previous issue date: 2010 / Resumo: Um conjunto de órgãos distribuidores de derivados de petróleo, incluindo refinarias e terminais, possuem demandas locais e produções de diferentes produtos ao longo de um dado horizonte de tempo. No entanto, pode não haver estoque local de algum produto para satisfazer a demanda correspondente, ou pode não haver espaço nos tanques para estocar uma produção local. Isso leva à necessidade de transporte dos derivados de petróleo entre os órgãos. Dentre os diversos modais, a rede de oleodutos é a melhor opção considerando-se custos e riscos ambientais. Em vista de sua grande complexidade operacional, um uso adequado da rede necessita de um planejamento tático composto mensalmente, e de um agendamento detalhado das operações, cobrindo poucos dias, e que deve ser atualizado diariamente. Tanto o planejamento mensal quanto o agendamento diário devem respeitar um grande conjunto de restrições, envolvendo a capacidade dos tanques, taxas de vazões nos oleodutos, níveis de estoques, dentre outras. Esta dissertação apresenta uma formalização do problema, desenvolvida em dois estágios, representado o planejamento mensal e o agendamento diário. O problema de planejamento recebeu um tratamento inicial heurístico seguido de uma modelagem por fluxo em redes, enquanto o agendamento diário utilizou programação por restrições. Os modelos foram testados sobre dados fornecidos pela companhia brasileira de petróleo Petrobras. Essas instâncias possuem uma das topologias mais complexas quando comparadas a outras redes encontrada na literatura aberta. Os resultados demonstram melhorias significativas sobre a resolução manual desses problemas / Abstract: A set of oil derivative distribution depots, including refineries and terminals, have local demands for and productions of different products in a given time horizon. However, there may be not enough local stock of some product to satisfy the corresponding demand, or there may not be enough tank capacity to stock the local production. This brings the need for transportation of oil derivatives between the depots. Among many transportation modes, the network of pipelines is one of the best options when considerying cost and environment risks. In order to adequately operate the pipeline network, a two phase planning strategy is developed. First, a tactical pumping plan is composed monthly and, secondly, a more detailed operational schedule, spanning a few days, is updated daily. Both the tactical and tghe operational plannings must satisfy a large set of operation constraints, involving many restrictions, such as tanks capacities, pipeline flow rates, and stock levels. This dissertation provides a formalization for the problem along with a decomposition of it in two stages, representing the monthly planning and operational schedule. The tactical stage is solved by applying a heuristic and then with a network flow model, while the operational schedule uses constraing programming. Our model treats the oil pipeline network that is operated by the Brazilian oil company Petrobras. This is one of the most complex and large topologies when compared to other networks treated in the open literature. The model was tested with real-world instances and showed significant improvements over human planning / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

The two-dimensional irregular cutting and packing problems (aka nesting problems) have been studied over the past six decades and consist in cutting (packing) convex and non-convex small pieces from (in) large boards without overlapping. There are several variants of this problem that are defined according to the board shapes and the objective of each problem. There are a number of heuristics proposed in the literature to solve irregular cutting and packing problems, but only few mixed-integer programming models. Specifically, these models were developed for the irregular strip packing problem, that consists in packing pieces into a single board with fixed width and length to be minimized. For the other problem variants, there is no exact methods presented in the literature. The main difficulty in solving irregular cutting and packing problems is how to handle with the geometric constraints. These constraints depend on the type of placement of the pieces on the board that can be continuous or discrete. In this thesis, we present two mixed-integer programming models for the irregular strip packing problem in which the pieces can be continuously placed on the board. These models do not demand complex structures to be built. We also present a new dot data structure to store the information on the placement of the pieces and overlapping positions bringing flexibility and efficiency to discrete approaches. Using this structure, a matheuristic is proposed, combining the advantages of the models with discrete and continuous placement positions for the pieces on the board. Furthermore, constraint programming models for several variants of irregular cutting and packing problems are exploited. For some variants, these models are the first modelling representation. A new global constraint is developed to eliminate the overlap among pieces. Computational experiments were conducted to evaluate the developed approaches. / Os problemas de corte e empacotamento de peças irregulares bidimensionais vêm sendo estudados há décadas e consistem em cortar (empacotar) peças menores, convexas e não convexas, a partir de (em) placas maiores de forma a não se sobreporem. Existem diversas variantes deste problema, definidas de acordo com o formato da placa e objetivo de cada problema. Na literatura, muitas heurísticas foram propostas para a resolução dos problemas de corte e empacotamento de peças irregulares, porém, poucos modelos de programação inteira mista podem ser encontrados. Especificamente, estes modelos foram desenvolvidos para o problema de empacotamento em faixa, que consiste em empacotar as peças em uma placa de largura fixa e comprimento a ser minimizado. Para as demais variantes do problema, não existem métodos exatos propostos na literatura. A principal dificuldade na resolução dos problemas de corte e empacotamento de peças irregulares está na manipulação das restrições geométricas. Estas restrições dependem do tipo de posicionamento das peças na placa, que pode ser discreto ou contínuo. Nesta tese, apresentamos dois modelos de programação inteira mista para o problema de empacotamento de peças em faixa, no qual cada peça pode ser alocada de forma contínua na placa. Estes modelos não demandam estruturas complexas para serem construídos. Também apresentamos uma nova estrutura de dados para armazenar informações sobre o posicionamento das peças e as posições de sobreposição, trazendo flexibilidade e eficiência para abordagens discretas. Utilizando esta estrutura, uma matheuristica foi proposta, combinando as vantagens dos modelos com alocação discreta e contínua das peças na placa. Além disso, modelos de programação por restrições para diversas variantes dos problemas de corte e empacotamento de peças irregulares foram explorados. Para algumas variantes, estes modelos são a primeira representação via modelagem. Uma nova restrição global foi desenvolvida para eliminar a sobreposição entre as peças. Experimentos computacionais foram realizados para avaliar as abordagens propostas.

O objetivo dessa dissertação é apresentar um problema de otimização do uso de recursos críticos no desenvolvimento de poços de petróleo marítimos e a técnica empregada para a abordagem proposta ao problema. A revisão da técnica de Programação por Restrições é feita analisando aspectos relevantes de modelagem, propagação, busca e paradigmas de programação. A especialização da técnica para problemas de escalonamento, o Escalonamento Baseado em Restrições, é descrita com ênfase nos paradigmas descritivos e nos mecanismos de propagação de restrições. Como subsídio ao uso da técnica em outros problemas, a linguagem comercial de modelagem OPL é apresentada no Apêndice. O objetivo da abordagem ao problema é obter um escalonador para maximizar a produção de óleo obtida no curto prazo. O escalonador proposto baseia-se na declaração de um modelo empregando variáveis de intervalo. Um algoritmo e um modelo de Programação Linear Inteira abordando relaxações do problema são apresentados para que se obtenha um limitante superior ao valor de produção ótimo. Para o cenário real no qual a análise experimental foi feita, foram obtidas soluções a menos de 16% do ótimo após uma hora de execução; e os testes em instâncias de tamanhos variados evidenciaram a robustez do escalonador. Direções para trabalhos futuros são apresentadas ponderando os resultados obtidos. / The aim of this work is to present a problem of optimizing the use of critical resources to develop offshore oil wells and the technique used to approach the problem. The review of the Constraint Programming technique is made by analyzing relevant aspects of modeling, propagation, search and programming paradigms. The specialization of the technique to scheduling problems, known as Constraint-Based Scheduling, is described with emphasis on descriptive paradigms and constraint propagation mechanisms. In order to support the use of the technique to tackle other problems, the commercial modeling language OPL is presented in the appendix. The aim of the approach to the problem is to obtain a scheduler that maximizes the short-term production of oil. The scheduler presented relies on the description of a model using interval variables. An algorithm and an Integer Linear Programming model approaching relaxations of the problem are presented in order to obtain an upper bound for the optimal production value. For the real scenario upon which the experimental analysis was done, there were found solutions within 16% of the optimal after one hour of execution; and the tests on instances of varied sizes gave evidence of the robustness of the scheduler. Directions for future work are presented based on the results achieved.

A área do petróleo é uma das que mais podem se beneficiar da melhoria de eficiência da gestão da cadeia de suprimentos. Entretanto, o comportamento dinâmico de tais cadeias é muito complexo para ser modelado de forma analítica. Por outro lado, estas cadeias mostram várias características intrínsecas em comum com sistemas multiagentes, que oferecem a flexibilidade necessária para modelar as complexidades e a dinâmica das cadeias de suprimentos reais sem a necessidade de premissas muito simplificadoras. Como o problema de gerenciamento da cadeia de suprimentos apresenta uma estrutura recursiva, torna-se ainda mais conveniente usar um modelo baseado em agentes holônicos, que mostram uma estrutura do tipo fractal. Além disso, o tipo de relacionamento entre as entidades da cadeia e a necessidade de uma otimização global sugerem modelar suas interações na forma de restrições. Por esta razão, esta tese propõe um modelo distribuído de otimização através da definição de um novo problema denominado Problema de Satisfação de Restrições Holônico com Otimização (HCOP), que é baseado nos conceitos do Problema de Satisfação de Restrições Distribuído com Otimização (DCOP) e agentes holônicos. Além disso, foi desenvolvido um meta-algoritmo baseado no algoritmo DTREE para solucionar este tipo de problema, onde vários algoritmos disponíveis de otimização centralizados podem ser embutidos e integrados de tal forma a obter a configuração mais adequada para cada caso. Assim, uma típica cadeia de suprimentos da indústria do petróleo foi modelada como um HCOP, e foi desenvolvido um protótipo que implementa o meta-algoritmo proposto em um ambiente que integra sistemas de otimização de produção e logística, que são representativos em relação a situações reais. Finalmente foram realizados experimentos sobre um estudo de caso da empresa PETROBRAS, que permitiram a verificação da viabilidade deste modelo e a comprovação de suas vantagens em relação às abordagens convencionais. / The oil area is one of those that may most benefit from the improved efficiency of supply chain management. However, the dynamic behavior of such chains is too complex to be modeled analytically. Moreover, these chains show several intrinsic characteristics in common with multiagent systems, which offer the required flexibility to model the complexities and dynamics of real supply chains without rather simplifying assumptions. As the problem of managing the supply chain has a recursive structure, it becomes more convenient to use a model based on holonic agents, which show a fractal-type structure. Furthermore, the type of relationship between entities in the chain and the need for global optimization suggest to model their interactions in the form of constraints. For this reason, this thesis proposes an optimization distributed model by defining a new problem called Holonic Constraint Optimization Problem (HCOP), which is based on concepts from Distributed Constraint Satisfaction Optimization Problem (DCOP) and holonic agents. In addition we developed a meta-algorithm based on DTREE algorithm for solving this type of problem, where several algorithms available for centralized optimization algorithms can be embedded and integrated so as to obtain the most suitable configuration for each case. Thus, a typical supply chain of the petroleum industry was modeled as a HCOP, and we developed a prototype that implements the meta-algorithm in an environment that integrates the optimization systems for production and logistics, which are representative in relation to actual situations. Finally experiments were performed on a case study of the company PETROBRAS, which allowed the verification of the feasibility of this model and the proof of their advantages over conventional approaches.

A área do petróleo é uma das que mais podem se beneficiar da melhoria de eficiência da gestão da cadeia de suprimentos. Entretanto, o comportamento dinâmico de tais cadeias é muito complexo para ser modelado de forma analítica. Por outro lado, estas cadeias mostram várias características intrínsecas em comum com sistemas multiagentes, que oferecem a flexibilidade necessária para modelar as complexidades e a dinâmica das cadeias de suprimentos reais sem a necessidade de premissas muito simplificadoras. Como o problema de gerenciamento da cadeia de suprimentos apresenta uma estrutura recursiva, torna-se ainda mais conveniente usar um modelo baseado em agentes holônicos, que mostram uma estrutura do tipo fractal. Além disso, o tipo de relacionamento entre as entidades da cadeia e a necessidade de uma otimização global sugerem modelar suas interações na forma de restrições. Por esta razão, esta tese propõe um modelo distribuído de otimização através da definição de um novo problema denominado Problema de Satisfação de Restrições Holônico com Otimização (HCOP), que é baseado nos conceitos do Problema de Satisfação de Restrições Distribuído com Otimização (DCOP) e agentes holônicos. Além disso, foi desenvolvido um meta-algoritmo baseado no algoritmo DTREE para solucionar este tipo de problema, onde vários algoritmos disponíveis de otimização centralizados podem ser embutidos e integrados de tal forma a obter a configuração mais adequada para cada caso. Assim, uma típica cadeia de suprimentos da indústria do petróleo foi modelada como um HCOP, e foi desenvolvido um protótipo que implementa o meta-algoritmo proposto em um ambiente que integra sistemas de otimização de produção e logística, que são representativos em relação a situações reais. Finalmente foram realizados experimentos sobre um estudo de caso da empresa PETROBRAS, que permitiram a verificação da viabilidade deste modelo e a comprovação de suas vantagens em relação às abordagens convencionais. / The oil area is one of those that may most benefit from the improved efficiency of supply chain management. However, the dynamic behavior of such chains is too complex to be modeled analytically. Moreover, these chains show several intrinsic characteristics in common with multiagent systems, which offer the required flexibility to model the complexities and dynamics of real supply chains without rather simplifying assumptions. As the problem of managing the supply chain has a recursive structure, it becomes more convenient to use a model based on holonic agents, which show a fractal-type structure. Furthermore, the type of relationship between entities in the chain and the need for global optimization suggest to model their interactions in the form of constraints. For this reason, this thesis proposes an optimization distributed model by defining a new problem called Holonic Constraint Optimization Problem (HCOP), which is based on concepts from Distributed Constraint Satisfaction Optimization Problem (DCOP) and holonic agents. In addition we developed a meta-algorithm based on DTREE algorithm for solving this type of problem, where several algorithms available for centralized optimization algorithms can be embedded and integrated so as to obtain the most suitable configuration for each case. Thus, a typical supply chain of the petroleum industry was modeled as a HCOP, and we developed a prototype that implements the meta-algorithm in an environment that integrates the optimization systems for production and logistics, which are representative in relation to actual situations. Finally experiments were performed on a case study of the company PETROBRAS, which allowed the verification of the feasibility of this model and the proof of their advantages over conventional approaches.

Orientador: Zanoni Dias / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-21T22:58:04Z (GMT). No. of bitstreams: 1 Iizuka_VictordeAbreu_M.pdf: 1453681 bytes, checksum: 1fec01321d56a93084d2597366b44422 (MD5) Previous issue date: 2012 / Resumo: A teoria da seleção natural de Darwin afirma que os seres vivos atuais descendem de ancestrais, e ao longo da evolução, mutações genéticas propiciaram o aparecimento de diferentes espécies de seres vivos. Muitas mutações são pontuais, alterando a cadeia de DNA, o que pode impedir que a informação seja expressa, ou pode expressá-la de um modo diferente. A comparação de sequências é o método mais usual de se identificar a ocorrência de mutações pontuais, sendo um dos problemas mais abordados em Biologia Computacional. Rearranjo de Genomas tem como objetivo encontrar o menor número de operações que transformam um genoma em outro. Essas operações podem ser, por exemplo, reversões, transposições, fissões e fusões. O conceito de distância pode ser definido para estes eventos, por exemplo, a distância de reversão é o número mínimo de reversões que transformam um genoma em outro [9] e a distância de transposição é o número mínimo de transposições que transformam um genoma em outro [10]. Nós trataremos os casos em que os eventos de reversão e transposição ocorrem de forma isolada e os casos quando os dois eventos ocorrem simultaneamente, com o objetivo de encontrar o valor exato para a distância. Nós criamos modelos de Programação por Restrições para ordenação por reversões e ordenação por reversões e transposições, seguindo a linha de pesquisa utilizada por Dias e Dias [16]. Nós apresentaremos os modelos de Programação por Restrições para ordenação por reversões, ordenação por transposições e ordenação por reversões e transposições, baseados na teoria do Problema de Satisfação de Restrições e na teoria do Problema de Otimização com Restrições. Nós fizemos comparações com os modelos de Programação por Restrições para ordenação por transposições, descrito por Dias e Dias [16], e com as formulações de Programação Linear Inteira para ordenação por reversões, ordenação por transposições e ordenação por reversões e transposições, descritas por Dias e Souza [17] / Abstract: The Darwin's natural selection theory states that living beings of nowadays are descended from ancestors, and through evolution, genetic mutations led to the appearance of different kinds of living beings. Many mutations are point mutations, modifying the DNA sequence, which may prevent the information from being expressed, or may express it in another way. The sequence comparison is the most common method to identify the occurrence of point mutations, and is one of the most discussed problems in Computational Biology. Genome Rearrangement aims to find the minimum number of operations required to change one sequence into another. These operations may be, for example, reversals, transpositions, fissions and fusions. The concept of distance may be defined for these events, for example, the reversal distance is the minimum number of reversals required to change one sequence into another [9] and the transposition distance is the minimum number of transpositions required to change one sequence into another [10]. We will deal with the cases in which reversals and transpositions events occur separately and the cases in which both events occur simultaneously, aiming to find the exact value for the distance. We have created Constraint Programming models for sorting by reversals and sorting by reversals and transpositions, following the research line used by Dias and Dias [16]. We will present Constraint Logic Programming models for sorting by reversals, sorting by transpositions and sorting by reversals and transpositions, based on Constraint Satisfaction Problems theory and Constraint Optimization Problems theory. We made a comparison between the Constraint Logic Programming models for sorting by transpositions, described in Dias and Dias [16], and with the Integer Linear Programming formulations for sorting by reversals, sorting by transpositions and sorting by reversals and transpositions, described in Dias and Souza [17] / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

O objetivo dessa dissertação é apresentar um problema de otimização do uso de recursos críticos no desenvolvimento de poços de petróleo marítimos e a técnica empregada para a abordagem proposta ao problema. A revisão da técnica de Programação por Restrições é feita analisando aspectos relevantes de modelagem, propagação, busca e paradigmas de programação. A especialização da técnica para problemas de escalonamento, o Escalonamento Baseado em Restrições, é descrita com ênfase nos paradigmas descritivos e nos mecanismos de propagação de restrições. Como subsídio ao uso da técnica em outros problemas, a linguagem comercial de modelagem OPL é apresentada no Apêndice. O objetivo da abordagem ao problema é obter um escalonador para maximizar a produção de óleo obtida no curto prazo. O escalonador proposto baseia-se na declaração de um modelo empregando variáveis de intervalo. Um algoritmo e um modelo de Programação Linear Inteira abordando relaxações do problema são apresentados para que se obtenha um limitante superior ao valor de produção ótimo. Para o cenário real no qual a análise experimental foi feita, foram obtidas soluções a menos de 16% do ótimo após uma hora de execução; e os testes em instâncias de tamanhos variados evidenciaram a robustez do escalonador. Direções para trabalhos futuros são apresentadas ponderando os resultados obtidos. / The aim of this work is to present a problem of optimizing the use of critical resources to develop offshore oil wells and the technique used to approach the problem. The review of the Constraint Programming technique is made by analyzing relevant aspects of modeling, propagation, search and programming paradigms. The specialization of the technique to scheduling problems, known as Constraint-Based Scheduling, is described with emphasis on descriptive paradigms and constraint propagation mechanisms. In order to support the use of the technique to tackle other problems, the commercial modeling language OPL is presented in the appendix. The aim of the approach to the problem is to obtain a scheduler that maximizes the short-term production of oil. The scheduler presented relies on the description of a model using interval variables. An algorithm and an Integer Linear Programming model approaching relaxations of the problem are presented in order to obtain an upper bound for the optimal production value. For the real scenario upon which the experimental analysis was done, there were found solutions within 16% of the optimal after one hour of execution; and the tests on instances of varied sizes gave evidence of the robustness of the scheduler. Directions for future work are presented based on the results achieved.

Made available in DSpace on 2016-12-12T17:38:36Z (GMT). No. of bitstreams: 1 Sigmundo Preissler Junior.pdf: 762835 bytes, checksum: 46b6541cdc2cad69654c5d7e8fa3c2c0 (MD5) Previous issue date: 2009-02-13 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Esta dissertação apresenta um estudo sobre o problema de corte unidimensional. Como resultado deste estudo, é proposta e desenvolvida uma aplicação da programação por restrições na solução do problema em uma aplicação industrial. O problema consiste em encontrar uma solução do factível para o problema de corte unidimensional de bobinas de aço, em uma situação real, considerando o tempo de preparação. O algoritmo gera planos de corte para um determinado período. Além da abordagem PSR (Programação por Satisfação de Restrições), são analisados os resultados de outros algoritmos já aplicados para o mesmo problema. Os resultados obtidos com o algoritmo PSR são comparados com duas técnicas a saber: Algoritmos Genéticos AG e Pesquisa Operacional PO.

Orientador: Flávio Keidi Miyazawa / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-19T18:16:55Z (GMT). No. of bitstreams: 1 Hokama_PedroHenriqueDelBianco_M.pdf: 1340789 bytes, checksum: b5cc3f26e41b90afabdfac5c7a33bf05 (MD5) Previous issue date: 2011 / Resumo: Nesta dissertação de mestrado apresentamos um método exato para o Problema do Caixeiro Viajante com Restrições de Empacotamento Tridimensional, que combina o Problema do Caixeiro Viajante o Problema de Empacotamento Tridimensional com Restrição de Ordem. Neste problema, um veículo deve partir carregado de um depósito e entregar caixas em pontos pré-definidos para seus clientes. Cada cliente tem um conjunto de caixas que deve receber e o objetivo é minimizar o custo de deslocamento do veículo. As caixas devem ser retiradas a partir da porta do contêiner do veículo e a remoção das caixas de um cliente não podem ser obstruídas pelas caixas a serem descarregadas posteriormente. Propomos uma abordagem exata baseada em branch-and-cut para buscar uma rota de custo mínimo. Apresentamos algumas adaptações de algoritmos da literatura e uma formulação em Programação por Restrições para encontrar um empacotamento que obedece restrições de ordem. Realizamos testes computacionais em instâncias geradas aleatoriamente e comparamos resultados com os algoritmos adaptados da literatura. Os resultados foram bastante satisfatórios resolvendo instâncias de tamanho médio em tempo computacional aceitável na prática / Abstract: We present an exact method for the Traveling Salesman Problem with Three-dimensional Loading Constraints. This problem combines the Traveling Salesman Problem, and the Three- Dimensional Packing Problem With Loading Constraints. In this problem, a vehicle must be loaded at the depot and deliver boxes to the customers. Every customer has a set of boxes that should receive and our goal is to minimize the travel cost of the vehicle. Unloading is done through a single side of the container and items from an unloading customer must not be blocked by items to be delivered later. We propose exact and heuristic branch-and-cut algorithm to find a minimum cost route. Adaptations of algorithms from the literature and a Constraint Programming formulation is presented to find a packing that consider unloading contraints. We performed computational tests on instances randomly generated and compared results with the algorithms adapted from literature. The results were quite satisfactory resolving several instances in reasonable computational time / Mestrado / Ciência da Computação / Mestre em Ciência da Computação