# Integer Linear Programming Models for the Containership Stowage Problem

Authors: Huiling Zhu; Mingjun Ji; Wenwen Guo
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

This study deals with the containership stowage problem, determining how to stow containers to the containership slots. To improve the containership operational efficiency and meet the containership seaworthy requirements, a basic model is proposed for the simplified containership stowage problem. And then, it is extended by incorporating more practical considerations, which are progressively embedded in extensive models for different scenarios. These integer linear programming models aim to minimize the number of overstows under the restriction of the mechanical factors, the physical structure, and the stowing rules. The experimental results show that the models have strong scalability for various scenarios.


---

## Body

## 1. Introduction

In the past two decades, container transportation has grown rapidly with the development of the global transportation industry. Since containerships are important means of container transportation, their operation efficiency affects the performance of global container transportation. A modern containership sails on a given route and handles thousands of containers at each port of call. Before the arrival of a containership at any port of call, the planner should develop an appropriate stowage plan to record the specific location of each container to be loaded into the containership. Once the stowage plan is completed, the operators follow the plan to complete the loading operations. Generally, the stowage plan is developed based on the mechanical factors, the physical structure, and the stowing rules. This study selects three indicators from the mechanical factors to measure the seaworthiness under sail, including the metacentric height (GM), trim, and strength. First, the GM must be ensured that it is within a reasonable range. Second, the trim must be within the corresponding limits. Finally, the weight distribution in the containership must meet the requirements of the stress limit of the containership structure. The requirements of the shear and bending moment are measured by the strength in this study. As for the physical structure, each container should be supported by another container, bottom plate, or deck. In addition, the loading of containers must obey the stowing rules. For example, a 40 ft container cannot be placed under a 20 ft container. Refrigerated containers should be placed closer to the main plug.To improve the containership operational efficiency, a stowage plan is made to minimize unnecessary operations when unloading containers from the containership. The number of overstows is a very common indicator to evaluate the quality of a stowage plan. Overstows cannot be avoided if containers destined for nearer ports are blocked by containers destined for farther ports. When the containership calls at a port, the container destined for the current port is defined as the target container. If a container destined for a farther port is stacking on the target container, the container is defined as the blocked container. In this condition, the handling equipment first needs to unload the blocked container and then unload the target container. The number of overstows equals the number of blocked containers. At present, the stowage plan is mainly completed manually with the aid of computers and is still characterized by implementation difficulties. First, stowage planners are faced with enormous time pressure. As the containership usually informs the port of its arrival time and containership status information only a few hours beforehand, the planners should make a stowage plan according to the corresponding information within only a few hours. Second, the stowage planners have a heavy workload in making the stowage plan. Ocean-going containerships generally have a large capacity. In any port of call, ocean-going containerships often need to handle thousands of containers. Finally, it is difficult to make a scheme to minimize the number of overstows under the interaction of the mechanical factors, the physical structure, and the stowing rules. Therefore, the containership stowage problem (CSP) is very complicated. Although much experience has been accumulated in practice, there are, nevertheless, few effective methods in solving the CSP. It is critical to contribute to the theoretical method for stowage optimization, thus facilitating intelligent stowage.The remainder of this study is organized as follows: a literature review is provided in Section2. Section 3 records the modeling progress, presenting discussions on four scenarios. Section 4 reports the results of the numerical experiments in different scenarios and verifies the efficiency of the established models. Finally, conclusions are drawn in Section 5.


## 2. Literature Review

A growing number of studies on the CSP have been published in the past few years. As the CSP is constrained by many factors and the capacity of the containership has grown rapidly during these years, Avriel et al. [1] demonstrated that the CSP is a large-scale multiconstrained NP-hard problem. In addition, Tierney et al. [2] analyzed the complexity of the CSP considering hatch overstowage.The CSP is usually solved by single-phase and multiphase approaches. Avriel et al. [3], Dubrovsky et al. [4], Azevedo et al. [5], and Ding and Chou [6] used the single-phase approach, consisting of formulating a model for describing the entire stowage problem. Wilson and Roach [7], Kang and Kim [8], Pacino et al. [9], and Ambrosino et al. [10, 11] divided the CSP into two phases, including master planning and slot planning. The master planning phase focused on satisfying stability according to the container distribution in the containership. Pacino et al. [9] researched master planning and decided on the number of containers of a specific group to be allocated to a location. Recently, a new heuristic for a master planning phase based on a partial variable fixing procedure was presented by Ambrosino et al. [11]. Moreover, the slot planning phase was executed after the master planning phase. Slot planning approaches are very simplified representations of stability as they are based on the results of the master planning phase [12].Many methods were used for solving the CSP, such as mathematical programming [13–16], constraint programming [16, 17], constraint-based local search [18], genetic algorithms [4, 19, 20], dedicated heuristics [3, 5, 6, 21–24], matheuristics [25], 3D packing [12], simulation [26], and case-based methods [27].Mathematical programming approaches in previous research include several accurate models with limited scalability. Here, the most representative models are presented from Table1: (1) Avriel et al.’s model [3] was regarded as the first stowage model of a ship bay, only involving 20 ft general containers to be loaded into the ship bay, and the ship bay is formulated as a rectangular structure. The stowing rules were not significant on the stowage planning because of the single container type and regular structure. (2) Ambrosino and Sciomachen [13] and Ambrosino et al. [14] established models for the master planning problem. The objective function was to minimize the total stowage time. This model considered 20 ft and 40 ft standard containers but did not consider refrigerated containers. In addition, it ignored the effect of hatch covers on the stowage. In this model, a constraint avoided positioning containers that have to be unloaded earlier below those containers that have to be unloaded later. The hard constraint may not be applicable because overstowage cannot be avoided in reality. (3) The third model was developed by Li et al. [15] based on the second model. The objective was to maximize space utilization while minimizing the operation cost from upload and download containers, with vessel stability, industry regulations, and customized rules as the constraints. The operation cost is being measured by the amount of shifting. This model considered the minimal amount of shifting as one of the objective functions. And this model was also applicable to a containership structured with hatch covers. However, it ignored refrigerated containers. As a multiobjective model, it was not easy to find the optimal solution. (4) The fourth model was proposed by Delgado et al. [16]. The objective function was a weighted sum of four objectives. The multiobjective model was finally transformed into the single-objective model. More types of containers were considered in this model, including standard, refrigerated, and high-cube containers. However, this model was only presented for a single-bay section, ignoring the impact of the weight distribution in the single bay on the whole containership mechanical indicators. In addition, a single-bay section was regarded as a separate storage area without considering hatch covers. (5) The last model was proposed by Fazi [33]. It was established for inland transportation to maximize the loading capacity. Thus, the containership’s structure was specific without hatch covers. It almost considered all types of containers excluding refrigerated containers.Table 1
List of established containership stowage mathematical models.
LiteratureHatch coverShip-bay configurationContainer typeContainer sizeContainer weightStabilityObjectiveGeneralRefrigeratedOthers20′40′ToleranceAccuracyAvriel et al. [3]Rectangular structure√√To minimize the number of overstowsAmbrosino and Sciomachen [13]Not mentioned√√√Groups√To minimize the stowage timeAmbrosino et al. [14]√Not mentioned√√√Groups√To minimize the stowage timeLi et al. [15]√Not mentioned√√√Groups√Multiobjectives: (1) to minimize the number of overstows; (2) to maximize the vessel utilizationPacino et al. [18]√Not mentioned√√√Groups√To minimize the difference between ballast water and its initial valueDelgado et al. [16]Rectangular structure√√High cube√√IndividualsWeighted goalAzevedo et al. [5]Rectangular structure√√SameWeighted goalAmbrosino et al. [11]√Practical√√√Groups√Weighted goalAmbrosino et al. [28]√Practical√√Open top√√Groups√Weighted goalChristensen and Pacino [29]Not mentioned√√High cube√√GroupsTo maximize the loading capacity/revenueRoberti and Pacino [30]Rectangular structure√√To minimize the number of unloading operationsLi et al. [31]Not mentioned√√Groups√To minimize the number of occupied ship stacksLi et al. [32]Rectangular structure√√√Groups√Two-stage objectives: (1) to minimize the ship-bay occupancy rate; (2) to minimize the heeling moment of each ship bay at each portFazi [33]Not mentioned√High cube√√Individuals√To maximize the loading capacityParreno-Torres et al. [34]Rectangular structure√√To minimize the number of overstowsKorach et al. [35]Rectangular structure√√High cube√√Individuals√Weighted goalThis study√Practical√√√√Individuals√To minimize the number of overstowsTable1 lists the objectives, constraints, and other practical considerations of the CSP in the established models. Most of the literature studies did not consider the influence of hatch covers on the model establishment. Some of them did not consider the stability constraints because of a single ship-bay’s stowage. For those works of the literature that considered the stability constraints, most of them used the tolerance of vessel bow and stern as the measurement of stability limitation for the purpose of simplifying calculations, but only a few works of the literature incorporated accurate stability indicators into the models. Besides, works of the literature regarded the ship bay with a rectangular structure, which only involves a single stowing rule, but is not realistic. These models were not universal for the practical CSP.To the best of our knowledge, none of the previous mathematical problems considered all the major characteristics of the CSP. This study establishes a basic integer linear programming model and gradually extends it in several integer linear programming models to strengthen scalability by progressively adding characteristics of the real problem as listed in the last row of Table1, which can be regarded as representative models of the CSP for various scenarios. The identifications of scenarios depend on different containership status information and container attributes as the key elements in Table 1, which are defined and analyzed in the next section. The models in this study determine the stowing locations of containers in the containership for various scenarios, considering the mechanical factors, the physical structure, and the stowing rules. These models help to reduce the number of overstows when unloading containers from the containership and improving containership operational efficiency. Thus, the mathematical formulation is obviously a single-phase approach, and there is no need to split the master planning and slot planning.


## 3. Modeling of the CSP

### 3.1. Problem Description

