An efficient heuristic for minimizing the number of moves for the retrieval of a single item in a puzzle-based storage system with multiple escorts

The Puzzle-Based Storage (PBS) system is an innovative high-density storage system for physical goods, which has the advantage of gravity flow racks in terms of space efficiency and a relatively high accessibility to each unit-load of a variety of personalized goods stored. For the PBS system, among many intricate scheduling problems studied, the minimization of total number of item-moves when retrieving a single item with multiple escorts is an essential building block for its operation. To tackle this problem, we propose a hybrid approach that combines state appraisal, neighborhood search, and beam search. Our numerical experiments on a large number of benchmark instances show that, compared with the results of these instances provided by the best existing heuristic with computational complexity of O ( n 4 ) , our algorithm with different computational complexity settings can improve the overall average solution accuracy from 1.096% to 0.055% by its setting of O ( n 3 ) , or to 0.570% by its setting of O ( n ) , where n is the size of the PBS system. For PBS systems that are more in line with the actual storage density, our algorithm shows stronger robustness by improving the accuracy from 1.086% to 0.026% by its setting of O ( n 3 ) , or to 0.249% by its setting of O ( n ) . The significant improvement in efficiency and accuracy of our algorithm for this basic problem makes its industrial applications in PBS systems promising.