| Compartilhamento |
|
Exportar este item:
Use este identificador para citar ou linkar para este item:
http://www.bdtd.uerj.br/handle/1/7727| Tipo do documento: | Dissertação |
| Título: | Meta-heurísticas para o problema de empacotamento 2D e 3D |
| Título(s) alternativo(s): | Metaheuristics for the 2D and 3D bin packing problem |
| Autor: | Moraes, Anderson Zudio de  |
| Primeiro orientador: | Pinto, Paulo Eustáquio Duarte |
| Primeiro coorientador: | Coelho, Igor Machado |
| Primeiro membro da banca: | Oliveira, Fabiano de Souza |
| Segundo membro da banca: | Szwarcfiter, Jayme Luiz |
| Terceiro membro da banca: | Ochi, Luiz Satoru |
| Resumo: | O problema de empacotamento consiste em empacotar, ortogonalmente e sem sobreposição, um conjunto de itens na menor quantidade de caixas possível. As versões bi e tridimensional do problema generalizam o caso bem conhecido unidimensional, um dos primeiros problemas da classe NP-Difícil. Esta dissertação estuda a versão clássica dos problemas de empacotamento bidimensional e tridimensional, considerando os casos com itens de orientação fixa e com rotação. O problema tem várias aplicações industriais, e o caso de orientação fixa se relaciona a outros problemas complexos como os de corte, repartição e agendamento. Várias heurísticas são propostas e combinadas com metaheurísticas para resolver instâncias de grande porte do problema com soluções de boa qualidade. Extensivos testes computacionais são realizados com 820 instâncias padrões utilizadas em vários trabalhos na literatura. Os resultados computacionais obtidos pela melhor abordagem deste trabalho, denominada BRKGA-VCD, demonstram que o método proposto obtém soluções de qualidade superior ou equivalente aos algoritmos estado da arte encontrados na literatura, melhorando o melhor resultado conhecido para este conjunto de instâncias |
| Abstract: | The bin packing problem consists of orthogonally packing a set of boxes into the minimum number of bins without overlap. The two and three-dimensional bin packing problem generalizes the well known unidimensional bin packing problem, which was characterized as NP-Hard in the beginning of NP-C Theory. This dissertation studies the classic versions of two and three-dimensional case of bin packing with fixed and non-fixed orientated boxes. The bin packing problem has many industrial applications and relates to other complex problems like cutting, repartitioning and scheduling. This work proposes heuristics combined with metaheuristics to devise good quality solutions for large-scale instances. This work presents extensive computational tests with 820 standard literature instances. The computational results devised by the best algorithm proposed, called BRKGA-VCD, demonstrate that this method produces equivalent or better solution compared to state-of-art algorithms found in the literature, improving the overall best known solution quality for this set of instances |
| Palavras-chave: | Metaheuristics Two-dimensional Bin Packing Three-dimensional Bin Packing Single bin-size Meta-heurística Empacotamento bidimensional Empacotamento tridimensional Contêiner de tamanho único Algoritmos computacionais Computação - Matemática Embalagens |
| Área(s) do CNPq: | CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO |
| Idioma: | por |
| País: | BR |
| Instituição: | Universidade do Estado do Rio de Janeiro |
| Sigla da instituição: | UERJ |
| Departamento: | Centro de Tecnologia e Ciências::Instituto de Matemática e Estatística |
| Programa: | Programa de Pós-Graduação em Ciências Computacionais |
| Citação: | MORAES, Anderson Zudio de. Meta-heurísticas para o problema de empacotamento 2D e 3D. 2018. 124 f. Dissertação (Mestrado em Modelagem matemático-estatístico-computacional) - Universidade do Estado do Rio de Janeiro, Rio de Janeiro, 2018. |
| Tipo de acesso: | Acesso Aberto |
| URI: | http://www.bdtd.uerj.br/handle/1/7727 |
| Data de defesa: | 19-Fev-2018 |
| Aparece nas coleções: | Mestrado em Ciências Computacionais |
Arquivos associados a este item:
| Arquivo | Tamanho | Formato | |
|---|---|---|---|
| Anderson Zudio_CComp_Completa.pdf | 1,18 MB | Adobe PDF | Baixar/Abrir Pré-Visualizar |
Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.