# Solving the Container Relocation Problem by Using a Metaheuristic Genetic Algorithm
## 4 A New Method for CRP Resolving Based on Genetic Algorithm
### A New Method for CRP Resolving
#### 4.2.1 The Chromosome  
Before starting the genetic algorithm, the chromosome that represents the solution to the optimization problem must be defined. In our procedure for solving CRP, the chromosome consists of a sequence of integer numerical values (genes) whose values depend on the total number of stacks. Each numerical value represents the position (stack) to which the next blocking container must be relocated. Thus, the values of the genes within the chromosome are equal to the indices of the stacks. The example of a chromosome solving the CRP on a bay with four tiers and four stacks (Figure 3) can be seen in Figure 4.  
The first value (gene) is equal to 2, indicating that the first blocking container must be relocated in the stack with index 2 (s\({}_{2}\)). Applying this chromosome to solve the problem in Figure 3, the first blocking container is container 6 because it blocks the retrieval of the container with priority 1. Therefore, as shown in Figure 5, the container with priority 6 must be relocated in stack 2 (s\({}_{2}\)). Then, the container with priority 1 can be retrieved and shipped to the next transport location. It can be seen that the container with priority 2 can be retrieved immediately because it is located on the top of the stack with index 0 (s\({}_{0}\)).  
It may happen that the next blocking container cannot be moved to the position defined in the solution (chromosome). There are two situations in which this can happen: when the stack into which the blocking container must be relocated is completely full, and when the position of relocating the blocking container is equal to the current position of that container.  
Considering the situation in Figure 6 (after the retrieval of the containers 1 and 2 in the example showed in Figure 5), the next container to be retrieved is the container with priority 3. The first blocking container is the container with priority 4 and the first unused gene within the chromosome is number 3. It means that the container with priority 4 must be moved to the stack with index 3. Stack 3 is fully occupied, so the second gene (number 3) within the chromosome (potential solution) is skipped and does not apply to the relocation of container 4. Therefore, container 4 is relocated to stack 2, because the first valid gene within the chromosome is the gene with the value 2.  
Figure 4: The example of a chromosome.  
Figure 5: The relocation of container 6 and the retrieval of container 1.  
Similarly, if the next gene within the chromosome that represents the next location for the current blocking container has the value of the stack in which the current blocking container is already located, as in the fully occupied stack above, the first valid gene within the chromosome is used to perform the relocation of the blocking container. Considering the possibility of genes appearing within chromosomes that are not valid, it is assumed that the length of the chromosome (the number of genes) must be slightly longer relative to the number of containers within the bay. Experiments have shown that the number of genes in a chromosome is determined by multiplying the number of containers stacked in the bay by the number 10. Thus, if the bay consists of five containers, the number of genes in a chromosome is 50. With this chromosome length, each CRP within the test set was successfully resolved. When talking about the quality of an individual solution (chromosome), only the number of applied genes represents the number of reshuffles (container relocations) within the bay, i.e., the value of the fitness function. The complete process of fitness function calculation for this problem is presented in the next subsection.