Abstract: Puzzle-based storage (PBS) is an emerging compact storage system where each cell is empty or occupied by an item, and each item can be moved to its adjacent empty cells. Under the single-load movement assumption, some existing exact and heuristic algorithms have enabled the minimum number of moves for the single-item retrieval problem in a puzzle-based storage system with multiple escorts (SRPME). Nevertheless, they failed to effectively optimize the retrieval time, which is a critical indicator of system throughput. In this article, both movement cost and retrieval time are taken into account in the SRPME. Based on a solution obtained by the existing algorithms for solving the single-item retrieval problem in PBS system with multiple escorts, an optimal algorithm considering parallel movement is designed, that is, to reduce the moving time of the item retrieval while keeping the number of item-moves unchanged. The proposed algorithm is based on the idea of implicit enumeration, and it only judges the parallelism between the first move of each escort during each iteration. Extensive numerical experiments were used to evaluate the impact of parallel movement and the algorithm’s performance, where the system size of the instances ranged from 4×4 to 30×30. The results show that the parallel movement saves an overall of more than 10% in retrieval time, and the number of O-move and the actual number of escorts used are the main factors affecting parallel movement. The average optimization ratio increases as the size of the system grows, while its marginal value decreases. The proposed method has good computational performance in small to medium-size issues, which can be seen as a good choose in a large variety of future applications of the PBS systems.

Key words: automated warehouse, Puzzle-based storage system, retrieval time, parallel movement, optimal algorithm