Container batch grouping for automated container terminals Open Access

Containers are extensively utilized in the international trade and logistics sector. The operations of automated container terminals (ACTs) facilitate a continuous and efficient flow of container transportation and handling (Lam and Chen, 2021). The large-scale development of container ships has accelerated, which increases the demand for container terminal operations. To meet these demands, many ports have expedited the construction of automated terminals and optimized the allocation and scheduling of operational resources to improve efficiency, ensuring that ships can handle imports and exports within the specified time and depart as scheduled. Increased ship operation time in port can result from congestion, declining operational efficiency or cascading events, all of which directly impact port efficiency (Dragović et al., 2023). This presents a significant challenge in optimizing resource use and equipment interaction. To ensure timely departures, it is crucial to schedule quay cranes (QCs), yard cranes (YCs) and automated guided vehicles (AGVs) effectively, enhancing operational efficiency and reducing costs. Unlike manual container terminals, automated ones cannot coordinate operations through truck drivers or crane operators, so delays in container handover can prolong berthing times. To mitigate this, classifying containers by attributes such as destination, size and weight and exchanging similar types can reduce container re-handling and minimize waiting times for AGVs and YCs. Thus, optimizing the scheduling of YCs and AGVs in automated terminals, considering multiple container attributes, is essential for improving operational efficiency and is a key concern for terminal managers.

Optimizing resource allocation is an effective approach for container terminals to reduce costs and enhance efficiency. Reducing waiting times and balancing the operational loads of YCs and AGVs are key focuses in current research on their joint scheduling problems. To reduce waiting times and balance workload, Xing et al. (2023) developed a model adjusting AGV speeds to minimize YC completion time and AGV energy use, solving it with directed graphs and heuristics. Xu et al. (2021) synchronized AGV and YC speeds to eliminate wait times. Chen et al. (2020) constructed a network flow model to balance the workloads of YCs and AGVs, using an alternating direction multiplier algorithm. Hsu et al. (2021) developed separate optimization models for YC and trucks, employing a heuristic for load balancing and simulation for interaction adjustment. Tao et al. (2023) introduced a load balancing agreement to reduce traffic congestion by optimizing travel distance and workload imbalance with a mixed-integer model and proposed the NSGA-II algorithm to solve it.

Several studies have independently investigated the optimization of scheduling for QCs (Kong et al., 2024), YCs (Oladugba et al., 2023) and horizontal transport vehicles (Chen et al., 2021). Yue et al. (2023) developed a mixed-integer model for dual YC to minimize AGV wait times and maximum completion time using a rule-based heuristic algorithm. Vallada et al. (2023) created a yard allocation and single crane scheduling model to minimize weighted costs by solving it with a local search algorithm. For AGV scheduling, Zhong et al. (2020) built a model to minimize AGV delay time, solving it with adaptive particle swarm optimization (PSO). Wang and Zeng (2022) designed a branch-and-bound algorithm to solve the sequencing for AGVs and proposed a heuristic algorithm to generate conflict-free routing. Branch-and-bound is often used for solving small-scale foundational problems. In practice, the joint scheduling optimization problem between AGVs and gantry cranes is large and complex, leading researchers to use heuristic algorithms to approximate optimal solutions (Naeem et al., 2023).

In summary, we found these literature gaps: (1) Existing research on the joint scheduling of YCs and AGVs treats all containers to be import and export as heterogeneous, without considering that the order of operation for containers of the same type in terms of destination port, size and weight can reduce the waiting time between YCs and AGVs. (2) Research on considering buffer brackets only simplifies them as fixed time window constraints, but the limited capacity of buffer brackets may be occupied for a long time by containers that do not arrive/leave within the time window and changing the order of operation for containers of the same type can promote the mobility of containers on the buffer brackets. (3) Research on AGV or YC scheduling mostly aims to minimize completion time. However, the double-cycle heavy load operation of AGVs or YCs (round-trip heavy load operation) can improve their utilization and reduce costs and changing the order of operation for containers of the same type can increase the number of double-cycle heavy load operations for YCs and AGVs.

Therefore, we propose a strategy called batch grouping, which aims at reducing inter-equipment waiting times by categorizing containers and optimizing the operational sequence of homogeneous containers. Containers of the same type can be interchanged and the time required for AGVs and YCs to load and unload containers varies by location. By optimizing the sequence of loading and unloading these containers, waiting times can be effectively reduced.

