A fast heuristic for a three-dimensional non-convex domain loading problem

In this paper we tackle a three-dimensional non-convex domain loading problem. We have to efficiently load identical small boxes into a highly irregular non-convex domain. The boxes to be loaded have a particular shape. If d is the length of the smallest edge of the box, its dimensions are d × nd × md, n ≤ m, with n and m integer values. This loading problem arises from an industrial design problem where it is necessary to obtain good solutions with very low computation time. We propose a fast heuristic based on an approximate representation of the non-convex domain in terms of cubes of dimension d and on the decomposition of the whole problem in several two-dimensional subproblems related to ‘planes’ of height d. The proposed heuristic shows good performances in terms of quality of solution and computation times. The results on several real test cases, coming from the industrial application, are shown.