[pt] A principal contribuição desta tese consiste no desenvolvimento de uma heurística híbrida, robusta e eficiente, para o problema de empacotamento unidimensional. A heurística proposta utiliza os seguintes componentes: limites inferiores e superiores do número de caixas; reduções; abordagem dual para a obtenção de soluções iniciais; heurísticas para redistribuição dos pesos; e busca tabu. O outro objetivo desta tese é a aplicação desta heurística para a solução do problema de escalonamento em processadores paralelos idênticos. São apresentados resultados computacionais obtidos sobre centenas de problemas testes da literatura. / [en] We propose in this work a hybrid improvement procedure for the bin packing problem. This heuristic has several components: lower and upper bounds; reductions, construction of initial solutions by reference to the dual problem;heuristics for load redistribution based on dominance, differencing, and unbalancing; and tabu search. We also investigate the application of this hybrid heuristic to the problem of task scheduling on identical parallel processors. Computational results on hundreds of benchmark test problem are presented.

Submitted by EDUARDO BATISTA DE MORAES BARBOSA null (ebmb@yahoo.com) on 2016-07-22T20:43:38Z No. of bitstreams: 1 Thesis-Full.pdf: 4249671 bytes, checksum: 293e98d71cda47dab135797fedb06e6f (MD5) / Approved for entry into archive by Ana Paula Grisoto (grisotoana@reitoria.unesp.br) on 2016-07-25T17:18:40Z (GMT) No. of bitstreams: 1 barbosa_ebm_dr_guara.pdf: 4249671 bytes, checksum: 293e98d71cda47dab135797fedb06e6f (MD5) / Made available in DSpace on 2016-07-25T17:18:40Z (GMT). No. of bitstreams: 1 barbosa_ebm_dr_guara.pdf: 4249671 bytes, checksum: 293e98d71cda47dab135797fedb06e6f (MD5) Previous issue date: 2016-07-01 / A configuração de parâmetros de algoritmos, em especial, das meta-heurísticas, nem sempre é trivial e, frequentemente, é realizada ad hoc de acordo com o problema sob análise. A fim de resolver o problema de sintonização de meta-heurísticas, a presente pesquisa propõe uma metodologia que combina o uso de técnicas estatísticas robustas (ex.: Planejamento de Experimentos) e métodos eficientes de Inteligência Artificial (ex.: Algoritmos de Corrida). A ideia central desta metodologia é um método heurístico, denominado Algoritmo de Corrida Orientada por Heurística (HORA), capaz de explorar o espaço de busca para perseguir diferentes alternativas na vizinhança de uma configuração de parâmetros promissora e encontrar sistematicamente boas configurações candidatas para diferentes algoritmos. Em síntese, o método HORA concentra as buscas sobre configurações candidatas promissoras, criadas dinamicamente em um processo iterativo, e utiliza uma técnica estatística robusta para avaliar as diferentes alternativas e descartar aquelas de qualidade inferior, assim que reunir evidências estatísticas suficientes contra elas. A partir dos resultados de diversos estudos computacionais, em que diferentes meta-heurísticas foram aplicadas sobre dois problemas clássicos de otimização combinatória, apresentam-se evidências estatísticas que as sintonizações obtidas pelo HORA são competitivas em relação ao método de Corrida e seu tempo no processo de sintonização é amplamente vantajoso. Em um estudo complementar, um algoritmo já bem configurado da literatura foi sintonizado por meio da metodologia proposta e os resultados da nova sintonização foram comparados com a literatura. Os resultados demonstram que a sintonização obtida pelo HORA pode encontrar soluções de melhor qualidade em relação à sintonização original. Portanto, a partir dos resultados apresentados nesta pesquisa conclui-se que a metodologia para sintonização de meta-heurísticas por meio do método HORA é uma abordagem promissora que pode ser aplicada sobre diferentes meta-heurísticas para resolução de uma diversidade de problemas de otimização. / The fine-tuning of the algorithms parameters, specially, of the meta-heuristics, it is not always trivial and often is performed by ad hoc methods according to the problem under analysis. In order to solve the problem of tuning metaheuristics, this research proposes a methodology combining statistical robust techniques (e.g.: Design of Experiments) and efficient methods from Artificial Intelligence (e.g.: Racing Algorithms). The key idea of this methodology is a heuristic method, called Heuristic Oriented Racing Algorithm (HORA), which explores the search space looking for alternatives near of a promising candidate and consistently finds good candidates configuration for different algorithms. Briefly, HORA focuses its searches over the promising candidates configuration, dynamically created in an iterative process, and employs a robust statistical method to evaluate and discarding them, as soon as gather enough statistical evidence against them. The results of several studies, where different metaheuristics were applied to solve two classical combinatorial optimization problems, present statistical evidences that the settings obtained by HORA are competitive to the Racing Algorithms and its time in the fine-tuning process is widely advantageous. In a complementary study, an already well setting algorithm from the literature was tuned by means of the proposed methodology and the new settings were compared with the literature. The results show that the fine-tuning from HORA can find better quality solutions than the original ones. Therefore, from the results presented in this study it is concluded that the methodology for fine-tuning of metaheuristics by means of HORA is a promising approach, which can be applied on different metaheuristics to solve a diversity of optimization problems.