A shipping company classifies containers based on attributes such as shipper, vessel name, voyage number, destination port, dimensions and weight and develops a loading plan accordingly. Upon the vessel’s arrival at a port, the terminal allocates berths and schedules for QCs, YCs and AGVs based on this loading plan. Delays in AGV operations may lead to QC delays, potentially extending ship berthing times and causing broader scheduling disruptions. For instance, as shown in Figure 1, Type III containers are designated for Quay Crane 1, while Type II containers are assigned to Quay Crane 3. The QCs unload import containers to AGVs or retrieve export containers from AGVs according to the scheduling plan. If an AGV arrives at the QC later than the planned operation time, it can cause delays, potentially extending the vessel’s stay at the berth and leading to cascading delays for multiple vessels. Additionally, mutual waiting between YCs and AGVs can easily result in further delays to the QC’s scheduled operations.

Buffer brackets in automated terminals help reduce wait times between YCs and AGVs. AGV transport containers from QCs to buffer brackets, while YCs move them to handover areas or from export yards to buffer brackets for AGV collection. This process ensures continuous operation without mutual waiting. However, limited buffer brackets can become fully occupied by incoming containers if YCs wait for AGVs or if export containers occupy frames prematurely.

Classifying containers by attributes enhances their mobility on buffer brackets without compromising ship stability or increasing container re-handling during loading/unloading by QCs or YCs. Containers with identical attributes can have their working orders interchanged. The operational times of YCs vary depending on container positioning: lower bay numbers reduce trolly time in non-cantilever areas. Lower tier numbers decrease spreader time during container retrieval and smaller row differences between adjacent containers minimize spreader movement time. For specific export and import containers handled by AGVs, optimizing the sequence of handling of YC for same-type containers can reduce buffer bracket occupancy without disrupting QC schedules. As illustrated in Figure 2 , export containers are categorized into eight groups (Types I-VIII) based on destination port, size and weight. For instance, QC 4 is scheduled to load 14 Type II containers, identified as ①, ⑩, ⑪, ⑭, ⑰ and ⑳, located in Block 9. Container ① is situated in Bay 3, row 3, Tier 3, while container ⑩ is in Bay 1, row 6, Tier 3. When QC 4 requires a Type II container both containers ① and ⑩ are accessible. Prioritizing container ⑩ due to its shorter moving time can prevent QC delays if the YC is operating near the AGV’s scheduled pick-up. Otherwise, container ① may be chosen to minimize buffer bracket occupation time while waiting for AGV arrival.

Sorting containers by attributes enhances the capacity of the YC to perform more double-cycle heavy-load operations. These operations entail the seaside YC picking up export containers from the handover area, placing them on buffer brackets and subsequently retrieving import containers from the buffer brackets to place them in the handover area. In non-cantilever blocks, YCs face operational span limitations, and their waiting time does not incur additional costs. Increasing these operations within a reasonable range can reduce movement expenses. The QC schedule dictates the latest time AGVs can collect export containers and the earliest time for delivering import containers. YC must position the designated export containers on buffer brackets before the AGV deadline and handover import containers to the handover area after AGV delivery. Traditionally, few combinations of import and export containers meet these time conditions. However, by classifying containers, YCs can optimize working time on export containers by selecting those from larger bays when time windows allow, thus increasing the number of viable double-cycle heavy-load operations.

The impact of various attributes on container type classification varies significantly. For export containers, factors such as destination port, size and weight relate to container turnaround time, cabin size and ship stability, respectively. It is inappropriate to exchange the handling sequence of containers with different attributes merely to reduce YC waiting times. Hence, export containers with varying destination ports, sizes and weights are considered distinct types for seaside cranes. Conversely, for import containers, the distance moved from the buffer brackets to the handover area remains constant, and the YC’s operational time is minimally affected by attributes such as owner, size or weight. Therefore, import containers with different owners, sizes and weights are treated as the same type by seaside YC. The AGV’s operational area lies between the QC and the block, with its capacity solely dependent on container size. An AGV can transport either two 20 ft containers or one 40 ft container simultaneously. For multi-load AGVs, all 20 ft import containers are classified as one type and all 40 ft import containers are classified as another. As depicted in Figure 2, import containers are categorized into two types (Types IX-X) based on size. An empty AGV picks up a 40 ft import container from QC 3 and transports it to block 5, placing it on a buffer bracket. The AGV then returns to QC 4, where it picks up two 20 ft import containers, delivers one to block 2 to place on a buffer bracket, and subsequently, in a half-load state, proceeds to block 4 to transport the other container.

