Solving integrated problem of stowage planning with crane split by an improved genetic algorithm based on novel encoding mode

Abstract

Stowage plan, which is planning for a reasonable movement of containers, plays an important role in enhancing the efficiency and competitiveness of container terminals. The time required for handling containerships also depends on the operations of quay cranes, which is one of the most expensive equipment in container terminals. Hence, this paper integrates stowage planning and crane split problem to minimize the total berthing time at each visiting port over the voyage. A new mathematical model is developed, which covers a wide range of operational and structural constraints for both stowage plan and crane operation. An improved genetic algorithm based on a novel encoding mode of assignment strategies, including container grouping and operation strategies, is designed to solve the problem, which also introduces penalty operations to solve the infeasible solutions. Finally, some computational experiments are carried out. Firstly, three small-sized experiments are implemented to verify the feasibility of the proposed model and algorithm. Secondly, large-sized experiments with 5 ports, 3385 containers, and 2 quay cranes show that the proposed approach can solve the integration problem with different productivity of quay cranes effectively and decrease the berthing time by 6.0%. Eventually, a comparison experiment with 5 ports, 5752 containers, and 2 quay cranes is conducted, and the results indicate that the proposed algorithm results in 62.3% and 87.7% decrease in the total number of rehandling times and computational time. Meanwhile, the results also show that the proposed algorithm can be convergent. So the proposed algorithm is effective and efficient in solving the integration problem and enhancing the efficiency of container terminals.

Keywords

Stowage planning crane split genetic algorithm container terminal

Introduction

Containerization is an intermodal transportation operation in which containers as cargo units can be loaded onto containerships, railway cars, and trucks without handling the contents. The global demand for containerized services has also shown an increasing trend over the past decade. The United Nations Conference on Trade and Development (2019) mentioned that the throughput of global container terminals was 793.26 million 20-foot equivalent units (TEUs), 4.7% increase compared to 2018.¹ So, globalization would have been impossible without containers.

To satisfy the growing demand, an increasingly large containerships are developed. These have put enormous pressure on ports and terminal operators to increase the efficiency of handling all these containers in a fast and smooth way. One of the main factors to evaluate the efficiency of container terminals is berthing time, which is composed of handling and rehandling time of containerships. Hence, arrangement of containers both within the container terminal and on the containership play an important role in determining the berthing time. Meanwhile, the berthing time of containerships is also influenced by the number of container movements (named as shifts), composed of the number of handling and rehandling movements. The task of determining an optimal container loading plan for a containership which minimizes the number of rehandling operations and maintains the overall stability of the containership is referred to as stowage planning. Ideally, an optimal way of stowing a containership will not only maintain the containership stability but has minimal rehandling operations. Therefore, it is vital to develop an optimal stowage plan to reduce the number of shifts so that the berthing time can be decreased.

Another important problem related to container terminals, named as crane split problem (CSP), is to allocate quay cranes to different sections of a containership. Both stowage planning problem (SPP) and CSP are of vital importance in improving the productivity and efficiency of container terminals. Existing literatures have hardly been devoted to these two problems together, while these two problems are highly interrelated in actual situations: (1) In the SPP, containers are handled from containerships using quay cranes, which is one of the most expensive equipment in container terminals. (2) SPP can determine the distribution of containers over bays, which will directly influence the utilization of quay cranes; in turn, the utilization of quay cranes will also influence the berthing time, which is one of the objectives in the SPP. In some cases, up to 10 quays cranes might be allocated to a containership; however, the berthing time, sometimes, could also be very long due to underutilized quay cranes. Hence, given the configuration of quay cranes at each visiting port, the stowage planning must consider the utilization of quay cranes as well as the reduction of shifts to minimize the berthing time over the voyage. It seems that the integration of SPP and CSP results in a more efficient working instruction which ultimately increases the utilization of container terminals.

Consequently, the main contribution of this paper is to integrate SPP and CSP, considering not only the constraints of SPP, such as the attributes of containers and the stability constraints but the constraints of CSP, such as the operational constraints of quay cranes. The other contributions of the paper are: (1) a novel mathematical model of the integration of SPP and CSP is established, whose objective is to minimize the berthing time; (2) an improved genetic algorithm (GA) based on a new encoding mode of assignment strategies is designed to solve the problem, which also introduces penalty operations to solve the infeasible solutions; (3) some computational experiments are conducted to prove the feasibility and efficiency of the proposed approach.

The rest of the paper is organized as follows: Section 2 presents a brief literature review on SPP and some other related problems. Section 3 describes the integrated SPP and CSP in deeper detail and presents a mathematical optimization model. In Section 4, an improved GA based on new encoding mode of assignment strategies is introduced. Some computational experiments are implemented to validate the feasibility and performance of the proposed approach in Section 5. Section 6 concludes the paper and proposes future studies.

Literature review

According to Steenken et al.,^2,3 the operations of container terminals can be divided into five main problems: berth allocation problem, stowage planning problem, crane split problem, quayside transportation problem and land-side transportation problem. Recent literature showed there seems to be a tendency to integrate the five problems. For example, some literatures integrated berth allocation and quay crane scheduling problem, such as Bierwirth and Meisel,⁴ Chang et al.,⁵ Imai et al.,⁶ Meisel and Bierwirth,⁷ and Yang et al.⁸; others integrated the allocation of berths and yard operation planning problem, such as Hendrisks et al.⁹; and some also integrated empty container allocation problem in the yard with vehicle routing problem, such as Braekers et al.¹⁰

The reason for the recent tendency is that the optimization of operations for just one stage cannot improve the overall efficiency of container terminals, because further and non-optimized stages behave are blockage. However, the integration problems of operations in container terminals are quite difficult due to the computational complexity of the mathematical model related to each stage which is NP-hard. Actually, a container terminal may be seen as a complex system as observed by Zeng and Yang¹¹: “Many complex systems such as manufacturing, supply chain, and container terminals are too complex to be modeled analytically. Discrete event simulation has been a useful tool for evaluating the performance of such systems. However, simulation can only evaluate a given design, not provide more optimization functions. Therefore, the integration of simulation and optimization is needed.”

An increasing number of studies on the stowage planning problem have been published in recent years. The first work on the stowage planning problem was described in the paper by Shields.¹² He used a Monte Carlo method to solve the problem. Multiple parameters and constraints were considered in the research, but the quality of the solution was not addressed. In this method, the solution space was not searched systematically. Since then, researchers began to propose mathematical programing models to describe the problem and develop artificial intelligence-based optimization methods and heuristic algorithms to solve the problem, especially for large-scale problems.

In separate work, Botter and Brinati^13,14 validated that the stowage planning problems are NP-complete and even small-sized problems can be very computationally expensive. Due to the large number of variables needed, it is impossible to find the optimal solution for large-sized problems in an acceptable time. Consequently, various optimization algorithms were developed to solve the problem effectively. The first metaheuristic approach by Dubrovsky et al.¹⁵ provided a GA with an efficient solution encoding scheme. Ding and Chou¹⁶ pointed out that it is always possible to assume that the ship is fully loaded when traveling between ports. They provided a new integer programing (IP) formulation and a heuristic method to solve the SSP, which was proved that the performance of the proposed algorithm was better than the suspensory heuristic of Avriel et al.¹⁷; however, they ignored the transportation information for subsequent ports. Ambrosino et al.^18,19 studied the multi-port master bay plan problem and proposed a mixed integer programing (MIP) heuristic to solve the SPP. Kroer et al.²⁰ developed an approach for modifying a stowage plan interactively without breaking its constraints and showed two approaches. Lee et al.²¹ studied how to improve the efficiency of solving the problem by sorting the constraints of SPP. Matsaini and Budi²² developed particle swarm optimization to solve the SPP, which was combined with some realistic rules, such as total weight, weight of one stack and so on. Roberti and Pacino²³ proposed a MIP formulation of SSP. They developed a column generation-based lower bounding procedure and combined it with a compact MIP model to solve large-sized problems.

The state-of-the-art compact IP formulation and heuristic method for solving the SPP have been provided by Parreño-Torres et al.²⁴ This new IP formulation had fewer variables than the formulations by Ding and Chou¹⁶ and Avriel et al.¹⁷ They introduced a greedy randomized adaptive search procedure (GRASP) and compare it with the heuristic algorithms by Ding and Chou¹⁶ and Avriel et al.¹⁷ on medium- and large-scale instances that they generated. The GRASP provided very good solutions of higher quality than those obtained by the previous algorithms. Then they proposed a matheuristic procedure, namely an insert-and-fix heuristic, to solve the SPP.²⁵

Other relevant papers include a variant of the SPP where the reshuffling cost is not identical for all ports (Zhang et al.²⁶) and a multi-port master bay planning problem variant with weight uncertainty (Li et al.²⁷).

