An optimal and a heuristic algorithm for the single-item retrieval problem in puzzle-based storage systems with multiple escorts

Altan Yalcin, Achim Koberstein and Kai-Oliver Schocke

International Journal of Production Research, 2019, vol. 57, issue 1, 143-165

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.

Date: 2019
References: Add references at CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://hdl.handle.net/10.1080/00207543.2018.1461952 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:taf:tprsxx:v:57:y:2019:i:1:p:143-165

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/TPRS20

DOI: 10.1080/00207543.2018.1461952

Access Statistics for this article

International Journal of Production Research is currently edited by Professor A. Dolgui

More articles in International Journal of Production Research from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().