Multi-shuttle crane scheduling in automated storage and retrieval systems

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.