Classifying containers by size can enhance the operational capacity of multi-load AGVs for heavy-load tasks. In the traditional model, multi-load AGV can transport either two consecutive 20 ft import or export containers or perform a sequence involving one import and one export container. As illustrated in Figure 3, if the initial task involves an import container received from the QC at point A, intended for placement in the block at point E, the movement paths for subsequent tasks of one-load and multi-load AGV comprise six scenarios. Among these, Cases 2, 4 and 6 provide two paths for multi-load AGV, indicating that their operational order can be interchanged at points E and F.

When AGVs handle two consecutive import containers, the heavy-load distance for multi-load AGVs increases compared to one-load operations, while the empty load path is shortened (Case 1–Case 4). Conversely, when handling one import and one export container consecutively, multi-load transport does not decrease transportation time and may even elevate full-load transport costs (Case 5–Case 6). Therefore, classifying two adjacent 20 ft containers as the same type by size can extend the heavy-load distance for AGVs. When AGVs manage import and export containers consecutively, they should prioritize delivering the import container to the yard first, and then, within the time window that accommodates the handover of the container under the QC, proceed to the blocks to handle the export container, ensuring a fully loaded round trip for the AGV.

Based on the QC scheduling scheme, we know the number of containers of various types that YCs must pick up or place in each block during different time periods. To prevent any delays in the QC operations, a scheduling optimization model for YCs in each block is developed to minimize their operating costs. Upon acquiring the YC operational scheme, the number of containers being loaded onto or unloaded from buffer brackets by YC in each block at any given moment is determined. Consequently, a dispatching optimization model is developed for all multi-load AGVs to minimize their operational costs.

1. The seaside YC places the containers directly in the handover area upon arrival, without being affected by the capacity of the handover area or the landside YC.

2. There are no containers from other ships that have not yet arrived in port above those awaiting loading and unloading.

3. The operating efficiency of all YCs is the same, and a single YC can only handle one container at a time.

4. The operating efficiency of all AGVs is the same, and each AGV can transport a maximum of one 40 ft container or two 20 ft containers simultaneously.

$H$

Set of blocks, $H={1,...h,...|H|}$

$Rh$

Set of rows in block h, $Rh={1,...rh,...|Rh|}$

$Eh$

Set of rows tiers in block h, $Eh={1,...eh,...|Eh|}$⁠, $enh$ indicates the tier on which container n located

$I$

Set of container attribute types, $I={1,...i,...|I|}$

$T$

Set of moments, $T={1,...t,...|T|}$

$N$

Set of containers, $N={1,...n,...|N|},n∈N$⁠, $n0$ is a virtual container. $N+$ indicates set of import containers, $N−$ indicates set of export containers. $Nf1$ is set of 20 ft containers, $Nf2$ is set of 40 ft containers. $Nh$ is set of containers within block h, $Nh+$ indicates the collection of import containers in the h, $Nh−$ indicates the collection of export containers in block h. $Nhr$ is set of containers in r row of stack in block h. $Ni$ is set of containers of type i. $|Nitd|$ indicates the number of i-types that must be handled during period $td$⁠. $Ns$ is set of 20 ft containers that are transported by a multi-load AGV

$Ka$

Set of AGVs, $Ka={1,...ka,...|Ka|}$

$Kq$

Set of QCs, $Kq={1,...kq,...|Kq|}$

$Ky$

Set of YCs, $Ky={1,...ky,...|Ky|}$

$Yq$

Buffer bracket capacity in a block

$Tkqn$

The moment when the QC $kq$ operates container n

$Tkqn0$

The planned moment when container n handled by QC $kq$ is placed onto the AGV or picked up from the AGV

$Tkqn1$

The actual moment when container n handled by QC $kq$ is placed onto the AGV or picked up from the AGV

$Tkyn0$

