EURO 2025 Leeds
Abstract Submission

1509. Exploiting GPU capabilities for voxel-based approaches to the 3D Irregular Strip Packing Problem

Invited abstract in session MD-21: 3D Packing, stream Cutting and packing (ESICUP).

Monday, 14:30-16:00
Room: Esther Simpson 2.12

Authors (first author is the speaker)

1. Alessio La Greca
Computer Science, KU Leuven
2. Jonas Tollenaere
NUMA, KU Leuven
3. Tony Wauters
Computer Science, KU Leuven

Abstract

The 3D Irregular Strip Packing Problem is a generalization of the Strip Packing Problem. Given a three-dimensional container of given width and depth but unconstrained height, the problem involves packing a given set of items into this container so that its total height is minimized. The items are not limited to being convex in shape and can have holes. Heuristic and metaheuristic approaches that tackle the problem require building solutions where no pair of items overlap. There are two methods that are commonly used to handle this constraint: one that explicitly takes into account the items' geometry and another that approximates items into simpler shapes by means of voxels. In this work, we consider the latter. While such approaches have received increasing attention in recent years, there has been a lack of research which considers their scalability on modern GPUs. We therefore propose three different voxelization approaches. The first one makes straightforward use of voxels to check for overlapping. The second builds atop the first by adding a Sparse Voxel Octree data structure. The third approach is based on recent advances and leverages the concept of the No-Fit Voxel. A metaheuristic is also proposed to show the speedup granted by the GPU implementations in terms of number of solutions explored, and to compare their performance. The preliminary results we present will demonstrate the potential of GPU integration into voxel-based algorithms to improve execution times.

Keywords

Status: accepted

Back to the list of papers