3D bin packing is a classic NP-hard problem, we need to pack the given boxes into the least possible number of bins or containers to save as much space as possible. In this project we are aiming to add one more objective to the space saving object; ordering the boxes according to packing priority ( which box is to be retrieved from the container first ). In this project, we will use Evolutionary Computing algorithms to solve this problem, namely NSGA-II. We will also use a so called Heuristic Decoder to handle feasibility issues for the produced solutions by the NSGA-II. In short, it will use the Empty Maximal Spaces process described in [2] to locate the empty space inside the container that is available for packing, it will also apply several other functions like box rotation, box placement, finding empty space and updating empty space after placement. The reason we decided to use the decoder mentioned above is to move the feasibility and complexity issues of this problem into the objective evaluation. So, now we can use sequence operators like two point crossover and shuffle indices mutation without worrying about the feasibility of the produced solutions. If we use the GA to change the boxes' locations directly then it's difficult to produce feasible solutions as the initialization and operators need to account for boxes not to overlap with each other in the container space. This makes the problem really complex, and the search space will be difficult to explore properly.
We will use the NSGA-II to find the order and orientation of the boxes we have, whereas the heuristic decoder is used to translate this genome ( order and orientations ) into a phenome (packed solution) in order to evaluate the individual during the NSGA-II.. We move feasibility issues of the problem to a heuristic decoder that will handle the box placement process, this decoder should take as input an individual and return a packed solution ( list of containers along with the boxes packed inside of them ). The decoder consists of the following :
1- Placement heuristic function: Try fitting the box in each EMS to determine which EMSs are feasible for this box.
2- Chooses the EMS according to the Back-Bottom-Left (BBL) heuristic rule ( choose the spot with the lowest Z, Y, X coordinates in order ) and places packs the box in that location, check figure below.
3- Empty Maximal Space creation function: After packing a box into a location, this function checks which existing EMSs intersect with the packed box in order to create the new EMSs.
4- Empty Maximal Space update function: Because some created empty spaces will have infinite thinness or might be totally inscribed within other EMSs, this function is meant to find such EMSs and remove them as they are unusable and only add overhead to the program in the next iterations. We also make sure to remove EMSs that do not fit any of the remaining boxes, i.e they have less volume than any of the remaining boxes or their dimensions don’t fit any of the remaining boxes. We apply those two checks in sequence as in [6], the removal of these EMSs reduces computational complexity as these EMSs won’t be used in any future box placement.
First, initialize a set of boxes with random dimensions, priorities, weights, and orientations, see figure below. Create an initial container to use for packing the boxes. The decoder handles opening additional containers when space is needed. Each individual consists of two parts, the first part is the order in which the boxes are packed, and the second part is the orientation of each box. For example: [3,9,8,10,7,4,6,5,1,2,1,1,1,0,0,0,0,1,2,2, 1] Here, the first 10 digits are the ID of each box, and the last 10 digits (0, 1, 2) are the arrangement of each box on the left side of the chromosome. The 0 direction means the original direction (no direction) in which the box was created, 1 means the front and back are up and down, and 2 means the sides are up and down.
Penalty Evaluation We have created the following merit functions, all of which need to be minimized:
- Space Penalty: This function performs really well for the 3D bin packing problem according to [6]. NB means the number of containers, BV is the volume of the last container's box, CV is the volume of the last container. This function represents how well the solution is using the available space (individually). Check only the last container because it contains enough information. This is because if it is better to pack the boxes using the previous container, the last container will receive less boxes. Use NB parts to punish the solution with more containers. If you use only the BV / CV of the last container, you cannot distinguish between a solution with two containers and a solution with three containers, see figure below.
- Priority Penality, PP is the priority penalty, P is the priority, N is the number of boxes, and I is the index (order) of the person's boxes. This function shows how wrong the priority is. Therefore, there are 50 boxes, with the 50th priority (highest priority) box first. Get 50-0/50 = 1.00. This is the maximum penalty, which is a percentage of how far the boxing order is from the correct position. We sum this penalty over every box in the chromosome and after that we divide them by N again, and this way, instead of getting some arbitrary number, we get a percentage that represents how off mark the individual is.
The following two GIFs show the visualization of the phenomes ( which are genomes that were passed to the decoder ) for a run of the program using 70 boxes with random dimensions sampled from a set of dimensions proportional to the container size, the larger the dimension the lower the probablity of using this dimension ( it produces fewer boxes with large width, depth or height ). The program was run for 50 generations:
Worst individual across the 50 generations ( used the space the most among all solutions ):
Best individual across the 50 generations ( as we can see the algorithm was able to reduce the number of containers used from 3 to 2 using this solution ):
**The following plots show the results we got when running the program for 70, 140, and 200 boxes :
The following are the pareto fronts for each of the runs above:
Pareto front for the 70 boxes run :
Pareto front for the 140 boxes run:
Pareto front for the 200 boxes run:
[1] Bean, J., 1994. Genetic algorithms and random keys for sequencing and optimization. ORSA Journal on Computing 6, 154–160.
[2] Lai, K., Chan, J., 1997. Developing a simulated annealing algorithm for the cutting stock problem. Computers and Industrial Engineering 32, 115–127.
[3] DEAP. (n.d.). Deap/nsga2.py at master · DEAP/deap. GitHub. Retrieved December 7, 2021, from https://github.com/DEAP/deap/blob/master/examples/ga/nsga2.py.
[4] David Kosiur. 2001. Understanding Policy-Based Networking (2nd. ed.). Wiley, New York, NY.
[5] J, Gonçalves. M. Resende. 2013. A biased random key genetic algorithm for 2D and 3D bin packing problems, Int. J. Production Economics 145 (2013) 500–510.