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(n4), 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(n3), 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 ofO(n3), or to 0.249% by its setting ofO(n). The significant improvement in efficiency and accuracy of our algorithm for this basic problem makes its industrial applications in PBS systems promising.