Voxelization-Based Variable Neighborhood Tabu Search Strategy for Three-Dimensional Irregular Strip Packing

This paper proposes an efficient algorithm that integrates a variable neighborhood search (VNS) framework with an adaptive voxel discretization for the three-dimensional irregular packing problem. The problem arises in additive manufacturing, logistics loading, and other fields, especially in strip packing scenarios where the filling length in a virtual container with a fixed cross-section and infinite length is to be minimized. The algorithm first discretizes continuous three-dimensional geometric models into Boolean voxel matrices, thereby transforming complex geometric interference detection into efficient logical operations. An initial solution is generated using a greedy “largest-volume-first” strategy. An innovative adaptive voxel precision adjustment mechanism is introduced to dynamically modify the discretization granularity according to the current filling rate, realizing a hierarchical solution strategy of “coarse-grained fast search + fine-grained precise optimization”. On this basis, a variable-neighborhood iterative framework based on tabu search (TS-VNS) is constructed. Three complementary neighborhood operators are designed: single-item reinsertion, block exchange, and rotation perturbation, together with an adaptive operator selection mechanism driven by historical contributions. Experiments on multiple standard instances of varying scales and complexities (e.g., miniature chess pieces and engine components) show that the proposed algorithm outperforms comparative methods in both packing height and average height, achieving a favorable balance between solution efficiency and stability. Thus, it provides a reliable and efficient approach for the practical engineering application of three-dimensional irregular packing.