A comprehensive toolbox for load retrieval in puzzle-based storage systems with simultaneous movements

Puzzle-based storage (PBS) is one of the most space-efficient types of storage systems. In a PBS unit, loads are stored in a grid of cells, where each cell may be empty or contain a load. A load can move only to adjacent empty cells. These cells are termed escorts in the literature, and their number is relatively small. When a load is requested for retrieval, a sequence of load movements is performed in order to bring it to an input/output (I/O) point of the unit. In this paper we minimize a weighted sum of two objectives. The first is the retrieval time of a requested item, and the second objective is the number of moves. While the first objective is associated with the quality of service, the second objective considers energy saving. Note that this operational problem should be solved quickly for every load request. The movement characteristics of loads in the PBS unit are determined by the technology used for its operation. In the most general and intricate case, simultaneous movements of blocks of loads can be performed, while simpler technology may allow only sequential movements or simultaneous movement of single loads. PBS units may also have one or several I/O points. In the latter case, the load may be retrieved via any one of the I/O points, based on the operator’s discretion. In this paper, we suggest a suite of complementary tools to solve load retrieval problems under various technology, including simultaneous block and load movements. First, we present a time-expanded-graph based integer linear-programming (ILP) formulation. This formulation provides optimal solutions for problems with a relatively large number of escorts and obtains lower bounds for other cases. For problems with a small number of escorts, we suggest a dynamic programming (DP) solution approach. A custom-made heuristic based on the DP approach was developed for the rest of the cases. Experiments show that our solution approaches’ ensemble yields optimal or near-optimal solutions to most of our benchmark instances.