Geometry Seminar

---

Fully Packed and Ready to Go: High-Density, Rearrangement-Free, Grid-Based Storage and Retrieval

Speaker: Tzvika Geft, Rutgers

Location: Warren Weaver Hall 1314

Videoconference link: https://youtu.be/ok4c-BLxyyQ

Date: Tuesday, September 30, 2025, 6 p.m.

Synopsis:

We consider an ordered storage and retrieval problem: a set of uniform-sized, labeled loads (e.g., containers, pallets, or totes) must be placed in a 2D grid storage area as they arrive sequentially, and then be retrieved in some (possibly different) order. Each load occupies a grid cell and may be moved, e.g., by a robot, along the cardinal directions. Such storage systems arise in logistics, industrial, and transportation domains, where space utilization and retrieval time are critical metrics. To maximize space utilization, loads must be densely packed with some loads blocking access to others, which raises a key question: How should one store the loads to minimize costly rearrangements, i.e., number of relocated loads, during retrieval?

We identify conditions, alongside efficient algorithms, for achieving either zero or near-optimal rearrangements under different knowledge assumptions. While the online case (i.e., no prior knowledge of the storage and retrieval sequences) induces a trade-off between density and rearrangement, we show that even partial prior knowledge essentially eliminates the trade-off. When sequences are fully known, we further provide an intriguing characterization: rearrangement can always be eliminated if the grid’s open side (used to access the loads) is at least 3 cells wide, even for full capacity storage. We also discuss other practical properties of our solutions.

This is a joint work with Kostas Bekris and Jingjin Yu.

Notes:

In person.  Plz contact Boris Aronov for if you are not NYU-affiliated and want to attend in person.
Also on Zoom.  Contact the same person to be put on the mailing list and get the Zoom information.