The planned moment when YC $ky$ begins to handle container n

$Tkyn1$

The actual moment when YC $ky$ begins to handle container n

$Tykan$

The moment when container n is placed onto the buffer brackets or is taken from the buffer brackets by AGV k_a

$tkynm$

The time taken for YC $ky$ to go to the operating container m with no-load after it the end of handled container n

$tkyn$

The time taken for YC $ky$ to lift container n from its location and move it to the target location

$tkan$

The time taken for AGV k_a to transport container n from its origin to its target location

$td$

The time node, is used to assist in determining whether the quantity of the same type of containers for loading and unloading meets the requirements

$tn1$

The time taken for the AGV to pick up/hand over a container under the QC

$tn2$

The time taken for the AGV to pick up/hand over a container at buffer brackets

$tnm1$

The time for the AGV to reach the starting point of container $m$ after handling over the container from the end point of container n

$tnm2$

The time taken by the AGV in the half-load state to transport containers n and m during one round is the shortest

$tnm3$

The time taken by the AGV in the fully load state to transport containers n and m simultaneously is the shortest

$tqkanw$

The time taken by AGV k_a waiting under the QC during the transport of container n

$tykanw$

The time taken by AGV k_a waiting under the YC during the transport of container n

c₁

The cost per unit time of no-load movement for a YC

c₂

The cost per unit time of half-load movement for an AGV

c₃

The cost per unit time of full-load movement for an AGV

c₄

The cost per unit time of waiting for an AGV

c₅

The cost per unit time of no-load movement for an AGV

$xkynt$

1, if YC k_y handle container n during period t; 0, otherwise

$xkynm$

1, if YC k_y handle container m after complete container n; 0, otherwise

$pkyt$

The number of containers on the buffer brackets in period t

$ykan$

1, if $ka$ transports container n; 0, otherwise

$ykanm$

1, if $ka$ transports container m after container n; 0, otherwise

$znm$

1, if an AGV goes to pick up container $m$ with taking n; 0, otherwise

s.t.

The objective function (1) is designed to minimize the cost associated with the infield crane’s empty travel operations. Constraint (2) requires each container to be handled once. Constraint (3) limits a YC to handle at most one container at a time. Constraint (4) ensures that all containers are handled. Constraint (5) indicates that each container has at most one immediate predecessor operation, where n₀ represents the virtual container and the distance between any container and the virtual container is zero. Constraint (6) indicates that each container has at most one immediate successor operation. Constraint (7) uses an auxiliary variable $un$ to avoid subtour. Constraint (8) dictates the movement of a YC between adjacent containers. Constraint (9) prioritizes upper tier containers for handling. Constraint (10) limits buffer bracket capacity. Constraints (11) and (12) are induced by YC operations. Constraints (13) and (14) are caused by AGV operations. Constraint (15) specifies the time window for the export containers handled by the YC. Constraint (16) specifies the quantity for the same type of export containers that must be processed by the YC. The left side of the constraint represents the quantity of i-type containers handled by gantry crane k_y before time td, while the right side represents the number of i-type containers that must be handled during period t_d, which is an input value derived from the overall workload schedule. Constraint (17) confirms $un$ is a positive real number. Constraint (18) defines decision variable ranges.

s.t.

The objective function (19) represents the minimization of the transportation cost of the AGV. Constraint (20) means that each container can only be transported by one AGV. Constraint (21) indicates that each container has one and only one immediate predecessor and successor operation. Constraint (22) means that, only one 20 ft container can be transported with another 20 ft container by the same AGV at the same time. Constraint (23) means that all 40 ft containers cannot be transported with other containers by the same AGV at the same time. Constraints (24)–(27) represent the rules for updating the number of containers on the buffer brackets. Constraint (28) indicates the capacity limits of the buffer brackets. Constraint (29) represents the time conditions that must be met for the AGV to hand over imported containers to the YC. Constraints (30) and (31) respectively indicate the moment for the AGV to pick up export container m, while when the predecessor container n is the import container and the export container, the AGV picks up export container m from the buffer brackets. Constraint (32) indicates the waiting time in the block when the AGV picks up export container n. Constraints (33)–(37) represent the actual time when QC k_q operates on container m. Constraint (33) is for import container m, while constraints (34) and (35) are for export container m. Constraint (34) is for the case where the preceding container n is an import container, and constraint (35) is for the case where the preceding container n is an export container. Constraint (36) is also for import container m, but specifically when its preceding task is a pair of 20 ft containers n and n'. Compared to constraint (36), constraint (37) differs in that container m is an export container. Constraint (39) indicates the operation time of updating the subsequent QC scheme after the delay. Constraint (40) indicates the time for updating the subsequent YC’s plan after the delay. Constraint (41) indicates that the total completion time of QC operations must not be delayed. Constraint (42) indicates the range of values of the decision variable.

