The Three-Dimensional Bin Packing Problem

TLDR

The paper tackles orthogonal packing of rectangular items into the fewest 3‑D rectangular bins, a strongly NP‑hard problem. An exact branch‑and‑bound algorithm for a single bin is devised, forming the basis of an exact algorithm for the full 3‑D bin packing problem that also integrates novel approximation methods. The continuous lower bound has an asymptotic worst‑case ratio of 1/8, and experiments on up to 90‑item instances show many can be solved optimally within reasonable time.

Abstract

The problem addressed in this paper is that of orthogonally packing a given set of rectangular-shaped items into the minimum number of three-dimensional rectangular bins. The problem is strongly NP-hard and extremely difficult to solve in practice. Lower bounds are discussed, and it is proved that the asymptotic worst-case performance ratio of the continuous lower bound is 1/8. An exact algorithm for filling a single bin is developed, leading to the definition of an exact branch-and-bound algorithm for the three-dimensional bin packing problem, which also incorporates original approximation algorithms. Extensive computational results, involving instances with up to 90 items, are presented: It is shown that many instances can be solved to optimality within a reasonable time limit.