The CSP determines the specific location of each container in a designated containership to improve the containership operational efficiency and meet the seaworthy requirements under sail. The mechanical factors, the physical structure, and the stowing rules are considered as the constraints of the mathematical model. Based on the literature review of objective functions in the models, this study chooses the number of overstows that is always easy to be quantified to measure the containership operational efficiency.For the establishment of mathematical models, a containership with a particular structure is separated by the ship bays, and the ship bays are made of ship tiers, as illustrated in Figure1. Ship bays marked by even numbers can hold 40 ft containers, but ship bays marked by odd numbers can only hold 20 ft containers. Refrigerated containers must be stowed in the refrigerated slots. It is important to distribute the weights in ship bays of horizontal length and in ship tiers of vertical height. The weight distribution should satisfy the GM, trim, and strength requirements [18], which are summarized as the stability constraints in this study. The GM is measured by the weight distribution in the longitudinal direction, while the trim and strength are both measured by the weight distribution in the vertical direction. The estimation of the GM, trim, and strength is based on the container distribution in each block and each tier. A block is defined as a separate storage unit not interrupted by other blocks. A block in this study refers to a 20 ft ship bay or the space on/under the deck of a 20 ft ship bay, depending on whether hatch covers are considered. The block can be defined according to different containership types: (1) for an ocean-going containership, there exist hatch covers for ship bays. Thus, the spaces on/below the deck of ship bay 01 and ship bay 03 can be regarded as four blocks. (2) For an inland containership, there is no hatch cover. Thus, ship bay 01 and ship bay 03 can be regarded as two blocks.Figure 1
Illustration of an ocean-going containership structure: (a) the front view of a containership; (b) the top view of a containership.
(a)(b)The containers to be loaded into the containership differ in terms of size, type, weight, and destination port. Besides, containers with the same attributes are classified into the same group. This study considers two sizes of containers, including 20 ft and 40 ft containers, and two types of containers, including general and refrigerated containers. The weight of containers to be loaded into the containership is uncertain because of logistics limitations, which are usually classified [31]. Contrary to Li et al. [31], we believe that the container weight is known in advance because precise weighing techniques have emerged and been used in multiple western ports [33]. And the number of container destination ports corresponds to the number of ports in the fixed voyage. The CSP focuses on how to allocate each group of containers to the ship tiers of the ship bays, which can be achieved by solving mathematical models.


### 3.2. Integer Programming (IP) Model Establishment

IP models are proposed for the CSP. The modeling process is gradually presented in four scenarios. The identifications of scenarios depend on different containership information and container attributes, as listed in Table2. Containership information involves the containership loading information and structure information. In summary, the richer the container types, the more complicated the stowing rules to consider. Whether the ship-bay configuration is rectangular or not mentioned in the model is worthy of universalization in this study. Besides, we select whether the containership is initially empty before the loading operations as the containership loading information and select whether the containership has hatch covers as the containership structure information.Table 2
Scenarios’ introduction of the four models.
Given informationParametersModel I (scenario I)Improved model I (scenario I)Model II (scenario II)Model III (scenario III)Model IV (scenario IV)Containership informationEmpty containership initiallyYYYNNHatch coversNNYYYContainer sizes20 ft containerYYYYY40 ft containerNNNNYContainer typesGeneral containerYYYYYRefrigerated containerNNNNYFigure 2
A feasible stowage plan for a ship bay structured with the hatch cover.Figure 3
Two kinds of status information of a ship bay before the loading process.
(a)(b)Figure 4
A feasible stowage plan of a 40 ft ship bay: (a) bay 01; (b) bay 03.
(a)(b)Figure 5
A feasible stowage plan of a 40 ft ship bay on the deck involving 20 ft and 40 ft containers: (a) bay 01; (b) bay 03.
(a)(b)The definition of scenarios is described as follows:(1)
Scenario I analysis:The containership is empty initially, and the containership in model I has no hatch cover in the hull structure. The containers to be loaded into the containership are all 20 ft general containers. To simplify the CSP, there are no 40 ft container and refrigerated container to be loaded into the containership.(2)
Scenario II analysis:From the view of the physical structure, each ship bay is divided into two subsections by a hatch cover, and each subsection can be regarded as a single unit for storage. The space on the deck can be open for stowing containers even if the space under the deck is not completely used, which is a special case and breaks the rule stipulated in the basic model. The containers on the deck are not suspended because they are supported by the hatch cover.A container is overstowed if it is discharged later than a container stowed below it, either in the same stack or under the hatch cover, which is defined as hatch overstowage, causing extra crane moves [9]. In Figure 2, containers destined for port 4 and port 3 are loaded under the deck, and containers destined for port 2 are loaded on the deck. Overstows are avoided in this instance by stowing containers with the descending order of destination ports.When the containers on the deck have a further destination compared to the containers under the deck, the containers on the deck must be overstowed when unloading the containers under the deck. Taking the ship bay in Figure2 as an example, if containers destined for port 2 are loaded under the deck and containers destined for port 3 are loaded on the deck, then at port 2, the operations should be unloading the containers on the deck first, unloading the containers destined for port 2, and finally reloading the containers where they are initially on the deck.(3)
Scenario III analysis:Model II is established in an ideal scenario, assuming the containership is empty initially before the loading process. Without the effect of initially loaded containers in the containership, it is easy to obtain a stowage plan to avoid overstows when unloading containers from the containership at subsequent ports, but when the containership has been loaded with containers before the loading process in the current port, the overstows cannot be completely avoided. If there are enough empty slots in the containership for stowing containers with a far destination, it is possible to avoid overstows. Whether the overstows can be avoided is based on the quantitative relation of containers loaded in each previous port, containers to be loaded in the current port, and the left slots of each kind of block for stowing containers. The blocks are characterized by the nearest destination of containers in each block.If there are containers that have a near destination occupying the lower space of all ship bays, overstows cannot be avoided. In this kind of extreme scenario, it is vital to find the optimal solution in minimizing overstows. In Figure3(a), the block on the deck is empty, denoted by M-block, in which M is a large number, but the block under the deck is loaded with containers destined for port 2, denoted by 2-block. If the containers with a near destination are loaded into the two blocks whether on the deck or under the deck, the overstows can be avoided. In Figure 3(b), if the containers to be loaded in the current port are to be shipped to port 4, overstows cannot be avoided. If there are 4 containers destined for port 4 to be loaded, they should be put on the containers destined for port 2 on the deck, minimizing overstows. If they are loaded under the deck, all the containers on the deck should first be overstowed, producing 12 overstows.(4)
Scenario IV analysis:The containership is initially not empty before the loading operations, and it has hatch covers in the hull structure. The containers to be loaded into the containership involve 20 ft general containers, 20 ft refrigerated containers, 40 ft general containers, and 40 ft refrigerated containers.A 40 ft container occupies two 20 ft slots in the containership. In this study, there is no definition of 40 ft slots and 40 ft ship bays. Two neighboring 20 ft slots with the same ship tier in the adjacent 20 ft ship bays are occupied simultaneously when a 40 ft container is loaded into the containership. The 20 ft ship bays are numbered by continuous integers, 1, 2, 3, …, etc. In this model, a 40 ft container may occupy two 20 ft slots of the first and second ship bays, or third and fourth ship bays, but it is impossible for a 40 ft container to occupy two 20 ft slots of the second and third ship bays or fourth and fifth ship bays limited by the containership structure.In Figure4, bay 01 and bay 03 correspond to the first and second 20 ft ship bays in the model. The containers on the deck are all 40 ft containers, that is, the slots in the first two tiers are occupied by these 40 ft containers, but the containers in bay 01 under the deck are 20 ft containers, and the corresponding slots in bay 03 are empty. If all containers are assigned on the deck, the stowage plan should comply with the stowing rule that 20 ft containers cannot be stowed on 40 ft containers. A feasible stowage plan is illustrated in Figure 5. 20 ft containers must be stowed below 40 ft containers, and it is better for two 20 ft containers occupying the slots in the same stack and tier of bay 01 and bay 03, which is helpful for 40 ft containers stowing on them.Besides, refrigerated containers must be stowed in the refrigerated slots with power plugs, which depends on the containership structure.


#### 3.2.1. Model I

IP of the CSP is presented in Tables3–5: Table 3 lists the parameters, Table 4 lists the decision variables, and Table 5 shows the objective function and constraints of model I.Table 3
Parameters in model I.
ParametersMeaningNtThe number oft-containers. t-containers refer to the containers in group t, which have fixed size, type, weight, and destination portCapbThe number of empty slots in blockbwtThe weight oft-containersPiThe weight of the containership’s constant, including the weight of the crew and supplies, spare parts, oil, and waterZiHeight between the center of gravity of loadPi and the baselineVDaThe vertical distance between ship tiera and the hull bottomxi¯The vertical distance between the center of gravity of loadPi and the baselineKMThe vertical distance between the transverse metacentric and the baselineslotabThe number of empty slots in tiera of block bdtThe destination port oft-containerMTCCentimeter-trim momentLCBThe horizontal distance between the buoyancy and the stern frame of the containershipCCGbThe horizontal distance between the center of gravity of blockb and the midshipCCGi0The horizontal distance between the center of gravity of loadPi and the midshipMA large positive numberGMmaxThe upper bound of the containership GMGMminThe lower bound of the containership GMTmaxThe upper bound of the containership trimTminThe lower bound of the containership trimUPbThe upper bound of the ship tier in blockbLPbThe lower bound of the ship tier in blockbCThe coefficient of the hull buoyancy levernThe total moment of the weight in the first half hull and that in the second half hullDLThe displacement of the unloaded containershipLThe length of the containershipTable 4
Decision variables in model I.
Decision variablesMeaningxbt= 1 ift-container is allocated to block b; = 0, otherwiseXbtThe number oft-containers allocated to block byabt= 1 ift-container is allocated to tier a of block b; = 0, otherwiseYabtThe number oft-containers allocated to tier a of block bRabt= 1 ift-containers allocated to tier a of block b are overstowed; = 0, otherwiseTable 5
Mathematical formulations of model I.
Objective(Obj)min∑a∑b∑tRabt⋅Yabt(1)Subject to∑bXbt=Nt,∀t∑tXbt=Capb,∀b(2)xbt≤Xbt,∀b,t(3)M⋅xbt≥Xbt,∀b,t(4)Xbt=∑aYabt,∀b,t(5)yabt≤Yabt,∀a,b,t(6)M⋅yabt≥Yabt,∀a,b,t(7)∑tYabt≤slotab,∀a,b(8)slotab−∑tYabt−≥slota+1b−∑tYa+1bt,∀a∈LPb,UPb−1,b(9)dt1⋅ya1bt1−dt2⋅ya2bt2−M⋅1−ya2bt2≤M⋅Ra1bt1,∀a1∈LPb,UPb−1,a2∈a1+1,UPb,b,t1,t2(10)GMmin≤KM−∑b∑a∑twt⋅Yabt⋅VDa+∑iPi⋅xi¯/∑twt⋅Nt+∑iPi≤GMmax(11)Tmin≤∑b∑twt⋅Xbt⋅CCGb+∑iPi⋅Zi−∑twt⋅Nt+∑iPi⋅LCB/MTC≤Tmax(12)Smin≤0.5⋅n⋅L⋅DL+∑b∑twt⋅Xbt⋅CCGb+∑iPi⋅CCGi0−C⋅L⋅∑twt⋅Nt+∑iPi≤Smax(13)The basic model is summarized as model I. Its objective function is established to minimize overstows, which is denoted by (obj).Constraint (1) ensures that all containers are loaded into the containership. Constraint (2) stipulates that the number of loaded containers does not exceed the capacity of each block. Constraints (3) and (4) illustrate the relationship between two decision variablesxbt and Xbt. Constraint (5) connects the ship tier and ship bay. Constraints (6) and (7) illustrate the relationship between two decision variables yabt and Yabt. Constraint (8) ensures that the number of loaded containers does not exceed the capacity of each ship tier. Constraint (9) avoids containers hanging on the containership space. Constraint (10) is used to mark the overstows. For an ideal situation with no overstows, the following constraint should be satisfied, that is, dt1⋅ya1bt1≤dt2⋅ya2bt2+M⋅1−ya2bt2,∀a1∈LPb,UPb−1,a2∈a1+1,UPb,b,t1,t2. If ya2bt2=1 and ya1bt1=1, then dt1≤dt2. The overstows could be avoided if the containers in the higher tier are unloaded before the containers in the lower tier. The serial number of the ship tiers is numbered by the ascending order from highest to lowest. The hard constraint strictly controls the distribution of containers with different destination ports in the vertical direction, generating optimal distribution with no overstows. To minimize the number of overstows, constraint (10) is proposed based on the aforementioned hard constraint of overstows. If dt1⋅ya1bt1−dt2⋅ya2bt2+M⋅1−ya2bt2>0, then Ra1bt1=1. Overstows are produced if the containers in the higher tier are unloaded after the containers in the lower tier; otherwise, the overstows could be avoided. Constraints (11) to (13) ensure that the GM, trim, and strength fall within a reasonable limit.


