Optimal Retrieval in Puzzle-Based Storage Systems Using Automated Mobile Robots

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.