"A sim-heuristic approach for the 3D irregular packing problem"
Germán Fernando Pantoja Benavides and David Álvarez Martínez

The 3D irregular packing problems are part of the combinatorial optimization problems (COP) [1], which have a high mathematical and computational complexity. In addition, these problems have a wide spectrum of applications in the industry where their solutions require to be of high quality and to be obtained in short computational times [2]. 
The problem to tackle in this work is to minimize the volume of a cuboid in which three-dimensional concave polyhedrons of different types are packed, and free rotation of the pieces is allowed. In the typology proposed by Wäsher et al. [3], this problem can be classified as: 
• Dimensionality: three-dimensional. 
• Kind of assignment: input minimization. 
• Assortment of small items: this criterion may vary from weakly heterogeneous assortment to strongly heterogeneous assortment, depending on the nature of the instances. 
• Assortment of large objects: one large object. 
• Shape of small items: irregular.
 
To solve the COP, several methodologies have been proposed that usually involve heuristics, since efficient solutions are obtained with them. Lately, combinations of various techniques have received great popularity especially the mixture of heuristics and simulation called sim-heuristics, due to the increase in computational power and the development of simulation software. 

In this work, a tool based on a sim-heuristic is developed using Unity®, a video game engine. Unity® incorporates colliders, a tool that can verify the overlapping between pieces and between piece-cuboid. Besides, Unity® allows programming heuristics based on movements, collisions, and forces that provide a convincing physical behavior of the elements (pieces and cuboid) due to the incorporated physics engines. 

The approach of this work is to perform simulations of 3D irregular packing of pieces that will be subdued under forces (movements) and collisions that will change their position. When the positions of the pieces allow the cuboid to be smaller, the faces of the cuboid will move to wards the pieces to compress the volume of the cuboid. 
The proposed method considers three sections. First, the pieces are enclosed in a sphere using the algorithm presented in [6], this is done in order to facilitate their initial ubication inside the cuboid based on the biggest sphere. Second, the pieces are subdued under an increased gravity force and movements of the box that induce movement of the pieces within the cuboid. Third, the faces of the cuboid move towards the pieces in order to decrease the volume of the cuboid. The latter are framed in a Tabu Search, in such a way that the simulation does not return to already visited states [7]. Therefore, the transition mechanisms are the simulated accelerations and the search strategy is a simple Tabu Search algorithm. 

In order to compare the performance of this approach with the results available in the literature, the instances used in this work are classical instances of concave pieces such as those found in [1], [4] and [5].