#### 3.2.2. Improved Model I

The optimal solution obtained by solving model I is unreasonable in reality. Taking a ship bay in Figure6(a) as an example, each tier of the ship bay is not fully loaded with containers, and there are only a few containers in each tier. This is not in conformity with stowage practice and safety requirements. The expectation is to achieve the container distribution in Figure 6(b). Thus, model I should be extended to improved model I, which is more practical and applicable for the industrial practices.Figure 6
Improving solutions: (a) a feasible solution; (b) an improved solution.
(a)(b)Thus, an additional stipulation is added to the rules for the stowage plan making; that is, for each storage block, the empty tier is open for storage only if the lower tiers are full of containers. Constraint (9) should be modified to the following constraint:(1)∑tYabt⋅slota+1b−∑tYa+1bt=0,∀a,b.For each storage block, when there is a container stowed in a certain tier (∑tYabt>0), all the lower tiers must be full of containers (slota+1b=∑tYa+1bt>0); when a certain tier is not full of containers (slota+1b≠∑tYa+1bt), any of higher tiers cannot be open for stowing (∑tYabt=0). Constraint (new 9) concludes the logic relationship as described above. However, it is nonlinear, thereby increasing the difficulty in solving the model by the existing solver Gurobi. Thus, the constraint should be linearized in the next step. To achieve linearization, a binary decision variable is introduced, denoted by Jab, in which Jab=1 if tier a of ship bay b is full of containers, and Jab=0, otherwise. The relationship among yabt, Jab, Ja+1b, and Yabt is expressed in constraint group (final 9). Showed by constraint (final 9a), when ∑tyabt equals 0, Jab must be equal to 0. Constraint (final 9b) describes the relationship of yabt and Ja+1b, showing that when ∑tyabt is greater than 0, Ja+1b must be equal to 1 for each block. Constraints (final 9c) and (final 9d) are the variants of an if-then structure. The first if-then structure can be expressed as if Jab=1, then slotab−∑tyabt=0. Another if-then structure can be expressed as if slotab−∑tyabt=0, then Jab=1. Constraint (final 9e) states that only if the slots in all the lower tiers are fully loaded with containers, the slots in the closest and higher tier can be open for stowing containers. Finally, the complete mathematical formulations of improved model I are shown in Table 6.Table 6
Mathematical formulations of improved model I.
Objective(Obj)……Subject to……(1)∼(8)M⋅∑tyabt≥Jab,∀a,b(Final 9a)∑tyabt≤M⋅Ja+1b,∀a,b(Final 9b)slotab−∑tYabt≤M⋅1−Jab,∀a,b(Final 9c)1−Jab≤slotab−∑tYabt,∀a,b(Final 9d)Jab≤Ja+1b,∀a,b(Final 9e)……(10)∼(13)


#### 3.2.3. Model II

Model II is listed in Table7. In this scenario, constraints (1) to (8) should also be satisfied. Because of the physical structure with hatch covers, constraint group (final 9) should be further extended, avoiding hanging in the air whether under the deck or on the deck, in which constraints (final 9b) and (final 9e) should be satisfied for each storage block separated by the hatch cover, including the block under the deck and the block on the deck. uH represents the lowest tier number on the deck.Table 7
Mathematical formulations of model II.
Objective(Obj)……Subject to……(1)∼(8)……(Final 9a)∑tyabt≤M⋅Ja+1b,∀a∈LPb,uH−1,b∈Ub(Final 9b_1)∑tyabt≤M⋅Ja+1b,∀a∈uH+1,UPb−1,b∈Lb(Final 9b_2)……(Final 9c)∼(final 9d)Jab≤Ja+1b,∀a∈LPb,uH−1,b∈Ub(Final 9e_1)Jab≤Ja+1b,∀a∈uH+1,UPb−1,b∈Lb(Final 9e_2)dt1⋅ya1bt1−dt2⋅ya2bt2−M⋅1−ya2bt2≤M⋅Ra1bt1,∀a1∈LPb,uH−1,a2∈a1+1,uH,b∈Ub,t1,t2(10a)dt1⋅ya1bt1−dt2⋅ya2bt2−M⋅1−ya2bt2≤M⋅Ra1bt1,∀a1∈uH+1,UPb−1,a2∈a1+1,UPb,b∈Lb,t1,t2(10b)dt1⋅ya1bt1−dt2⋅ya2bt2−M⋅1−ya2bt2≤M⋅Ra1bt1,∀a1∈LPb,uH,a2∈uH+1,UPb,b∈Lb,t1,t2(10c)……(11)∼(13)Table 8
Mathematical formulations of model III.
Objective(New obj)min∑a∑b∑tRabt⋅Yabt+∑a=1uH∑brb⋅NEab(1)∼(8)Subject to …………Group (final 9)……(10a)∼(10c)Dt⋅ya1bt−NDa2b≤M⋅Ra1bt,∀a1∈LPb,UPb−1,a2∈a1+1,UPb,b(10d)GMmin≤KM−∑b∑a∑twt⋅Yabt+NEab⋅VDa+∑iPi⋅Zi/∑twt⋅Nt+∑a∑bNEab+∑iPi≤GMmax(New 11)Tmin≤∑b∑twt⋅Xbt⋅HDb+∑a∑bNEab⋅HDb+∑iPi⋅xi¯−∑twt⋅Nt+∑iPi+∑a∑bNEab⋅94.42/MTC≤Tmax(New 12)Smin≤0.5⋅n⋅L⋅DL+∑b∑twt⋅Xbt⋅CCGb+∑b∑aNEab⋅CCGb+∑iPi⋅CCGi0−C⋅L⋅∑twt⋅Nt+∑iPi+∑a∑bNEab≤Smax(New 13)Yabt≤M⋅rb,∀a∈uH+1,UPb,b∈LP,t(14)Table 9
Mathematical formulations of model IV.
Objective(New obj)……(Final 1)Subject to∑bXbt=Ct⋅Nt,∀t……(2)∼(8)……(Final 9)……(10)GMmin≤KM−∑b∑a∑twt⋅Yabt+NEab⋅VDa+∑iPi⋅Zi/∑twt⋅Ct⋅Nt+∑a∑bNEab+∑iPi≤GMmax(Final 11)Tmin≤∑b∑twt⋅Xbt⋅HDb+∑a∑bNEab⋅HDb+∑iPi⋅xi¯−∑twt⋅Ct⋅Nt+∑iPi+∑a∑bNEab⋅94.42/MTC≤Tmax(Final 12)Smin≤0.5⋅n⋅L⋅DL+∑b∑twt⋅Xbt⋅CCGb+∑b∑aNEab⋅CCGb+∑iPi⋅CCGi0−C⋅L⋅∑twt⋅Ct⋅Nt+∑iPi+∑a∑bNEab≤Smax(Final 13)……(14)Fet⋅Ya2β−1t=Fet⋅Ya2βt,∀a,t,β∈1,B/2(15a)∑tTet⋅Yabt+Fet⋅Ya+1bt≤slotab,∀b,a∈LPb,uH−1(15b)∑tTet⋅Yabt+Fet⋅Ya+1bt≤slotab,∀b,a∈uH+1,UPb−1(15c)∑tRet⋅Yabt≤slotRab,∀b,a(16)The constraint about overstows should also be extended to three specific limitations, including the overstows on the deck, the overstows under the deck, and the hatch overstowage. The initially single constraint (10) is extended to constraint group (10).


#### 3.2.4. Model III

In this scenario, the containership is not empty when arriving at the current port, and containers in the containership would be shipped to different destinations. Therefore, two parametersNEab and NDab are introduced to record the weight and destination of containers in ship tier a of ship bay b, respectively. If ship tier a of ship bay b is empty, NEab is set to 0, and NDab is set to a large number M. Model III is expressed in Table 8.The weight distribution of the existing containers, which were loaded in the previous ports, should be considered to calculate the GM, trim, and strength. Thus, the constraints of GM, trim, and strength should be adjusted in this scenario, generating constraints (new 11), (new 12), and (new 13).The stacking positions of currently loaded containers are affected by the existing containers’ distribution in the containership. Constraint (10d) is added to constraint group (10), and it is used to justify whether the existing containers are blocked by the newly loaded containers.Because of the hatch cover, it is easy to guarantee containership GM, but it may cause more overstows when some containers have been stowed on the deck in the previous ports, and the space under the deck is not fully loaded with containers. If the containers to be loaded in the current port are going to be stowed under the deck, the existing containers on the deck need to be overstowed first. Thus, we add another decision variablerb to justify whether containers on the deck are overstowed (rb=1) or not (rb=0) by the current generated stowage plan. Constraint (14) is used to bind the value of rb. If some containers are stowed to the space under the deck, the existing containers on the deck must be overstowed, and they should be unloaded first.The overstows of existing containers in the containership before the loading operation are replenished to the objective function, generating the new objective (new obj).


#### 3.2.5. Model IV

