This project is a 3D Bin Packing optimization application designed to solve the complex problem of packing a given set of boxes into a 3D container as efficiently as possible. The primary goal is to maximize the filled volume of the container. The application features a graphical user interface where users can set up container dimensions, generate various types of test data such as unit cubes or realistic mixed sizes, and visually observe the placement evolution in 3D space.
The core packing logic relies on the Extreme Points Heuristic. This constructive algorithm maintains a dynamic list of valid placement coordinates called extreme points. For every box that needs to be packed, the algorithm sorts the available extreme points and attempts to place the box in various allowed orientations. Once a valid position is found without any overlaps or boundary violations, the box is placed, the used extreme point is removed, and new extreme points are generated at the top, right, and front corners of the newly placed box. This approach ensures tight and compact packing within the container.
To find the optimal order and orientations for the boxes, the project implements two distinct metaheuristic optimization methods.
The Genetic Algorithm (GA) mimics the process of natural selection and is built using the DEAP framework. For the encoding process, each individual in the population is represented as a list of two distinct arrays: the first array defines the order of the boxes (a permutation of box indices), and the second array specifies the 3D orientation for each box (an integer between 0 and 5).
During the selection phase, the algorithm uses Tournament Selection with a tournament size of 3. This means that three individuals are randomly picked from the population, and the one with the highest volume is selected to become a parent for the next generation.
When creating offspring through crossover, a custom hybrid approach is used. The box order undergoes Partially Matched Crossover (PMX) to ensure valid permutations without missing or duplicate boxes. Simultaneously, the orientations array undergoes Two-Point Crossover to inherit rotation traits from both parents.
The mutation process also operates on two fronts. For the packing sequence, it performs a swap mutation, randomly exchanging the positions of two boxes in the order. For the box orientations, it applies a random resetting mutation, assigning a completely new valid rotation with a given probability.
To guarantee that the most successful packing strategies are never lost due to destructive crossovers or mutations, the algorithm employs an elitism mechanism. Based on an elitism ratio, a specific number of the absolute best individuals (tracked via a Hall of Fame) are cloned directly into the next generation.
The second method is Tabu Search, which operates quite differently. Instead of permuting the order of boxes, it sorts the boxes descending by volume and encodes a solution as an array of extreme point choices. Essentially, for each box, the algorithm decides whether to place it at the first available extreme point, the second, the third, and so on.
The search space is explored by generating local neighbors. A neighbor is created by slightly tweaking the extreme point choice for a specific box (adding or subtracting 1 to the choice index). The algorithm samples a neighborhood of these local changes and evaluates them. It always moves to the best neighbor found, even if its fitness is lower than the current state, which allows it to escape local optima.
To prevent the algorithm from infinitely looping back to recently visited states, it utilizes a Tabu List—a short-term memory implemented as a queue with a fixed capacity. Any move (like changing the choice index of a specific box) is recorded in this list and forbidden for a set number of iterations. However, Tabu Search implements an aspiration criterion: if a tabu move leads to a solution that is strictly better than the absolute best packing found so far, the tabu restriction is ignored and the move is accepted. The algorithm stops early if it encounters prolonged stagnation without any improvement.
The entire project is developed in Python, relying on a few key libraries to deliver both functionality and user experience.
The graphical interface is built using CustomTkinter, a library that provides a modern, sleek appearance with built-in dark mode and custom theming capabilities, making the application visually appealing and easy to navigate.
For the visual representation of the packing process, the project utilizes Matplotlib. By leveraging its 3D plotting toolkit, the application can draw complex polygons in a 3D space, color-code the boxes, and update the view dynamically. This allows the user to interactively inspect the container from different angles and watch the placement evolution step by step.
Finally, NumPy is employed behind the scenes to efficiently handle the numerical operations, array manipulations, and coordinates management required by the heavy calculations of the metaheuristic algorithms and the 3D rendering engine.