Tzvika Geft, Rutgers University

Abstract

Grid-based storage systems with uniformly shaped loads (e.g., containers,pallets, or totes) are prevalent in logistics, industrial, and transportation domains. They are increasingly optimized and automated via the incorporation of robotics solutions. A key performance metric for such systems is the maximization of storage space utilization, which typically requires some loads to be placed deeply behind or below others, preventing direct access to them. Consequently, dense storage settings bring up the challenge of determining how to place loads while minimizing costly rearrangement efforts necessary during load retrieval. We consider a setting that involves two phases: an inbound phase, during which loads arrive, followed by an outbound phase, during which loads depart. This setting is prevalent in distribution centers, automated parking garages, and container ports. In both phases, minimizing the number of rearrangement actions results in fast and energy-efficient operation. In contrast to previous work focusing on stack-based systems, this effort examines the case where loads can be freely moved along the grid, e.g., by a mobile robot, expanding the range of possible motions. While fully online scenarios (without prior arrival/departure knowledge) force a trade-off between density and rearrangement, we show that even partial arrival/departure sequence information enables simultaneously achieving (near-)zero rearrangement and full-capacity storage. In particular, when the sequences are fully known, we establish an intriguing characterization showing that rearrangement can always be avoided if and only if the open side of the grid (used to access storage) is at least 3 cells wide. We also discuss useful practical implications of our solutions.

See: https://theory.cs.rutgers.edu/theory_seminar