A Partial Depth-Search Heuristic for Packing Spheres

Abstract: This paper proposes a new heuristic for packing non-identical spheres into a three-dimensional container of fixed dimensions. Given a set that contains n spheres, the objective is to place a subset of spheres so as to maximize the volume occupied by these ones. The proposed heuristic is based on an idea that applies a two-level look-forward search. The computational investigation indicates that the heuristic is effective since it improves most of the best known results in the literature on the used instances.