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

Yunfeng Ma, Haoxun Chen and Yugang Yu

European Journal of Operational Research, 2022, vol. 301, issue 1, 51-66

Abstract: 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.

Keywords: Heuristics; Automated warehouses; Compact storage systems; Puzzle-based storage; Beam search (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221721008079
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:301:y:2022:i:1:p:51-66

DOI: 10.1016/j.ejor.2021.09.032

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().