Made available in DSpace on 2019-03-30T00:01:35Z (GMT). No. of bitstreams: 0
Previous issue date: 2015-01-27 / This work presents a block-loading hybrid approach to solve the Container Loading Problem. The general idea behind the proposed algorithm is to decompose this classic Cutting and Packing problem into two subproblems, namely, a three-dimensional problem of generating a set of blocks of boxes and a two-dimensional problem of positioning a subset of these blocks on the floor of the container. On the one hand, the block generation phase is completely deterministic. Constructive algorithms to accomplish this task have been recently proposed. On the other hand, the positioning phase is non-deterministic. It comprises the Generate-and-Solve methodology, a hybrid optimization framework that combines a metaheuristic engine with an exact solver. Computational experiments performed on benchmark problem instances show that hybrid approach presents very competitive results compared to those found by state-of-the-art algorithms, obtaining in average a space utilization of 93.49% for the instances under investigation. Regarding only the best solution found for each instance, the space utilization was of 94.13% in average. In particular, for instances with a few number of box types, the proposed approach outperformed the best results reported in the literature in several test cases.
Key-words: Combinatorial Optimization. Cutting and Packing. Container Loading. HybridMetaheuristics. / Este documento apresenta uma abordagem híbrida de posicionamento de blocos para resolver o Problema de Carregamento de Contêiner. A ideia central do algoritmo proposto é decompor esse clássico problema de Corte e Empacotamento em dois subproblemas: um problema de empacotamento tridimensional que objetiva gerar blocos de caixas; e um problema de posicionamento bidimensional no piso do contêiner que busca maximizar o volume ocupado por um subconjunto desses blocos. Por um lado, a fase de geração de blocos é completamente determinística. Algoritmos construtivos que realizam essa tarefa têm sido recentemente propostos. Por outro lado, a fase de posicionamento de blocos é não-determinística. Esta compreende a metodologia híbrida Gerar-e-Resolver, que combina uma metaheurística com um modelo exato. Experimentos computacionais realizados em bibliotecas de testes da literatura mostram que a abordagem híbrida apresenta resultados bastante competitivos em relação àqueles do estado da arte, alcançando aproveitamento médio de 93,49% do espaço do contêiner para as instâncias estudadas. Considerando apenas a melhor solução encontrada para cada instância, o aproveitamento médio foi de 94,13%. Em particular, para instâncias com poucos tipos de caixas, a abordagem superou os melhores resultados conhecidos na literatura em diversos casos de teste.
Palavras-chaves: Otimização Combinatória. Corte e Empacotamento. Carregamento de Contêiner. MetaheurísticasHíbridas.
| Identifer | oai:union.ndltd.org:IBICT/oai:dspace.unifor.br:tede/93415 |
| Date | 27 January 2015 |
| Creators | Saraiva, Rommel Dias |
| Contributors | Nepomuceno, Napoleao Vieira, Pinheiro, Plácido Rogério, Silva, Jose Lassance de Castro, Soma, Nei Yoshihiro, Nepomuceno, Napoleao Vieira |
| 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.0819 seconds