Multi-shuttle crane scheduling in automated storage and retrieval systems

Lukas Polten and Simon Emde

European Journal of Operational Research, 2022, vol. 302, issue 3, 892-908

Abstract: We study a shared-storage automated storage and retrieval system (AS/RS) with one crane capable of carrying multiple unit loads. In a shared-storage system, items to be stored are not pre-assigned to dedicated shelf spaces. Therefore, given a set of storage and retrieval requests, the crane scheduling problem consists of deciding which requests are processed together in the same tour, determining the sequence in which the requests are processed, and assigning each storage request to an available slot on the shelf. We reformulate the problem as a special type of capacitated vehicle routing problem, which we use to close some open questions regarding the time complexity of related geometric routing problems. The reformulation allows us to tap into the rich and mature vehicle routing toolbox from the literature to propose a new exact solution approach. We show that this method is capable of solving large instances to optimality, outperforming previous methods from the literature. We use our new approach to derive multiple insights. Specifically, we show that system throughput can be predicted from the capacity of the crane via a simple rule. We also determine the optimal shape of a shelf and investigate the value of having knowledge of multiple requests when planning the crane schedule. Finally, we demonstrate that our approach can easily be extended to solve a whole family of multi-shuttle crane scheduling problems.

Keywords: Scheduling; Automated storage and retrieval system; Multi-shuttle crane scheduling; Vehicle routing problem; Complexity analysis (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/S0377221722000819
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:302:y:2022:i:3:p:892-908

DOI: 10.1016/j.ejor.2022.01.043

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 ().