The container ship stowage planning problem (CSPP) determines the specific location of a container on a ship. As an essential part of maritime container transportation, the CSPP is one of the problems that container terminals and shipping companies must face and solve every day ^[1][2][1,2]. The quality of stowage determines the safety and seaworthiness of a ship, which directly affects the berthing time of vessels and indirectly affects transportation efficiency. In addition, the quality of stowage is closely related to the shipping company’s efficiency and the cargo owner’s vital interests. When making a container stowage plan, the following aspects must be considered ^[3][4][5][3,4,5].

First, the seaworthiness and proper stability of the ship must be ensured. Because there are many containers on the deck, and the number of containers on the deck may even exceed the number of containers in the hold, container ships are different from other ship types. Container ships are prone to the characteristics of a sizeable wind-receiving area and a high center of gravity. During the whole process of loading and unloading and the entire process of sailing, it is necessary to ensure a certain initial metacentric height (GM), appropriate trim, and timely adjustments to the ship’s heeling, as well as to consider the influence of the blind area of the bridge’s sight. The initial metacentric height is significant for the navigation of ships, and at the same time represents a “sensitive” constraint. If its value is too small, the ship is prone to capsizing. Especially as the ship becomes larger and faster, the economic pressure of navigation in severe weather will tend to increase, thus increasing the risk of capsizing [6]. A too-large value will shorten the rolling period, aggravate hull shaking, reduce crew comfort, and increase the lashing rope’s risk of loosening. In [7], ship stability is regarded as a mandatory constraint. The ship’s operator can use ballast water to adjust non-critical stability issues [8]; however, a good stowage plan needs to optimize the use of ballast water to reduce the ship’s trim in order to improve fuel efficiency.

Second, the limitations imposed by the physical structure of the containers must be met. Both the loading and unloading of containers follow the LIFO (last in, first out) policy [9]. Special containers such as reefer containers, dangerous goods containers, and oversized containers have specific storage requirements. Due to corn fittings at the bottom, two 20-ft containers cannot stack on a 40-ft container.

Third, the container ship’s hull must have sufficient strength. Measures of the strength of a container ship’s hull includes shear force, transverse strength, torsional strength, local strength, and longitudinal strength. In loading, unloading, and transportation, stowage planning must meet the hull’s strength and safety requirements and extend the ship’s service life.

Fourth, the number of container shifts should be minimized. There are many ports of call and the loading and unloading of midway ports are more frequent, especially for transoceanic and global container liners. For this reason, when planning stowage an overall view of the whole route should be taken that carefully considers the order in which ships call and the information provided by each port of call. Earlier ports must be considered when planning for later ports. The starting port should lay the foundation for the entire route to avoid the situation of containers meant for earlier ports being blocked by those meant for later ports. Otherwise, container shifting will reduce the efficiency of loading and unloading, extend the turnaround time, and increase the cost. In addition, relocation will incur expensive additional loading and unloading costs (usually, a single loading and unloading costs tens to hundreds of US dollars) ^[10][11][10,11].

Finally, excessive concentration of containers in the same port of discharge is to be avoided. The makespan of quay cranes directly affects a ship’s turnaround time and port costs. Usually, two or more cranes simultaneously speed up the discharge process for large container ships [12]. However, the quay crane cannot simultaneously lift the containers in two adjacent spaces on the container ship. In the case of the above situation, containers intended for the same discharge port should not be arranged in adjacent holds.

Based on the above discussion, the following two goals are crucial in container stowage.

Goal (a) relates to the safety of ships, while goal (b) relates to the profit and efficiency of shipping companies and port terminals. While each has its own merits, in actual operation there are often conflicts. For example, reducing the number of container shifts may come at the cost of reducing the ship’s stability. In engineering applications, this type of combinatorial optimization problem is called a multi-objective CSPP (MO-CSPP). In theour research, the number of objectives exceeds three (i.e., six); thus, it is a many-objective CSPP (MaO-CSPP). As a remarkably realistic engineering problem in container transportation, MaO-CSPP has attracted the attention of more and more scholars. Multi-objective optimization is a common type of optimization decision-making problem which has been applied in many fields. The optimal solution is usually based on the trade-off between two or more conflicting objectives. To solve an MaO-CSPP according to different decision-making methods, two methods are typically used, namely, the a priori and a posteriori techniques [13].

