Paper Info
Title
An Optimal And A Heuristic Algorithm For The Single-Item Retrieval Problem In Puzzle-Based Storage Systems With Multiple Escorts
Abstract
Puzzle-based storage systems consist of densely stored unit loads on a square grid. The problem addressed in this paper is to retrieve a stored unit load from a puzzle-based storage using the minimum number of item moves. While previous research contributed optimal algorithms for only up to two empty locations (escorts), our approach solves configurations where multiple empty locations are arbitrarily positioned in the grid. The problem is formulated as a state space problem and solved to optimality using an exact search algorithm. To reduce the search space, we derive bounds on the number of eligible empty locations and develop several search-guiding estimate functions. Furthermore, we present a heuristic variant of the search algorithm to solve larger problem instances. We evaluate both solution algorithms on a large set of problem instances. Our computational results show that the algorithms clearly outperform existing approaches where they are applicate and solve more general configurations, which could not be solved to optimality before. The heuristic variant efficiently yields high-quality solutions for significantly larger instances of practically relevant size.
Year
DOI
Venue
2019
10.1080/00207543.2018.1461952
INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH
Keywords
DocType
Volume
puzzle-based storage, compact storage systems, automated warehouse, combinatorial optimisation problem, A* algorithm
Journal
57
Issue
ISSN
Citations 
1
0020-7543
2
PageRank 
References 
Authors
0.41
9
3
Name
Order
Citations
PageRank
Altan Yalcin120.41
Achim Koberstein2809.48
Kai-Oliver Schocke320.41