Storage Systems with Very High Density
One problem with increasing the amount of stuff in a space is that it takes longer to get things out (think your garage, or your bedroom closet, or the ship above). For some systems, it might be necessary to move interfering items to get to a requested item. We say that such systems have very high density.
Here is a simple (and fun) problem I first worked on during a … ahem … less-than-exciting faculty meeting: Given a rectangular grid of squares, what is the maximum number of items you can store, such that every item is retrievable by moving no more than k-1 interfering items? Here is an example:
Each grid shows an arrangement of items such that every item is no more than k spaces away from an “aisle,” for k=1, 2, 3, and 4. The design for k=1 is optimal. The algorithm that produces these designs is simple enough to teach a child, yet it has never been shown to produce less than an optimal solution. (But I could not prove it optimal either!) Read more about this work in
- Kevin R. Gue, Very High Density Storage Systems, IIE Transactions 38 (1), 93-104, 2006.
Puzzle-Based Storage Systems
Storage systems with the highest possible density are based on the “slide-puzzle architecture,” which was inspired by the famous 15-puzzle. Below is the real 15-puzzle; to the right is the NAVSTORS storage system proposed to the Navy by Agile Systems, a robotics developer in Ohio.
We have developed algorithms that show how to move items within such a system to move a requested item to a “pickup and deposit” point on the boundary. For the case of a single open space, we have an optimal algorithm. We also have an algorithm for the case of multiple open spaces. For details, check out our paper,
- Kevin R. Gue and Byung Soo Kim, Puzzle-Based Storage Systems, Naval Research Logistics 54 (5), 556-567, 2007.
This research has served as inspiration for a new paradigm in material handling we call Grid-Based Intralogistics.