Made available in DSpace on 2016-06-02T19:51:39Z (GMT). No. of bitstreams: 1 2523.pdf: 1711552 bytes, checksum: cf13454170c0e1db1eb5ae2aa8cff6a3 (MD5) Previous issue date: 2009-02-26 / Financiadora de Estudos e Projetos / The object of this study is a particular case of the cutting and packing problems, known as container loading problems. These problems consist in arranging rectangular boxes orthogonally into containers (or into trucks, railcars and pallets), in order to optimize an objective function, for example, maximize the utilization of the available space, or minimize the number of the required containers to load all the available items. The objective of this study is to develop mathematical programming models to deal with situations commonly found in container loading practice. Multiple orientations of the boxes, weight limit of the container, cargo stability, load bearing strength of the boxes and multiple destinations of the cargo are considered. The author is not aware of mathematical formulations available in the cutting and packing literature that deal with such considerations, and this paper intends to contribute with possible formulations that describe these situations, although not very realistic for being used in practice. Computational experiments with the proposed models are performed with the software AMS/CPLEX and randomly generated instances extracted from the cutting and packing literature. The results show that the models are consistent and properly represent the practical situations treated, although this approach (in its current version) is limited to solve to optimality only medium-sized problems. However, we believe that the proposed models can be useful to motivate future research exploring decomposition methods, relaxations, heuristics, among others, to solve the present problems. / O objeto de estudo deste trabalho é um caso particular dos problemas de corte e empacotamento, conhecido como problemas de carregamento de contêineres. Estes problemas consistem em arranjar caixas retangulares ortogonalmente dentro de contêineres (ou caminhões, vagões ferroviários e paletes), de maneira a otimizar uma função objetivo, por exemplo, maximizar o aproveitamento do espaço disponível, ou então minimizar o número de contêineres necessários para carregar todas as caixas disponíveis. O objetivo deste trabalho é desenvolver modelos de programação matemática que abordem situações comumente encontradas na prática do carregamento de contêineres. Considerações de múltiplas orientações das caixas, limite de peso do contêiner, estabilidade do carregamento, resistência das caixas ao empilhamento e carga fracionada em múltiplos destinos são tratadas. O autor não tem conhecimento de formulações matemáticas disponíveis na literatura de corte e empacotamento que tratem estas considerações, e este trabalho pretende contribuir com possíveis formulações que, embora pouco realistas para serem aplicadas na prática, descrevem estas situações. Experimentos computacionais com os modelos propostos são realizados utilizando o aplicativo GAMS/CPLEX e exemplos gerados aleatoriamente e da literatura. Os resultados mostram que os modelos são coerentes e representam adequadamente as situações tratadas, embora esta abordagem (na sua versão atual) esteja limitada a resolver otimamente apenas problemas de tamanho bem moderado. No entanto, os modelos podem ser úteis para motivar pesquisas futuras explorando métodos de decomposição, métodos de relaxação, métodos heurísticos, entre outros, para resolver os problemas em questão.

Made available in DSpace on 2016-06-02T19:51:41Z (GMT). No. of bitstreams: 1 2685.pdf: 1876781 bytes, checksum: d3c1e2f0274bc0264d006a778e4c3ccd (MD5) Previous issue date: 2009-09-25 / Financiadora de Estudos e Projetos / Intermodal transport, that is, the integration between different transport modes was facilitated by the use of containers. The stowage devices in the breakdown of the cargo is an important logistics activity, since the total volume actually used can affect significantly the cost of transporting the products. This approach addresses the Container Loading Problem, which more generally consists in arranging items (for example, products packaged in boxes) of various sizes within larger objects (for example, containers) with the maximum use of the available volume. In particular, it is considered the special case where the boxes to be arranged are rectangular and identical (single sized) and there is only a single container. In order to tackle these problems, the 2006´s Tabu Search heuristic by Pureza and Morabito, originally proposed for the Manufacturer s Pallet Loading Problem, was extended. From an initial solution generated by a block heuristic, moves are applied to selected blocks in order to change their box orientation and/or to expand them in one of the six directions, which result in the reduction, elimination and creation of other blocks. Criteria for stability of the load are also addressed in this work. Computational experiments using a set of instances in the literature demonstrate the performance of the proposed approach. / O transporte intermodal, ou seja, a integração entre diversos modos de transporte foi facilitada com o uso de contêineres. O acondicionamento da carga em dispositivos de unitização de cargas é uma importante atividade logística, uma vez que o volume total efetivamente utilizado pode afetar de maneira significativa o custo de transporte dos produtos. Este trabalho aborda o problema do carregamento de contêineres, cuja forma mais geral consiste em arranjar itens (por exemplo, produtos embalados em caixas) de vários tamanhos dentro de objetos maiores (por exemplo, contêineres) com máximo aproveitamento do volume disponível. Em particular, é considerado o caso especial em que as caixas a serem arranjadas são retangulares e idênticas e dispõe-se de apenas um único contêiner. Com vistas à resolução destes problemas, estendemos a heurística de busca tabu de Pureza e Morabito (2006), originalmente projetada para o problema de carregamento de paletes do produtor. Partindo-se de uma solução inicial gerada por uma heurística de blocos, são realizados movimentos de troca de orientação e/ou expansão de blocos selecionados, e que resultam na diminuição, eliminação e criação de outros blocos. Critérios de estabilidade da carga são também abordados neste trabalho. Experimentos computacionais utilizando um conjunto de instâncias da literatura demonstram o desempenho da abordagem proposta.