Several parameters are introduced into model IV, in whichTt, Ft, and Rt are used to determine whether t-containers are 20 ft, 40 ft, or refrigerated, and they are binary parameters. Ct represents the transformation coefficient of t-containers from the quantity to the TEU capacity. When t-containers are 40 ft, the transformation coefficient is 2. Otherwise, the transformation coefficient is 1. Model IV is listed in Table 9.The previous constraints (1), (new 11), (new 12), and (new 13) are adjusted byCt, generating new constraints (final 1), (final 11), (final 12), and (final 13).Three constraints for 40 ft containers are added to the model, generating constraint group (15). Constraint (15a) represents that a 40 ft container occupies the neighboring ship stacks in the transverse direction across two 20 ft ship bays. Constraints (15b) and (15c) state that only 40 ft containers can be stowed on 20 ft containers on the deck or under the deck for safe fixation.Constraint (16) regarding refrigerated containers’ storage positions is replenished in the model.slotRab is introduced to record the number of refrigerated slots in tier a of block b.To better review the proposed four models, Table10 summarizes the newly added parameters and decision variables based on the basic model.Table 10
Additional parameters and decision variables in four models based on the basic model.
ModelsParametersDecision variablesMeaningImproved model IJab(binary)=1 if theath tier of ship bay b is full of containers, and =0, otherwiseModel IIuHThe lowest tier number on the deckModel IIINEabThe weight of containers loaded in ship tiera of ship bay bNDabThe destination of containers loaded in ship tiera of ship bay brb(binary)=1 if the containers on the deck are overstowed; =0, otherwiseModel IVTt(binary)=1 ift-containers are 20’; =0, otherwiseFt(binary)=1 ift-containers are 40’; =0, otherwiseRt(binary)=1 ift-containers are refrigerated; =0, otherwiseCtThe transformation coefficient of containers from the quantity to the TEU capacityslotRabThe number of refrigerated slots in tiera of block b


## 3.1. Problem Description

The CSP determines the specific location of each container in a designated containership to improve the containership operational efficiency and meet the seaworthy requirements under sail. The mechanical factors, the physical structure, and the stowing rules are considered as the constraints of the mathematical model. Based on the literature review of objective functions in the models, this study chooses the number of overstows that is always easy to be quantified to measure the containership operational efficiency.For the establishment of mathematical models, a containership with a particular structure is separated by the ship bays, and the ship bays are made of ship tiers, as illustrated in Figure1. Ship bays marked by even numbers can hold 40 ft containers, but ship bays marked by odd numbers can only hold 20 ft containers. Refrigerated containers must be stowed in the refrigerated slots. It is important to distribute the weights in ship bays of horizontal length and in ship tiers of vertical height. The weight distribution should satisfy the GM, trim, and strength requirements [18], which are summarized as the stability constraints in this study. The GM is measured by the weight distribution in the longitudinal direction, while the trim and strength are both measured by the weight distribution in the vertical direction. The estimation of the GM, trim, and strength is based on the container distribution in each block and each tier. A block is defined as a separate storage unit not interrupted by other blocks. A block in this study refers to a 20 ft ship bay or the space on/under the deck of a 20 ft ship bay, depending on whether hatch covers are considered. The block can be defined according to different containership types: (1) for an ocean-going containership, there exist hatch covers for ship bays. Thus, the spaces on/below the deck of ship bay 01 and ship bay 03 can be regarded as four blocks. (2) For an inland containership, there is no hatch cover. Thus, ship bay 01 and ship bay 03 can be regarded as two blocks.Figure 1
Illustration of an ocean-going containership structure: (a) the front view of a containership; (b) the top view of a containership.
(a)(b)The containers to be loaded into the containership differ in terms of size, type, weight, and destination port. Besides, containers with the same attributes are classified into the same group. This study considers two sizes of containers, including 20 ft and 40 ft containers, and two types of containers, including general and refrigerated containers. The weight of containers to be loaded into the containership is uncertain because of logistics limitations, which are usually classified [31]. Contrary to Li et al. [31], we believe that the container weight is known in advance because precise weighing techniques have emerged and been used in multiple western ports [33]. And the number of container destination ports corresponds to the number of ports in the fixed voyage. The CSP focuses on how to allocate each group of containers to the ship tiers of the ship bays, which can be achieved by solving mathematical models.


## 3.2. Integer Programming (IP) Model Establishment

IP models are proposed for the CSP. The modeling process is gradually presented in four scenarios. The identifications of scenarios depend on different containership information and container attributes, as listed in Table2. Containership information involves the containership loading information and structure information. In summary, the richer the container types, the more complicated the stowing rules to consider. Whether the ship-bay configuration is rectangular or not mentioned in the model is worthy of universalization in this study. Besides, we select whether the containership is initially empty before the loading operations as the containership loading information and select whether the containership has hatch covers as the containership structure information.Table 2
Scenarios’ introduction of the four models.
Given informationParametersModel I (scenario I)Improved model I (scenario I)Model II (scenario II)Model III (scenario III)Model IV (scenario IV)Containership informationEmpty containership initiallyYYYNNHatch coversNNYYYContainer sizes20 ft containerYYYYY40 ft containerNNNNYContainer typesGeneral containerYYYYYRefrigerated containerNNNNYFigure 2
A feasible stowage plan for a ship bay structured with the hatch cover.Figure 3
Two kinds of status information of a ship bay before the loading process.
(a)(b)Figure 4
A feasible stowage plan of a 40 ft ship bay: (a) bay 01; (b) bay 03.
(a)(b)Figure 5
A feasible stowage plan of a 40 ft ship bay on the deck involving 20 ft and 40 ft containers: (a) bay 01; (b) bay 03.
(a)(b)The definition of scenarios is described as follows:(1)
Scenario I analysis:The containership is empty initially, and the containership in model I has no hatch cover in the hull structure. The containers to be loaded into the containership are all 20 ft general containers. To simplify the CSP, there are no 40 ft container and refrigerated container to be loaded into the containership.(2)
Scenario II analysis:From the view of the physical structure, each ship bay is divided into two subsections by a hatch cover, and each subsection can be regarded as a single unit for storage. The space on the deck can be open for stowing containers even if the space under the deck is not completely used, which is a special case and breaks the rule stipulated in the basic model. The containers on the deck are not suspended because they are supported by the hatch cover.A container is overstowed if it is discharged later than a container stowed below it, either in the same stack or under the hatch cover, which is defined as hatch overstowage, causing extra crane moves [9]. In Figure 2, containers destined for port 4 and port 3 are loaded under the deck, and containers destined for port 2 are loaded on the deck. Overstows are avoided in this instance by stowing containers with the descending order of destination ports.When the containers on the deck have a further destination compared to the containers under the deck, the containers on the deck must be overstowed when unloading the containers under the deck. Taking the ship bay in Figure2 as an example, if containers destined for port 2 are loaded under the deck and containers destined for port 3 are loaded on the deck, then at port 2, the operations should be unloading the containers on the deck first, unloading the containers destined for port 2, and finally reloading the containers where they are initially on the deck.(3)
Scenario III analysis:Model II is established in an ideal scenario, assuming the containership is empty initially before the loading process. Without the effect of initially loaded containers in the containership, it is easy to obtain a stowage plan to avoid overstows when unloading containers from the containership at subsequent ports, but when the containership has been loaded with containers before the loading process in the current port, the overstows cannot be completely avoided. If there are enough empty slots in the containership for stowing containers with a far destination, it is possible to avoid overstows. Whether the overstows can be avoided is based on the quantitative relation of containers loaded in each previous port, containers to be loaded in the current port, and the left slots of each kind of block for stowing containers. The blocks are characterized by the nearest destination of containers in each block.If there are containers that have a near destination occupying the lower space of all ship bays, overstows cannot be avoided. In this kind of extreme scenario, it is vital to find the optimal solution in minimizing overstows. In Figure3(a), the block on the deck is empty, denoted by M-block, in which M is a large number, but the block under the deck is loaded with containers destined for port 2, denoted by 2-block. If the containers with a near destination are loaded into the two blocks whether on the deck or under the deck, the overstows can be avoided. In Figure 3(b), if the containers to be loaded in the current port are to be shipped to port 4, overstows cannot be avoided. If there are 4 containers destined for port 4 to be loaded, they should be put on the containers destined for port 2 on the deck, minimizing overstows. If they are loaded under the deck, all the containers on the deck should first be overstowed, producing 12 overstows.(4)
Scenario IV analysis:The containership is initially not empty before the loading operations, and it has hatch covers in the hull structure. The containers to be loaded into the containership involve 20 ft general containers, 20 ft refrigerated containers, 40 ft general containers, and 40 ft refrigerated containers.A 40 ft container occupies two 20 ft slots in the containership. In this study, there is no definition of 40 ft slots and 40 ft ship bays. Two neighboring 20 ft slots with the same ship tier in the adjacent 20 ft ship bays are occupied simultaneously when a 40 ft container is loaded into the containership. The 20 ft ship bays are numbered by continuous integers, 1, 2, 3, …, etc. In this model, a 40 ft container may occupy two 20 ft slots of the first and second ship bays, or third and fourth ship bays, but it is impossible for a 40 ft container to occupy two 20 ft slots of the second and third ship bays or fourth and fifth ship bays limited by the containership structure.In Figure4, bay 01 and bay 03 correspond to the first and second 20 ft ship bays in the model. The containers on the deck are all 40 ft containers, that is, the slots in the first two tiers are occupied by these 40 ft containers, but the containers in bay 01 under the deck are 20 ft containers, and the corresponding slots in bay 03 are empty. If all containers are assigned on the deck, the stowage plan should comply with the stowing rule that 20 ft containers cannot be stowed on 40 ft containers. A feasible stowage plan is illustrated in Figure 5. 20 ft containers must be stowed below 40 ft containers, and it is better for two 20 ft containers occupying the slots in the same stack and tier of bay 01 and bay 03, which is helpful for 40 ft containers stowing on them.Besides, refrigerated containers must be stowed in the refrigerated slots with power plugs, which depends on the containership structure.


### 3.2.1. Model I

