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

Abstract

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.

Keywords:

• Puzzle-based storage system
• block movement
• simultaneous movement of multiple empty cells
• shortest unimpeded retrieval

Acknowledgments

The authors would like to thank the DE and anonymous reviewers for their comments and suggestions that help improve this paper significantly.

Additional information

Funding

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).

Notes on contributors

Hu Yu

Hu Yu is a post-doctoral researcher at the Department of Management Science and Engineering, School of Management, University of Science and Technology of China (USTC). He received his BS degree in information and computing science from Wuhan University of Technology, and his PhD degree in management science and engineering from USTC. His current research interests are warehousing, combinatorial optimization, and algorithm design.

Yugang Yu

Yugang Yu is executive dean and yangtze scholar distinguished professor of logistics and operations management at the University of Science and Technology of China (USTC). He received his PhD in management science and engineering from USTC in 2003. His current research interests are warehousing, supply chain management, business analytics and business optimization. He has published more than 100 papers in academic journals such as Manufacturing & Service Operations Management, Productions and Operations Management, Transportation Science, and IISE Transactions.

René de Koster

René de Koster is a professor of logistics and operations management at Rotterdam School of Management, Erasmus University, and chairs the Department of Technology and Operations Management. He holds a PhD from Eindhoven University of Technology (1988). His research interests are warehousing, material handling, and behavioral operations. He is the founder of the Material Handling Forum (www.rsm.nl/mhf) and is author/editor of eight books and over 200 papers in books and academic journals. He is associate editor of Transportation Science, Service Science, and Operations Research.