New Interactive and Heuristic Approaches to 2D Rectangular Strip Packing

In this paper, we consider the two-dimensional rectangular strip packing problem. This problem appears unamenable to standard local search techniques, such as simulated annealing or genetic algorithms. A standard simple heuristic, Bottom-Left-Decreasing (BLD), has been shown to handily beat these more sophisticated search techniques.

We introduce and demonstrate the effectiveness of BLD*, a stochastic search variation of BLD. While BLD places the rectangles in decreasing order of height, width, area, and perimeter, BLD* successively tries random orderings, chosen from a distribution determined by their Kendall-tau distance from one of these fixed orderings. Our experiments on benchmark and randomly generated problems show that BLD* produces significantly better packings than BLD after only 1 minute of computation.

Furthermore, we observe that people seem able to reason about packing problems extremely well. We incorporate our new algorithms in an interactive system that combines the advantages of computer speed and human reasoning. Using the interactive system, we are able to quickly produce significantly better solutions than previous methods on benchmark problems.