Made available in DSpace on 2016-06-02T19:50:20Z (GMT). No. of bitstreams: 1 5182.pdf: 6075915 bytes, checksum: 91596b4ab6b9108e05799c5f3c87831d (MD5) Previous issue date: 2013-05-17 / Financiadora de Estudos e Projetos / The object of this study are combined problems of the Vehicle Routing Problem and the Container Loading Problem, recently addressed as Integrated Vehicle Routing and Loading Problems. In these problems, the objective is to optimize simultaneously the planning of the vehicles routes and the arrangement of the cargo inside them, while considering a series of practical constraints from both vehicle routing and container loading. The objectives of this study are: (i) to study the integration between the Vehicle Routing Problem and the Container Loading Problem; (ii) to develop mathematical programming models to represent Integrated Vehicle Routing and Loading Problems; (iii) to develop and implement heuristics and metaheuristics to solve some of these problems; (iv) to analyze and compare the performance of the proposed models, by means of modeling languages and optimization solvers, as well as the heuristic methods, when solving instances from the literature and real-world situations. Besides being hard and relatively less studied problems, the main reason for this study is that with effective solution methods for optimizing the vehicle routing and the cargo loading, operational and tactical decisions could be made with more reliability, accuracy, quickness and with less uncertainty in real situations, besides of an improved use of the staff tasked to load and unload the cargo. On the other hand, these methods can also be usefull to reduce fixed and variable costs in a company that might use them. Computational experiments with some of the proposed models were performed with an optimization software and randomly generated instances. The results show that the models are consistent and properly represent the practical situations treated, although this approach (in its current version) is limited to solve to optimality only problems of moderate size, that is, situations with few customers, few vehicles, and mainly with a relatively reduced number of possible positions to load the boxes. This has motivated the development of heuristic and metaheuristic methods to solve more realistic vehicle routing and loading problems. The algorithms are based on the combination of classical heuristics from both the vehicle routing and container loading literatures, as well as two metaheuristic strategies, and their use in more elaborate procedures. Although these approaches cannot assure optimal solutions for the respective problems, they are relatively simple, fast enough to solve real instances, flexible enough to include practical considerations, and normally assure relatively good solutions in acceptable computational times in practice. Computational experiments were performed with these methods considering instances based on the vehicle routing literature and actual customers orders, as well as instances based on a real-world situation where the problem occurs. / O objeto de estudo deste trabalho são problemas combinados do Problema de Roteamento de Veículos com o Problema de Carregamento de Contêineres, tratados mais recentemente na literatura como Problemas Integrados de Roteamento e Carregamento de Veículos. Nestes problemas, genericamente, busca-se otimizar simultaneamente o planejamento dos roteiros dos veículos e o arranjo da carga dentro dos mesmos, respeitando-se uma série de considerações práticas que advêm tanto do Problema de Roteamento de Veículos como do Problema de Carregamento de Contêineres. Os objetivos deste trabalho são: (i) estudar a integração do Problema de Roteamento de Veículos com o Problema de Carregamento de Contêineres; (ii) desenvolver modelos de programação matemática para representar Problemas Integrados de Roteamento e Carregamento de Veículos; (iii) desenvolver e implementar métodos heurísticos e meta-heurísticos para resolver alguns destes problemas; (iv) analisar e comparar o desempenho da solução dos modelos, via linguagens de modelagem e aplicativos de otimização, e dos métodos heurísticos desenvolvidos ao resolver exemplos baseados na literatura e em situações reais em que este problema ocorre. Além de serem problemas difíceis e relativamente pouco estudados, a principal justificativa para o estudo destes problemas é que, com métodos de solução eficazes para a otimização do roteamento dos veículos e do carregamento das cargas, decisões operacionais e táticas podem ser tomadas com maior segurança, acurácia, rapidez e menor incerteza em situações reais, além de possibilitar um melhor desempenho do pessoal encarregado da montagem e descarregamento da carga. Por outro lado, estes métodos também podem ser úteis na redução de custos fixos e variáveis de uma empresa que venha a utilizá-los. Experimentos computacionais com alguns dos modelos propostos foram realizados utilizando um aplicativo de otimização e aplicados a exemplos gerados aleatoriamente. Estes resultados mostram que os modelos são coerentes e representam adequadamente as situações tratadas, embora esta abordagem (na sua versão atual) esteja limitada a resolver otimamente apenas problemas de tamanho bem moderado, isto é, em que haja poucos clientes, poucos veículos, e que o número de possíveis posições para se arranjar as caixas dentro de cada veículo seja relativamente pequeno. Isso motivou o desenvolvimento de métodos heurísticos e meta-heurísticos para resolver problemas mais realistas de roteamento e carregamento de veículos. Os algoritmos são baseados na combinação de heurísticas clássicas das literaturas de Roteamento de Veículos e de Carregamento de Contêineres, bem como em duas estratégias meta-heurísticas, e no uso delas em procedimentos mais elaborados. Embora não haja garantias de que as soluções obtidas para os respectivos problemas sejam ótimas, tratam-se de heurísticas relativamente simples, suficientemente rápidas para resolver problemas reais, razoavelmente flexíveis para incorporar aspectos práticos, e que normalmente garantem soluções relativamente boas em tempos computacionais aceitáveis na prática. Experimentos computacionais foram realizados com estes métodos considerando exemplos baseados na literatura de Roteamento de Veículos e em pedidos reais de cargas, bem como exemplos baseados em um caso real em que o problema ocorre.