The GUROBI solver can directly solve the first phase of the model. The multi-load AGV scheduling problem for transporting import containers has been proven by Kong et al. (2024) to be NP-complete, with computation time growing exponentially as the problem size increases. This paper builds on the research by Kong et al. (2024) by extending it to include an analysis of export containers, which results in the problem also being NP-complete. Therefore, a two-stage approach is more suitable for solving the model.

The scheming period P is segmented into equal parts, with GUROBI solving YC schedules within each segment. Subsequently, a variable neighborhood search immune algorithm (VNS-IA) addresses AGV scheduling and updating schemes based on segment completion and delays.

Decimal encoding is used to represent the sequence of AGV transport containers. As depicted in Figure 4, the 10 containers are categorized into two groups based on their varying attribute values. During the generation and mutation of antibodies, AGVs are randomly assigned container numbers to ensure compliance with constraints (20)–(23). An AGV can carry full load if it sequentially handles two 20 ft export or import containers without QC delays. Otherwise, it operates with half-load. The antibody’s fitness value is set as the inverse of the objective function value.

Four structures, as shown in Figure 5, are used to enhance the search depth of the algorithm.

1. Insertion: randomly select a container, insert it behind another container at a random position, and have it transported by the same AGV. For example, after container 6 in Figure 5(a) is inserted behind container 5, it is transported by AGV 1.

2. Swap: randomly select two positions and swap the order of the containers at those positions, but keep the AGV allocation scheme unchanged. As shown in Figure 5(b), five containers, including container 5 and container 3, have exchanged positions.

3. Local Perturbation: randomly determine the number of containers each AGV needs to transport, but keep the order of container operations unchanged. As shown in Figure 5(c), the workload of AGV 1 and AGV 3 is reduced, while that of AGV 2 is increased.

4. Global Perturbation: randomly determine the order of container operations but keep the number of containers each AGV handles constant. As shown in Figure 5(d), the workload of the three AGVs remains unchanged, but the containers they handled have all changed.

During the decoding process, AGVs may fail to pick up/deliver containers at the cranes on time due to the unreasonable order of individual containers, leading to crane delays of duration $Δt$⁠. If the current phase is not the last cycle of the rolling loop, let $c6$ be the penalty cost per unit time of crane delay, denoted as fitness $F=1/(f2+c6Δt)$⁠. When solving the scheduling scheme within the last cycle, antibodies that do not meet the contracted laytime are assigned a fitness of 0 and are not passed on to the next generation.

When the iteration count reaches its limit, the algorithm terminates.

We designed a series of numerical experiments based on the layout and equipment operation parameters of Yangshan Ⅳ ACT of Shanghai Port. The relevant input parameters are shown in Table 1. All experiments are coded in MATLAB and the optimization solver used is GUROBI 9.5.2. The calculation environment was a PC with an Intel(R) Core(TM) i7-7700 CPU @ 3.60 GHz and 8 GB of RAM.

To verify the correctness of the algorithm, the stealth enumeration algorithm (SEA) is used to solve small-scale instances and compare the results with those obtained using the improved VNS-IA. The SEA involves enumerating all feasible paths and directly solving the AGV scheduling model. The improved VNS-IA runs each instance 10 times and calculates the average value. The comparison results are shown in Table 2.

Table 2 illustrates that AGV costs vary depending on the case characteristics. Scenarios with a higher number of containers exhibit higher AGV costs. When the number of containers and AGVs exceeds a certain threshold, enumerating all feasible AGV schedules becomes infeasible due to the extensive solution space. VNS-IA addresses more cases than the SEA does. When comparing the Gap1 values, it is evident that although VNS-IA might not achieve the optimal solution for large numbers of containers, the performance gap remains small. In terms of runtimes, the efficiency of this algorithm is comparable to that of the exact method.