O objetivo de projetos de reforma agrária é redistribuir terras de grandes latifúndios para terrenos menores, com destino à agricultura familiar. Um dos principais problemas do Instituto Nacional de Colonização e Reforma Agrária (INCRA) é subdividir uma parcela grande de terra em lotes menores que são balanceados com relação a certos atributos. Este problema é difícil por que precisa considerar diversas restrições legais e éticas. As soluções atuais são auxiliadas por computador, mas manuais, demoradas e suscetíveis a erros, tipicamente produzindo lotes retangulares de áreas similares mas que são injustos com relação a critérios como aptidão do solo ou acesso a recursos hidrográficos. Nesta dissertação, nós propomos um algoritmo genético para gerar subdivisões justas de forma automática. Nós apresentamos um algoritmo construtivo guloso randomizado baseado em locação-alocação para gerar soluções iniciais, assim como operadores de mutação e recombinação que consideram especificidades do problema. Experimentos com 5 instâncias reais e 25 instâncias geradas artificialmente confirmam a efetividade dos diferentes componentes do método proposto, e mostram que ele gera soluções mais balanceadas que as atualmente usadas na prática. / The goal of agrarian reform projects is the redistribution of farmland from large latifundia to smaller, often family farmers. One of the main problems the Brazilian National Institute of Colonization and Agrarian Reform (INCRA) has to solve is to subdivide a large parcel of land into smaller lots that are balanced with respect to certain attributes. This problem is difficult since it considers several constraints originating from legislation as well as ethical considerations. Current solutions are computer-assisted, but manual, time-consuming and error-prone, leading to rectangular lots of similar areas which are unfair with respect to soil aptitude and access to hydric resources. In this thesis, we propose a genetic algorithm to produce fair land subdivisions automatically. We present a greedy randomized constructive heuristic based on location-allocation to generate initial solutions, as well as mutation and recombination operators that consider specifics of the problem. Experiments on 5 real-world and 25 artificial instances confirm the effectiveness of the different components of our method, and show that it leads to fairer solutions than those currently applied in practice.

Drivers are essential factors affecting the efficiency and management level of a carrier. In this thesis, the driver assignment problem is investigated and methods for obtaining lower total operational costs are introduced for small and medium-sized truck freight transportation companies. Three interrelated research topics, including the following, have been systematically studied. Firstly, extending the traditional costing and Activity-Based Costing (ABC) method, the new Time-Driven Activity-Based Costing (TDABC) method, TDABC-FTC, has been introduced for truck freight companies. Detailed implementation process flow has been designed to streamline the easy incorporation of overhead cost. Fuel costs hold about one-third of the total operational costs of truck freight transportation, and drivers’ driving behaviors heavily influence the fuel consumption rate. In this work, the On-Board Diagnostics (OBD) Ⅱ, GPS tracker and Controller Area Network (CAN) bus are used to retrieve related truck operation data and transfer these data to a central database for later processing to obtain driving behavior parameters. An artificial neural network (ANN) model, built using MATLAB toolbox, is introduced to capture the relations between driving behavior and fuel consumption rate. The fuel consumption indicators for different drivers are then developed to reflect their relative fuel consumption rate quantitatively. The driver assignment problem is modeled as an optimization problem for minimizing the total operational cost of the truck, and the NP-hard problem is solved as a mixed integer programming problem. Two solution methods, Branch and Bound, and the Hungarian algorithm, are used to solve the formulated driver assignment problem. The Hungarian algorithm has been modified to address two particular situations in the driver assignment problem. Numerical experiments are conducted to validate the effectiveness of the newly introduced TDABC model, the fuel saving oriented optimal driver assignment method associating driver behavior to truck fuel consumption rate for different transportation tasks, and the solution methods for the special optimization problems formulated in this work. The newly introduced methods were tested using real truck fleet data, showing considerable benefit of the optimal scheduling techniques, and forming the foundation for further research in this area. / Graduate

