# 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.2 The Fitness Function  
As earlier mentioned, the fitness function is the most important part of the genetic algorithm because it represents the optimization problem that has to be solved. The quality of each chromosome in the genetic algorithm process is evaluated with the fitness function. In terms of the CRP, the fitness function is defined by the following equation:  
\[fitness=\#relocations \tag{1}\]  
where \(\#relocations\) is the number of all relocations of blocking containers while retrieving the containers based on their priorities. The smaller the value of the fitness function, the better the potential solution (chromosome). The pseudo code for the fitness function calculation of our method is shown in Algorithm 2. Figure 6: The relocation of container 4 with an example of a fully occupied stack. An example of the fitness function calculation for CRP and particular chromosomes can be seen in Figures 7-9. First, the container with priority 1 must be retrieved. Container 6 blocks container 1, so it must be relocated. Container 6 would be relocated on the position corresponding to the value of the first gene in the chromosome. The value of the first gene is 2, so container 6 is relocated to stack 2 (Figure 7, part #2). The value of the fitness function is now equal to 1. Container 1 can be retrieved and shipped further (Figure 7, part #2) after the relocation of container 6. Container 2 is next for retrieving. Since this container is not blocked by any container, it can be retrieved immediately (Figure 7, part #3). Now, the container with priority 3 must be retrieved. Containers 4 and 5 block container 3, thus they must be relocated. First, the relocation of container 4 must be performed. The next not used gene within the chromosome has value 3 indicating that the following relocation must be made on stack 3. As stack 3 is fully occupied, this relocation cannot be made thus this gene is skipped (Figure 7, part #4). The next available gene has value 2, thus container 4 is relocated to stack 2 (Figure 7, part #5). The blocking container 5 is relocated to stack 1 (Figure 7, part #6). Now, the fitness function is equal to 3. Currently, there are no containers blocking the retrieval of containers with priorities 3, 4, 5, and 6, so they can be shipped further without making any relocations (Figure 8, parts #7, #8, #9, and #10). Container 8 blocks container 7 and therefore must be relocated. Container 8 is moved to the position corresponding to the value of the first unused gene within the chromosome. The value of the first unused gene is 0, so container 8 is relocated in stack 0 (Figure 8, part #11). The value of the fitness function is now equal to 4. Containers 7 and 8 can now be retrieved and shipped further (Figure 8, part #12 and Figure 9. Part #13). The container with priority 12 blocks the retrieval of container 9, and so has to be relocated according to the value of the next available gene. The value of the next available gene is 3, so the relocation cannot be performed because container 12 is already positioned in stack 3 (Figure 9, part #14). The next gene is equal to 2, so container 12 is relocated into stack 2 (Figure 9, part #15). The fitness function value is now equal to 5, and container 9 can now be retrieved and shipped further (Figure 9, part #16). The container with priority 11 blocks the retrieval of container 10, so it must be relocated according to the value of the next available gene, which equals 1. Consequently, container 11 is relocated to stack 1 (Figure 9, part #17), and the value of the fitness function is increased by 1 (equal to 6). Now, all remaining stacked containers (10, 11 and 12) can be retrieved according to their priorities (Figure 9, part #18). Figure 7: A complete fitness function calculation (1). In the end, the fitness function is equal to 6 for this example chromosome. In order to obtain better and better chromosomes during the evolution process within the genetic algorithm, selection, crossover and mutation must be performed.