Additionally, Avriel et al.^14,17 formulated the SPP as a binary linear programing model but neglected stability constraints. Since the stability was not considered, the stowage plan generated in their paper did not satisfy realistic conditions. According to the previous studies, most on the SPP considered the stability of containerships. There are two common methods to deal with the stability in the mathematical model: one is to incorporate it in the objective function, such as Imai et al.,²⁸ Azevedo et al.²⁹ and Araújo et al.³⁰; the other is to take it as constraints, such as Ambrosino et al.³¹ and Fazi.³² In addition to ship stability, some other constraints were also considered in the SPP, such as different weight of containers (Parthibaraj et al.³³ and Shen et al.³⁴), different types of containers (Parreño et al.,³⁵ Ambrosino and Sciomachen³⁶ and Korach et al.³⁷), and ship draft restrictions (Christensen and Pacino³⁸).

As not to distract the reader with a lengthy literature discussion, some studies that focused only on single-port problems are excluded (see Larsen and Pacino³⁹ for an up-to-date review).

SPP, which is the problem to determine how to organize the containers in a containership, is an everyday problem solved by the containership planners. The classical objective is to minimize the number of shifts to unload and load containers from/to the containership so that the total berthing time that the containership spends at all the ports is reduced. For the basic SPP, some IP models, exact and heuristic methods can be found. However, compared to other combinatorial optimization problems, the literature on the SPP is relatively scarce, and a standard definition of the problem and benchmarks have not yet been established. Additionally, the number of shifts and other aspects in handling operations, such as quay crane operation, can both affect the total berthing time. Most literatures above just considered the constraints of stowing containerships and neglected the constraints of quay crane operations, although they introduced many advanced solution algorithms. The main reason is that most researchers just took quay cranes as normal equipment to handle containers and did not consider the interrelation between SPP and CSP. Meanwhile, as mentioned before, SPP is NP-complete and even small size problems can be very computationally expensive, so considering the operations of quay cranes will make it more difficult to solve the problem.

In addition, some researchers did consider the quay crane utilization as constraints or the lower bound within the models; however, they still ignored some other constraints. For example, Hamedi⁴⁰ studied the SPP considering quay crane operations with the assumption that 20 ft containers could be loaded on top of 40 ft containers. As it turns out, this is not the case in the real world and consequently, the results of the experiments in his paper may not be correct. Meanwhile, Hamedi⁴⁰ also neglected some allocation constraints for 20 ft and 40 ft containers. Azevedo et al.⁴¹ considered the influence of quay cranes in solving the SPP; however, they assumed that containers were all the same. Martínez⁴² also combined the ship loading problem with crane split problem, but he just established two models to describe the problem, not considering the internal relationship between ship loading and crane split.

Therefore, in this paper, we improve the problem proposed by Hamedi,⁴⁰ which integrates SPP and CSP, considering different container weight, sizes and types, stability constraint and crane utilization constraint, to reduce the berthing time of a containership.

Problem description and formulation

Problem description

At the quayside area of the container port system, berthing time is one of the most important performance measures. Quay cranes, as one of the most expensive equipment at the port, play a major role in terminal productivity. Depending on the size of the containership and the availability of quay cranes, usually, more than one quay crane will be assigned to a containership. However, if the stowage plan of the vessel does not match the quay crane assignment, assigning more quay cranes to a containership might not improve the berthing time successfully. As a result, to generate more efficient stowage plan and save the berthing time of the containerships, the CSP should be combined with the traditional SPP.

Instead of focusing on minimization of the number of shifts, the real objective of the proposed problem, which is the minimization of overall berthing time at all ports, will be used. This will be done by maximizing the utilization of quay cranes and minimizing the number of shifts. Additionally, realistic stability and operational constraints, as well as characteristics of individual container, are taken into consideration as well.

Structure of containerships

A containership has a cellular structure. The layout of containerships differs from ship to ship because the location of engine rooms, accommodation sections, and hull shapes are different in each ship. Figure 1 shows the cellular structure of a sample containership.

Figure 1.

An example of a containership.

Containers are held in bays along the length of the containership (shown in Figure 1). The containers are stacked in rows and tiers in each bay. Each tier and row in the bay are made up of a slot. The position of the container within the containership, in general, is entirely specified by three indices: bay-row-tier. So, to describe the position of the containers, a three-dimensional matrix is introduced. Each element of the matrix corresponds to a slot in the vessel. The value in the matrix might serve as the container number assigned to the corresponding slot or simply can be a binary digit showing the availability of the slot. Specific hull shapes and design structures may be addressed by using predefined values in this way.

As shown in Figure 1, 20 ft containers are positioned in the odd bays, while 40 ft containers are assigned in the even bays. Two odd bays can make up of an even bay. Therefore, if a 40 ft container is placed in an even bay, then the odd bays that together make that even bay cannot be used for 20 ft containers.

Container stowage

Container stowage is to allocate containers in the optimal slots of a containership according to several principles and information. The stowage results of containerships are shown in figures, such as container pre-stowage plan, actual container stowage plan, and final stowage plan of a containership. Both the actual container stowage plan and final stowage plan of a containership are based on the container pre-stowage plan of a containership.

Figure 2 shows the detailed process of container stowage. Firstly, according to the information of containers, the voyage, and booking of containerships, as well as the relevant parameters of containerships, the shipping company compiles the container pre-stowage plan of the containership in a container terminal and send the figure to the shipping agent. Then the shipping agent hands it to the container terminal. When the pre-stowage plan cannot meet the principle of the stowage, it is essential to adjust the allocation of some containers according to the stability, strength, and floating state of the containership. After that, the container terminal compiles the actual stowage plan of the containership according to the pre-stowage plan and conditions of the container terminals without violating the stowage principle. Then the container terminal staff will handle containers from the containership based on the proofreading actual stowage plan. Finally, after the handling operations, the shipping company will compile the final stowage plan according to the actual handling situations, which can provide the basis for the next container terminal. Meanwhile, the final stowage plan is also an important source to validate the stability, buoyancy, and strength of the containership.

Figure 2.

The flow chart of container stowage.

As a result, according to the description of container stowage, making a suitable stowage plan (pre-stowage plan) is of vital importance during the process of loading containerships. Moreover, the stability of the containership is of vital importance and runs throughout the whole process of stowage plan.

Containership stability

To guarantee the safety of a containership during the voyage, the stability and stress forces should be considered. A complete description of the technical requirements for containerships can be found in Jensen et al.⁴³ The stability of a containership is the ability to return to its upright position when disturbed, after the disturbing force is eliminated. Meanwhile, it is crucial for containers and containerships that the weight is properly distributed; in that case, the structure is not overstressed, and the standard criteria of stability are met. In general, there are two types of stability rules, named as hydrostatic and experimental rules of stability for containerships.

Hydrostatic rules of stability

Hydrostatic rules of stability come from the Archimedes rules, which says that a body floating or submerging in a fluid is buoyed up by a force equal to the water it displaces. The way to measure the stability of a containership is to determine the location of the center of gravity (G), the center of buoyancy (B) and the meta-center of the ship (M). The location relationship among these three forces is shown in Figure 3.

(1) G under M: A containership is in stable equilibrium meaning that when inclined, it tends to return to the initial upright position.

(2) G above M: Unstable equilibrium exists in this situation. In this situation if the ship is inclined to a small angle, it tends to heel over even further.

(3) G coincides with M: A containership is in neutral equilibrium in this situation and if inclined to a small angle, it will tend to stay in that angle until another external force is applied.

Figure 3.

An example of gravity forces, buoyancy forces and meta-center of a containership.

Experimental rules of stability

Since calculating the meta-centric height requires detailed information of the containership structure, experimental rules of stability have been created by ship planners, which are applicable to typical containerships. These rules can be categorized as longitudinal, cross, and vertical equilibrium.

(1) Longitudinal equilibrium

Containers stowed at the bow side of the ship create a tilt which acts as an opposite force to the tilt created by the containers at the stern side. If these forces cancel out each other, the bow and stern will have the same waterline height. Longitudinal equilibrium requires that the difference in the height of waterline between the bow and stern does not exceed a given threshold. Figure 4 shows an example of longitudinal equilibrium.

(2) Cross equilibrium

Figure 4.

An example of longitudinal equilibrium.

Related to the axis of symmetry going through the bow to the stern, the containers at the left side also create a tilt opposite to the one by the containers at the right side. If these tilts are not equal, the vessel will heel toward the heavier side. To ensure the stability, the weight difference between the two sides must be kept within a predetermined range. Figure 5 illustrates different situations.

(3) Vertical equilibrium

Figure 5.

An example of cross equilibrium.

According to the hydrostatic rules, the location of G changes when the vertical weight changes in the vessel. However, the vertical shift does not affect B, because the underwater portion of the containership does not change. This means that shifting the heavier containers to the lower compartments of the vessels helps improve the stability. This is the reason why empty containers are mostly stored above the deck area. The experimental rule of vertical stability requires that the total weight of each tier of containers to be less than or equal to the total weight of the tier underneath.

Container properties

In this problem, container weight, type, size, and destinations are also of significant importance. Therefore, the followings introduce the container weight, type, and destination.

Container weight

In this paper, all containers have different weight. To guarantee the safety and stability of the containership, the total weight of all containers cannot exceed the weight capacity of the containership. Also, the weight of a row of three 20 ft and 40 ft containers cannot exceed a prior established value, called MT and MF, respectively.

Container type

Containers have different types, such as standard, refrigerated, and hazardous containers. When stowed, refrigerated containers are placed in a specific position of a containership, where there is a plug. Considering the safety during the voyage, hazardous containers are not allowed on the upper deck or adjacent to the refrigerated containers.

