A multi-start random constructive heuristic for the container loading problem
| Autor: | Vinícius Amaral Armentano, Olinto César Bassi de Araújo |
|---|---|
| Rok vydání: | 2007 |
| Předmět: |
Mathematical optimization
Cuboid container loading Selection (relational algebra) heurística construtiva aleatória com múltiplos inícios lcsh:Mathematics Probabilistic logic Volume (computing) Process (computing) Management Science and Operations Research lcsh:QA1-939 multi-start random constructive heuristic Set (abstract data type) Reduction (complexity) Container (abstract data type) cuboid arrangement arranjo com cubóides carregamento de contêiner Mathematics |
| Zdroj: | Pesquisa Operacional v.27 n.2 2007 Pesquisa operacional Sociedade Brasileira de Pesquisa Operacional (SOBRAPO) instacron:SOBRAPO Pesquisa Operacional, Vol 27, Iss 2, Pp 311-331 (2007) Pesquisa Operacional, Volume: 27, Issue: 2, Pages: 311-331, Published: AUG 2007 |
| ISSN: | 0101-7438 |
| DOI: | 10.1590/s0101-74382007000200007 |
| Popis: | This paper deals with the container loading problem which involves the selection of a subset of boxes, each box with a given volume, such that they fit in a single container and maximize its volume utilization subject to orientation and stability constraints. We propose a multi-start random constructive heuristic with a load arrangement that is based on maximal cuboids that fit in given empty spaces. Each instance is adaptively evaluated by a set of criteria, and at each step of the construction process one maximal cuboid is chosen probabilistically from a restricted list of candidates. In order to enhance the flexibility in the construction of a solution, a probabilistic reduction on such cuboids is allowed. Computational tests on several instances from the literature show that the proposed method performs better than other approaches.Neste trabalho abordamos o problema de carregamento de contêiner que trata da seleção de um subconjunto de caixas, cada caixa com um dado volume, de forma a maximizar o volume ocupado de um único contêiner sujeito a restrições de orientação e estabilidade. Propomos uma heurística construtiva aleatória com múltiplos inícios que utiliza um arranjo de carga baseado em cubóides que maximizam a ocupação de espaços vazios. Cada instância é avaliada de forma adaptativa por um conjunto de critérios, e em cada passo do processo construtivo um cubóide é selecionado probabilisticamente de uma lista restrita de candidatos. Para aumentar a flexibilidade na construção de uma solução, permite-se uma redução probabilística no tamanho dos cubóides. Resultados computacionais em instâncias da literatura mostram que o método proposto apresenta um desempenho superior a outros enfoques sugeridos na literatura. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|