Sorting algorithms for autonomously organized block stacking warehouses

Thumbnail Image

Date

2023

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Block stacking storage systems are a very simple and widely used type of warehouse, where unit loads like pallets, boxes, containers, or movable shelves are placed on the ground and may be stacked atop one another. The advantages of block storage are that it is highly flexible, easily scalable, and mobile, without requiring large investments in infrastructure. Autonomous mobile robots (AMRs) are increasingly used to automate operations in such storage systems. However, even though automated block stacking warehouses can be very efficient, they still lack characteristics such as the adaptability and creativity of human operators. This thesis introduces a vision of autonomously organized block stacking storage systems that integrate the advantageous characteristics of both automated and manually operated warehouses. We describe the related major operational decision problems, but because it would exceed the scope of this paper to consider all such decision problems, we select one of the most interesting, namely the unit-load pre-marshalling problem (UPMP), and study it in depth. The UPMP deals with sorting such a system in off-peak hours to prepare for future orders and hence allows making use of the constant availability of AMRs. The goal is to sequence all stored unit loads in ascending order based on the retrieval priority group of each unit load. A similar problem is the container pre-marshalling problem in maritime transportation, where each stack is accessible from the top via a crane. In the case of the UPMP, a bay (storage area consisting of multiple columns and rows of stacks) is accessed by AMRs from the side, from as many as four access directions. We present a novel two-step solution approach that is able to consider multiple access directions. In the first step we determine the access direction to each stack based on a network flow model, which allows us in the second step to adapt an existing optimal tree-search procedure and lower bound heuristics from container pre-marshalling. Our solution approach is first tested on different sizes of single-bay experiments. In a second step, we extend and improve our approach and demonstrate its practicality on larger multi-bay block stacking warehouses containing multiple columns and rows of bays. Both experiments on randomly generated problem instances show that multiple access directions greatly improve the access times to storage locations and the overall sorting effort. We outline the need for a future long-term research program related to pre-marshalling and other interrelated decision problems to deal with the associated challenges in block stacking storage systems

Description

Table of contents

Keywords

Block storage, Warehouse robotics, Sorting algorithms, Reshuffling

Citation