Container size

Standard container slots on containerships are usually designed for 20 ft containers, so 40 ft containers need two 20 ft container slots. Each container needs four twist locks fixed in the upper lock hole of the container below it, and thus 20 ft containers cannot be put on the 40 ft containers. In addition, when two 20 ft containers are put on one 40 ft container, the middle of the container is under great pressure, which makes the container easily deformed and damaged. Consequently, 40 ft containers are only allowed to be put on two 20 ft containers or one 40 ft containers, while 20 ft containers are not allowed to be put on 40 ft containers.

Container destination

Generally, containers with further destinations should be loaded first on the lower tiers, while the containers with nearer destinations should be loaded last on the upper tiers to reduce the number of rehandling operations during the voyage.

Assumptions

The following assumptions are made to formulate a new mathematical model of the proposed integrated problem.

(1) The structure of the containership is general, and each position is identified using bay-row-tier.

(2) The route which the containership takes in her voyage and the sequence of the ports where she stops are fixed and known in advance.

(3) The number of containers to be handled at each port and the complete relevant information of the containers (weight, size, type, and destination) are known ahead.

(4) The number of available quay cranes and the technical parameters of quay cranes are known before as well as the range of each bay.

(5) The proper storage plan in the yard is done to rip the benefit of the SPP model.

Problem formulation

Based on the assumptions in the former section, a novel mathematical model that minimizes the ship’s berthing time at all ports by minimizing the number of shifts and maximizing crane utilization is proposed. This formulation of the problem improves the model in Hamedi.⁴⁰

Notations and variables

The notations and variables used in the model are as follows.

$i, j$ : the container index;

$p$ : the port index;

$k$ : the quay crane index;

$b$ : the bay index of the containership;

$s$ : the row index in the bay $b$ ;

$c$ : the tier index in the stack $s$ of the bay $b$ ;

$T_{c}$ : the set of all the 20 ft containers;

$F_{c}$ : the set of all the 40 ft containers;

$C$ : the set of all the containers, $i, j \in C, T_{c} \cup F_{c} \equiv C$ ;

$R$ : the set of all the refrigerated containers;

$H$ : the set of all the hazardous containers;

$P$ : the set of all the ports, $p \in P$ ;

$L$ : the set of all the container locations available in the containership, $(b, s, c) \in L$ ;

$K$ : the set of quay cranes in each port, $k \in K$ ;

$E$ : the set of all the even bays in the containership;

$O$ : the set of all the odd bays in the containership;

$B$ : the set of all the bays in the containership, $b \in B, E \cup O \equiv B$ ;

$B_{r}$ : the set of all the bays with the plugs;

$S_{b}$ : the set of all the rows in the bay $b$ , $s \in S_{b}$ ;

$T_{b, s}$ : the set of all the tiers in the row $s$ of the bay $b$ , $t \in T_{b, s}$ ;

$O_{i}$ : the origin of the container $i$ ;

$D_{i}$ : the destination of the container $i$ ;

$N$ : the number of ports;

$N K_{p}$ : the number of quay cranes at the port $p$ ;

$N_{kp}$ : the number of containers handled by quay crane $k$ at the port $p$ ;

$t h_{k}$ : the handling time of a container by quay crane $k$ ;

$S B_{kp}$ : the start bay of the quay crane $k$ at the port $p$ ;

$E B_{kp}$ : the end bay of the quay crane $k$ at the port $p$ ;

$W_{i}$ : the weight of the container $i$ ;

$W_{p max}$ : the containership weight capacity at the port $p$ ;

$W_{row}$ : the maximum weight allowed for a row;

$MT$ : the container weight threshold among three adjacent 20 ft containers in a row;

$MF$ : the container weight threshold among three adjacent 40 ft containers in a row;

$LRB$ : the left-right balance threshold;

$BSB$ : the bow-stern balance threshold;

$CWB$ : the quay crane workload balance threshold;

$T B_{p}$ : decision variable, the total berthing time of all the ports;

$δ_{ip}^{(b, s, t)}$ : decision variable, if the container $i$ is assigned to the slot $(b, s, t)$ at the port $p$ , $δ_{ip}^{(b, s, t)} = 1$ ; otherwise, $δ_{ip}^{(b, s, t)} = 0$ ;

$U_{ip}$ : decision variable, if the container $i$ is unloaded at the port $p$ , $U_{ip} = 1$ ; otherwise, $U_{ip} = 0$ ;

$I_{ijp}$ : decision variable, if the container $i$ is on top of the container $j$ at the port $p$ , $I_{ijp} = 1$ ; otherwise, $I_{ijp} = 0$ ;

$J_{ikp}$ : decision variable, if the container $i$ is handled by quay crane $k$ at the port $p$ , $J_{ikp} = 1$ ; otherwise, $J_{ikp} = 0$ .

Objectives

In general, the objective of SPP was to minimize the number of shifts. However, the actual objective is to reduce the total berthing time for container terminal dispatchers. Although minimizing the number of shifts may contribute to this aim, there are still some other factors influencing this aim, such as quay crane operations. Maximizing the utilization of quay crane and minimizing the number of shifts in the meanwhile will produce a better stowage plan, which will save the operational cost and congestion.

The total berthing time of each port equals to the time that the last allocated quay crane finishes its job.

F_{1} = min \sum_{p = 1}^{N} T B_{p}

(1)

\begin{matrix} T B_{p} = max {t h_{k_{1}} \sum_{i_{1} = 1}^{N_{k_{1} p}} J_{i_{1} k_{1} p}, t h_{k_{2}} \sum_{i_{2} = 1}^{N_{k_{2} p}} J_{i_{2} k_{2} p}, . . ., \\ t h_{k_{N K_{p}}} \sum_{i_{N K_{p}} = 1}^{N_{k_{N K_{p}} p}} J_{i_{N K_{p}} k_{N K_{p}} p}} \end{matrix}

(2)

However, the objective function is nonlinear, so we transfer the crane utilization considerations to the constraints (Constraints (33)−(39)) and use the following objective function. Thus, an improved objective function is introduced, which minimizes the total number of shifts over the voyage.

F_{2} = min \sum_{i \in C} \sum_{p = 1}^{N} U_{ip}

(3)

Constraints

The constraints are divided into four parts: (1) slot assignment constraints; (2) stability constraints; (3) shift constraints; (4) crane utilization constraints.

Slot assignment constraints

The slot assignment constraints are written as follows.

During the whole voyage, a container is forced to be assigned to a slot at its origin port and stay aboard up to its destination.

\sum_{(b, s, t) \in L} δ_{ip}^{(b, s, t)} = 1, \forall i \in C, \forall p \in [O_{i}, D_{i} - 1]

(4)

A container is prohibited to be assigned to a slot before its origin or after its destination port, which is shown as follows.

\sum_{(b, s, t) \in L} \sum_{p = D_{i}}^{N} δ_{ip}^{(b, s, t)} = 0, \forall i \in C

(5)

\sum_{(b, s, t) \in L} \sum_{p = 1}^{O_{i} - 1} δ_{ip}^{(b, s, t)} = 0, \forall i \in C

(6)

An individual slot can be assigned to no more than one container at each time.

\sum_{i \in C} δ_{ip}^{(b, s, t)} \leq 1, \forall p \in P, \forall (b, s, t) \in L

(7)

A container can be only assigned to one slot at each time.

\sum_{(b, s, t) \in L} δ_{ip}^{(b, s, t)} = 1, \forall i \in C, \forall p \in P

(8)

A container cannot be assigned onto an empty slot. Considering the characteristics of different sizes of containers in the slot, this constraint is written separately for 20 ft and 40 ft containers, which was not considered in Hamedi.⁴⁰

When the container is a 20 ft container, the constraint is shown as follow:

\begin{matrix} \sum_{i \in T_{c}} δ_{ip}^{(b, s, t)} - \sum_{j \in T_{c}} δ_{jp}^{(b, s, t + 1)} \geq 0, \forall p \in P, \forall b \in O, \forall s \in S_{b}, \\ \forall t = 1, 2, . . ., | T_{b, s} | - 1 \end{matrix}

(9)

When the container is a 40 ft container, the constraint is shown as follow:

\begin{matrix} (\sum_{i \in F_{c}} δ_{ip}^{(b, s, t)} - \sum_{j \in F_{c}} δ_{jp}^{(b, s, t + 1)}) \\ + (\sum_{i_{1} \in T_{c}} δ_{i_{1} p}^{(b - 1, s, t)} + \sum_{i_{2} \in T_{c}} δ_{i_{2} p}^{(b + 1, s, t)} - \sum_{j \in F_{c}} δ_{jp}^{(b, s, t + 1)}) \geq 0, \\ \forall p \in P, \forall b \in E, \forall s \in S_{b}, \forall t = 1, 2, . . ., | T_{b, s} | - 1 \end{matrix}

(10)

The relationship between two containers $i$ and $j$ at the same port that the container $i$ cannot be put both on top, and under the container $j$ at the same time is shown as follow:

I_{jip} + I_{ijp} \leq 1, \forall i \neq j \in C, \forall p \in P

(11)

