Made available in DSpace on 2019-03-29T23:27:59Z (GMT). No. of bitstreams: 0
Previous issue date: 2011-09-27 / Transport of goods has represented an important role in economic development throughout the history and ship containerization brought great advantages. Its invention in mid-1950s brought down the cost of transport and reduced time for loading and unloading cargo. Consequently, it increased efficiency of port working and reduced handling cargo to hours instead of weeks, as before.
However, the good use of containerization involves new and specialized logistic process, a number of technologies and automated systems to handle a great number of containers and even greater volume of cargo. To answer these requirements, computation appears as important tool. The described scenary has been treated in academic literature as the Container Loading Problem (CLP), with some variants.
It is necessary consider practical requirements, for example the stability of cargo or weight distribution. The last one is of vital importance since the position of the centre of gravity of cargo affects the stability during its transport. When desconsidered, it could result in damage to cargo or vehicle. During our research, we were specially interested in this requirement. But, in order compare the found solutions with other ones, we proposed a methodology to measures the weight distribution.
So, to the described problem, specifically the Knapsack Loading Problem (3D-KLP), this work presents a methodology that not only maximizes the packed cargo volume but also optimizes the weight distribution, its great contribution. Mainly if we consider that the cargo to be packed is composed by items with different densities, which turns the problem more difficult.
The present methodology is composed by two phases with distinct goals. The first phase is concerned with maximize the weight distribution combining a search algorithm, the backtracking, with heuristics that solve integer linear programming models. The second phase executes a Genetic Algorithm to maximize the weight distribution of previously packed cargo. We also present a justification for why genetic algorithm was used in our methodology.
An additional application was made to solve cutting problems. This class of problems occurs in various industrial process, when it is necessary to cut different types of material as glass, wood or parper, with a minimum of waste.
We use a well-known benchmark test to compare our results with other approaches. This work also presents a case study of our implementation using some real data in a factory of stoves and refrigerators in Brazil. It shown promising results in reduced time.
Keywords: Container Loading Problem, Knapsack Loading Problem, Weight Distribution, Integer Programming, Backtracking, Genetic Algorithms. / O transporte de carga tem representado um papel fundamental no desenvolvimento econômico no decorrer da história e a conteinerização trouxe grandes vantagens. Seu advento reduziu os custos de transporte bem como o tempo de carga. Portanto, aumentou a eficiência do trabalho em portos e reduziu o tempo necessário para operações com carga para horas, ao invés de semanas como anteriormente.
Contudo, o bom uso dos contêineres involve novos e especializados processos logísticos, uma grande quantidade de tecnologias além de sistemas automatizados para manipular uma elevada quantidade de contêineres e ainda maior volume de carga. Para atender a estes requisitos, computação aparece como uma importante ferramenta. O cenário descrito tem sido tratado na literatura acadêmica como o Problema de Carregamento de Contêiner (CLP, do inglês Container Loading Problem), com algumas variantes.
é também necessário considerar requisitos práticos como, por exemplo, a estabilidade da carga ou distribuição do peso. Este último de vital importância uma vez que o centro de gravidade da carga afeta a estabilidade durante seu transporte. Se descosiderado, pode-se danificar tanto a carga como o veículo. Durante nossa pesquisa, nós estivemos especialmente interessados neste requisito. E a fim de comparar a qualidade dos resultados obtidos, propusemos uma maneira de mensurar a distribuição do peso.
Portanto, dado o problema descrito, especificamente o 3D Knapsack Loading Problem, este trabalho apresenta um algoritmo que não apenas maximiza o volume total carregado mas também otimiza a distribuição do peso da carga, sua grande contribuição. Principalmente se considerarmos que a carga é composta de itens com diferentes valores de densidade, o que torna o problema ainda mais difícil.
A metodologia consiste em duas fases com objetivos diferentes. A primeira fase ocupa-se em maximizar o volume carregado por combinar um algoritmo de busca, o backtracking, com heurísticas que resolvem modelos de programação linear inteira. A segunda fase executa um algoritmo genético para maximizar a distribuição do peso da carga previamente colocada. Apresentamos também uma justificativa do porque algoritmo genéticos foram usados em nossa metodologia.
Uma aplicação adicional foi feita para resolver problemas de corte. Esta classe de problemas ocorre em vários processos industriais, quando é necessário cortar diferentes tipos de materiais, como vidro, madeira ou papel, com um mínimo de desperdício.
A fim de comparação, usamos bibliotecas de teste bem conhecidas na literatura e um estudo de caso usando informações reais de uma fábrica de fogões e geladeiras no Brasil. São apresentados resultados promissores alcançados em tempo reduzido.
Palavras-chave: Problema de Carregamento de Contêiner, Knapsack Loading Problem, Distribuição do Peso, Programação Linear Inteira, Backtracking, Algoritmos Genéticos.
| Identifer | oai:union.ndltd.org:IBICT/oai:dspace.unifor.br:tede/88221 |
| Date | 27 September 2011 |
| Creators | Araujo, Luiz Jonatã Pires de |
| Contributors | Pinheiro, Plácido Rogério, Pinheiro, Plácido Rogério, Viana, Gerardo Valdisio Rodrigues, Aragão, Marcus Vinicius Soledade Poggi de |
| Publisher | Universidade de Fortaleza, Mestrado Em Informática Aplicada, UNIFOR, Brasil, Centro de Ciências Tecnológicas |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Source | reponame:Biblioteca Digital de Teses e Dissertações da UNIFOR, instname:Universidade de Fortaleza, instacron:UNIFOR |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | 5443571202788449035, 500, 500, -7645770940771915222 |
Page generated in 0.006 seconds