Autor(es): Pires, Ricardo Morgado
Data: 2012
Identificador Persistente: http://hdl.handle.net/10400.22/7569
Origem: Repositório Científico do Instituto Politécnico do Porto
Assunto(s): Problema de Empacotamento de Contentor; Heurísticas; Algoritmo Genético; Container Packaging Problem; Heuristics; Genetic Algorithm; Sistemas de Planeamento e Industrial
No âmbito da investigação operacional o problema de empacotamento de contentores é conhecido por procurar definir uma configuração de carga, de forma a otimizar a utilização de um espaço disponível para efetuar o empacotamento. Este problema pode ser apresentado em diversas formas, formas estas que variam em função das características de cada empacotamento. Estas características podem ser: o tipo de carga que se pretende carregar (homogénea ou heterogénea), a possibilidade de a carga poder sofrer rotações em todas as suas dimensões ou apenas em algumas, o lucro que está associado a cada caixa carregada ou restrições inerentes ao contentor como por exemplo dimensões. O interesse pelo estudo de problemas de empacotamento de contentores tem vindo a receber cada vez mais ênfase por várias razões, uma delas é o interesse financeiro dado que o transporte é uma prática que representa custos, sendo importante diminuir estes custos aproveitando o volume do contentor da melhor forma. Outra preocupação que motiva o estudo deste problema prende-se com fatores ambientes, onde se procura racionalizar os recursos naturais estando esta também ligada a questões financeiras. Na literatura podem ser encontradas varias propostas para solucionar este problema, cada uma destas dirigidas a uma variante do problema, estas propostas podem ser determinísticas ou não determinísticas onde utilizam heurísticas ou metaheurísticas. O estudo realizado nesta dissertação descreve algumas destas propostas, nomeadamente as metaheurísticas que são utilizadas na resolução deste problema. O trabalho aqui apresentado traz também uma nova metaheurísticas, mais precisamente um algoritmo genético que terá como objetivo, apresentar uma configuração de carga para um problema de empacotamento de um contentor. O algoritmo genético tem como objetivo a resolução do seguinte problema: empacotar várias caixas retangulares com diversos tamanhos num contentor. Este problema é conhecido como Bin-Packing. A novidade que este algoritmo genético vai introduzir nas diversas soluções apresentadas até à data, é uma nova forma de criar padrões iniciais, ou seja, é utilizada a heurística HSSI (Heurística de Suavização de Superfícies Irregulares) que tem como objetivo criar uma população inicial de forma a otimizar o algoritmo genético. A heurística HSSI tenta resolver problemas de empacotamento simulando, o comportamento da maioria das pessoas ao fazer este processo na vida real, contudo, tem um campo de busca reduzido entre as soluções possíveis e será então utilizado um algoritmo genético para ampliar este campo de busca e explorar novas soluções. No final pretende-se obter um software onde será possível configurar um dado problema de empacotamento de um contentor e obter, a solução do mesmo através do algoritmo genético. Assim sendo, o estudo realizado tem como principal objetivo contribuir com pesquisas e conclusões, sobre este problema e trazer uma nova proposta de solução para o problema de empacotamento de contentores.
As part of the operational research the problem of load packing containers is known to try to define a configuration load, to optimize the use of available space to make the packaging. This problem can be presented in several forms, these forms could be according to the characteristics of each packaging. These characteristics may include: the type of load which is intended load (homogeneous or heterogeneous), the possibility of the load can undergo rotations in all its forms or in only some, the profit is associated with each box loaded or restrictions inherent such as container dimensions. Interest in the study of container packing problems has received increasing emphasis for several reasons, one of which is the financial interest given that transportation is a practice that represents costs being important to reduce these costs by taking advantage of the volume of container best. Another concern that motivates the study of this problem is related to environmental factors, which seeks to rationalize natural resources this also being linked to financial issues. Can be found in the literature several proposals to solve this problem, each of these led to a variant of the problem, these proposals can be deterministic or nondeterministic where use heuristics or metaheuristics. The study in this thesis describes some of these proposals, particularly the metaheuristics that are used to solving this problem. The work presented here also brings a new metaheuristics, specifically a genetic algorithm that will aim to present a load configuration for a problem of packing a container. The genetic algorithm aims at solving the following problem: packing rectangular boxes with several different sizes in a container. This problem is known as Bin-Packing. The novelty of this genetic algorithm will introduce the various solution presented to date, is a new way to create initial patterns, HSSI is used heuristics (Heuristics Smoothing Irregular surfaces) that aims to create an initial population of order to optimize the genetic algorithm. The HSSI heuristic tries to solve packing problems simulating the behavior of most people to do this process in real life, however, has a search field between small and possible solutions will be then used a genetic algorithm to extend the search field and explore new solutions. At the end it is intended to obtain software where it is possible to configure a given problem of a packaging container and obtain the solution of the same through the genetic algorithm. Thus, the study's main objective is to contribute to research and conclusions on this issue and bring a new proposal for a solution to the problem of packaging containers.