IP of the CSP is presented in Tables3–5: Table 3 lists the parameters, Table 4 lists the decision variables, and Table 5 shows the objective function and constraints of model I.Table 3
Parameters in model I.
ParametersMeaningNtThe number oft-containers. t-containers refer to the containers in group t, which have fixed size, type, weight, and destination portCapbThe number of empty slots in blockbwtThe weight oft-containersPiThe weight of the containership’s constant, including the weight of the crew and supplies, spare parts, oil, and waterZiHeight between the center of gravity of loadPi and the baselineVDaThe vertical distance between ship tiera and the hull bottomxi¯The vertical distance between the center of gravity of loadPi and the baselineKMThe vertical distance between the transverse metacentric and the baselineslotabThe number of empty slots in tiera of block bdtThe destination port oft-containerMTCCentimeter-trim momentLCBThe horizontal distance between the buoyancy and the stern frame of the containershipCCGbThe horizontal distance between the center of gravity of blockb and the midshipCCGi0The horizontal distance between the center of gravity of loadPi and the midshipMA large positive numberGMmaxThe upper bound of the containership GMGMminThe lower bound of the containership GMTmaxThe upper bound of the containership trimTminThe lower bound of the containership trimUPbThe upper bound of the ship tier in blockbLPbThe lower bound of the ship tier in blockbCThe coefficient of the hull buoyancy levernThe total moment of the weight in the first half hull and that in the second half hullDLThe displacement of the unloaded containershipLThe length of the containershipTable 4
Decision variables in model I.
Decision variablesMeaningxbt= 1 ift-container is allocated to block b; = 0, otherwiseXbtThe number oft-containers allocated to block byabt= 1 ift-container is allocated to tier a of block b; = 0, otherwiseYabtThe number oft-containers allocated to tier a of block bRabt= 1 ift-containers allocated to tier a of block b are overstowed; = 0, otherwiseTable 5
Mathematical formulations of model I.
Objective(Obj)min∑a∑b∑tRabt⋅Yabt(1)Subject to∑bXbt=Nt,∀t∑tXbt=Capb,∀b(2)xbt≤Xbt,∀b,t(3)M⋅xbt≥Xbt,∀b,t(4)Xbt=∑aYabt,∀b,t(5)yabt≤Yabt,∀a,b,t(6)M⋅yabt≥Yabt,∀a,b,t(7)∑tYabt≤slotab,∀a,b(8)slotab−∑tYabt−≥slota+1b−∑tYa+1bt,∀a∈LPb,UPb−1,b(9)dt1⋅ya1bt1−dt2⋅ya2bt2−M⋅1−ya2bt2≤M⋅Ra1bt1,∀a1∈LPb,UPb−1,a2∈a1+1,UPb,b,t1,t2(10)GMmin≤KM−∑b∑a∑twt⋅Yabt⋅VDa+∑iPi⋅xi¯/∑twt⋅Nt+∑iPi≤GMmax(11)Tmin≤∑b∑twt⋅Xbt⋅CCGb+∑iPi⋅Zi−∑twt⋅Nt+∑iPi⋅LCB/MTC≤Tmax(12)Smin≤0.5⋅n⋅L⋅DL+∑b∑twt⋅Xbt⋅CCGb+∑iPi⋅CCGi0−C⋅L⋅∑twt⋅Nt+∑iPi≤Smax(13)The basic model is summarized as model I. Its objective function is established to minimize overstows, which is denoted by (obj).Constraint (1) ensures that all containers are loaded into the containership. Constraint (2) stipulates that the number of loaded containers does not exceed the capacity of each block. Constraints (3) and (4) illustrate the relationship between two decision variablesxbt and Xbt. Constraint (5) connects the ship tier and ship bay. Constraints (6) and (7) illustrate the relationship between two decision variables yabt and Yabt. Constraint (8) ensures that the number of loaded containers does not exceed the capacity of each ship tier. Constraint (9) avoids containers hanging on the containership space. Constraint (10) is used to mark the overstows. For an ideal situation with no overstows, the following constraint should be satisfied, that is, dt1⋅ya1bt1≤dt2⋅ya2bt2+M⋅1−ya2bt2,∀a1∈LPb,UPb−1,a2∈a1+1,UPb,b,t1,t2. If ya2bt2=1 and ya1bt1=1, then dt1≤dt2. The overstows could be avoided if the containers in the higher tier are unloaded before the containers in the lower tier. The serial number of the ship tiers is numbered by the ascending order from highest to lowest. The hard constraint strictly controls the distribution of containers with different destination ports in the vertical direction, generating optimal distribution with no overstows. To minimize the number of overstows, constraint (10) is proposed based on the aforementioned hard constraint of overstows. If dt1⋅ya1bt1−dt2⋅ya2bt2+M⋅1−ya2bt2>0, then Ra1bt1=1. Overstows are produced if the containers in the higher tier are unloaded after the containers in the lower tier; otherwise, the overstows could be avoided. Constraints (11) to (13) ensure that the GM, trim, and strength fall within a reasonable limit.


### 3.2.2. Improved Model I

The optimal solution obtained by solving model I is unreasonable in reality. Taking a ship bay in Figure6(a) as an example, each tier of the ship bay is not fully loaded with containers, and there are only a few containers in each tier. This is not in conformity with stowage practice and safety requirements. The expectation is to achieve the container distribution in Figure 6(b). Thus, model I should be extended to improved model I, which is more practical and applicable for the industrial practices.Figure 6
Improving solutions: (a) a feasible solution; (b) an improved solution.
(a)(b)Thus, an additional stipulation is added to the rules for the stowage plan making; that is, for each storage block, the empty tier is open for storage only if the lower tiers are full of containers. Constraint (9) should be modified to the following constraint:(1)∑tYabt⋅slota+1b−∑tYa+1bt=0,∀a,b.For each storage block, when there is a container stowed in a certain tier (∑tYabt>0), all the lower tiers must be full of containers (slota+1b=∑tYa+1bt>0); when a certain tier is not full of containers (slota+1b≠∑tYa+1bt), any of higher tiers cannot be open for stowing (∑tYabt=0). Constraint (new 9) concludes the logic relationship as described above. However, it is nonlinear, thereby increasing the difficulty in solving the model by the existing solver Gurobi. Thus, the constraint should be linearized in the next step. To achieve linearization, a binary decision variable is introduced, denoted by Jab, in which Jab=1 if tier a of ship bay b is full of containers, and Jab=0, otherwise. The relationship among yabt, Jab, Ja+1b, and Yabt is expressed in constraint group (final 9). Showed by constraint (final 9a), when ∑tyabt equals 0, Jab must be equal to 0. Constraint (final 9b) describes the relationship of yabt and Ja+1b, showing that when ∑tyabt is greater than 0, Ja+1b must be equal to 1 for each block. Constraints (final 9c) and (final 9d) are the variants of an if-then structure. The first if-then structure can be expressed as if Jab=1, then slotab−∑tyabt=0. Another if-then structure can be expressed as if slotab−∑tyabt=0, then Jab=1. Constraint (final 9e) states that only if the slots in all the lower tiers are fully loaded with containers, the slots in the closest and higher tier can be open for stowing containers. Finally, the complete mathematical formulations of improved model I are shown in Table 6.Table 6
Mathematical formulations of improved model I.
Objective(Obj)……Subject to……(1)∼(8)M⋅∑tyabt≥Jab,∀a,b(Final 9a)∑tyabt≤M⋅Ja+1b,∀a,b(Final 9b)slotab−∑tYabt≤M⋅1−Jab,∀a,b(Final 9c)1−Jab≤slotab−∑tYabt,∀a,b(Final 9d)Jab≤Ja+1b,∀a,b(Final 9e)……(10)∼(13)


### 3.2.3. Model II

Model II is listed in Table7. In this scenario, constraints (1) to (8) should also be satisfied. Because of the physical structure with hatch covers, constraint group (final 9) should be further extended, avoiding hanging in the air whether under the deck or on the deck, in which constraints (final 9b) and (final 9e) should be satisfied for each storage block separated by the hatch cover, including the block under the deck and the block on the deck. uH represents the lowest tier number on the deck.Table 7
Mathematical formulations of model II.
Objective(Obj)……Subject to……(1)∼(8)……(Final 9a)∑tyabt≤M⋅Ja+1b,∀a∈LPb,uH−1,b∈Ub(Final 9b_1)∑tyabt≤M⋅Ja+1b,∀a∈uH+1,UPb−1,b∈Lb(Final 9b_2)……(Final 9c)∼(final 9d)Jab≤Ja+1b,∀a∈LPb,uH−1,b∈Ub(Final 9e_1)Jab≤Ja+1b,∀a∈uH+1,UPb−1,b∈Lb(Final 9e_2)dt1⋅ya1bt1−dt2⋅ya2bt2−M⋅1−ya2bt2≤M⋅Ra1bt1,∀a1∈LPb,uH−1,a2∈a1+1,uH,b∈Ub,t1,t2(10a)dt1⋅ya1bt1−dt2⋅ya2bt2−M⋅1−ya2bt2≤M⋅Ra1bt1,∀a1∈uH+1,UPb−1,a2∈a1+1,UPb,b∈Lb,t1,t2(10b)dt1⋅ya1bt1−dt2⋅ya2bt2−M⋅1−ya2bt2≤M⋅Ra1bt1,∀a1∈LPb,uH,a2∈uH+1,UPb,b∈Lb,t1,t2(10c)……(11)∼(13)Table 8
Mathematical formulations of model III.
Objective(New obj)min∑a∑b∑tRabt⋅Yabt+∑a=1uH∑brb⋅NEab(1)∼(8)Subject to …………Group (final 9)……(10a)∼(10c)Dt⋅ya1bt−NDa2b≤M⋅Ra1bt,∀a1∈LPb,UPb−1,a2∈a1+1,UPb,b(10d)GMmin≤KM−∑b∑a∑twt⋅Yabt+NEab⋅VDa+∑iPi⋅Zi/∑twt⋅Nt+∑a∑bNEab+∑iPi≤GMmax(New 11)Tmin≤∑b∑twt⋅Xbt⋅HDb+∑a∑bNEab⋅HDb+∑iPi⋅xi¯−∑twt⋅Nt+∑iPi+∑a∑bNEab⋅94.42/MTC≤Tmax(New 12)Smin≤0.5⋅n⋅L⋅DL+∑b∑twt⋅Xbt⋅CCGb+∑b∑aNEab⋅CCGb+∑iPi⋅CCGi0−C⋅L⋅∑twt⋅Nt+∑iPi+∑a∑bNEab≤Smax(New 13)Yabt≤M⋅rb,∀a∈uH+1,UPb,b∈LP,t(14)Table 9
Mathematical formulations of model IV.
Objective(New obj)……(Final 1)Subject to∑bXbt=Ct⋅Nt,∀t……(2)∼(8)……(Final 9)……(10)GMmin≤KM−∑b∑a∑twt⋅Yabt+NEab⋅VDa+∑iPi⋅Zi/∑twt⋅Ct⋅Nt+∑a∑bNEab+∑iPi≤GMmax(Final 11)Tmin≤∑b∑twt⋅Xbt⋅HDb+∑a∑bNEab⋅HDb+∑iPi⋅xi¯−∑twt⋅Ct⋅Nt+∑iPi+∑a∑bNEab⋅94.42/MTC≤Tmax(Final 12)Smin≤0.5⋅n⋅L⋅DL+∑b∑twt⋅Xbt⋅CCGb+∑b∑aNEab⋅CCGb+∑iPi⋅CCGi0−C⋅L⋅∑twt⋅Ct⋅Nt+∑iPi+∑a∑bNEab≤Smax(Final 13)……(14)Fet⋅Ya2β−1t=Fet⋅Ya2βt,∀a,t,β∈1,B/2(15a)∑tTet⋅Yabt+Fet⋅Ya+1bt≤slotab,∀b,a∈LPb,uH−1(15b)∑tTet⋅Yabt+Fet⋅Ya+1bt≤slotab,∀b,a∈uH+1,UPb−1(15c)∑tRet⋅Yabt≤slotRab,∀b,a(16)The constraint about overstows should also be extended to three specific limitations, including the overstows on the deck, the overstows under the deck, and the hatch overstowage. The initially single constraint (10) is extended to constraint group (10).


