Tree search for the stacking problem

• Type: Article in International Scientific Journal
• Date: 2013

Authors

Rui Rei (Author) Other; Joao Pedro Pedroso (Author) FCUP

Journal

Title: Annals of Operations Research

Vol. 203

Pages: 371-388

ISSN: 0254-5330

Publisher: Springer Nature

Indexing

ISI Web of Knowledge - 20 Citations

Scopus - 30 Citations

Scientific classification

FOS: Engineering and technology > Industrial biotechnology

Other information

Authenticus ID: 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.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 18