Optimal retrieval in puzzle-based storage systems using automated mobile robots

Tal Raviv*, Yossi Bukchin, Rene de Koster

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

2 Citations (Scopus)


Puzzle-based storage (PBS) systems store unit loads at very high density, without consuming space for transport aisles. In such systems, each load is stored on a moving device (conveyor module or transport vehicle), making these systems very expensive to build and maintain. This paper studies a new type of PBS system where loads are moved by a small number of autonomous mobile robots (AMRs). The AMRs (or vehicles) can travel freely underneath loads and lift a specific load and carry it to a neighboring vacant space. These systems are hard to analyze, as all the AMRs can move simultaneously with or without loads. We formulate an integer linear programming model that minimizes the retrieval time and the number of load and vehicle movements. The proposed model can handle single-load movements as well as block movements, multiple input/output points, and various constraints on simultaneous vehicle movements. The integer linear programming formulation can solve relatively small problems (a grid with up to about 50 cells) and a sufficient number of empty cells. For larger systems or those with few empty cells, a three-phase heuristic (3PH) is developed, which significantly outperforms the heuristic methods known to date and solves large instances sufficiently fast. The 3PH and an additional hybrid heuristic yield relatively small gaps from a lower bound provided by the integer linear programming model. We find that increasing the number of vehicles has a diminishing return effect on the retrieval times. Using a relatively small number of vehicles makes retrieval times only slightly longer than those obtained when having a vehicle under each load (which is equivalent to the traditional PBS systems). With single-load movement, more vehicles are needed compared with block movement to reach short retrieval times. Also, the marginal contribution of extra empty slots appears to decrease rapidly, which implies high storage densities can be obtained in practice.

Original languageEnglish
Pages (from-to)424-443
Number of pages20
JournalTransportation Science
Issue number2
Publication statusPublished - 2023

Bibliographical note

Funding Information:
We would like to acknowledge the help of the Academy of Rehabilitation Research and Prof. Dr. Sc. Vlatki Mejaški Bošnjak, MD. and thank her for assistance in conducting research. Our gratitude is extended to Dr. Sc. Mirni Kostović Srzentić, prof. for the initial presentation of the project and for connecting the members of the team for this project. We are grateful to dr. Dianne Russell for valuable advice, practical suggestions and the time to review the translation of the GMFM test. Thanks should also go to all the participants who took their time to help us conduct this research.

Publisher Copyright:
© 2023 INFORMS.


Dive into the research topics of 'Optimal retrieval in puzzle-based storage systems using automated mobile robots'. Together they form a unique fingerprint.

Cite this