### 3.2.4. Model III

In this scenario, the containership is not empty when arriving at the current port, and containers in the containership would be shipped to different destinations. Therefore, two parametersNEab and NDab are introduced to record the weight and destination of containers in ship tier a of ship bay b, respectively. If ship tier a of ship bay b is empty, NEab is set to 0, and NDab is set to a large number M. Model III is expressed in Table 8.The weight distribution of the existing containers, which were loaded in the previous ports, should be considered to calculate the GM, trim, and strength. Thus, the constraints of GM, trim, and strength should be adjusted in this scenario, generating constraints (new 11), (new 12), and (new 13).The stacking positions of currently loaded containers are affected by the existing containers’ distribution in the containership. Constraint (10d) is added to constraint group (10), and it is used to justify whether the existing containers are blocked by the newly loaded containers.Because of the hatch cover, it is easy to guarantee containership GM, but it may cause more overstows when some containers have been stowed on the deck in the previous ports, and the space under the deck is not fully loaded with containers. If the containers to be loaded in the current port are going to be stowed under the deck, the existing containers on the deck need to be overstowed first. Thus, we add another decision variablerb to justify whether containers on the deck are overstowed (rb=1) or not (rb=0) by the current generated stowage plan. Constraint (14) is used to bind the value of rb. If some containers are stowed to the space under the deck, the existing containers on the deck must be overstowed, and they should be unloaded first.The overstows of existing containers in the containership before the loading operation are replenished to the objective function, generating the new objective (new obj).


### 3.2.5. Model IV

Several parameters are introduced into model IV, in whichTt, Ft, and Rt are used to determine whether t-containers are 20 ft, 40 ft, or refrigerated, and they are binary parameters. Ct represents the transformation coefficient of t-containers from the quantity to the TEU capacity. When t-containers are 40 ft, the transformation coefficient is 2. Otherwise, the transformation coefficient is 1. Model IV is listed in Table 9.The previous constraints (1), (new 11), (new 12), and (new 13) are adjusted byCt, generating new constraints (final 1), (final 11), (final 12), and (final 13).Three constraints for 40 ft containers are added to the model, generating constraint group (15). Constraint (15a) represents that a 40 ft container occupies the neighboring ship stacks in the transverse direction across two 20 ft ship bays. Constraints (15b) and (15c) state that only 40 ft containers can be stowed on 20 ft containers on the deck or under the deck for safe fixation.Constraint (16) regarding refrigerated containers’ storage positions is replenished in the model.slotRab is introduced to record the number of refrigerated slots in tier a of block b.To better review the proposed four models, Table10 summarizes the newly added parameters and decision variables based on the basic model.Table 10
Additional parameters and decision variables in four models based on the basic model.
ModelsParametersDecision variablesMeaningImproved model IJab(binary)=1 if theath tier of ship bay b is full of containers, and =0, otherwiseModel IIuHThe lowest tier number on the deckModel IIINEabThe weight of containers loaded in ship tiera of ship bay bNDabThe destination of containers loaded in ship tiera of ship bay brb(binary)=1 if the containers on the deck are overstowed; =0, otherwiseModel IVTt(binary)=1 ift-containers are 20’; =0, otherwiseFt(binary)=1 ift-containers are 40’; =0, otherwiseRt(binary)=1 ift-containers are refrigerated; =0, otherwiseCtThe transformation coefficient of containers from the quantity to the TEU capacityslotRabThe number of refrigerated slots in tiera of block b


## 3.2.1. Model I

IP of the CSP is presented in Tables3–5: Table 3 lists the parameters, Table 4 lists the decision variables, and Table 5 shows the objective function and constraints of model I.Table 3
Parameters in model I.
ParametersMeaningNtThe number oft-containers. t-containers refer to the containers in group t, which have fixed size, type, weight, and destination portCapbThe number of empty slots in blockbwtThe weight oft-containersPiThe weight of the containership’s constant, including the weight of the crew and supplies, spare parts, oil, and waterZiHeight between the center of gravity of loadPi and the baselineVDaThe vertical distance between ship tiera and the hull bottomxi¯The vertical distance between the center of gravity of loadPi and the baselineKMThe vertical distance between the transverse metacentric and the baselineslotabThe number of empty slots in tiera of block bdtThe destination port oft-containerMTCCentimeter-trim momentLCBThe horizontal distance between the buoyancy and the stern frame of the containershipCCGbThe horizontal distance between the center of gravity of blockb and the midshipCCGi0The horizontal distance between the center of gravity of loadPi and the midshipMA large positive numberGMmaxThe upper bound of the containership GMGMminThe lower bound of the containership GMTmaxThe upper bound of the containership trimTminThe lower bound of the containership trimUPbThe upper bound of the ship tier in blockbLPbThe lower bound of the ship tier in blockbCThe coefficient of the hull buoyancy levernThe total moment of the weight in the first half hull and that in the second half hullDLThe displacement of the unloaded containershipLThe length of the containershipTable 4
Decision variables in model I.
Decision variablesMeaningxbt= 1 ift-container is allocated to block b; = 0, otherwiseXbtThe number oft-containers allocated to block byabt= 1 ift-container is allocated to tier a of block b; = 0, otherwiseYabtThe number oft-containers allocated to tier a of block bRabt= 1 ift-containers allocated to tier a of block b are overstowed; = 0, otherwiseTable 5
Mathematical formulations of model I.
Objective(Obj)min∑a∑b∑tRabt⋅Yabt(1)Subject to∑bXbt=Nt,∀t∑tXbt=Capb,∀b(2)xbt≤Xbt,∀b,t(3)M⋅xbt≥Xbt,∀b,t(4)Xbt=∑aYabt,∀b,t(5)yabt≤Yabt,∀a,b,t(6)M⋅yabt≥Yabt,∀a,b,t(7)∑tYabt≤slotab,∀a,b(8)slotab−∑tYabt−≥slota+1b−∑tYa+1bt,∀a∈LPb,UPb−1,b(9)dt1⋅ya1bt1−dt2⋅ya2bt2−M⋅1−ya2bt2≤M⋅Ra1bt1,∀a1∈LPb,UPb−1,a2∈a1+1,UPb,b,t1,t2(10)GMmin≤KM−∑b∑a∑twt⋅Yabt⋅VDa+∑iPi⋅xi¯/∑twt⋅Nt+∑iPi≤GMmax(11)Tmin≤∑b∑twt⋅Xbt⋅CCGb+∑iPi⋅Zi−∑twt⋅Nt+∑iPi⋅LCB/MTC≤Tmax(12)Smin≤0.5⋅n⋅L⋅DL+∑b∑twt⋅Xbt⋅CCGb+∑iPi⋅CCGi0−C⋅L⋅∑twt⋅Nt+∑iPi≤Smax(13)The basic model is summarized as model I. Its objective function is established to minimize overstows, which is denoted by (obj).Constraint (1) ensures that all containers are loaded into the containership. Constraint (2) stipulates that the number of loaded containers does not exceed the capacity of each block. Constraints (3) and (4) illustrate the relationship between two decision variablesxbt and Xbt. Constraint (5) connects the ship tier and ship bay. Constraints (6) and (7) illustrate the relationship between two decision variables yabt and Yabt. Constraint (8) ensures that the number of loaded containers does not exceed the capacity of each ship tier. Constraint (9) avoids containers hanging on the containership space. Constraint (10) is used to mark the overstows. For an ideal situation with no overstows, the following constraint should be satisfied, that is, dt1⋅ya1bt1≤dt2⋅ya2bt2+M⋅1−ya2bt2,∀a1∈LPb,UPb−1,a2∈a1+1,UPb,b,t1,t2. If ya2bt2=1 and ya1bt1=1, then dt1≤dt2. The overstows could be avoided if the containers in the higher tier are unloaded before the containers in the lower tier. The serial number of the ship tiers is numbered by the ascending order from highest to lowest. The hard constraint strictly controls the distribution of containers with different destination ports in the vertical direction, generating optimal distribution with no overstows. To minimize the number of overstows, constraint (10) is proposed based on the aforementioned hard constraint of overstows. If dt1⋅ya1bt1−dt2⋅ya2bt2+M⋅1−ya2bt2>0, then Ra1bt1=1. Overstows are produced if the containers in the higher tier are unloaded after the containers in the lower tier; otherwise, the overstows could be avoided. Constraints (11) to (13) ensure that the GM, trim, and strength fall within a reasonable limit.


## 3.2.2. Improved Model I

The optimal solution obtained by solving model I is unreasonable in reality. Taking a ship bay in Figure6(a) as an example, each tier of the ship bay is not fully loaded with containers, and there are only a few containers in each tier. This is not in conformity with stowage practice and safety requirements. The expectation is to achieve the container distribution in Figure 6(b). Thus, model I should be extended to improved model I, which is more practical and applicable for the industrial practices.Figure 6
Improving solutions: (a) a feasible solution; (b) an improved solution.
(a)(b)Thus, an additional stipulation is added to the rules for the stowage plan making; that is, for each storage block, the empty tier is open for storage only if the lower tiers are full of containers. Constraint (9) should be modified to the following constraint:(1)∑tYabt⋅slota+1b−∑tYa+1bt=0,∀a,b.For each storage block, when there is a container stowed in a certain tier (∑tYabt>0), all the lower tiers must be full of containers (slota+1b=∑tYa+1bt>0); when a certain tier is not full of containers (slota+1b≠∑tYa+1bt), any of higher tiers cannot be open for stowing (∑tYabt=0). Constraint (new 9) concludes the logic relationship as described above. However, it is nonlinear, thereby increasing the difficulty in solving the model by the existing solver Gurobi. Thus, the constraint should be linearized in the next step. To achieve linearization, a binary decision variable is introduced, denoted by Jab, in which Jab=1 if tier a of ship bay b is full of containers, and Jab=0, otherwise. The relationship among yabt, Jab, Ja+1b, and Yabt is expressed in constraint group (final 9). Showed by constraint (final 9a), when ∑tyabt equals 0, Jab must be equal to 0. Constraint (final 9b) describes the relationship of yabt and Ja+1b, showing that when ∑tyabt is greater than 0, Ja+1b must be equal to 1 for each block. Constraints (final 9c) and (final 9d) are the variants of an if-then structure. The first if-then structure can be expressed as if Jab=1, then slotab−∑tyabt=0. Another if-then structure can be expressed as if slotab−∑tyabt=0, then Jab=1. Constraint (final 9e) states that only if the slots in all the lower tiers are fully loaded with containers, the slots in the closest and higher tier can be open for stowing containers. Finally, the complete mathematical formulations of improved model I are shown in Table 6.Table 6
Mathematical formulations of improved model I.
Objective(Obj)……Subject to……(1)∼(8)M⋅∑tyabt≥Jab,∀a,b(Final 9a)∑tyabt≤M⋅Ja+1b,∀a,b(Final 9b)slotab−∑tYabt≤M⋅1−Jab,∀a,b(Final 9c)1−Jab≤slotab−∑tYabt,∀a,b(Final 9d)Jab≤Ja+1b,∀a,b(Final 9e)……(10)∼(13)


