An optimal and a heuristic algorithm for the single-item retrieval problem in puzzle-based storage systems with multiple escorts
Authors:
- 4 May 2018
- journal article
- research article
- Published by Taylor & Francis in International Journal of Production Research
- Vol. 57 (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.Keywords
Funding Information
- Hesse's Ministry of Higher Education (HA 422/14-32, HA 405/13-44)
This publication has 15 references indexed in Scilit:
- Retrieval time performance in puzzle-based storage systemsJournal of Manufacturing Technology Management, 2015
- Heuristics for puzzle-based storage systems driven by a limited set of automated guided vehiclesJournal of Intelligent Manufacturing, 2010
- Puzzle‐based storage systemsNaval Research Logistics (NRL), 2007
- Using Board Puzzles to Teach Operations ResearchINFORMS Transactions on Education, 2007
- PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computationTheoretical Computer Science, 2005
- Rush Hour is PSPACE-complete, or “Why you should generously tip parking lot attendants”Theoretical Computer Science, 2001
- Playing Games with Algorithms: Algorithmic Combinatorial Game TheoryLecture Notes in Computer Science, 2001
- Criticizing solutions to relaxed models yields powerful admissible heuristicsInformation Sciences, 1992
- Depth-first iterative-deepeningArtificial Intelligence, 1985
- A note on two problems in connexion with graphsNumerische Mathematik, 1959