La conception d'architectures de systèmes est une tâche complexe qui implique des enjeux majeurs. Au cours de cette activité, les concepteurs du système doivent créer des alternatives de conception et doivent les comparer entre elles afin de sélectionner l'architecture la plus appropriée suivant un ensemble de critères. Dans le but d'étudier différentes alternatives, les concepteurs doivent généralement limiter leur étude comparative à une petite partie de l'espace de conception qui peut être composé d'un nombre immense de solutions. Traditionnellement, le processus de conception d'architecture est principalement dirigé par le jugement et l'expérience des concepteurs, et les alternatives sélectionnées sont des versions adaptées de solutions connues. Le risque est donc de sélectionner une solution pertinente mais sous-optimale. Pour gagner en confiance sur l'optimalité de la solution retenue, la couverture de l'espace de conception doit être augmentée. L'utilisation de méthodes de synthèse calculatoire d'architecture a prouvé qu'elle était un moyen efficace pour supporter les concepteurs dans la conception d'artefacts d'ingénierie (structures, circuits électriques...). Pour assister les concepteurs de systèmes durant le processus de conception d'architecture, une méthode calculatoire pour les systèmes complexes est définie. Cette méthode emploie une approche évolutionnaire (algorithmes génétiques) pour guider le processus d'exploration de l'espace de conception vers les zones optimales. La population initiale de l'algorithme génétique est créée grâce à une technique de synthèse calculatoire d'architecture qui permet de créer différentes architectures physiques et tables d'allocations pour une architecture fonctionnelle donnée. La méthode permet d'obtenir les solutions optimales du problème de conception posé. Ces solutions peuvent être ensuite utilisées par les concepteurs pour des études comparatives plus détaillées ou pour des négociations avec les fournisseurs de systèmes / The design of system architectures is a complex task which involves major stakes. During this activity, system designers must create design alternatives and compare them in order to select the most relevant system architecture given a set of criteria. In order to investigate different alternatives, designers must generally limit their trade studies to a small portion of the design-space which can be composed of a huge amount of solutions. Traditionally, the architecture design process is mainly driven by engineering judgment and designers' experiences and the selected alternatives are often adapted versions of known solutions. The risk is then to select a pertinent but yet under optimal solution. In order to increase the confidence in the optimality of the selected solution, the coverage of the design-space must be increased. The use of computational design synthesis methods proved to be an efficient way to support designers in the design of engineering artifacts (structures, electrical circuits...). In order to assist system designers during the architecture design process, a computational method for complex systems is defined. This method uses an evolutionary approach (genetic algorithms) to guide the design-space exploration process toward optimal zones. The initial population of the genetic algorithm is created thanks to a computational design synthesis technique which permits to create different physical architectures and allocation mappings for a given functional architecture. The method permits to obtain the optimal solutions of the stated design problem. These solutions can be then used by designers for more detailed trade studies or for technical negotiations with system suppliers.

Esta dissertação trata do planejamento do abastecimento de última milha em centros urbanos, propondo métodos para agrupar pedidos de clientes em programação de entregas. Neste estudo, é considerado que o frete pago ao transportador em uma rota é definido pela distância direta do ponto de entrega mais distante do depósito em contraposição à distância total da rota que é usual na literatura sobre problemas de roteirização de veículos. Além disso, também são consideradas categorias, conjunto de produtos similares, que não podem ser transportadas juntas por não serem compatíveis entre si. O objetivo do problema proposto é determinar o agrupamento e sequenciamento de pedidos em roteiros de veículos de acordo com as características operacionais descritas acima, utilizando uma frota homogênea de veículos capacitados que parte de um depósito, de tal forma que toda a demanda seja atendida com o menor frete possível. Para resolução desse problema são propostas uma formulação matemática para obtenção de soluções exatas e a implementação da heurística \"Multi Start Perturbation Tabu\" (MSPT) que é composta das metaheurísticas \"Greedy Randomized Adaptive Search Procedure\" (GRASP), \"Tabu Search\" (TS) e \"Iterated Local Search\" (ILS) para obtenção de soluções heurísticas. Os resultados experimentais indicam que a MSPT é competitiva com os resultados do método exato com até 5 horas de processamento utilizando os recursos computacionais de alto desempenho do Laboratório de Computação Científica Avançada (LCCA) da Universidade de São Paulo. / This dissertation addresses the planning of the last mile supply in urban centers and proposes methods to group customer orders into shipments. In this study, freight paid to the carrier on a route is defined as the direct distance from the point of delivery that is furthest from the depot as opposed to be defined as the total distance of the route which is commonly found in the literature on vehicle routing problems. In addition, it is also considered categories, a set of similar products, which cannot be transported together because they are not compatible with each other. The objective of the proposed problem is to determine the grouping and sequencing of orders into vehicle shipments according to the operational characteristics described above, using a homogeneous fleet of capacitated vehicles that is located in a depot, in such a way that all the demand is delivered with the lowest freight possible. To solve this problem, it is proposed a mathematical formulation to obtain exact solutions and the implementation of the Multi Start Perturbation Tabu (MSPT) heuristic that is composed of the Greedy Randomized Adaptive Search Procedure (GRASP), Tabu Search (TS) and \"Iterated Local Search\" (ILS) for heuristic solutions. Finally, the experimental results indicate that the MSPT is competitive with the outcomes of the exact method with up to 5 hours of processing using the high performance computational resources of the Advanced Scientific Computation Laboratory (LCCA) of the University of São Paulo (USP).

