# Solving the Container Relocation Problem by Using a Metaheuristic Genetic Algorithm
## 1 Introduction  
These days, maritime transport plays a very important role in global transport, as more than 90% of global trade is carried out by sea [1]. Considering various transport modes of maritime transportation, more than 15% refers to container transport [2]. Therefore, container transportation plays an essential role in world trade, and consequently container terminals have become a very important hub of global trade. An increasing number of container shipments leads to higher demands on the seaport container terminals, container logistics, and management, as well as on technical equipment [3]. Therefore, container transportation requires almost perfect coordination between all stakeholders, work resources and processes within the entire container transport system [4]. There are a large number of logistics problems inside container terminals (perth allocation, stacking, transport optimization, crane split, etc.) that have to be optimized and mutually integrated to improve and speed up the overall container transfer through the terminal in order to reduce the waiting time of the transfer means (vessels, trains and trucks) when loading and unloading containers and thus to increase the total container traffic within the terminal. According to [5], one of the most important optimization problems at the container terminal is the stacking of containers in the stacking area (the part of a storage yard). On average, 80% of the containers are transferred to the stacking area before being transferring from the container terminal [5]. Thus, the optimization of the stacking logistics problems has become one of the most important research areas with respect to the optimization of container terminal processes. In the storage area, containers are stacked side by side and on top of each other, forming blocks. When a target container is to be retrieved, there is a high probability that one or more containers are stacked above it and blocking its retrieval. Moving blocking containers adds additional cost to the retrieval of a target container due to the additional crane running time and increased retrieval time. Therefore, containers must be stacked in such a way that there is a minimum number of additional container movements within the stacking area [6]. These additional unproductive movements are called reshuffles. As mentioned earlier, reshuffling slows down the retrieval time of the target container and thus the total container shipment time between the stacking area and other areas of the container terminal. Therefore, the crane operation schedule needs to be optimized to minimize the number of reshuffles, i.e., to minimize the time of retrieving the blocking containers, as well as to maximize the utility of each crane operating in the stacking area. One of the well-known post-stacking optimization problems within the stacking area is the Container Relocation Problem (CRP), also known as Block Relocation Problem (BRP) [7]. In CRP, the operations of reshuffling the blocking containers and retrieving the next container that has to be shipped are performed in parallel. Each container must be retrieved with a minimum amount of reshuffling of the blocking containers. Within the CRP, there are two main sub-problems: restricted and unrestricted CRP [8]. In the restricted CRP, when the desired (target) container is retrieved, only the containers that block the retrieval of the desired (target) container can be relocated. In contrast to the restricted CRP, in the unrestricted CRP, all containers can be relocated to facilitate the reach of containers that must be retrieved later. Therefore, solving restricted CRP is much more complex and demanding with respect to the unrestricted CRP. The restricted CRP is NP-hard [5], so it is difficult to determine a good solution for retrieving all containers with a minimum number of unproductive reshuffles. One of the possible solutions to solve the restricted CRP is to implement nature-inspired metaheuristic algorithms that solve various NP-hard real-life problems very effectively.