The effective use of space is a goal for almost every organization. In logistics and transportation, increasing storage density (items per square or cubic foot) allows smaller or less expensive facilities, and it delays the purchase or lease of new facilities as the firm grows. The picture below shows an interesting example on a Navy logistics ship, where supplies and vehicles are stowed for rapid offload to support Marine operations.

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.

Our research addresses two theoretical questions in very high density storage systems. The first is simple to state: 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:

The figure on the right has 61 items stored, and every one is accessible without moving any other item. This is the optimal solution for a 10x10 grid.

We were able to prove a theoretical bound on the storage density of any space, given a constraint on the maximum lane depth (number of items stored one-behind-another per picking location). For a k-deep storage system, the maximum storage density is 2k/(2k+1). So, for example, the maximum density for a warehouse with single-deep storage rack is 2/3. For a double-deep rack, the maximum density is 4/5, and so on.

For more information on this problem, see my paper,

1. ‣Kevin R. Gue, Very High Density Storage Systems, IIE Transactions 38 (1), 93-104, 2006.
   

To see how our algorithm packs grids of different sizes, check out our Interactive High Density Storage Page.

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.  On the left below is (you guessed it) the real 15-puzzle.  To the right is a 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,

1. ‣Kevin R. Gue and Byung Soo Kim, Puzzle-Based Storage Systems, Naval Research Logistics 54 (5), 556-567, 2007.

Sponsored by the Office of Naval Research

and the

National Science Foundation