Submitted by Erika Demachki (erikademachki@gmail.com) on 2017-06-21T21:21:46Z No. of bitstreams: 2 Dissertação - Liliane de Azevedo Oliveira - 2017.pdf: 1274368 bytes, checksum: 9b7a4aa781e0951c3f12045277a55582 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Erika Demachki (erikademachki@gmail.com) on 2017-06-29T18:27:23Z (GMT) No. of bitstreams: 2 Dissertação - Liliane de Azevedo Oliveira - 2017.pdf: 1274368 bytes, checksum: 9b7a4aa781e0951c3f12045277a55582 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2017-06-29T18:27:23Z (GMT). No. of bitstreams: 2 Dissertação - Liliane de Azevedo Oliveira - 2017.pdf: 1274368 bytes, checksum: 9b7a4aa781e0951c3f12045277a55582 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2017-02-22 / Fundação de Amparo à Pesquisa do Estado de Goiás - FAPEG / In this work we applied an algorithm based on the resolution of integer linear models for the problem of packing boxes into a single container considering the cargo stability constraint. The problem consists of arranging items (boxes) of different sizes inside a large object (container) to maximize the occupied container volume while respecting the imposed constraints. Four methods are investigated and compared due to vertical cargo stability, in which three of these methods are proposed in this work and based on the equilibrium of rigid bodies, and the other one is based on the factor of support of boxes bottom faces. In the case of the factor of support, a set of constraints can be inserted totally in the integer formulation, while in the other methods cutting planes are inserted during optimization of the formulation by a branch-and-cut algorithm. Computational tests on instances from the literature show that the usage of a factor of support underestimates the value of the optimal solution. The computational tests showed that the use of the factor of support may underestimate the solution, but its use with integer linear programming models has the advantage that feasible solutions are stable, while the other developed methods only verify stability and thus they depend of the integer linear program to return feasible solutions more quickly. By the way, the methods for the cargo stability developed here also overcame the factor of support for tests involving different types of mesh to pack into the container. / Aplica-se um algoritmo baseado na resolução de modelos de programação linear inteira para o problema de carregamento de caixas dentro de um único contêiner considerando a restrição de estabilidade de carga. O problema em estudo consiste em arranjar itens (caixas) de diferentes tamanhos dentro de um objeto maior (contêiner), de maneira maximizar a ocupação do volume do contêiner enquanto respeita as restrições dadas. Quatro métodos são investigados e comparados quanto a estabilidade vertical do empacotamento, sendo que três deles são desenvolvidos neste trabalho e baseados em conceitos do equilíbrio de corpos rígidos, enquanto um deles é baseado no fator de suporte da base das caixas. No caso do fator de suporte, um conjunto de restrições pode ser inserido totalmente dentro da formulação inteira, enquanto nos demais métodos planos de corte são inseridos durante a resolução da formulação por um algoritmo branch-and-cut. Os testes computacionais mostraram que o uso do fator de suporte pode subestimar a solução, porém seu uso com modelos de programação linear inteira tem a vantagem das soluções viáveis poderem ser estáveis, enquanto os demais métodos desenvolvidos apenas verificam a estabilidade e, assim, dependem do programa linear inteiro retornar soluções viáveis mais rapidamente. Os métodos para a estabilidade de carga desenvolvidos neste trabalho mostraram-se superiores ao fator de suporte para testes envolvendo diferentes tipos de malhas para o empacotamento no contêiner.