# A 3D Offline Packing Algorithm considering Cargo Orientation and Stability
## Overview
- The paper solves the 3d bin packing problem which has unlimited **ULDs of same size**s and we need to find **minimum number of ULDs** required **to pack all items**.
- This Paper also **considers orientation constraints** which is not part of our actual problem.

Intelligent optimization algorithms(inspired by certain phenomenon in nature):
- Genetic Algorithm (read : https://www.datacamp.com/tutorial/genetic-algorithm-python)
- Particle Swarm Algorithm
- Simulated Annealing algorithm
- Ant colony Algorithm

**Convergence speed of Intelligent optimization solutions is greatly affected by the initial solution and encoding method.**

The algorithm **combines the genetic algorithm and tabu search algorithm**. Also designs a corner-occupancy heuristic loading algorithm (**COHLA**) based on division and merging of remaining space, which converts the solution in the intelligent search algorithm into a packing scheme that conforms to mathematical model.


## Creating an initial population
Paper designs a TSRNEM(two stage real number encoding method) based on random keys as the encoding method.
**TSRNEM:**
1) For packing problem of n items, two segment real number code contains 2*n numbers, where each real number is a random number between 0,1.
2) First n real numbers are packing sequence S, in which $i$th real number $s_i$ represents packing sequence values with item number $i$.
3) Second n real numbers are rotation state R, of which the $i$th real number $r_i$ represents rotation state with item number $i$.
4) Sort the items by the packing sequence value. After this, the rotation state of each item(1 to 6) is found by multipying $r_i$ by 6 and rounding to the nearest integer.


## Calculating the fitness value according to heuristic loading algorithm

**Heuristic loading algorithm**
The paper designs a **COHLA**(corner occupancy heuristic loading algorithm) based on division and merging of space.
- **Corner occupation strategy** is used as the positioning rule. Basic idea of this is : first, place the items in a corner of ULD, then place it along edge of box, and finally fill the box. Paper chooses **left rear corner rule** as the positioning rule.
- To reduce the division of large space and improve the utilization rate of space, this paper selects the space with the smallest volume from the remaining spaces that can be loaded as the loading space.
- Then the remaining spaces are merged by two methods - **front and rear merging ; left and right merging**. Space merging operations is performed on all the abandoned spaces.

**Fitness value**
Average value of inverse of the space utilization of all boxes is chosen as the optimization objective of the mathematical model of 3d offline box packing problem.


## Select Action
There are mainly 3 types ways of select operation -
1. Roulette method : has better global search ability, but leads to decrease in convergence speed
2. Optimal Preservation strategy : easily gives local optimal solution, but possible that it may not find global optimal solution.
3. Tournament method : both selective and deterministic, a method between roulette and optimal preservation strategy.

In paper:
1. In the **early stage** of the genetic algorithm, when the iteration $g<g_0$, the **roulette method is selected** as the selection operation method, so that the search can be carried out in a wider range and the global search ability is maintained.
2. In the **later stage**, when the iteration $g>g_0$, the **optimal preservation strategy** is used as the selection method. The operation method enhances the search ability of the algorithm in the optimal solution range and accelerates the convergence speed.

$$ g_0 = \frac{2G}{3}$$
where $G$ is total number of iterations.

## Crossover
Crossover operation method is based on partial random key and uniform crossover.
1. One of parent individuals is derived from individuals selected by selection operation.
2. Other parent is randomly selected from the parent population.

For crossover between two parents:
- Generate a random number between 0 and 1, if less than crossover probability, then gene in chromosome of first parent individual is selected, otherwise gene in second parent individual is selected.

## Mutation (Tabu Search here)

1. For individual A, a random number between 0 and 1 is randomly generated, and the random number conforms to the average distribution.
2. If the random number is less than the mutation probability, individual A will proceed to the next step; otherwise, keep individual A and perform mutation operation on the next individual;
3. Then, the chromosome of individual A is used as the initial solution of the **tabu search algorithm**, and the tabu search is performed;
4. Then, the optimal solution obtained through the tabu search is used as the chromosome to obtain the individual B, and the individual B is used to replace A
5. All individuals perform the previous steps and finally obtain a new population after mutation and continue to perform the genetic algorithm-related steps on the new population.

## Results