# Solving the Container Relocation Problem by Using a Metaheuristic Genetic Algorithm
## 1 Introduction
Metaheuristics are becoming very popular over the last decade due to their simplicity, flexibility, derivation-free mechanism and local optima avoidance capability [9]. According to [6], the term metaheuristics is defined in computer science and mathematical optimization 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 the available information in the optimization problem is incorrect or incomplete, or the computational capacity is limited. Although it was invented a long time ago [10], the genetic algorithm is still one of the most used nature-inspired metaheuristics in solving different optimization problems. In [11], an overview of the use of nature-inspired metaheuristics for optimization problems in a container terminal is presented. Thus far, the genetic algorithm has been used in [7; 12; 13; 14; 15; 16; 17; 18; 19]. Only the solutions in [17; 18; 19] use a genetic algorithm to solve restricted CRP. Besides [17; 18; 19], which use a genetic algorithm to solve restricted CRP, there are only two solutions for restricted CRP [20; 21] that use nature-inspired metaheuristics. In [20], the ant colony optimization algorithm [22] was used, while in [21], simulation annealing [23] is used for restricted CRP solving. Considering the excellent results of [17; 18] obtained in resolving the most complex test set of restricted CRPs [24], we assume that there is a great potential for using nature inspired metaheuristics to solve restricted CRP. The test set described in [24] consists of a huge set of CRPs considering different bay sizes. All CRPs within this test set have a maximum occupancy capacity, which makes it more difficult to solve the problem given the large number of blocking containers. In [17; 18], for solving restricted CRP, the use of a genetic algorithm is proposed, to determine the order of executing one of the four relocation rules (based on stacks occupancy) for blocked containers on the terminal stacking area. These rules prefer to perform the reshuffle of the blocking container to the nearest possible stack (column) that satisfies the restrictions set within a particular relocation rule. Along with minimizing the number of relocations in CRP, these four rules of relocation optimize the horizontal movement of reshuffled containers. The main objective of CRP is to minimize the number of reshuffles. When applying these four rules of relocation to solve CRP, the focus is sometimes on optimizing the horizontal distance (relocate to the nearest stack) rather than the number of relocations. In certain situations, the total number of relocations ends up being lower if the reshuffled container is not relocated to the nearest possible stack (column). Therefore, it is necessary to improve the method described above, which uses a genetic algorithm. The list of contributions of this paper is as follows. We have studied in the literature review only the methods and models that have been used to solve the most complex test instances of restricted CRPs [24]. We believe that these methods and models are the most appropriate for comparison with our new method. In this paper, we propose a new genetic algorithm-based solution in order to minimize the number of relocations within the bay. Using the genetic algorithm, the method finds an optimal sequence of container relocations to determine a minimum number of total relocations. Considering a certain container that has to be relocated, the best current stack (column) position is not determined, but the stack position that will optimize the total number of relocations at the end. We also implement the linear programming model to resolve CRP as well as to get optimal results for small bay sizes. As stated before, CRP is NP-hard problem. Hence, using the linear programming model, it cannot only resolve CRPs for large bay sizes.