Relações min-max são objetos centrais em otimização combinatória. Elas basicamente afirmam que, numa dada estrutura, o valor ótimo de um certo problema de minimização é igual ao valor ótimo de um outro problema de maximização. Relações desse tipo fornecem boas caracterizações e descrições poliédricas para diversos problemas importantes, além de geralmente virem acompanhadas de algoritmos eficientes para os problemas em questão. Muitas vezes, tais algoritmos eficientes são obtidos naturalmente das provas construtivas dessas relações; mesmo quando isso não ocorre, essas relações revelam o suficiente sobre a estrutura combinatória dos problemas, levando ao desenvolvimento de algoritmos eficientes. O foco principal desta dissertação é o estudo dessas relações em grafos. Nossa ênfase é sobre grafos orientados. Apresentamos o poderoso arcabouço poliédrico de Edmonds e Giles envolvendo fluxos submodulares, bem como o algoritmo de Frank para um caso especial desse arcabouço: o teorema de Lucchesi-Younger. Derivamos também diversas relações min-max sobre o empacotamento de conectores, desde o teorema de ramificações disjuntas de Edmonds até o teorema de junções disjuntas de Feofiloff-Younger e Schrijver. Apresentamos também uma resenha completa sobre as conjecturas de Woodall e sua versão capacitada, conhecida como conjectura de Edmonds-Giles. Derivamos ainda algumas relações min-max clássicas sobre emparelhamentos, T-junções e S-caminhos. Para tanto, usamos um teorema de Frank, Tardos e Sebö e um arcabouço bastante geral devido a Chudnovsky, Geelen, Gerards, Goddyn, Lohman e Seymour. Ao longo do texto, ilustramos vários aspectos recorrentes, como o uso de ferramentas da combinatória poliédrica, a técnica do descruzamento, o uso de funções submodulares, matróides e propriedades de troca, bem como alguns resultados envolvendo subestruturas proibidas. / Min-max relations are central objects in combinatorial optimization. They basically state that, in a given structure, the optimum value of a certain minimization problem equals the optimum value of a different, maximization problem. Relations of this kind provide good characterizations and polyhedral descriptions to several important problems and, moreover, they often come with efficient algorithms for the corresponding problems. Usually, such efficient algorithms are obtained naturally from the constructive proofs involved; even when that is not the case, these relations reveal enough of the combinatorial structure of the problem, leading to the development of efficient algorithms. The main focus of this dissertation is the study of these relations in graphs. Our emphasis is on directed graphs. We present Edmonds and Giles\' powerful polyhedral framework concerning submodular flows, as well as Frank\'s algorithm for a special case of this framework: the Lucchesi-Younger Theorem. We also derive several min-max relations about packing connectors, starting with Edmonds\' Disjoint Branchings Theorem and ending with Feofiloff-Younger and Schrijver\'s Disjoint Dijoins Theorem. We further derive some classical min-max relations on matchings, T-joins and S-paths. To this end, we use a theorem due to Frank, Tardos, and Sebö and a general framework due to Chudnovsky, Geelen, Gerards, Goddyn, Lohman, and Seymour. Throughout the text, we illustrate several recurrent themes, such as the use of tools from polyhedral combinatorics, the uncrossing technique, the use of submodular functions, matroids and exchange properties, as well as some results involving forbidden substructures.

