Dense and fast: Achieving shortest unimpeded retrieval with a minimum number of empty cells in puzzle-based storage systems

Hu Yu, Yugang Yu*, René de Koster

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

3 Citations (Web of Science)
20 Downloads (Pure)


This article studies puzzle-based storage (PBS) systems with multiple simultaneously movable empty cells and with block movement (i.e., multiple loads in a line can move simultaneously). Simultaneous movements can potentially reduce the retrieval time substantially, but has not yet been rigorously studied. Our aim is to determine the minimum number of empty cells sufficient for creating a shortest and unimpeded retrieval path for a requested load to the Input/Output (I/O) point at the bottom left corner of the system. We prove that four (or five) empty cells are sufficient for shortest unimpeded retrieval of a load from any interior location (or location on the left or bottom boundary), independent of the system size. This means the vast majority of cells in the system can be utilized for storing loads without any impact on the retrieval time. In addition, constructive optimal algorithms are developed for scheduling four or five empty cells to realize shortest unimpeded retrieval. Interestingly, the requested load’s shortest unimpeded retrieval path to the I/O point may contain upward or rightward movements, even if the I/O point is at the bottom left corner of the system. Compared with systems with one empty cell (sequential movements), systems with four or five empty cells (simultaneous movements) can bring about 70% (50% or more) retrieval time reduction. Furthermore, PBS systems can yield shorter average retrieval time (in addition to their intrinsic advantage of a higher storage density), compared with parallel-aisle unit-load storage systems.

Original languageEnglish
Pages (from-to)156-171
Number of pages16
JournalIISE Transactions
Issue number2
Early online date10 Dec 2021
Publication statusPublished - 2022

Bibliographical note

Funding Information:
This work was supported by the National Natural Science Foundation of China (No.72001200, No.72091215/72091210, and No. 71991464/71991460) and the Fundamental Research Funds for the Central Universities (No. WK2040000044). The authors would like to thank the DE and anonymous reviewers for their comments and suggestions that help improve this paper significantly.

Publisher Copyright:
© Copyright © 2022 “IISE”.


Dive into the research topics of 'Dense and fast: Achieving shortest unimpeded retrieval with a minimum number of empty cells in puzzle-based storage systems'. Together they form a unique fingerprint.

Cite this