The a priori technique represents the basic idea behind solving multi-objective optimization problems in traditional mathematical programming. Before searching, the decision information is input and one solution is run to the decision-maker. The main methods include lexicographical, linear fitness, and nonlinear fitness methods. The objective functions of the MaO-CSSP are aggregated to obtain a single-objective optimization problem. Then, the single-objective optimization method is used to obtain a single Pareto-optimal solution. While the idea of this method is simple, in practical engineering applications it is difficult to determine the weighting preferences between the objectives. In MaO-CSPP, the stability and strength of the ship must be guaranteed within a specific range. However, it is difficult to determine the respective weights of the amount of container relocation and the ship’s stability and strength from the perspective of economic profit. Therefore, the priori technique is sometimes not suitable for solving MaO-CSPPs in this context.

In contrast, running the a posteriori technique generates solutions for decision-makers to choose from. This technique generates a representative subset of the global or local Pareto-optimal solutions. If at least one of its goals is not inferior to other solutions in the solution space, the solution is Pareto optimal. If it is not dominated by any other solutions in the solution space, it is Pareto optimal [14]. Domination-based multi-objective optimization has been proven to be suitable for MaO-CSPPs.

A set of Pareto-optimal solutions can be obtained in a single run without prior information by using the a posteriori technique. Decision-makers can then weigh different goals and choose an ideal solution for actual implementation. The above studies on CSPPs seldom consider the principles of ship stability, strength, draught, etc., as they are conducted from a purely mathematical point of view and the yard optimization problem is not included. At the same time, most of the literature does not incorporate the characteristics of the full-route ports of call, instead using only a single port to design the stowage plan.

2. Literature Review

