Tree search for the stacking problem

• Tipo: Artigo em Revista Científica Internacional
• Data: 2013

Autores

Rui Rei (Autor) Outra; Joao Pedro Pedroso (Autor) FCUP

Revista

Título: Annals of Operations Research

Vol. 203

Páginas: 371-388

ISSN: 0254-5330

Editora: Springer Nature

Indexação

ISI Web of Knowledge - 20 Citações

Scopus - 30 Citações

Classificação Científica

FOS: Ciências da engenharia e tecnologias > Biotecnologia industrial

Outras Informações

ID Authenticus: P-002-04R

DOI: 10.1007/s10479-012-1186-2

Abstract (EN): The stacking problem is a hard combinatorial optimization problem with high practical interest in, for example, steel storage or container port operations. In this problem, a set of items is stored in a warehouse for a period of time, and a crane is used to place them in a limited number of stacks. Since the entrance and exit of items occurs in an arbitrary order, items may have to be relocated in order to reach and deliver other items below them. The objective of the problem is to find a feasible sequence of movements that delivers all items, while minimizing the total number of movements. We study the scalability of an exact approach to this problem, and propose two heuristic methods to solve it approximately. The two heuristic approaches are a multiple simulation algorithm using semi-greedy construction heuristics, and a stochastic best-first tree search algorithm. The two methods are compared in a set of challenging instances, revealing a superior performance of the tree search approach in most cases.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 18