## 3.2.3. Model II

Model II is listed in Table7. In this scenario, constraints (1) to (8) should also be satisfied. Because of the physical structure with hatch covers, constraint group (final 9) should be further extended, avoiding hanging in the air whether under the deck or on the deck, in which constraints (final 9b) and (final 9e) should be satisfied for each storage block separated by the hatch cover, including the block under the deck and the block on the deck. uH represents the lowest tier number on the deck.Table 7
Mathematical formulations of model II.
Objective(Obj)……Subject to……(1)∼(8)……(Final 9a)∑tyabt≤M⋅Ja+1b,∀a∈LPb,uH−1,b∈Ub(Final 9b_1)∑tyabt≤M⋅Ja+1b,∀a∈uH+1,UPb−1,b∈Lb(Final 9b_2)……(Final 9c)∼(final 9d)Jab≤Ja+1b,∀a∈LPb,uH−1,b∈Ub(Final 9e_1)Jab≤Ja+1b,∀a∈uH+1,UPb−1,b∈Lb(Final 9e_2)dt1⋅ya1bt1−dt2⋅ya2bt2−M⋅1−ya2bt2≤M⋅Ra1bt1,∀a1∈LPb,uH−1,a2∈a1+1,uH,b∈Ub,t1,t2(10a)dt1⋅ya1bt1−dt2⋅ya2bt2−M⋅1−ya2bt2≤M⋅Ra1bt1,∀a1∈uH+1,UPb−1,a2∈a1+1,UPb,b∈Lb,t1,t2(10b)dt1⋅ya1bt1−dt2⋅ya2bt2−M⋅1−ya2bt2≤M⋅Ra1bt1,∀a1∈LPb,uH,a2∈uH+1,UPb,b∈Lb,t1,t2(10c)……(11)∼(13)Table 8
Mathematical formulations of model III.
Objective(New obj)min∑a∑b∑tRabt⋅Yabt+∑a=1uH∑brb⋅NEab(1)∼(8)Subject to …………Group (final 9)……(10a)∼(10c)Dt⋅ya1bt−NDa2b≤M⋅Ra1bt,∀a1∈LPb,UPb−1,a2∈a1+1,UPb,b(10d)GMmin≤KM−∑b∑a∑twt⋅Yabt+NEab⋅VDa+∑iPi⋅Zi/∑twt⋅Nt+∑a∑bNEab+∑iPi≤GMmax(New 11)Tmin≤∑b∑twt⋅Xbt⋅HDb+∑a∑bNEab⋅HDb+∑iPi⋅xi¯−∑twt⋅Nt+∑iPi+∑a∑bNEab⋅94.42/MTC≤Tmax(New 12)Smin≤0.5⋅n⋅L⋅DL+∑b∑twt⋅Xbt⋅CCGb+∑b∑aNEab⋅CCGb+∑iPi⋅CCGi0−C⋅L⋅∑twt⋅Nt+∑iPi+∑a∑bNEab≤Smax(New 13)Yabt≤M⋅rb,∀a∈uH+1,UPb,b∈LP,t(14)Table 9
Mathematical formulations of model IV.
Objective(New obj)……(Final 1)Subject to∑bXbt=Ct⋅Nt,∀t……(2)∼(8)……(Final 9)……(10)GMmin≤KM−∑b∑a∑twt⋅Yabt+NEab⋅VDa+∑iPi⋅Zi/∑twt⋅Ct⋅Nt+∑a∑bNEab+∑iPi≤GMmax(Final 11)Tmin≤∑b∑twt⋅Xbt⋅HDb+∑a∑bNEab⋅HDb+∑iPi⋅xi¯−∑twt⋅Ct⋅Nt+∑iPi+∑a∑bNEab⋅94.42/MTC≤Tmax(Final 12)Smin≤0.5⋅n⋅L⋅DL+∑b∑twt⋅Xbt⋅CCGb+∑b∑aNEab⋅CCGb+∑iPi⋅CCGi0−C⋅L⋅∑twt⋅Ct⋅Nt+∑iPi+∑a∑bNEab≤Smax(Final 13)……(14)Fet⋅Ya2β−1t=Fet⋅Ya2βt,∀a,t,β∈1,B/2(15a)∑tTet⋅Yabt+Fet⋅Ya+1bt≤slotab,∀b,a∈LPb,uH−1(15b)∑tTet⋅Yabt+Fet⋅Ya+1bt≤slotab,∀b,a∈uH+1,UPb−1(15c)∑tRet⋅Yabt≤slotRab,∀b,a(16)The constraint about overstows should also be extended to three specific limitations, including the overstows on the deck, the overstows under the deck, and the hatch overstowage. The initially single constraint (10) is extended to constraint group (10).


## 3.2.4. Model III

In this scenario, the containership is not empty when arriving at the current port, and containers in the containership would be shipped to different destinations. Therefore, two parametersNEab and NDab are introduced to record the weight and destination of containers in ship tier a of ship bay b, respectively. If ship tier a of ship bay b is empty, NEab is set to 0, and NDab is set to a large number M. Model III is expressed in Table 8.The weight distribution of the existing containers, which were loaded in the previous ports, should be considered to calculate the GM, trim, and strength. Thus, the constraints of GM, trim, and strength should be adjusted in this scenario, generating constraints (new 11), (new 12), and (new 13).The stacking positions of currently loaded containers are affected by the existing containers’ distribution in the containership. Constraint (10d) is added to constraint group (10), and it is used to justify whether the existing containers are blocked by the newly loaded containers.Because of the hatch cover, it is easy to guarantee containership GM, but it may cause more overstows when some containers have been stowed on the deck in the previous ports, and the space under the deck is not fully loaded with containers. If the containers to be loaded in the current port are going to be stowed under the deck, the existing containers on the deck need to be overstowed first. Thus, we add another decision variablerb to justify whether containers on the deck are overstowed (rb=1) or not (rb=0) by the current generated stowage plan. Constraint (14) is used to bind the value of rb. If some containers are stowed to the space under the deck, the existing containers on the deck must be overstowed, and they should be unloaded first.The overstows of existing containers in the containership before the loading operation are replenished to the objective function, generating the new objective (new obj).


## 3.2.5. Model IV

Several parameters are introduced into model IV, in whichTt, Ft, and Rt are used to determine whether t-containers are 20 ft, 40 ft, or refrigerated, and they are binary parameters. Ct represents the transformation coefficient of t-containers from the quantity to the TEU capacity. When t-containers are 40 ft, the transformation coefficient is 2. Otherwise, the transformation coefficient is 1. Model IV is listed in Table 9.The previous constraints (1), (new 11), (new 12), and (new 13) are adjusted byCt, generating new constraints (final 1), (final 11), (final 12), and (final 13).Three constraints for 40 ft containers are added to the model, generating constraint group (15). Constraint (15a) represents that a 40 ft container occupies the neighboring ship stacks in the transverse direction across two 20 ft ship bays. Constraints (15b) and (15c) state that only 40 ft containers can be stowed on 20 ft containers on the deck or under the deck for safe fixation.Constraint (16) regarding refrigerated containers’ storage positions is replenished in the model.slotRab is introduced to record the number of refrigerated slots in tier a of block b.To better review the proposed four models, Table10 summarizes the newly added parameters and decision variables based on the basic model.Table 10
Additional parameters and decision variables in four models based on the basic model.
ModelsParametersDecision variablesMeaningImproved model IJab(binary)=1 if theath tier of ship bay b is full of containers, and =0, otherwiseModel IIuHThe lowest tier number on the deckModel IIINEabThe weight of containers loaded in ship tiera of ship bay bNDabThe destination of containers loaded in ship tiera of ship bay brb(binary)=1 if the containers on the deck are overstowed; =0, otherwiseModel IVTt(binary)=1 ift-containers are 20’; =0, otherwiseFt(binary)=1 ift-containers are 40’; =0, otherwiseRt(binary)=1 ift-containers are refrigerated; =0, otherwiseCtThe transformation coefficient of containers from the quantity to the TEU capacityslotRabThe number of refrigerated slots in tiera of block b


## 4. Numerical Experiments for the IP Models

Instances in these numerical experiments are randomly generated. Since the containership parameters are difficult to obtain, we only consider a specific containership in this study. All the instances differ in the containership information, container sizes, and container types as listed in Table2.


### 4.1. Experiment on Scenario I Using Improved Model I, Model II, Model III, and Model IV

All the four models can solve scenario I when the containership is initially empty and only 20 ft general containers are waiting to be loaded into the containership. The experimental results on scenario I are listed in Table11. The first column (instance no.) represents the assigned serial number of instances in the first experiment. The second column (C) represents the number of containers to be loaded into the containership in the current port. The third column (D) represents the number of ports in the fixed voyage. The fourth column (T) represents the number of container groups in the instance. The next eight columns (model IV, model III, model II, and improved model I) record the results of the four models, including the objective and runtime for each model.Table 11
Experimental results on scenario I by the four models.
Instance no.CDTModel IVModel IIIModel IIImproved model IObjTime (s)ObjTime (s)ObjTime (s)ObjTime (s)1-01525433044010209302341-0265644201090154018401661-0359044701870226026203621-0476644802180377033802001-0565445002150331027305371-0646145902590432042204781-0772445904640490047605171-0881545903200530051505281-0955146202850528056606701-108444620313053904500719Scenario I defines the containership empty initially. Therefore, it is easy to find the optimal solution without overstows in the first experiment. The optimal stowage plan is contributed by the reasonable weight distribution in the longitude and latitude direction of the containership structure. The experimental results show that the proposed models are efficient enough to solve the stowage problem in scenario I.Comparing improved model I, the optimal solution can be found quickly when each ship bay is divided into two blocks on the deck and under the deck in model II. Some parameters and decision variables are added to model III and model IV. Since the containership is initially empty and only 20 ft general containers are waiting to be loaded into the containership, the newly added parameters and decision variables have no influence on the actual solving speed of model III and model IV. Therefore, the solving speed of model III and model IV is almost equivalent to that of model II. The experimental results show that the extensions of the basic model have no effect on the solving efficiency in scenario I.


### 4.2. Experiment on Scenario III Using Models III and IV