O problema de caminhos mínimos (SP shortest path problem) é frequentemente colo- cado em prática em uma grande variedade de aplicações em diversas áreas. Nessas aplicações geralmente se deseja realizar algum tipo de deslocamento ou transporte entre dois ou mais pontos específicos em uma rede. Tal ação deve ser executada de forma ótima em relação a algum critério, por exemplo o menor custo possível, ou o menor gasto de tempo ou o máximo de confiabilidade/segurança. Na prática, muitas vezes não desejamos apenas o menor custo ou o menor tempo, mas desejamos otimizar uma combinação de diferentes critérios, por exemplo, um caminho que seja rápido e barato. Como não é possível otimizar sobre todos os critérios de uma só vez, nós escolhemos um dos critérios para representar a função custo, que será minimizada, e para os demais critérios representamos como recursos e definimos os limites que julgamos aceitáveis para o consumo de cada um desses recursos. Esta variação é cha- mada de problema de caminhos mínimos com restrições por recursos, ou como preferimos chamar, problema de caminhos mínimos com recursos limitados (RCSP resource constrained shortest path problem), o qual será o objeto de estudo neste trabalho. A adição de restrições por recursos no SP, infelizmente torna o problema NP-difícil, mesmo em grafos acíclicos, com restrições sobre um único recurso, e com todos os consu- mos de recursos positivos. Temos reduções dos famosos problemas N P-difíceis Mochila e Partição para o nosso problema. Em contextos diversos são encontrados problemas de cunho teórico e prático que po- dem ser formulados como problemas de caminhos mínimos com recursos limitados, o que nos motivou a estudá-lo a fim de desenvolver um trabalho que resumisse informações sufi- cientes para auxiliar pesquisadores ou desenvolvedores que tenham interesse no problema. Nós apresentamos aqui, uma detalhada revisão bibliográfica do RCSP, tendo como foco o desenvolvimento de algoritmos exatos para o caso onde possuímos um único recurso e a im- plementação e comparação dos principais algoritmos conhecidos, observando-os em situações práticas. / The problem of choosing a route to a trip, where we want minimize the distance of the path is a major problem in computing. In this basic form, this is the shortest path problem. But sometimes, besides the length we need to consider more parameters for selecting a good path. A common parameters to consider is the consumption of resources in a limited budget. A shortest path with these additional constraints is called resource constrained shortest path - RCSP. This paper has two main objectives: to present a literature review of the problem RCSP, focusing on exact algorithms for the case where we have a single resource, and implement and compare some algorithms, observing them in practical situations. The Shortest Path (SP) problem is among the fundamental problems of computer sci- ence. Its been deeply studied and subject of many publications. Also, many efficient solutions (polynomial time algorithms) are known for this problem. The SP is widely applied in many fields of science, not only computer science. These situations usually need to transport a load between two or more specific spots of a network. This action must be taken optimally regarding to some criterion, for instance the least cost, or the least time or maximum relia- bility. While new solutions for SP were presented, new demands were issued too, with new variations for the problem. One of these variations comes from the fact that, in a real scenario, a combination of many criteria must be optimized, for instance a path with least cost and least time. This problem is known as Multiobjective Shortest Path. Since its not possible to optimize all criteria at once, one of them is chosen to represent the cost function to be minimized and the others to represent resources with defined boundary. This variation, known as Resource Constrained Shortest Path (RCSP), was the object of the present study. By adding resource constraints, the SPbecomes N P-hard, even in acyclic graphs with only one resource constrained and all resource consumption being positive. There are reduc- tions from the famous NP-hard problems Knapsack and Partition to our problem. In many fields, are found theoretical and practical problems that may be expressed as a Resource Constrained Shortest Path Problem, which motivated us to study this problem in order to summarize enough information to researchers and developers involved with this problem. This paper presents a detailed bibliographic revision to RCSP, focusing on the development of exact algorithms for the case when there is only only one resource and on the implementation and comparison of the main known algorithms in practical situations.

