# Solving the Container Relocation Problem by Using a Metaheuristic Genetic Algorithm
## 3 Literature Review  
The CRP was first mentioned in [25]. In the research paper, the simulation model has been used in order to analyze the impact of the number of stacks and tiers in a bay with respect to the total number of crane operations. A similar approach for solving CRP has been proposed in [26; 27], where certain heuristic rules were applied for the first time in order to reduce the total number of additional container relocations at a container stacking area. In [28], an equation, which explains the relation between stacks' height within a bay and the expected number of container relocations within that bay with respect to the number of containers, is proposed. Thereby, the corresponding maximum height of the stacks (the number of containers that can stack above each other) is determined within the bay to minimize additional container relocation operations. The integer linear programming method has been used in [29; 30; 31] for solving these small data sets. However, for real restricted CRP, where there is a large number of containers in one bay, linear programming does not meet the requirements for efficiently solving restricted CRP. Newer solutions usually use heuristic methods based on branching and bounding method (B&B) with diverse searching and branching strategies [24; 32; 33; 34; 35; 36; 37]. In [32], for the first time, the B&B and heuristic rule was proposed for determining the optimal positions for blocking containers to minimize the amount of container reshuffling. Additionally, the specific equation was proposed to estimate the number of reshuffles within a bay. The A\({}^{\star}\) (A-star) method, a path search algorithm implemented in [36], was used to minimize additional reshuffles in restricted CRP together with a heuristic algorithm that shortened the time for solving the problem. In [35; 37], a new improved A\({}^{\star}\) (A-star) method, which is  
Figure 2: Yard container bay and RTG crane [17]. based on iterative execution procedure, was proposed for solving restricted CRP. The new heuristic approach, which considers in account the characteristics of the next relocating container when deciding on the position of this container, is proposed in [27]. The new heuristic approach is an improvement of the min-max approach for solving restricted CRP. The improved search algorithm was applied to restricted CRP by reducing the complexity of the search space for quicker obtaining the requested solution. In addition to the proposed solutions, based on the B&B method, several models use other methods [24; 34]. In [24], the beam search algorithm was proposed for the same purpose. The improved beam search algorithm was proposed in [34]. The Decision Support System (DSS) has been implemented in order to optimize the entire Hong Kong container terminal [38]. To minimize the amount of container reshuffling at a container stacking area, a rule Reshuffle Index (RI) was defined specifying the stack with the smallest RI (a stack that contains the smallest number of containers that must be retrieved before the blocking container being relocated) into which the blocking container will be relocated in order to retrieve the desired (target) container within the stacking area. Several authors introduce metaheuristic algorithms inspired by nature to solve restricted CRP. According to [6], the term metaheuristics in computer science and mathematical optimization is defined as a higher-level process or heuristics designed to find, generate or select heuristics that can find a sufficiently good solution for some optimization problem, especially when available information in the optimization problem is incorrect or incomplete, or there is a limited computational capacity. Nature-inspired metaheuristics algorithms have been applied to solve a large number of real-life optimizing problems. These algorithms imitate various natural systems and processes using mathematical models and algorithms.