An Improvement of Retrieval Time for Puzzle-Based Storage System Considering Parallel Movement and Block Movement

Puzzle-based storage (PBS) is an emerging compact storage system in which items are scheduled in a similar way to a puzzle game. 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. Nevertheless, the retrieval of target item should also be accomplished as rapidly as possible. The retrieval optimizing process can be divided into two phases and our work focuses on the second. In the first phase, the number of moves is minimized by existing algorithms with the single-load movement assumption. In the second phase, the retrieval time of target item is shortened by parallel and block movement technologies based on the solution from the first phase. First, we develop an exact algorithm for the scenario when only parallel movement is considered, and present an integer linear programming (ILP) formulation to verify the optimality of the algorithm. Then, we provide a heuristic algorithm for the case where parallel and block movements are considered simultaneously. The computational complexities of the proposed two algorithms are both , where is the size of the grid. Extensive experiments demonstrate that parallel movement and simultaneous movement decrease the overall retrieval time by more than 13% and 20%, respectively. The two-phase method, as a local optimal solution, has advantages in solving medium to large-size issues. Compared to the global optimal solutions of the existing literature, the method has small average solution gaps and much less CPU time consumption in small-size systems. The proposed method can be seen as a good compromise in a large variety of future applications of the PBS systems