The following constraint determines whether there are some containers on the container $i$ .

\begin{matrix} δ_{ip}^{(b, s, t)} + \sum_{t' > t \in T_{b, s}} δ_{i' p}^{(b, s, t')} \leq i + I_{i' ip}, \forall i \neq i' \in C, \\ \forall p \in P, \forall b \in B, \forall s \in S_{b} \end{matrix}

(12)

The relationship between containers with different destination ports that containers with further destination ports cannot be positioned on the containers with nearer destination ports is shown as follow, and this constraint was not mentioned in Hamedi.⁴⁰

\begin{matrix} D_{i} * δ_{ip}^{(b, s, t)} - D_{j} * δ_{jp'}^{(b, s, t')} \geq 0, \\ \forall p \in [O_{i}, D_{i} - 1], \forall p' \in [O_{j}, D_{j} - 1], \forall b \in B, \forall s \in S_{b}, \\ \forall t = 1, 2, . . ., | T_{b, s} | - 1, D_{i} < D_{j} \end{matrix}

(13)

Since in this paper, both 20 feet and 40 ft containers are considered, their location constraints should also be taken into consideration. Hamedi⁴⁰ had incorrect location constraints for these containers. Hence the revised constraints are shown in Constraints (14)−(19).

Constraint (14) guarantees that 20 ft containers cannot be stowed in the even bays, while Constraint (15) ensures that 40 ft containers cannot be assigned in the odd bays.

\sum_{i \in T_{c}} δ_{ip}^{(b, s, t)} = 0, \forall p \in P, \forall b \in E, \forall s \in S_{b}, \forall t \in T_{b, s}

(14)

\sum_{i \in F_{c}} δ_{ip}^{(b, s, t)} = 0, \forall p \in P, \forall b \in O, \forall s \in S_{b}, \forall t \in T_{b, s}

(15)

20 ft containers cannot be stowed in odd bays that consist of even bays already chosen for 40 ft containers, which is shown as follows:

\begin{matrix} \sum_{i \in T_{c}} δ_{ip}^{(b + 1, s, t)} + \sum_{j \in F_{c}} δ_{jp}^{(b, s, t)} \leq 1, \forall p \in P, \forall b \in O, \\ \forall s \in S_{b}, \forall t \in T_{b, s} \end{matrix}

(16)

\begin{matrix} \sum_{i \in T_{c}} δ_{ip}^{(b - 1, s, t)} + \sum_{j \in F_{c}} δ_{jp}^{(b, s, t)} \leq 1, \forall p \in P, \forall b \in O, \\ \forall s \in S_{b}, \forall t \in T_{b, s} \end{matrix}

(17)

Constraints (18) and (19) make the stowage of 20 ft containers on 40 ft containers infeasible.

\begin{matrix} \sum_{i \in T_{c}} δ_{ip}^{(b - 1, s, t + 1)} + \sum_{j \in F_{c}} δ_{jp}^{(b, s, t)} \leq 1, \forall p \in P, \forall b \in O, \\ \forall s \in S_{b}, \forall t = 1, 2, . . ., | T_{b, s} | - 1 \end{matrix}

(18)

\begin{matrix} \sum_{i \in T_{c}} δ_{ip}^{(b + 1, s, t + 1)} + \sum_{j \in F_{c}} δ_{jp}^{(b, s, t)} \leq 1, \forall p \in P, \forall b \in O, \\ \forall s \in S_{b}, \forall t = 1, 2, . . ., | T_{b, s} | - 1 \end{matrix}

(19)

In this paper, different types of containers are also considered. So, refrigerated containers must be stowed in the bays with plugs.

\begin{matrix} δ_{ip}^{(b, s, t)} = 1, \forall i \in R, \forall p \in [O_{i}, D_{i}], \forall b \in B_{r}, \\ \forall s \in S_{b}, \forall t \in T_{b, s} \end{matrix}

(20)

To ensure the safety of the voyage, the stowage of hazardous containers adjacent refrigerated containers is prohibited. Although Hamedi⁴⁰ considered different types of containers, the constraints related to them were not clear in his model. As a result, a more clear and detailed description is proposed.

Constraints (21) and (22) ensure that hazardous containers and refrigerated containers are not adjacent in the horizontal direction, while Constraint (23) prevents hazardous containers being positioned adjoining refrigerated containers in the vertical direction.

\begin{matrix} δ_{ip}^{(b, s, t)} + δ_{jp}^{(b + 1, s, t)} \leq 1, \forall i \in R, \forall j \in H, \forall p \in P, \\ \forall b = 1, 2, . . ., | B | - 1, \forall s \in S_{b}, \forall t \in T_{b, s} o r \forall i \in H, \\ \forall j \in R, \forall p \in P, \forall b = 1, 2, . . ., | B | - 1, \forall s \in S_{b}, \forall t \in T_{b, s} \end{matrix}

(21)

\begin{matrix} δ_{ip}^{(b, s, t)} + δ_{jp}^{(b, s + 1, t)} \leq 1, \forall i \in R, \forall j \in H, \forall p \in P, \forall b \in B, \\ \forall s = 1, 2, . . ., | S_{b} | - 1, \forall t \in T_{b, s} o r \forall i \in H, \forall j \in R, \\ \forall p \in P, \forall b \in B, \forall s = 1, 2, . . ., | S_{b} | - 1, \forall t \in T_{b, s} \end{matrix}

(22)

\begin{matrix} δ_{ip}^{(b, s, t)} + δ_{jp}^{(b, s, t + 1)} \leq 1, \forall i \in R, \forall j \in H, \forall p \in P, \forall b \in B, \\ \forall s \in S_{b}, \forall t = 1, 2, . . ., | T_{b, s} | - 1 o r \forall i \in H, \forall j \in R, \\ \forall p \in P, \forall b \in B, \forall s \in S_{b}, \forall t = 1, 2, . . ., | T_{b, s} | - 1 \end{matrix}

(23)

Stability constraints

The stability of the vessel must be maintained through the entire voyage, so the stability constraints based on experimental rules of stability are written as follows.

Constraints (24) and (25) are the horizontal and cross equilibrium stability showing that the weight difference between the right side and the left side and between the bow side and the stern side are within acceptable thresholds.

\begin{matrix} | \sum_{i \in C} \sum_{b \in B} \sum_{s = 1}^{⌊ | S_{b} | / 2 ⌋} \sum_{t \in T_{b, s}} δ_{ip}^{(b, s, t)} * W_{i} * (⌊ | S_{b} | / 2 ⌋ - s) - \sum_{i \in C} \sum_{b \in B} \sum_{s = ⌈ | S_{b} | / 2 ⌉}^{| S_{b} |} \sum_{t \in T_{b, s}} δ_{ip}^{(b, s, t)} * W_{i} * (r - ⌊ | S_{b} | / 2 ⌋) | \\ \leq LRB, \forall p \in P \end{matrix}

(24)

\begin{matrix} | \sum_{i \in C} \sum_{b = 1}^{⌊ | B | / 2 ⌋} \sum_{s \in S} \sum_{t \in T_{b, s}} δ_{ip}^{(b, s, t)} * W_{i} * (⌊ | B | / 2 ⌋ - b) - \sum_{i \in C} \sum_{b = ⌈ | B | / 2 ⌉}^{| B |} \sum_{s \in S} \sum_{t \in T_{b, s}} δ_{ip}^{(b, s, t)} * W_{i} * (b - ⌊ | B | / 2 ⌋) | \\ \leq BSB, \forall p \in P \end{matrix}

(25)

The weight of each tier must be equal to or lighter than the weight of the tier underneath, which is shown as follow:

\begin{matrix} \sum_{i \in C} \sum_{b \in B} \sum_{s \in S_{b}} δ_{ip}^{(b, s, t)} * W_{i} & \leq \sum_{j \in C} \sum_{b \in B} \sum_{s \in S_{b}} δ_{jp}^{(b, s, t - 1)} * W_{j}, \\ \forall p \in P, \forall t = 2, . . ., | T_{b, s} | \end{matrix}

(26)

Constraints (27) and (28) limit the total weight of the containers on board for the vessel and for each row, respectively.

\sum_{i \in C} \sum_{(b, s, t) \in L} δ_{ip}^{(b, s, t)} * W_{i} \leq W_{p max}, \forall p \in P

(27)

\sum_{i \in C} \sum_{b \in B} \sum_{s \in S_{b}} δ_{ip}^{(b, s, t)} * W_{i} \leq W_{row}, \forall p \in P, \forall t \in T_{b, s}

(28)

Moreover, we also added another two constraints on container weights (Constraints (29) and (30)) to make the model more realistic. Constraints (29) and (30) state that a row of at most three containers of either 20 ft or 40 ft cannot exceed the values $MT$ and $MF$ , respectively, which usually correspond to 45 and 60 t.