CSPP is occasionally referred to as the master bay plan problem (MBPP) or ship stowage planning problem (SSPP) [15]. In 1970, Webster and Van Dyke first studied CSPP [16]. As their research only discussed simple issues, and did not conduct many experimental data tests, it is impossible to demonstrate the practical significance of their methods. Subsequently, in the 1980s Shields proposed the CAPS system (computer-aided pre-planning system) and applied it to the American President Line (APL) [17]; this system uses Monte Carlo stochastic simulation technology to generate different stowage plans. Avriel et al., proved that the CSSP is an NP-hard problem and demonstrated its relationship with the graph coloring problem [15], then established a 0–1 mathematical programming model and designed a “Suspensory Heuristic Procedure” in which the optimal solution for the small-scale stowage plan is automatically generated [18]. Ambrosino et al., attempted to derive rules that determine a good stowage plan [19]. The authors define and characterize the feasible solution space by satisfying certain constraints. The 0–1 linear programming model was then established to solve this combined optimization problem ^[20][21][20,21] using rules to develop a heuristic algorithm in which containers that have the same attribute should be placed in the same hold. However, the papentryr does not explicitly consider the issue of relocation related to the loading process. The authors expanded the original basic model by considering the influence of different container types (i.e., 20-ft and 40-ft containers) ^[22][23][22,23]. Imai et al., established an integer programming model intended to minimize the shift volume of the yard and the ship’s stability. However, the model did not consider the impact of hatch covers on stowage [8]. It is difficult to estimate the number of shifts when the information left by the container truck is uncertain as to storage space. Therefore, Imai proposed an estimate of the expected number of shifts [24]. Li et al., established a 0–1 mathematical programming model [25] by maximizing container ship hold utilization while minimizing operating costs over the whole route. Cruz-Reyes et al., developed 0/1 IP and employed a constructive heuristic to find the solution [26]. Petering et al., introduced a new mathematical formula for the block relocation problem by establishing an integer programming model. This method has been proven to produce fewer decision variables and better performance [27]. N. Wang et al., established an integer programming model and solved it with a CPLEX solver [28]. Fan et al., designed an effective algorithm to solve the optimization problem of the container stowage plan while considering many practical and operational constraints. However, no specific mathematical model has been set up to describe the optimization of container stowage plans [29]. All of the above-mentioned literature relies on traditional mathematical programming methods to deal with the problem of container stowage; this is only suitable for small-scale situations, and most applications are single-bay container stowage problems [30], which do not have practical engineering significance. Therefore, scholars often adopt a multi-stage method when facing actual scale problems, i.e., the CSPP is decomposed into sub-problems that are easier to handle. The corresponding sub-problems are then dealt with separately, and the solutions of the sub-problems are spliced to obtain a solution. In addition, Monaco introduced a systematic classification scheme for CSPP [31]. Wilson et al., designed a two-stage process for a container stowage plan in which the first stage is a global stowage strategy and the second stage is a partial stowage strategy [32]. Kang and Kim decomposed the container stowage problem into two sub-problems. The first sub-problem allocates containers to different countermeasure holds, and the second sub-problem determines the specific placement of containers in each hold [33]. Ambrosino et al., described the problem as an optimization problem [22]. They defined the problem as a master bay plan problem (MBPP). In response to this problem, the author proposed a three-stage heuristic model to deal with the sub-problems of each stage separately and developed a basic 0–1 linear programming model to minimize the total loading time. The subsequent literature [23] expanded the work of [22] and achieved specific results. Based on their consideration of structural and operational constraints, Ambrosino et al., proposed a multi-port MBPP heuristic algorithm based on MIP to minimize ship berthing time [34]. Later, they offered an MIP model to minimize the number of reprocessing and crane makespan which took into account such realistic constraints as six ports of call and both standard containers and reefer containers [35]. In a recent study, the authors used a specific stowage principle to solve the CSPP in the presence of dangerous containers [36]. Delgado et al., decomposed the ship stowage plan into two sub-problems, the main stowage plan and the location plan, using the calculation result of the main stowage plan as the input data of the location plan [30]. Pacino et al., proposed a two-stage method for large container ships; the first stage deals with the multi-port main bay stowage plan and the second stage uses the constraint programming (CP) method and slot planning to allocate specific slots for each container [37]. Iris Ç et al., presented a flexible container ship loading problem for seaport container terminals. They integrated the assignment and scheduling of transfer vehicles and container load sequencing with the assignment of specific containers to specific vessel positions [38]. Gumus et al., developed a multi-stage heuristic of the CSPP by decomposing the problem into four stages, explaining many complex and realistic CSPPs [39]. Zhang et al., deteriorated the full-route container stowage problem into a bay selection sub-problem and a slot plan sub-problem. The second sub-problem was then further subdivided into single destination port and a multi-destination port bay position optimization problem [40]. Azevedo et al., studied the optimization of container stowage plans considering the operation of quay cranes, taking additional practical and operational constraints into account, and designed a new solution method to solve the problem. However, the related characteristics of the container crane and the container were simplified without considering different container weights and sizes or the additional productivity of the quay crane [41]. Christensen et al., extended the liner shipping cargo mix problem by including the concepts of block stowage and draft restrictions and restricting the number of containers able to be selected, with the aim of determining the optimal cargo mix, not of creating a fully feasible stowage plan. Instead of assigning specific containers to specific slots on the vessel, containers are grouped by container type and assigned to blocks. Each container type represents several containers with the same properties [42]. Yaagoubi et al., studied 3D container loading planning of inland navigation barges. They proposed a heuristic method based on the first fitting algorithm of the packing problem, which is able to deal with actual structural and operational constraints [43]. According to inland container liner transportation characteristics, Li et al., decomposed the current port stowage planning problem into two sub-problems and proposed two heuristic algorithms for them [44]. Iris et al., systematically reviewed the literature related to stowage planning, loading sequencing, and scheduling. From the perspective of the ship loading problem (SLP), the authors pointed out that the literature on integration efforts for the SLP was rather limited, that is, most literature focuses on optimizing partial SLP issues. These studies have contributed to solving the SLP by proposing new models or algorithms to find improved solutions to various aspects of the SLP [45]. To enhance the practicality of the algorithm, scholars have gradually begun to apply heuristic or meta-heuristic methods to the field of ship stowage. Avriel et al., developed a Suspensory Heuristic Procedure to process CSPP that minimizes the number of container shifts without considering stability or strength [18]. Based on [18], Ding extended and enriched the Suspensory Heuristic Procedure [46]. Dubrovsky et al., proposed compact coding technology to design a genetic algorithm (GA) suitable for the CSPP. The significant feature of this method is that it reduces the number of iterations [47]. Jin et al., established an MIP model based on reality constraints, proposed an interactive hybrid algorithm consisting of a combination of a heuristic algorithm and a GA based on a pre-allocation strategy, and realized the visualization of stowage plans using the VB program [48]. Sciomachen and Tanfani considered this model’s structural and operational constraints as they relate to containers and ships. They proposed a heuristic method that uses the relationship between MBPP and the three-dimensional packing problem to solve the MBPP problem [49]. Parreño proposed a greedy randomized adaptive search procedure (GRASP) to solve the problem of container stowage slot planning [3]. Similarly, they studied multi-port CSPP and proposed an IP model and a GRASP algorithm, generating a stowage plan with the smallest number of container shifts for large-scale problems [50]. Araújo et al., proposed a Pareto clustering search algorithm to solve the double objective optimization model of container stowage (with the objectives of the number of movements necessary to load and unload the container ship and the stability of the ship in each port), designed a heuristic algorithm, grouped clustering through local search, and found the Pareto frontier to obtain the effective solution of the problem [51]. Zhang studied a multi-objective CSPP, seeking to optimize the stability of the ship and the number of containers to be reprocessed at the same time. The author developed multiple heuristic algorithms to deal with both containers in the yard and containers in the bay of ships, then integrated these heuristic algorithms into a non-dominated sorting GA [52]. Wilson and Roach used Tabu Search (TS) to generate CSPP solutions, and found that TS can gradually improve the location of containers [53]. Yurtseven implemented two meta-heuristic algorithms, namely, GA and simulated annealing (SA), to solve the CSPP. Their results show that SA can reach near-optimal results faster than GA [54]. Ambrosino et al., tested the performance of three methods to solve the MBBP, i.e., TS, a simple heuristic algorithm, and an ant-colony optimization (ACO) algorithm. Their results show that ACO is the best for large-scale instances, while TS is ideal for medium-sized cases [23]. Bilican et al., proposed a two-stage heuristic solution method using IP and a swapping heuristic (SH), which effectively increases the scale of solvable problems [6]. Junqueira et al., proposed an optimization model that combines the multi-port stowage planning problem with the container relocation problem. The author presented two heuristic methods to quickly generate feasible solutions [55]. Ji et al., established a mixed-integer nonlinear programming model based on small feeder container ships’ “sensitive” characteristics to ensure navigation safety. The authors designed a heuristic algorithm to update branch routes through variable neighborhood search and GA in order to obtain the stowage plan [56]. Although the literature mentioned above discusses several objectives of CSPP, most studies treat the CSPP as a single-objective optimization problem; there are few studies on the MO-CSPP or MaO-CSPP. Imai et al., considered two criteria with respect to the MO-CSSP, namely, ship stability and the number of rehandlings [8]. However, they used a weighted sum method and designed a GA to handle single-objective CSSPs. Liu et al., considered five objectives, i.e., the number of container shifts, the quay cranes’ makespan, the number of stacks exceeding the weight limit, the number of stacks without containers, longitudinal stability, and transverse stability, then developed a random algorithm incorporating TS to find a set of Pareto-optimal solutions [57]. In 1989, David Goldberg proposed using evolutionary algorithms (EA) to achieve multi-objective optimization technology. Multi-objective evolutionary algorithms (MOEA) have subsequently attracted widespread attention from many researchers, and many research results have emerged. When solving MO-CSSPs, to the best of  our knowledge only Zhang et al., have used the MOEA [52].