To validate the superiority of VNS-IA over other heuristic algorithms, we designed and solved large-scale test cases using the immune algorithm, the local search algorithm and the algorithm from this paper to calculate the objective function values. Under the condition of the same number of iterations, each algorithm was executed 10 times and the average cost and run time values were statistically analyzed, as shown in Table 3.

Table 3 demonstrates that all the two heuristic algorithms consistently produce satisfactory solutions across the 23 scenarios examined. When analyzing the “Gap2” column, it reveals that while the VNS can sometimes closely approximate the optimal solution, it often fails to escape from local optima, thus exhibiting instability. Comparing the “Gap3” column shows that although the solution time of VNS-IA is relatively slower, the minimum objective function values obtained are lower than those of the IA, reflecting the IA’s inability to conduct in-depth searches. The VNS-IA combines the advantages of the two algorithms, taking longer in the solution process than both, yet offering superior solution quality and efficiency.

This section demonstrates the cost-effectiveness of the proposed container batch grouping strategy through comparative experiments. First, 24 comparative scenarios were designed with varying proportions of 40-ft containers (0%, 20%, 40%, 60%, 80% and 100%) and unloading container ratios (25%, 50% and 75%). Subsequently, the model and algorithms proposed in this paper were applied to calculate the operational costs of AGVs and YCs for handling 150 containers using 9 YCs and 14 AGVs. Finally, under the same scenarios, Constraint (16) was relaxed to allow YCs to operate containers under a first-come-first-served (FCFS) principle and their operational costs were computed. The comparison results are shown in Figure 6.

From Figure 6, it can be observed that as the number of container increases, the costs associated with AGVs and YCs gradually rise. However, in the same case study, when applying the container batch grouping strategy, AGV costs are consistently lower than when not considering this attribute, as shown in the left subplot of Figure 6. In most cases, the YC costs are also lower when using the container batch grouping strategy compared to not considering this attribute. However, in certain scenarios, the YC costs may be higher when applying the container batch grouping strategy, as illustrated in the right subplot of Figure 6. This is because, as the proportion of unloaded 40 ft containers increases, the container batch grouping strategy may lead to insufficient buffer rack capacity, resulting in increased waiting costs for YC. Therefore, the container batch grouping strategy should be dynamically adjusted based on the proportion of different container types in the specific scenario.

This study focuses on the joint scheduling problem of YCs and multi-load AGVs in an ACT. The main conclusions are as follows:

1. Considering the multiple attributes of containers, the payload capacity of AGVs, and the buffer bracket capacity in each block, mixed integer programming models are developed for YC scheduling and AGV scheduling.

2. The YC scheduling model is directly solved using GUROBI optimization software to verify its correctness. A VNS-IA is designed to solve the AGV scheduling model. Experimental results show that the algorithm presented in this paper has higher solution quality and greater efficiency.

3. By classifying containers based on their multiple attributes and optimizing the handling sequence of the same-type containers, the ACT can effectively achieve a reduction in the total cost of up to 8.9%.

From a management perspective, considering container classification and interchangeability in this study can lead to more flexible and efficient terminal operations. Thoughtful container classification enables a more precise planning of equipment, pathways and resources, consequently enhancing overall port efficiency. Substituting containers contribute to a partial balance in resource allocation and operational workflows, which effectively addresses unexpected situations and changes during the cargo handling process, ultimately improving the adaptability and resilience of the terminal operations system.

In the future, research directions could focus on optimizing container classification and interchangeability strategies to enhance terminal operations. One potential area is developing dynamic container classification systems that consider real-time data, such as container size, weight and destination, to improve resource allocation and operational efficiency. Another direction is exploring advanced interchangeability algorithms that prioritize container compatibility and minimize disruptions during cargo handling. Additionally, integrating machine learning and IoT technologies could enable predictive modeling of container flow and resource demand, further enhancing adaptability. Finally, research could investigate the environmental impact of container classification and interchangeability, aiming to develop sustainable practices that reduce energy consumption and emissions while maintaining operational efficiency.

This work is partly supported by the China Scholarship Council Fund (CSC202206570020) and Natural Science Foundation of Hebei Province, China (G2025210006).