Neste trabalho foi estudado um problema de dimensionamento de lotes em uma indústria química brasileira, cujo objetivo era determinar o tamanho dos lotes dos produtos para atender às demandas, minimizando os custos produtivos. Os itens podem ser produzidos em máquinas paralelas distintas, através de diferentes processos, e devem ser armazenados em taques cativos, exclusivos a um produto, ou multipropósitos, compartilhado entre produtos, desde que não simultaneamente. Foram propostos dois modelos matemáticos de programação inteira mista para representar o problema, o primeiro apresentava uma função objetivo compreendendo o preço das matérias-primas consumidas nas reações, os gastos com a estocagem de produtos e o custo de descarte de produtos quando os tanques de armazenamento não tiverem capacidade suficiente para armazená-los, já o segundo estendendo este modelo para considerar custos de preparação de máquina. Experimentos computacionais com os modelos propostos, utilizando instâncias geradas a partir dos dados fornecidos pela empresa, mostraram que o software de otimização empregado foi capaz de resolver poucas instâncias, após uma hora de processamento. Portanto, foram propostas heurísticas construtivas do tipo LP-and-fix e relax-and-fix, além de heurísticas de melhoria do tipo fix-and-optimize. Após serem realizados testes com essas heurísticas, constatou-se que algumas proporcionaram a obtenção de soluções factíveis de boa qualidade, quando comparadas às obtidas pelo software, sendo ainda capazes de resolver um maior número de instâncias / In this dissertation the lot sizing problem in a chemical Brazilian industry was studied, with the goal to determine the products lot size to satisfy the demands, minimizing the production costs. The items can be produced on distinct parallel machines through different processes and then must be stored in exclusive tanks, used by only one product, or multipurpose tanks, when more than one product can use the tank, but not simultaneously. Two models were proposed to represent the problem, the first one aiming to minimize the price of raw material consumed in the reactions, storage product spending and the cost of discarting products when the storage tanks do not have enough capacity to store them, and the second one considering setup cost either. Computational experiments using the proposed models, with instances were generated from the data provided by the company, showed that the used optimization software was able to solve only few instances after processing for one hour. In this dissertation we propose constructives heuristics such LP-and-fix and relax-and-fix, and improving heuristics like fix-and-optimize. After performing the tests with those heuristics, it was found that some of them provided feasible solutions with good quality, when compared to the ones obtained by the software, and they were also able to solve a larger number of instances

Orientador: Flávio Keidi Miyazawa / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-16T14:13:04Z (GMT). No. of bitstreams: 1 Azevedo_BrunoLuisPiresde_M.pdf: 1384772 bytes, checksum: 48aa7ca2380aaa03fd6375cb9b35aebc (MD5) Previous issue date: 2009 / Resumo: Nesta dissertação apresentamos um algoritmo exato para o Problema de Roteamento de Veículos Capacitados com Restrições Bidimensionais. Este combina o problema de carregar um conjunto de itens bidimensionais em veículos com o problema de minimizar o custo total de transporte. Existem várias aplicações práticas para este problema, dado que em muitas situações os itens não podem ser empilhados por diversas razões. Propomos um algoritmo exato baseado em uma abordagem branch-and-cut. Sete desigualdades válidas para o Problema de Roteamento de Veículos Capacitados foram adaptadas e utilizadas. As restrições de empacotamento são garantidas através de um algoritmo exato. Também apresentamos uma nova heurística de empacotamento bidimensional. Exploramos duas variantes do problema, as versões seqüencial e irrestrita. Para ambos os casos, consideramos os itens possuirem orientação fixa. Efetuamos testes computacionais e comparamos os resultados obtidos com a abordagem exata, para o caso seqüencial, apresentada por Iori, Salazar-González e Vigo. Observamos resultados satisfatórios e nove instâncias da literatura foram resolvidas à otimalidade pela primeira vez. Como o caso irrestrito ainda não havia sido abordado de modo exato, apresentamos também as soluções de cinqüenta instâncias nunca resolvidas à otimalidade / Abstract: We present an exact algorithm for the Vehicle Routing Problem with Two-dimensional Loading Constraints. This problem combines the problems of loading vehicles with two-dimensional items and minimizing transportation costs. It has many practical applications, since in many cases items can not be stacked on top of each other. We propose an exact algorithmbased on a branch-and-cut approach. Seven valid inequalities for the the Capacitated Vehicle Routing Problems were modified and used. The packing constraints are imposed by an exact algorithm. We also present a new heuristic for two-dimensional packing. We explored two variants of the problem, the sequential and the unrestricted cases. For both variants we assume the items to have fixed orientation. We performed computational tests and compared the results with the exact approach by Iori, Salazar-González and Vigo for the sequential case. We found the results to be satisfactory and nine instances from the literature were solved to optimality for the first time. Since the unrestricted case haven't been tested so far by an exact algorithm, we also present the solutions for fifty instances never solved to optimality before / Mestrado / Teoria da Computação / Mestre em Ciência da Computação