Only models III and IV can be used for solving the stowage problem when the containership has been loaded with some containers. The experimental results on scenario III are listed in Table12. Similarly, the first column (instance no.) represents the assigned serial number of instances in the second experiment. The second column (Cap (%)) represents the occupied capacity of the containership by the containers from the previous ports in the given route. 30 instances are randomly generated, involving two kinds of initial containership status information. From instances 2-01 to 2-10, the containership is occupied initially by 12.72%. From instances 2-11 to 2-20, the containership is occupied initially by 21.73%. From instances 2-21 to 2-30, the containership is occupied initially by 43.04%. Models III and IV can also find the optimal solution quickly for most of the instances, but they take the longest runtime, about 15 minutes, to achieve the optimal solution of instances 2-18, 2-20, and 2-29. They have not found the optimal solution of instance 2-30 within 1 hour. Comparing the solution quality and runtime of each instance by models III and IV, there is no obvious difference between the two models in solving scenario III.Table 12
Experimental results on scenario III by model III and model IV.
Instance no.Cap (%)CDTModel IVModel IIIObjTime (s)ObjTime (s)2-0112.725254330100.480232.892-0212. 726564420251.010296.892-0312. 725904470241.910413.572-0412. 727664480293.340477.892-0512. 726544500220.650390.742-0612. 724614590321.500381.732-0712. 727244590376.960623.542-0812. 728154590412.220653.332-0912. 725514620358.520690.342-1012. 728444620527.830845.682-1121.73525433092.660269.412-1221.736564420243.210302.812-1321.735904470173.290106.872-1421.737664480208.3701023.232-1521.736544500181.290470.552-1621.734614590343.300300.792-1721.737244590392.170627.142-1821.738154590951.2601055.352-1921.735514620338.790400.222-2021.73844462186882.47186934.072-2143.04872430090.63061.442-2243.045254330156.08035.952-2343.044444350198.47056.132-2443.04444435063.94028.632-2543.0455443514654.3014202.862-2643.0458243633678.6337537.172-2743.0460243733802.7254846.032-2843.0464343733733.7033826.342-2943.04683437332120.95332538.262-3043.04701439663600.00663600.00The runtime by model III or IV increases with the number of containers and container groups to be loaded into the containership. In addition, due to the initial distribution of existing containers in the containership, a stowage plan without overstows may not exist, which is reflected in instances 2-20, 2-25, 2-26, 2-27, 2-28, 2-29, and 2-30.


### 4.3. Experiment on Scenario IV Using Model IV

There are four kinds of containers to be loaded into the containership in scenario IV. There are two sizes, including twenty-equivalent-unit (20 ft) and forty-equivalent-unit (40 ft). There are two types, including general containers (G) and refrigerated containers (R). Only model IV can be used for solving this specific scenario. Various kinds of containers increase the difficulty in solving the mathematical model. The experimental results on scenario IV are listed in Table13. For instance 3-08, the optimal solution cannot be found within 6 hours, but a feasible solution is found by the objective of 188 overstows. For instance 3-05, it requires nearly 6 hours to find the optimal solution by the objective of 8 overstows. For instance 3-04, it requires almost 3 hours to find the optimal solution by the objective of 2 overstows. There is a huge increase in the runtime with the increasing number of containers and container groups to be loaded into the containership. Among the ten instances, two of them are solved by more than 1 hour, and even one of them is not solved using 6 hours.Table 13
Experimental results on scenario IV by model IV.
Instance no.Cap (%)CDT20 ft40 ftModel IVGRGRObjTime (s)3-0112.388634331870297410709.4463-0212.388904424220199350804.8723-0312.386784475020365201434.993-0412.38872448630305848210746.43-0512.3877045053807541821483.53-0612.38523459381185750809.7233-0712.387744595982633420963.6343-0812.3895045949801636318821600.03-0912.386194624622143250783.5153-1012.388854627742904103074.33This experiment verifies the validity and practicability of model IV. Model IV can solve instances with several hundred containers to be loaded into the containership. Therefore, model IV can achieve the optimal stowage plan for large-scale instances in a relatively short runtime.


## 4.1. Experiment on Scenario I Using Improved Model I, Model II, Model III, and Model IV

All the four models can solve scenario I when the containership is initially empty and only 20 ft general containers are waiting to be loaded into the containership. The experimental results on scenario I are listed in Table11. The first column (instance no.) represents the assigned serial number of instances in the first experiment. The second column (C) represents the number of containers to be loaded into the containership in the current port. The third column (D) represents the number of ports in the fixed voyage. The fourth column (T) represents the number of container groups in the instance. The next eight columns (model IV, model III, model II, and improved model I) record the results of the four models, including the objective and runtime for each model.Table 11
Experimental results on scenario I by the four models.
Instance no.CDTModel IVModel IIIModel IIImproved model IObjTime (s)ObjTime (s)ObjTime (s)ObjTime (s)1-01525433044010209302341-0265644201090154018401661-0359044701870226026203621-0476644802180377033802001-0565445002150331027305371-0646145902590432042204781-0772445904640490047605171-0881545903200530051505281-0955146202850528056606701-108444620313053904500719Scenario I defines the containership empty initially. Therefore, it is easy to find the optimal solution without overstows in the first experiment. The optimal stowage plan is contributed by the reasonable weight distribution in the longitude and latitude direction of the containership structure. The experimental results show that the proposed models are efficient enough to solve the stowage problem in scenario I.Comparing improved model I, the optimal solution can be found quickly when each ship bay is divided into two blocks on the deck and under the deck in model II. Some parameters and decision variables are added to model III and model IV. Since the containership is initially empty and only 20 ft general containers are waiting to be loaded into the containership, the newly added parameters and decision variables have no influence on the actual solving speed of model III and model IV. Therefore, the solving speed of model III and model IV is almost equivalent to that of model II. The experimental results show that the extensions of the basic model have no effect on the solving efficiency in scenario I.


## 4.2. Experiment on Scenario III Using Models III and IV

Only models III and IV can be used for solving the stowage problem when the containership has been loaded with some containers. The experimental results on scenario III are listed in Table12. Similarly, the first column (instance no.) represents the assigned serial number of instances in the second experiment. The second column (Cap (%)) represents the occupied capacity of the containership by the containers from the previous ports in the given route. 30 instances are randomly generated, involving two kinds of initial containership status information. From instances 2-01 to 2-10, the containership is occupied initially by 12.72%. From instances 2-11 to 2-20, the containership is occupied initially by 21.73%. From instances 2-21 to 2-30, the containership is occupied initially by 43.04%. Models III and IV can also find the optimal solution quickly for most of the instances, but they take the longest runtime, about 15 minutes, to achieve the optimal solution of instances 2-18, 2-20, and 2-29. They have not found the optimal solution of instance 2-30 within 1 hour. Comparing the solution quality and runtime of each instance by models III and IV, there is no obvious difference between the two models in solving scenario III.Table 12
Experimental results on scenario III by model III and model IV.
Instance no.Cap (%)CDTModel IVModel IIIObjTime (s)ObjTime (s)2-0112.725254330100.480232.892-0212. 726564420251.010296.892-0312. 725904470241.910413.572-0412. 727664480293.340477.892-0512. 726544500220.650390.742-0612. 724614590321.500381.732-0712. 727244590376.960623.542-0812. 728154590412.220653.332-0912. 725514620358.520690.342-1012. 728444620527.830845.682-1121.73525433092.660269.412-1221.736564420243.210302.812-1321.735904470173.290106.872-1421.737664480208.3701023.232-1521.736544500181.290470.552-1621.734614590343.300300.792-1721.737244590392.170627.142-1821.738154590951.2601055.352-1921.735514620338.790400.222-2021.73844462186882.47186934.072-2143.04872430090.63061.442-2243.045254330156.08035.952-2343.044444350198.47056.132-2443.04444435063.94028.632-2543.0455443514654.3014202.862-2643.0458243633678.6337537.172-2743.0460243733802.7254846.032-2843.0464343733733.7033826.342-2943.04683437332120.95332538.262-3043.04701439663600.00663600.00The runtime by model III or IV increases with the number of containers and container groups to be loaded into the containership. In addition, due to the initial distribution of existing containers in the containership, a stowage plan without overstows may not exist, which is reflected in instances 2-20, 2-25, 2-26, 2-27, 2-28, 2-29, and 2-30.


## 4.3. Experiment on Scenario IV Using Model IV

There are four kinds of containers to be loaded into the containership in scenario IV. There are two sizes, including twenty-equivalent-unit (20 ft) and forty-equivalent-unit (40 ft). There are two types, including general containers (G) and refrigerated containers (R). Only model IV can be used for solving this specific scenario. Various kinds of containers increase the difficulty in solving the mathematical model. The experimental results on scenario IV are listed in Table13. For instance 3-08, the optimal solution cannot be found within 6 hours, but a feasible solution is found by the objective of 188 overstows. For instance 3-05, it requires nearly 6 hours to find the optimal solution by the objective of 8 overstows. For instance 3-04, it requires almost 3 hours to find the optimal solution by the objective of 2 overstows. There is a huge increase in the runtime with the increasing number of containers and container groups to be loaded into the containership. Among the ten instances, two of them are solved by more than 1 hour, and even one of them is not solved using 6 hours.Table 13
Experimental results on scenario IV by model IV.
Instance no.Cap (%)CDT20 ft40 ftModel IVGRGRObjTime (s)3-0112.388634331870297410709.4463-0212.388904424220199350804.8723-0312.386784475020365201434.993-0412.38872448630305848210746.43-0512.3877045053807541821483.53-0612.38523459381185750809.7233-0712.387744595982633420963.6343-0812.3895045949801636318821600.03-0912.386194624622143250783.5153-1012.388854627742904103074.33This experiment verifies the validity and practicability of model IV. Model IV can solve instances with several hundred containers to be loaded into the containership. Therefore, model IV can achieve the optimal stowage plan for large-scale instances in a relatively short runtime.


## 5. Conclusion

The study shows the modeling progress in the CSP, establishing four models corresponding to four scenarios. Improved model I is established as the basic model, and a further study is made on the mathematical models for the CSP. Improved model I is then extended to model II, which is used for the containership structure with hatch covers. After that, model II is extended to model III, which is used for the initially nonempty containership. Finally, model III is extended to model IV, which is used for various sizes and types of containers to be loaded into the containership. Set with more practical parameters, model IV can achieve the optimal solution quickly. It is interesting to further extend the established mathematical models by analyzing more detailed scenarios, making the models more applicable for practical stowage plan and handling operation. With the increasing number of containers, types, and groups, the number of variables and constraints are growing rapidly. Therefore, it takes longer to find the optimal solution by the solver. It is challenging to develop a solution method solving the large-scale CSP in our further study.



---

*Source: 4382745-2020-10-14.xml*