## 1 Introduction  
Generally, in the yard of the container terminal containers are stacked on top of each other in the ground slots, forming stacks. At the same time, a row comprises several stacks placed abreast, constituting a bay, and each yard block is composed of dozens of bays. The containers in a stack adhere to the last-in-first-out (LIFO) principle. If a target container that needs to be retrieved is not the topmost in its stack and is covered by other containers, the blocking containers must be moved to another stack in the same bay first. As a result, the yard crane is required to perform one or more relocation movements. Moving a blocking container, referred to as relocation (rehanding or reshuffling), is an unproductive operation. A high proportion of unproductive operations resulting from container rehanding decreases yard operational efficiency, delays the turnaround time of external trucks, and increases the detention time of vessels. Regarding relocations, three topics have been identified: the re-marshaling problem, the pre-marshaling problem, and the relocation problem. The relocation problem is referred to as the container relocation problem (CRP) or the block relocation problem (BRP) in the literature and is defined as needing to retrieve all the containers (export or import) from a bay in the prescribed order while minimizing the number of rehandles. Despite the fact that CRP has attracted much attention for decades, the CRP during the pickup of import containers is still an intractable problem, which is the focus of this paper. The difficulty in dealing with the CRP of import containers is not only due to the fact that it is an NP-hard problem [1] but also to the uncertainty of the pickup sequence and the decentralization of the retrieval operations. In response to the first point, the NP-hard nature, it is necessary to find more efficient methods for solving this problem. Various existing models or algorithms are based on the idea of reducing the problem scale to improve the solution efficiency, whether it is to use a solver to solve an integer programming model, to solve based on a tree search algorithm, or to use heuristic methods. However, the CRP aims to find the optimal operation plan for retrieving all the containers in a bay while minimizing the number of relocations during the pickup operations. The computational effort of the solution process increases rapidly as the instance size increases. Many methods do not perform well in solving the CRP, e.g., restricted CRP is still an NP-hard problem, and the B&B algorithm and other variants of the tree search algorithm are not easy to solve medium-sized and large-sized instances quickly. To improve the efficiency of solving the CRP, we need to consider some ways to reduce the problem size further. To be precise, it is difficult to accurately master the retrieval order of containers in advance since the arrival time of trucks is random [2]. But, the truck appointment system (TAS), which is implemented in most container terminals, can provide container terminals with more credible retrieval information and help terminals optimize yard operations [3,4]. On this basis, the stochastic container relocation problem (SCRP) [5], also called a CRP with time windows [6], has been the focus of research related to the import container relocation problem. In the SCRP, the containers are divided into different batches (groups) according to their appointment departure time window, i.e., a batch of containers indicates a group of containers stacked in the same bay and with the same appointment retrieval time window. Containers are ordered so that all containers in a batch must be retrieved before any containers from a later batch. The pickup order of the containers within the same batch is uncertain. This suggests that their pickup sequence needs to be determined based on the arrival of corresponding external trucks (ETs).