\begin{matrix} \sum_{i \in T} δ_{ip}^{(b, s, t)} * W_{i} + \sum_{i' \in T} δ_{i' p}^{(b, s, t + 1)} * W_{i'} \\ + \sum_{j \in T} δ_{jp}^{(b, s, t + 2)} * W_{j} \leq MT, \\ \forall p \in P, \forall b \in B, \forall s \in S_{b}, \forall t = 1, . . ., | T_{b, s} | - 2 \end{matrix}

(29)

\begin{matrix} \sum_{i \in F} δ_{ip}^{(b, s, t)} * W_{i} + \sum_{i' \in F} δ_{i' p}^{(b, s, t + 1)} * W_{i'} \\ + \sum_{j \in F} δ_{jp}^{(b, s, t + 2)} * W_{j} \leq MF, \\ \forall p \in P, \forall b \in B, \forall s \in S_{b}, \forall t = 1, . . ., | T_{b, s} | - 2 \end{matrix}

(30)

Shift constraints

A container is forced to be unloaded at its destination port.

U_{i D_{i}} = 1, \forall i \in C

(31)

A container should be unloaded if the container underneath must be unloaded at a port.

U_{ip} - U_{jp} \leq 1 - I_{jip}, \forall i \neq j \in C, \forall p \in P

(32)

If the position of a container in the containership changes from one port to another, the container must be rehandled to shift its original position. When the location $(b', s', t')$ in the port $p + 1$ is different from the location $(b, s, t)$ in the port $p$ , the container $i$ has been rehandled in the port $p + 1$ . Although Hamedi⁴⁰ referred to the same constraints, we improve the mathematical expression to make it express more clearly and succinctly.

\begin{matrix} δ_{i (p + 1)}^{(b', s', t')} - δ_{ip}^{(b, s, t)} - M (1 - U_{i (p + 1)}) \leq 0, \forall i \in C, \\ \forall p \in [O_{i}, D_{i}], \forall (b, s, t) \in L \end{matrix}

(33)

Crane utilization constraints

Compared to Hamedi,⁴⁰ more clear and detailed crane utilization constraints have been developed in this paper.

Given the number of quay cranes at each port and the range of bays on which the quay cranes will operate, Constraints (34)−(37) find which quay crane performs the loading/unloading operation for each container at its origin and destination port and ensure that only one quay crane will perform the handling operation.

J_{ik O_{i}} \geq \sum_{b = S B_{k O_{i}}}^{E B_{k O_{i}}} \sum_{s \in S_{b}} \sum_{t \in T_{b, s}} δ_{i O_{i}}^{(b, s, t)}, \forall i \in C, \forall k \in [1, N K_{O_{i}}]

(34)

\sum_{k = 1}^{N K_{O_{i}}} J_{ik O_{i}} = 1, \forall i \in C

(35)

J_{ik D_{i}} \geq \sum_{b = S B_{k D_{i}}}^{E B_{k D_{i}}} \sum_{s \in S_{b}} \sum_{t \in T_{b, s}} δ_{i D_{i}}^{(b, s, t)}, \forall i \in C, \forall k \in [1, N K_{D_{i}}]

(36)

\sum_{k = 1}^{N K_{D_{i}}} J_{ik D_{i}} = 1, \forall i \in C

(37)

Constraints (38)−(39) determines the shifting at that port is by which quay crane.

\begin{matrix} J_{jkp} + 2 \geq U_{ip} + J_{ikp} + I_{jip}, \forall i \neq j \in C, \forall p \notin [O_{j}, D_{j}], \\ \forall k \in [1, N K_{p}] \end{matrix}

(38)

\sum_{k = 1}^{N K_{p}} J_{ikp} = U_{ip}, \forall i \in C, \forall p \notin [O_{i}, D_{i}]

(39)

Constraint (40) balances the load among available quay cranes at each port. That is to say; it is required that the difference between the workload of any quay crane and the average workload over all the quay cranes at a port does not exceed a given threshold.

\begin{matrix} | \sum_{i \in C} \sum_{k = 1}^{N K_{p}} J_{ikp} / N K_{p} - \sum_{i \in C} J_{ik' p} | \leq \sum_{i \in C} \sum_{k = 1}^{N K_{p}} J_{ikp} / CWL, \\ \forall p \in P, \forall k' \in [1, N K_{p}] \end{matrix}

(40)

Solution approach

Avriel et al.¹⁴ proposed the SPP, considering a single type of containers, which proved to be an NP-complete problem, while in this paper, not only different types, and sizes of containers but quay crane operations are considered. Therefore, the problem is more complicated in this paper. Additionally, a large number of variables and constraints are involved in the model, so it is difficult to solve large-scale problems in polynomial time.

GA is an adaptive heuristic search method based on the evolutionary idea of natural selection which represents processes in natural system for evolution, specifically the principle of survival of the fittest by Charles Darwin. As such it performs an intelligent directed random search within a defined search space to optimize a problem. GAs use a vector of numbers to represent decision variables. They pursue an iterative process in which several solution points are being explored simultaneously at each step. The only information required for search is a fitness assessment. In summary, GAs have been succeeded in solving optimization problems, especially SPP (such as Dubrovsky et al.,¹⁵ Hamedi,⁴⁰ Azevedo et al.,⁴¹ Todd and Sen⁴⁴). Hence, to solve the large-scale problems effectively, we improve GA proposed by Hamedi⁴⁰ and Azevedo et al.,⁴¹ and design a better GA based on a new encoding mode of assignment strategies to solve the integration of SPP and CSP. The procedure of the proposed algorithm is illustrated in Figure 6.

Figure 6.

The procedure of genetic algorithm based on the new encoding mode of assignment strategy.

Moreover, chromosome in GAs means the data structure that holds a potential solution, while individual in GAs means collection of a chromosome and its fitness value.

Representation

There are two typical encoding modes on SPP. One is the complete encoding mode proposed by Todd and Sen.⁴⁴ In this mode, each chromosome represents a slot and the natural number encoding method is adopted, which represents the number of containers to be transported. This method is easy to operate, but too cumbersome, especially when calculating the fitness function. The other is the compact encoding mode proposed by Dubrovsky et al.¹⁵ This mode improves the complete encoding mode, and the chromosomes only represent the changed slots. However, this mode is still unable to encode containers of different sizes and types.

Consequently, to encode containers of different sizes and types, a new encoding mode based on assignment strategy is introduced.

Four basic properties of the containers are size, weight, destination, and type. One can sort a list of containers based on each of these criteria or any combination of them. For example, the list can be sorted by destination only or by destination first, then weight and then size. Furthermore, each criterion can be applied in an ascending or descending fashion. The total number of sorting possibilities is 632 $(\sum_{r = 1}^{4} P_{r}^{4} * 2^{r} = 632)$ .

Based on the analysis above and the characteristics of the proposed problem, 13 grouping strategies are introduced to group the containers, shown in Table 1.

Table 1.

Grouping strategies.

Grouping strategy	Instructions
Grouping strategy 1 (G1)	The containers are grouped only by weight from heavy to light.
Grouping strategy 2 (G2)	The containers are grouped only by weight from light to heavy.
Grouping strategy 3 (G3)	The containers are grouped only by destination port from far to near.
Grouping strategy 4 (G4)	The containers are grouped only by destination port from near to far.
Grouping strategy 5 (G5)	The containers are grouped by weight from heavy to light and destination port from far to near.
Grouping strategy 6 (G6)	The containers are grouped by weight from heavy to light and destination port from near to far.
Grouping strategy 7 (G7)	The containers are grouped by weight from light to heavy and destination port from far to near.
Grouping strategy 8 (G8)	The containers are grouped by weight from light to heavy and destination port from near to far.
Grouping strategy 9 (G9)	The containers are grouped by destination port from far to near and weight from heavy to light.
Grouping strategy 10 (G10)	The containers are grouped by destination port from far to near and weight from light to heavy.
Grouping strategy 11 (G11)	The containers are grouped by destination port from near to far and weight from heavy to light.
Grouping strategy 12 (G12)	The containers are grouped by destination port from near to far and weight from light to heavy.
Grouping strategy 13 (G13)	The containers are grouped randomly.

Meanwhile, there are also some different loading strategies for container loading operations. In this paper, six loading strategies are adopted to load containers.

(1) Loading strategy 1 (L1):

The containers are loaded tier by tier from left to right. The containers are placed from the lowest tier of each bay. When all the empty slots of the bay are filled, then containers can be assigned to the next bay.

(2) Loading strategy 2 (L2):

The containers are loaded bay by bay from left to right. The containers are placed from the lowest tier of each bay. When all the empty slots of the lowest tier in all the bays are filled, then containers can be assigned to the second-lowest tier.

(3) Loading strategy 3 (L3):

In contrast to L1, the containers are loaded tier by tier from right to left.

(4) Loading strategy 4 (L4):

In contrast to L2, the containers are loaded bay by bay from right to left.

(5) Loading strategy 5 (L5):

All the previous loading strategies are to load containers from the bow to the stern. This strategy is to load containers from the middle of the containership to the bow and stern, respectively. Containers are assigned to the lowest tier of each row from left to right.

(6) Loading strategy 6 (L6):

Like L5, but containers are assigned to the slots from the bow to the middle of the containership and from the middle of the containership to the stern.

When arriving at each destination port, containers need unloading. So, two different unloading strategies are adopted in the paper.

(1) Unloading strategy 1 (U1):

Only containers belonging to the destination port and containers blocking other containers to be unloaded are unloaded.

(2) Unloading strategy 2 (U2):

All the containers are unloaded at the destination port.

Based on the determined loading and unloading strategies, quay cranes begin to handle the containers. Since a containership is usually operated by multiple quay cranes, there are a variety of quay crane operation strategies according to the different location relationships between quay cranes. Taking two quay cranes as an example, the quay crane operation strategies are shown as follows:

(1) Quay crane operation strategy 1 (QC1):

One quay crane operates containers from the stern to the middle of the containership, and the other operates containers from the middle to the bow.

(2) Quay crane operation strategy 2 (QC2):

One quay crane operates containers from the bow to the stern, and the other operates containers from the middle to the stern.

As a result, loading, unloading and quay crane operation strategies can be summarized as operation strategies (shown in Table 2).

Table 2.

Operation strategies.

Operation strategy	Instructions
Operation strategy 1 (O1)	L1+U1+QC1
Operation strategy 2 (O2)	L1+U2+QC1
Operation strategy 3 (O3)	L2+U1+QC1
Operation strategy 4 (O4)	L2+U2+QC1
Operation strategy 5 (O5)	L3+U1+QC1
Operation strategy 6 (O6)	L3+U2+QC1
Operation strategy 7 (O7)	L4+U1+QC1
Operation strategy 8 (O8)	L4+U2+QC1
Operation strategy 9 (O9)	L5+U1+QC1
Operation strategy 10 (O10)	L5+U2+QC1
Operation strategy 11 (O11)	L6+U1+QC1
Operation strategy 12 (O12)	L6+U2+QC1
Operation strategy 13 (O13)	L1+U1+QC2
Operation strategy 14 (O14)	L1+U2+QC2
Operation strategy 15 (O15)	L2+U1+QC2
Operation strategy 16 (O16)	L2+U2+QC2
Operation strategy 17 (O17)	L3+U1+QC2
Operation strategy 18 (O18)	L3+U2+QC2
Operation strategy 19 (O19)	L4+U1+QC2
Operation strategy 20 (O20)	L4+U2+QC2
Operation strategy 21 (O21)	L5+U1+QC2
Operation strategy 22 (O22)	L5+U2+QC2
Operation strategy 23 (O23)	L6+U1+QC2
Operation strategy 24 (O24)	L6+U2+QC2

Consequently, the core of chromosome encoding proposed in this paper is to use different assignment strategies (grouping strategies + operation strategies). Figure 7 shows an example of a chromosome. The first half of the chromosome represents the grouping strategy, while the second half shows the operation strategy. According to the chromosome, the containership passes through four ports. Take Port 1 and Port 4 as an example: the grouping strategy in Port 1 is G10, and the operation strategy in Port 1 is O14, that is, L1+U2+QC2. Since Port 4 is the final destination port, only unloading operations are carried out. Therefore, only quay crane operation strategy is considered in Port 4, which is QC1.

Figure 7.

An example of chromosome encoding based on assignment strategy.

Fitness function and selection

The choice of the fitness function has a significant impact on the convergence rate of GAs and whether the optimal solutions can be found. Since the proposed problem is a minimization problem, the smaller the objective value is, the higher the fitness value should be. So, the reciprocal of the objective function should be taken as the fitness function.

The roulette wheel method with the elitist strategy is used to select the better parent individuals in this paper. Firstly, some parent individuals with better fitness value will be reserved and do not participate in genetic operations in the current generation; then, the rest will be retained based on the roulette wheel method.

Crossover operation

Crossover operations are a vital operation in GAs, which will affect the convergence rate of GAs. There are numerous methods of crossover operations, while in the paper the crossover method in Figure 8 is applied.

Figure 8.

An example of crossover operation.

Mutation operation

After the crossover operation, to prevent GAs from falling into the local optimal solution, the mutation operation is adopted. Considering the encoding characteristics of the chromosomes, randomly change the number of grouping strategy and operation strategy of one port into another strategy to complete the mutation operation (see Figure 9).

Figure 9.

An example of mutation operation.

Penalty operation

In the process of calculation, it is easy to determine whether the containership achieves stability balance according to the weight and position of containers and whether the number of containers operated by quay crane exceed the maximum workload. However, since the individuals are generated randomly, and genetic operations will also change the original individuals, there might be some solutions not satisfying the stability or crane utilization constraints. To solve these problems, penalty operation is introduced. After genetic operations, the objective of the individual does not meet the stability or crane utilization constraints, penalty operation will work, which means the objective will be multiplied by penalty factor, and then obtain a new objective.

For example, if the longitudinal balance of the containership is not satisfied, the calculation of the penalty factor and notations used in the calculation are shown as follows:

$bow_weigh t_{i}$ : Individual $i$ ’s weight of all containers from the bow to the middle of the containership;

$stern_weigh t_{i}$ : Individual $i$ ’s weight of all containers from the stern to the middle of the containership;

$avg_weigh t_{i}$ : Individual $i$ ’s average weight of all containers in the containership;

$θ$ : the threshold of longitudinal balance;

$μ_{i}$ : the penalty factor of the individual $i$ .

μ_{i} = \frac{| bow_weigh t_{i} - stern_weigh t_{i} | - avg_weigh t_{i} * θ}{avg_weigh t_{i} * θ}

(41)

Stopping criterion

Many common stopping criteria are adopted in traditional GAs to balance the computation time and convergence to the approximate optimal solution. It is of vital importance to choose the best approach to stop the operation. Thus, in this paper, when the maximum generations are proposed, the algorithm is terminated.

Computational experiments

Initial setting

Some experimental and parameter settings are considered to conduct the experiments as follows.

(1) The data we used in all large-sized experiments are from the survey data we collected from Dalian Container Terminal.

(2) According to the pilot experiments, the population size, maximum iteration, selection probability, crossover probability, and mutation probability are set to be 100, 300, 0.9, 0.8, and 0.15, respectively.

(3) To reduce the potential error of each group of experiments due to randomness, each group of experiments is conducted 30 times, and the results are the average of 30 experiments.

(4) The proposed algorithm in our paper is carried out using MATLAB R2016b. All the experiments are conducted based on a personal computer with Intel Core i7–8650 @ 4.20GHz processors and 16 GB RAM under the Windows 10 operating system.

Small-sized experiments

Model validation

To verify the proposed model in this paper can produce the optimal solution, a sample data is taken from Avriel et al.,¹⁷ where the stability constraints of the containership were not considered. In their paper, they aimed to reduce the number of shifts and considered containers were all the same. In this part, we also neglect the stability constraints and crane utilization constraints. In this experiment, the containership visits five ports and it has one bay, two rows, and five tiers. Table 3 shows the transportation matrix.

Table 3.

Transportation matrix.

Origin port Destination port	2	3	4	5
1	4	4	2	0
2	0	2	0	1
3	0	0	2	3
4	0	0	0	1

As is shown in Table 3, the number of containers is 19; however, the number of shifts is reported to be 20. That is to say, at least one rehandling operation is performed. The result of the new problem also verifies that result. The solutions of the new problem (stowage plan) are shown in Figure 10. In Figure 10, the dotted rectangle represents the slot of the containership, and the rectangle with two colors represents a container. The narrow color bar shows the origin port of a container, while the wide color bar shows the destination port of a container. The black dot on the right corner of the rectangle means that the container will be unloaded in the next port, and the rectangle with the red dot represents the container needs to be rehandled in the next port. The rectangle with black frame surrounded shows that the container has been rehandled in the current port.

Figure 10.

Stowage plan of the new problem.

As is observed in Figure 10, Container 13 must be rehandled in Port 4 so that Container 9 and 10 can be unloaded in Port 4. Hence, although there are 19 containers to be transported between ports, the number of shifts is 20.

In general, stability constraints cannot be ignored. It is assumed that all the containers in previous experiment are all the same and weigh 1 unit. As is seen from Figure 10, the stowage plan in Ports 2–4 does not satisfy the stability constraint, since the total weight on the right side of the containership in Ports 2–4 is not equal to the total weight on the left side. Assume that 1-unit tolerance in the weight difference is allowed; however, Ports 3 and 4 still violate the stability constraints. Therefore, to make the stowage plan in every port meet the stability constraints, the previous problem will be resolved, considering stability constraints with 1-unit threshold. The new stowage plan is shown in Figure 11.

Figure 11.

Stowage plan of the new problem considering stability constraints.

As is seen from Figure 11, the number of rehandling operations remains the same. If we had set the stability weight threshold to 0, the problem would be infeasible, because of the number of containers in Ports 2 and 4. Thus, in realistic situations, ballast water is used to maintain balance.

The experiment with different types of containers

In this section, containers are of different types. The containership visits four ports and it has one bay, four rows, and five tiers. The plugs are in the last row of the bay. In each port, there are two quay cranes. Two scenarios are considered in this experiment. Scenario 1 aims at reducing the number of shifts, while Scenario 2 attempts to minimize the total berthing time. The results are shown in Table 4, and the stowage plan of Scenario 2 is shown in Figure 12. In Figure 12, the red dotted rectangle represents the slot with the plug, which can be occupied with the refrigerated container.

Table 4.

The solution of the example with single size containers.

	Crane utilization at Port 1/%		Crane utilization at Port 2/%		Crane utilization at Port 3/%		Crane utilization at Port 4/%		Crane utilization at Port 5/%		The number of shifts	Total berthing time	Average crane utilization/%
	1	2	1	2	1	2	1	2	1	2
1	100	100	100	100	76.9	100	100	100	20	100	41	41	89.7
2	100	100	100	100	91.7	100	75	100	100	100	42	39	96.7

Figure 12.

Stowage plan of Scenario 2.

From Table 4, we can see that the proposed model can solve the problem with different types of containers. Although the number of shifts in Scenario 2 is a little greater than that in Scenario 1, the average crane utilization in Scenario 2 is 7% greater than that in Scenario 1 and the total berthing time in Scenario 2 is 4.9% less than that in Scenario 1. Meanwhile, the utilization of quay cranes in each port in Scenario 2 are all better than that in Scenario 1.

The experiment with different sizes of containers

In this experiment, we use containers of different sizes. We used the same data in 4.3.2 of Hamedi.⁴⁰ However, the model was not able to obtain feasible solutions. Solutions indicated that not all containers departing from Port 2 could be loaded on the containership and some containers are left in Port 2. This is because Hamedi⁴⁰ assumed that 20 ft containers could be loaded on top of the 40 ft containers, and he neglected that 20 ft containers cannot be loaded in even bays and 40 ft containers cannot be loaded in odd bays.

To solve the problem, we changed Container 23 in Hamedi⁴⁰ from a 20 ft container to a 40 ft container in this paper. Thus, there are 44 containers to be transported between four ports, including 17 40 ft containers and 27 20 ft containers. The other data in this example remain the same as Hamedi.⁴⁰

Same as the experiment in the section above, 2 scenarios are considered in this section as well. The objective of Scenario 1 is to minimize the number of shifts, while Scenario two aims at minimizing the total berthing time. The solution of the example is shown in Table 5.

Table 5.

The solution of the example with single size containers.

	Crane utilization at Port 1/%		Crane utilization at Port 2/%		Crane utilization at Port 3/%		Crane utilization at Port 4/%		Crane utilization at Port 5/%		The number of shifts	Total berthing time	Average crane utilization/%
	1	2	1	2	1	2	1	2	1	2
1	100	100	9.1	100	18.1	100	75	0	100	85.7	44	51	68.8
2	100	100	30	100	20	100	80	13.3	100	85.7	46	49	72.9

It can be seen from Table 5, although the number of shifts in Scenario 2 is a little greater than that in Scenario 1, the average crane utilization in Scenario 2 is 4.1% greater than that in Scenario one and the total berthing time in Scenario 2 is 3.9% less than that in Scenario 1.

From all the small-sized experiments above, the model is feasible. Also, using an appropriate objective in stowage planning problem can save berthing time. Although the classical objective, minimizing the number of shifts, can help reduce the total berthing time, it cannot be used as the only objective. The results indicate that simultaneously considering the maximization of crane utilization and the minimization of the number of shifts can enhance the total berthing time. Thus, the model balances the tradeoff between crane utilization and the number of shifts.

Large-sized experiments

Experiments with different productivity of quay cranes

According to Azevedo et al.,⁴¹ it was generally assumed that the productivity of quay cranes is the same; in fact, none of the stowage planning papers in the literature have considered the important features of quay crane scheduling described in Meisel and Bierwirth⁷ However, in practice, the productivity of quay cranes differs from ports to ports. The following experiments are conducted to verify that the proposed algorithm can find the optimal solutions in the experiments with different productivity of quay cranes.

In the experiment, the containership is composed of 20 bays, each of which has 10 rows and 10 tiers. During the voyage, the containership passes through five ports, where there are two quay cranes to handle containers. The capacity of the containership is 2000 TEUs, and the transportation matrix of containers between ports is shown in Table 6.

Table 6.

Transportation matrix for the 2000 TEUs containership.

Origin port destination port	2	3	4	5
1	463	141	308	685
2	0	217	155	319
3	0	0	270	155
4	0	0	0	672

Firstly, the productivity of quay cranes in five ports is assumed to be constant, and the time for each quay crane to operation a container is 4 s/container. The results of the experiment are shown in Table 7.

Table 7.

Results for the constant productivity of quay cranes.

	Port 1		Port 2		Port 3		Port 4		Port 5		Total
No. of Quay cranes	1	2	1	2	1	2	1	2	1	2
Operation frequencies of quay cranes	800	797	600	626	427	428	750	751	915	916
Operation time of quay cranes/s	3200	3188	2400	2504	1708	1712	3000	3004	3660	3664
The number of shifts	1597		1226		855		1501		1831		7010
The total number of rehandling times	0		37		36		48		0		121
The berthing time/s	3200		2504		1712		3004		3664		14,084

Secondly, under the same other conditions, upgrade the productivity of quay cranes in Port 3, which is twice that of quay cranes in other ports. Therefore, the results of the new experiment are shown in Table 8.

Table 8.

Results for the updated productivity of quay cranes at Port 3.

	Port 1		Port 2		Port 3		Port 4		Port 5		Total
No. of quay cranes	1	2	1	2	1	2	1	2	1	2
Operation frequencies of quay cranes	800	797	600	622	500	485	715	721	915	916
Operation time of quay cranes/s	3200	3188	2400	2488	1000	970	2860	2884	3660	3664
The number of shifts	1597		1222		985		1436		1831		7071
The total number of rehandling times	0		33		166		31		0		230
The berthing time/s	3200		2488		1000		2884		3664		13,236

From Tables 7 and 8, the number of shifts and the total number of rehandling times are increased by 0.9% and 90.1%, respectively, but the berthing time is decreased by 6.0%. Hence, the algorithm tries to rehandle the containers at the port with faster quay cranes, to reduce the number of shifts at the second and the fourth port. From the economical perspective if the shipping line is charged by time, having extra container moves at Port 3 in the cases that upgraded quay cranes are available is advised. Otherwise, if the ports charge per container handling basis, solutions for minimizing the total number of rehandling times should be used. In any case, the algorithm is flexible to create appropriate stowage and loading plan with respect to technical and economic considerations.

The performance of the proposed algorithm

To show the performance of the proposed algorithm, a comparison experiment between the proposed method and the previous method in Hamedi⁴⁰ is implemented by using all the data in the section above and the productivity of quay cranes are the same at all ports. In addition, $GAP$ is introduced to represent the difference value of the result between the proposed method and the previous method in Hamedi.⁴⁰ The calculation of $GAP$ is shown as follow:

G A P = \frac{t h e r e s u l t u s e d t h e p r e v i o u s m e t h o d - t h e r e s u l t u s e d t h e p r o p o s e d m e t h o d}{t h e r e s u l t u s e d H a m e d i' s m e t h o d} * 100 %

(42)

The comparative results are shown in Table 9.

Table 9.

Results of the comparison experiment.

	The proposed method	The previous method	GAP (%)
The number of shifts	7010	7092	1.2
The total number of rehandling times	121	321	62.3
The berthing time/s	14,084	14,316	1.6
Computational time/s	2189.2	17,759.1	87.7

From Table 9, the number of shifts, the total number of rehandling times, and the berthing time calculated by the proposed algorithm are all better than those calculated by the previous algorithm in Hamedi.⁴⁰ This is because a novel encoding mode based on assignment strategies is introduced, which is composed of grouping strategies as well as operation strategies. However, Hamedi⁴⁰ only considered grouping strategies and neglect the operation strategies, which can also affect the location of containers in containerships and help reduce the total number of rehandling times. Also, the computational time of our algorithm has obvious advantages over that of the algorithm in Hamedi.⁴⁰ Since Hamedi⁴⁰ used binary code to solve the problem, it will take long time to decode, especially in large-sized experiments. In the proposed algorithm, decimal coding is used, which is easy to understand and timesaving to decode. Moreover, the penalty operation is introduced to solve the infeasible solutions and reduce the computational time. Therefore, the proposed algorithm in the paper has more advantages than the algorithm in Hamedi⁴⁰ in solving the integration of SPP and CSP.

Convergence experiment of the proposed algorithm

To show the convergence of the proposed algorithm, another experiment is carried out. In this experiment, the containership is composed of 20 bays, each of which has 10 rows and 10 tiers. During the voyage, the containership passes through five ports, where there are two quay cranes to handle containers. Meanwhile, there are 5752 containers will be transported during the voyage. Additionally, the productivity of quay cranes in five ports is assumed to be the same, and the time for each quay crane to operation a container is 2 s/container. The convergence graph is shown in Figure 13.

Figure 13.

The convergence graph.

As is shown in Figure 13, after nearly 170 generations, the results of berthing time tend to a fixed value, which proves that the proposed method is convergent and conforms to the convergence rules of GAs.

Conclusion

Because of the tense competition among ports in recent years, improving the efficiency of ports has become an important issue in containership operations. One of the major performance measures is the berthing time at a port. The arrangement of containers both within the container terminal and on the containership plays a vital role in determining the berthing time. The utilization of quay cranes, responsible for loading and unloading containers to and from the containerships, can also affect the total berthing time of containerships. Therefore, stowage planning and crane split problem are interrelated in this paper. Additionally, to conform to the real situation, constraints of both stowage planning problem and crane split problem are considered.

Stowage planning problem is verified to be an NP-complete problem, and meanwhile the operation of quay cranes is considered in the paper, which makes the problem more complicated. Hence, a GA based on a novel encoding mode of assignment strategies is developed, which introduces penalty operations to solve the unfeasible solution problems. To verify the proposed algorithm feasible and efficient, some experiments are conducted: firstly, a series of small-sized experiments are carried out to prove that the model can balance the tradeoff between crane utilization and the number of shifts. Secondly, two groups of experiments are implemented: the result of the first group experiment on different productivity of quay cranes shows that the proposed algorithm is flexible to create appropriate stowage plan with respect to technical and economic considerations and the algorithm can rehandle the containers at the port with faster quay crane so that the berthing time can be reduced by 6.0%, while the result of the second group verifies that the proposed algorithm can get a better solution (the number of shifts, the total number of rehandling times and the berthing time are decreased by 1.2%, 62.3%, and 1.6%, respectively) in a shorter time than that the previous algorithm. Finally, another large-sized experiment is conducted to validate the convergence of the proposed algorithm. Therefore, according to the computational experiments, the proposed algorithm is effective and efficient in solving the integration problem and enhancing the efficiency of container terminals.

Future work can pay attention to the following parts: firstly, to verify the performance of the proposed algorithm, some experiments with much larger data and other comparison experiments with other algorithms will be conducted; secondly, we will focus on the uncertainty of the model parameters; thirdly, we will integrate stowage planning problem with other operations in container terminals, such as yard operations; last but not least, there are some up-to-date methods in the optimization problems, such as Garra Ruffa inspired optimization, spider monkey optimization, etc., which can be also used in the integrated problem of stowage planning and crane split in future; finally, with the development of rail-water intermodal transportation, railway transportation plan will be considered, which will also affect stowage planning problem.

Footnotes

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was supported by the General science and technology projects of Beijing Municipal Education Commission, [grant number KM202110037001] and the Youth Research Fund Project of Beijing Wuzi University, [grant number 2020XJQN05].

ORCID iD

Yimei Chang

References

The United Nations Conference on Trade and Development. Review of Maritime Transport, 2019.

Steenken

Voß

Stahlbock

. Container terminal operation and operations research-a classification and literature review. OR Spectrum 2004; 26(1): 3–49.

Guan

Yang

Zhou

The crane scheduling problem: models and solution approaches. Ann Oper Res 2013; 203(1): 119–139.

Bierwirth

Meisel

A survey of berth allocation and quay crane scheduling problems in container terminals. Eur J Oper Res 2010; 202(3): 615–627.

Chang

Jiang

Yan

, et al. Integrating berth allocation and quay crane assignments. Transport Res E-Log 2010; 46(6): 975–990.

Imai

Chen

Nishimura

, et al. The simultaneous berth and quay crane allocation problem. Transport Res E-Log 2008; 44(5): 900–920.

Meisel

Bierwirth

Heuristics for the integration of crane productivity in the berth allocation problem. Transport Res E-Log 2009; 45(1): 196–209.

Yang

Wang

An optimization approach for coupling problem of berth allocation and quay crane assignment in container terminal. Comput Ind Eng 2012; 63(1): 243–253.

Hendriks

MPM

Lefeber

Udding

. Simultaneous berth allocation and yard planning at tactical level. OR Spectrum 2013; 35(2): 441–456.

10.

Braekers

Caris

Janssens

GK.

Integrated planning of loaded and empty container movements. Spectrum 2013; 35(2): 457–478.

11.

Zeng

Yang

Integrating simulation and optimization to schedule loading operations in container terminals. Comput Oper Res 2009; 36(6): 1935–1944.

12.

Shields

JJ.

Containership stowage: A computer-aided preplanning system. Mar Technol 1984 1984; 21(04): 370–383.

13.

Botter

Brinati

MA.

Stowage container planning: A model for getting an optimal solution. In: International conference on computer applications in the automation of shipyard operation & ship Design, VII. DBLP, 1991.

14.

Avriel

Penn

Shpirer

Container ship stowage problem: complexity and connection to the coloring of circle graphs. Discrete Appl Math 2000; 103(1-3): 271–279.

15.

Dubrovsky

Levitin

Penn

A genetic algorithm with a compact solution encoding for the container ship stowage problem. J Heuristics 2002; 8(6): 585–599.

16.

Ding

Chou

MC.

Stowage planning for container ships: A heuristic algorithm to reduce the number of shifts. Eur J Oper Res 2015; 246(1): 242–249.

17.

Avriel

Penn

Shpirer

, et al. Stowage planning for container ships to reduce the number of shifts. Ann Oper Res 1998; 76: 55–71.

18.

Ambrosino

Paolucci

Sciomachen

A MIP heuristic for multi port stowage planning. Transp Res Procedia 2015; 10: 725–734.

19.

Ambrosino

Paolucci

Sciomachen

Experimental evaluation of mixed integer programming models for the multi-port master bay plan problem. Flexible Serv Manuf J 2015; 27(2-3): 263–284.

20.

Kroer

Svendsen

Jensen

, et al. Symbolic configuration for interactive container ship stowage planning. Comput Intell 2016; 32(2): 259–283.

21.

Lee

Fan

Hsu

WJ.

A near-optimal algorithm for constraint test ordering in automated stowage planning. IEEE Trans Autom Sci Eng 2018; 15: 1298–1308.

22.

Matsaini Budi

. Solving the container stowage problem (CSP) using particle swarm optimization (PSO). IOP Conference2018, pp.337: 1–6.

23.

Roberti

Pacino

A decomposition method for finding optimal container stowage plans. Transp Sci 2018; 52(6): 1444–1462.

24.

Parreño-Torres

Alvarez-Valdes

Parreño

Solution strategies for a multiport container ship stowage problem. Math Probl Eng 2019; 2019: 1–12.

25.

Parreño-Torres

Çalık

Alvarez-Valdes

, et al. Solving the generalized multi-port container stowage planning problem by a matheuristic algorithm. Comput Oper Res 2021; 133(2–3): 105383.

26.

Zhang

Mei

Liu

, et al. Stowage planning in multiple ports with shifting fee minimization. Sci Program 2018 2018; 2018: 1–9.

27.

Zhang

, et al. Multi-port stowage planning for inland container liner shipping considering weight uncertainties. IEEE Access 2018; 6: 66468–66480.

28.

Imai

Sasaki

Nishimura

, et al. Multi-objective simultaneous stowage and load planning for a container ship with container rehandle in yard stacks. Eur J Oper Res 2006; 171(2): 373–389.

29.

Azevedo

ATD

Ribeiro

Sena

GJD

, et al. Solving the 3D container ship loading planning problem by representation by rules and meta-heuristics. Int J Data Anal Tech Strateg 2014; 6: 228–260.

30.

Araújo

Chaves

de Salles Neto

, et al. Pareto clustering search applied for 3D container ship loading plan problem. Expert Syst Appl 2016; 44: 50–57.

31.

Ambrosino

Paolucci

Sciomachen

Computational evaluation of a MIP model for multi-port stowage planning problems. Soft Comput 2017; 21: 1753–1763.

32.

Fazi

A decision-support framework for the stowage of maritime containers in inland shipping. Transport Res E-Log 2019; 131: 1–23.

33.

Parthibaraj

Palaniappan

Gunasekaran

, et al. Multi-agent system with iterative auction mechanism for master bay plan problem in marine logistics. Marit Pol Manage 2017; 44: 705–726.

34.

Shen

Zhao

Xia

, et al. A deep q-learning network for ship stowage planning problem. Pol Marit Res 2017; 24(s3): 102–109.

35.

Parreño

Pacino

Alvarez-Valdes

A grasp algorithm for the container stowage slot planning problem. Transport Res E-Log 2016; 94: 141–157.

36.

Ambrosino

Sciomachen

A shipping line stowage-planning procedure in the presence of hazardous containers. Marit Econ Logist 2021; 23: 49–70.

37.

Korach

Brouer

Jensen

RM.

Matheuristics for slot planning of container vessel bays. Eur J Oper Res 2020; 282(3): 873–885.

38.

Christensen

Pacino

A matheuristic for the cargo mix problem with block stowage. Transport Res E-Log 2017; 97: 151–171.

39.

Larsen

Pacino

A heuristic and a benchmark for the stowage planning problem. Marit Econ Logist 2021; 23(1): 94–122.

40.

Hamedi

Containership load planning with crane operations. PhD thesis, University of Maryland, USA, 2011.

41.

Azevedo

Neto

Chaves

, et al. Solving the 3D stowage planning problem integrated with the quay crane scheduling problem by representation by rules and genetic algorithm. Appl Soft Comput 2018; 65: 495–516.

42.

Martínez

RM.

Solving the Ship Loading and Crane Split Problem. Master’s thesis, Polytechnic University of Catalonia, Spain, 2020.

43.

Jensen

Pacino

Ajspur

, et al. Container Vessel Stowage Planning. Copenhagen: Weilbach, 2018.

44.

Todd

Sen

A multiple criteria genetic algorithm for containership loading. In: Presented at international conference on genetic algorithms, East Lansing, MI, 1997.