Optimization Models and Algorithms for Services and Operations Management 2020
View this Special IssueResearch Article  Open Access
Cheng Luo, Hongying Fei, Dana Sailike, Tingyi Xu, Fuzhi Huang, "Optimization of Continuous Berth Scheduling by Taking into Account DoubleLine Ship Mooring", Scientific Programming, vol. 2020, Article ID 8863994, 11 pages, 2020. https://doi.org/10.1155/2020/8863994
Optimization of Continuous Berth Scheduling by Taking into Account DoubleLine Ship Mooring
Abstract
“DoubleLine Ship Mooring” (DLSM) mode has been applied as an initiative operation mode for solving berth allocation problems (BAP) in certain giant container terminals in China. In this study, a continuous berth scheduling problem with the DLSM model is illustrated and solved with exact and heuristic methods with an objective to minimize the total operation cost, including both the additional transportation cost for vessels not located at their minimumcost berthing position and the penalties for vessels not being able to leave as planned. First of all, this problem is formulated as a mixedinteger programming model and solved by the CPLEX solver for smallsize instances. Afterwards, a particle swarm optimization (PSO) algorithm is developed to obtain good quality solutions within reasonable execution time for largescale problems. Experimental results show that DLSM mode can not only greatly reduce the total operation cost but also significantly improve the efficiency of berth scheduling in comparison with the widely used singleline ship mooring (SLSM) mode. The comparison made between the results obtained by the proposed PSO algorithm and that obtained by the CPLEX solver for both smallsize and largescale instances are also quite encouraging. To sum up, this study can not only validate the effectiveness of DLSM mode for heavyloaded ports but also provide a powerful decision support tool for the port operators to make good quality berth schedules with the DLSM mode.
1. Introduction
With the deepening of economic globalization, the world container transportation volume has increased dramatically in recent years [1]. As one of the most important components of container transportation network, container terminals play an important role in world economy. Considering that the efficiency of berth allocation problem has great impact on the output of container terminals, a lot of studies have been dedicated to the berth scheduling problems.
In general, berth schedules are determined by specifying berthing time and position for the coming vessels by taking into account various constraints, such as the berth capacity, announced arrival time and departure time of container ships, and certain specific berthing requirements. In order to avoid collisions between vessels, the singleline ship mooring (SLSM) mode, which specifies that “no more than one vessel can be allocated to the same berth position at the same time,” is normally applied in container terminals over the world, and this rule is regarded as a default in most of the studies on berth scheduling [2].
As one of the most important economic role in the world economy, China is continuously developing the economic innovation, resulting in huge container throughput of the international hubs in China. Yangshan deepwater port is located in Shanghai, a mega city in China. As the largest seaisland artificial deepwater port, Yangshan deepwater port is an important part of Shanghai International Shipping Center, and its annual throughput has increased constantly since it was built in the year of 2005.
Having been one of the world’s busiest container terminals, Yangshan deepwater port has applied a socalled “DoubleLine Ship Mooring” (DLSM) mode to build berth schedules since the year of 2019. Different from the widely used SLSM mode, DLSM mode allows two container ships to be moored simultaneously at the same berth location, enabling more container ships to be moored at their ideal berth and cranes to operate two container ships at the same time, a reasonable way to improve the efficiency of berth operation. Despite that, the real efficiency of the port with DLSM mode depends on how sophisticated the operators are according to the investigation made at Yangshan port, because berth scheduling with DLSM is much more complex than with the SLSM system. In consequence, it is essential to develop an effective decision support system to help berth operators improve the quality and efficiency of daily schedules with the DLSM mode.
This study aims at minimizing the additional operation costs for the vessels not placed at their ideal berthing position and penalties for the ships not being able to leave before their preplanned departure time, for a continuous berth allocation problems (BAP) model with the DLSM mode. The main contributions of this study are as follows: (1) as the first study on berth scheduling with the DLSM mode, it validates the contribution of DLSM model in comparison with the widely used SLSM mode; (2) a mixed integer programming model is constructed for the continuous BAP with DLSM mode, enabling a benchmark for the future studies on such topic; (3) a PSO algorithm is developed to obtain good quality DLSM berthing schedules within reasonable execution time, offering the berth operators at busy ports a powerful decision support tool to improve their work efficiency.
The reminder of this paper is structured as follows. Section 2 is dedicated to the literature review of related work. The problem description is given in Section 3. In Section 4, the targeted problem is formulated as a mixed integer programming model, which can be solved by CPLEX solver, and then, the details of the proposed PSO algorithm are given in Section 5. Section 6 is dedicated to discussions about the experimental results, and this paper ends up with conclusions and perspectives.
2. Related Work
According to the literature, berth allocation problem (BAP) is regarded as the most important issue faced by the management of container terminals. As the quality of berth schedule has a great influence on the improvement of port operation efficiency, a lot of researchers have been studying BAPs, and numerous results were published [2]. Since Imai et al. [3] firstly addressed a static berth allocation problem (SBAP) and further developed a dynamic BAP model (DBAP for public berth system [4]), numerous studies have been published on BAP aiming to optimize the operation efficiencies by taking into account the various constraints affecting BAP [2], such as tidal influence [5], vessel service priority [6], timevarying water depth [7], and channel flow control [8]. As to our knowledge, no study on BAPs with the DLSM mode is observed in the literature; thus, this study aims to fill the research gaps in this field by taking into account the DLSM mode when constructing berth schedules. Furthermore, this study is specifically dedicated to continuous BAP, which copes with the real situation of Yangshan deepwater port that we have investigated and can also be applied to many other huge container hubs.
With regard to the methodologies applied to BAPs, it can be observed in the literature that the BAPs are normally formulated as Mixed Integer Programming (MIP) models, which can be solved with commercial programming solvers for smallsize problems [2–11]. Since BAPs are NPhard, lots of researchers have also taken much effort on developing nearoptimal solutions with efficient heuristics and metaheuristics, such as genetic algorithm and its variants [12–15], subgradient optimization method [15], simulated annealing [9], evolutionary algorithms [16, 17], particle swarm optimization [10], and islandbased metaheuristic algorithm [18].
Particle swarm optimization (PSO) is an evolutionary computation technique firstly developed by Eberhart and Kennedy [19]. Since the particles used in PSO algorithm are only updated by internal velocity and fewer parameters should be tuned, the principles of PSO can be easily understood and widely adapted to various specific applications. According to the literatures, PSO algorithms have been proven quite efficient in dealing with berth allocation [20] yard allocation [21], quay crane scheduling [10, 22]; and many other planning and scheduling problems [23, 24]; in consequence, a PSO algorithm is also proposed in this study to develop efficient berth schedules by taking into account DLSM.
3. Problem Description
3.1. Assumptions
In general, the berth operators are in charge of arranging each vessel arriving at the port to a suitable berth position according to the availability of the wharf resources and respecting the preplanned arrival and departure of the vessel. According to the practices observed at the targeted container terminal, a set of assumptions are defined as follows:(1)Each vessel arrives at the port on the preplanned arrival time(2)If a vessel cannot leave the port before the preplanned departure time, the port has to incur a penalty(3)The coordinate corresponding to the leftmost end of the vessel is used to represent its berthing position, using the leftmost boundary of the wharf as the coordinate reference point(4)Each vessel has a predefined minimumcost berthing position, which is determined according to the goods that will be loaded/unloaded at the port, and if a vessel cannot be berthed at its ideal berthing position, additional operation cost will occur(5)DLSM mode is applied, i.e., at most, two vessels can be simultaneously moored at the same berth position(6)When two vessels are moored in doubleline, the length of the innerside ship cannot be longer than the vessel moored outside(7)When two vessels are moored in doubleline, the innerside one must be berthed earlier and leave later than the outside one
3.2. Notations
For a better understanding, two types of notations are applied in this study: (1) Latin letters are used to denote parameters; (2) Greek letters are applied to represent decision variables.
3.2.1. Parameters
: set of the vessels waiting to be allocated at the berth; L: length of the wharf at the port; T: planning horizon of this study; M: sufficiently large positive number; i, j, k: indices of vessels i, j, k ∈ ; c_{1i}: unit distance cost for transporting containers from/to vessel i, ; c_{2i}: penalty cost per unit of time caused by the late departure of vessel i from the port, ; p_{i}: predefined minimumcost berthing position of vessel i, . : preplanned arrival time of vessel i; h_{i}: total handling time required by the port to finish the necessary unloading/unloading operations of vessel i, ; : preplanned departure time of vessel i, ; l_{i}: length of vessel i, . In this study, the necessary gap that must be reserved to guarantee the safety is also integrated in this value for each vessel;
3.2.2. Decision variables
μ_{i}: integer variable representing the actual berthing position of vessel i, ; θ_{i}: Integer variable representing the actual berthing time of vessel i, i.e., the moment that this vessel is moored at its berthing position where it can be operated by the cranes, ; σ_{i,j}: binary variable representing the relative berthing position of two adjacent vessels, which equals 1 if vessel i is moored on the left to vessel j () and 0 otherwise; π_{i,j}: binary variable indicating the sequential relationship between the berthing time of two vessels, which equals 1 if vessel i is berthed before vessel j () and 0 otherwise; ε_{i,j}: binary variable representing the relative line position of two vessels that are moored in doubleline, which equals to 1 if vessel i is berthed on the innerside to vessel j () and 0 otherwise.
3.3. Timeline Corresponding to the Berth Scheduling of a Vessel
As shown in Figure 1, the timeline of the berth scheduling of vessel i starts from its arrival time at the port, denoted as , and ends up at the moment when all the necessary unloading/loading operations are completed, and the vessel is ready to leave the port for the next destination.
It is worth noting that (1) a gap between the preplanned arrival time and actual berthing time θ_{i} may be observed in the condition that no berth location is available on the arrival of the vessel which has to be waiting at the anchorage until inwharf permission is delivered; (2) although setup operations (such as berthing, mooring ropes, and removing twist locks) are necessary before and after the cranes operating the vessels, the setup time of vessel i is integrated into its overall operation time hi in this study to simplify the expression because it is observed in the targeted port that the setup time is generally not vesseldependent.
3.4. Berth Scheduling with DLSM Mode
When the DLSM mode is applied at the port and two vessels will be scheduled to be moored in doubleline at the same berthing position, it is necessary to determine the relative berthing line positions between these two vessels. Through the interview with the berth operators at the targeted port, a general rule is applied to ensure the berthing safety: Vessel i can be moored in the innerside line to vessel as long as the following conditions can be satisfied: (1) the length of vessel i is larger than that of vessel j; (2) vessel i arrives no later than vessel j at the port; (3) the actual departure time of vessel is not earlier than that of vessel ; (4) the berthing position of the innerside vessel should not be larger that of the outside moored ship while the coordinate of the rightmost end of the former along the wharf must be at least as large as that of the latter.
Figure 2 is the threedimensional schematic diagram of a DLSM example with three vessels, where vessels and are moored in doubleline.
For a better understanding of this example, the corresponding sidewharf section and timewharf one are detailed in Figures 3 and 4, respectively. It can be observed that vessel is placed on the innerside line to vessel since the following conditions are satisfied (1) (as shown in Figure 3); (2) (as shown in Figure 4); (3) (as shown in Figure 4); (4) (as shown in Figure 4); in a berth schedule, a vessel can either be placed at its minimumcost position (e.g., vessels and ) or nonoptimal berthing position (e.g., vessel ).
As for vessel k, since it is moored on the right to the pair of doublelined ships, the coordinates of its berthing position must be larger than those of the rightmost of the innerside moored ship to avoid overlaps, i.e., .
4. Mathematical Formulation
4.1. Construction of the Objective Function
As mentioned in Section 1, the objective function of the targeted BAP problem consists of two parts:(1)Minimization of the additional operation cost for vessels not located at its minimumcost berthing position Considering that the ports normally predefine the minimumcost berthing position for each vessel according the cargos that will be unloaded/loaded to maximize the operation efficiency, it is obvious that the larger is the deviation between the berthing position and the predefined minimumcost position of a vessel, the more is operation cost at the wharf; in this study, this part of the objective function is formulated as .(2)Minimization of the penalty cost for vessels not leaving before their preplanned departure time Let denote the preplanned departure time of vessel . As is known, when the actual departure time of vessel is later than , an additional cost will be incurred due to the influence of such delay on the rest of the voyage, and if the delay in the ship’s departure is caused by the inefficient operation of the port, the port would have to pay certain fine for such delay. Therefore, this study aims also at minimizing the total penalties related to the delays of the vessels within the planning period, and this part of the objective function can be formulated as , where . To sum up, the objective function can be formulated as follows:
4.2. MixedInteger Programming Model
Considering that formula (1) is nonlinear, it should be linearized to meet the requirements of linear programming solver that will be applied in this study to optimally solve smallsize instances.
Let = when , = when , and and denote the nonnegative and negative value of , respectively. Furthermore, let = 0 when to ensure that the smaller is , the better is the solution. Formula (1) can be linearized to formulas (2), (3), and (4) and then the mixedinteger programming model of the targeted problem can be constructed as follows:subject to
Objective function (2) and constraints (3) and (4) indicate that the objective of this study is to minimize both total additional operation cost corresponding to vessels not berthing at their minimumcost berthing position vessels and the penalty cost incurred when vessels cannot leave before their preplanned departure time.
Constraint (5) ensures that no more than two vessels can be berthed at the same position simultaneously. Constraint (6) indicates that the rightmost end of each vessel must be limited by the length of the wharf. Constraint (7) ensures the position relationship of two adjacent vessels along the wharf. Constraint (8) indicates the sequential relationship between the berthing time of two vessels that will be berthed at the same position but not in doubleline. Constraints (9)–(12) indicate the conditions to be respected when two vessels are berthed in doubleline at the berth as detailed in Section 3.4. Constraints (13) ensure that at least one relationship between two vessels waiting to be berthed within the planning period, as shown in Figure 4, holds.
Constraints (14) and (15) ensure the SLSM mode and DLSM mode cannot be applied to the same pair of vessels simultaneously, i.e., if vessel i is berthed in doubleline with vessel j, it can neither be berthed to the left of vessel j nor be berthed before the arrival or after the departure of vessel j. Constraint (16) ensures that vessels can only be berthed after their arrival. Constraints (17) and(18) define the range of decision variables.
5. PSO Algorithm for BAP with DLSM Mode
5.1. Introduction to PSO
In PSO algorithms, the particle swarm concept originated as a simulation of a simplified social system by introducing a number of simple entities—the particles—in the search space, where each particle represents a solution approach corresponding to a given position and velocity, which can be used to evaluate the objective function at its current location.
The movement of each particle is guided by their position, according to their own best position and a swarm’s best position, which represents the quality of searching, and the velocity decides the direction in which the particle would move in the next generation. These particles search for optimal solutions through updating generations. Formulas (19) and (20) represent how velocity and position update in the classical PSO algorithm, respectively:where and represent the current and previous flight velocity of particle i on dimension d in iteration k, respectively, and represent the current and previous position of particle i on dimension d in iteration k, is the inertial weight coefficient, which can adjusts the search range of solution space, and are acceleration weights, which adjust the learning maximum step length, and are two random functions with a value range of [0, 1], whose function is to increase the randomness of the search. denotes the best position of particle i on dimension d up to iteration k, while denotes the best position of the whole swarm on dimension d until iteration k.
Considering that the classical PSO algorithm mentioned above may lead the particles to grow unlimitedly, which influences the particles’ convergence to the optimal solution, Shi and Eberhart [25] improved the updating mechanism, by introducing an inertia weight coefficient, which can be dynamically adjusted to balance the quality of solution and convergence velocity of the algorithm, as shown in the following formula:where , which is the inertia weight coefficient, and denote the maximum and minimum values of the inertia weight coefficient, respectively, and represents the maximum number of iterations.
The PSO algorithm proposed in this study is based on the updating mechanism proposed by Shi and Eberhart (1998).
5.2. Encoding
Assuming that vessels are waiting to be scheduled within the planning period, n random numbers, denoted as , are randomly generated in the range of 0 and 1.0, where each random number corresponds to the vessel with the same index.
Sort those generated random numbers in descending order and then allocate the corresponding vessels to berth positions one after another, i.e., the greater the random number is, the earlier vessel is allocated to a berth position. Ties are broken by selecting the vessel with smallest index.
For a better understanding, here illustrated in Figure 5 is the encoding process with an example of 5 vessels, where a solution with the corresponding berthing order of the vessels as 53142 is obtained.
5.3. Decoding
The decoding process, which is applied in this study to construct the berth schedule corresponding to a given solution obtained by the proposed PSO algorithm, consists of three steps as follows:(i)Step 1: initialization of the berthing schedule The initial berth schedule can be generated by arranging each vessel one after another in the order defined by the solution to its minimumcost berthing position. It is worth mentioning that although placing vessels to their predefined minimumcost berthing positions can avoid additional operation costs, it is hardly possible for berth operators to arrange all the vessels to their minimumcost berthing positions without overlapping any of them at a busy port. In consequence, there is a good chance that the berth schedule obtained at this step is infeasible due to the overlaps, and therefore, actions have to be taken to detect and resolve possible overlaps.(ii)Step 2: detection of overlaps Considering that the overlap between two vessels takes place if and only if both berthing periods and spaces of these two vessels are partly overlapped; the overlap between two vessels and can be detected by verifying constraints (22)–(25); in Figure 6, an example of three vessels with overlap detected between two vessels and is shown:(iii)Step 3: overlaps resolving Once overlaps are detected, the current berth schedule is not yet feasible, and thus actions must be taken to remove those overlaps. The procedure resolving overlaps between two vessels and is as follows: Step 3.1: removing overlap detected between two vessels In this study, the overlap detected between two vessels is eliminated by fixing one vessel and moving the other one towards all possible directions until no overlap is observed between them. Here shown in Figure 7 is an example with two overlapped vessels, which are represented with solid line rectangles. Let vessel j be fixed and vessel can be moved towards four possible directions to eliminate the overlap: (i) left (in condition that the leftmost end of vessel does not exceed the left end of the wharf), (ii) right (in condition that the rightmost end of vessel does not exceed the right end of the wharf), (iii) up (to delay its berthing time), and (iv) outside (in condition that the DLSM constraints are satisfied). The possible positions of vessel after performing these movements are mentioned with dashed line rectangles, and the rectangle corresponding to the outside movement is shaded on this timewharf section. Upon further analysis of the four movements mentioned above, it can be observed that only movement (iii) can result in a feasible solution because (1) movement (i) is not available because there is not enough space on the left (dashed rectangle exceeds the left boundary of the wharf); (2) movement (ii) introduces an overlap between vessel and vessel ; (3) movement (iv) is not available as well because the constraints related to the DLSM mode, as described in Section 4, cannot be satisfied. Nevertheless, the feasibility of the solution obtained by (ii) can be improved by taking into account the relationship between the vessel being moved, i.e., vessel , and the nearby vessels that may be overlapped by the newly placed vessel , e.g., vessel in the example shown in Figure 7. Step 3.2: improving the feasibility of berthing schedule by taking into account the nearby vessels having overlaps with certain moved vessel Since it is possible to introduce new overlaps between the vessel being moved and some of the nearby ships, the relationship of all vessels that may have overlaps with the newly placed vessel must be considered to avoid introducing new overlaps. For a better understanding, let us continue the illustration with the example mentioned in step 3.1. Since moving vessel towards right may introduce an overlap between the vessels and , the movements of vessel around vessel are also considered to generate possible feasible berthing schedules. As shown in Figure 8, three new berthing schedules can obtained by finding the optimal position of placing vessel adjacent to vessel in condition that it does not overlap with any other vessels. It is worth noting that the berthing schedule corresponding to the optimal position above vessel is not shown in Figure 8 because that berthing schedule can be dominated by at least the one with vessel on lower left, i.e., the berthing schedule corresponding to movement (i) shown in Figure 8. Step 3.3: accepting the best feasible berthing schedule Compare all of the possible feasible berthing schedules generated by the adjustments described in steps 3.1 and 3.2 and accept the best one, i.e., the feasible berthing schedule with the smallest objective value as the one that corresponds to the given solution obtained by the proposed PSO algorithm.
5.4. General Procedure of the Proposed PSO Algorithm
The general procedure of the proposed PSO algorithm is as follows.(i)Step 1: set up the parameters of the PSO algorithm, such as the number of particles and the value of inertia weight coefficient.(ii)Step 2: initialize the position and velocity in allowable ranges for each particle and set iteration k = 1.(iii)Step 3: calculate the fitness value, which is equal to the objective value of the proposed model, for each particle.(iv)Step 4: set the localbest value and globalbest value for each particle, where the former equals the particle’s current position and the latter the position of the best particle.(v)Step 5: update the velocity and the position for each particle.(vi)Step 6: update the fitness value for each particle.(vii)Step 7: compare the current fitness value of each particle with the localbest one. If the current fitness value of a particle is better, update the localbest position of this particle; otherwise, it remains unchanged.(viii)Step 8: find out the particle with the best fitness function from the current swam. If the current best fitness value is better than that of the recorded globalbest one, replace the globalbest position with the position of the current best particle; otherwise, the globalbest one remains unchanged.(xi)Step 9: if the number of iteration k attains the predefined threshold, the PSO algorithm terminates and reports the recorded globalbest particle as the final solution; otherwise, set k = k + 1 and return to step 3.
6. Experimental Results
6.1. Experimental Settings
In this study, instances of different scales are randomly generated with the method introduced by Park and Kim [15]. The length of wharf is set as 1200 meters. The planning horizon T is set as 120 time units, where the time unit is one hour.
The cost coefficients and are set as 2 and 10, respectively, as proposed by Meisel and Bierwirth [26]. In order to ensure that most of the vessels can leave the port before their preplanned departure time, the value of the preplanned departure time of a vessel is determined by adding 1.0 to 2.0 times of the corresponding operation time to its preplanned arrival time, i.e., and q is a decimal randomly generated between 1.0 and 2.0, as proposed by Park and Kim [15]. The generation of the other parameters is detailed in Table 1.

The numerical experiments are programmed in C# (VS2017) on a PC with 2.3 GHz Intel Core i5 CPU and 4 GB RAM, and CPLEX 12.5 is applied as the programming solver for smallsize instances. Both programming solver and the proposed PSO algorithm are set to terminate within 3 hours (10,800 s).
6.2. Comparison between Different Mooring Modes
First of all, experiments are conducted to compare between two different mooring modes, i.e., DLSM mode and SLSM mode by considering both objective values and execution time for smallsize instances, i.e., the instances with up to 25 vessels.
As shown in Table 2, it can be observed that the optimal solutions for both modes can be obtained by CPLEX solver within 5 seconds for the instances with no more than 15 vessels. As for SLSM mode, the execution time used to solve instances with the SLSM mode by the CPLEX solver (as shown in column “CPU1”) increases dramatically when the number of vessels is beyond 20. When the DLSM mode is applied, solution for instances with up to 20 vessels can be obtained within 10 seconds and the instances with 25 vessels can still be obtained within 30 minutes (as shown in column “CPU2”). As shown in column “Diff_CPU,” the different rate of the execution time (Diff_CPU1 = (CPU2 − CPU1)/CPU1 100%) varies from −79.16% to −98.87% for the instances with 20 and 25 vessels, and it is reasonable to conclude that the application DLSM mode can greatly improve the work efficiency of port operators.

With regard to the objective values, it can be observed that the DLSM mode obviously dominates the SLSM mode because the objective values of solutions with the DLSM mode (shown in column “OBJ2”) are at least as good as those with the SLSM mode (shown in column “OBJ1”). According to the difference rates shown in column “Diff_Obj1” (Diff_Obj1 = (OBJ2 − OBJ1)/OBJ1 100%), operation costs can be reduced in average of 20.35% and the maximum reduction rate reaches 37.14%.
To sum up, it can be concluded that DLSM mode can help the port operators in not only improving their work efficiency but also reducing overall operation costs.
It should also be mentioned that the optimal solutions cannot be obtained by CPLEX solver within 3 hours for the instances with more than 25 vessels for neither of these two modes. Therefore, we can conclude that CPLEX solver is only effective for solving smallscale problems regardless of whether DLSM is applied, and thus it is necessary to develop efficient heuristics to obtain good quality solution within reasonable execution time for largescale instances so as to cope with the real requirements of the huge terminal containers such as Yangshan port.
6.3. Comparison between Different Methodologies
As mentioned before, the CPLEX solver is just capable of solving BAP models for smallscale instances with both SLSM and DLSM modes, though much more vessels must be scheduled during even 120 hours. Thus, in this study, a PSO algorithm has been proposed to obtain good quality solutions within reasonable execution time for largescale instances.
As shown in Table 3, when comparing the solutions obtained by CPLEX solver and the proposed PSO algorithm for instances with DLSM modes, we can observe that both CPLEX solver and the proposed PSO algorithm can get the final solution very quickly for the instances within 20 vessels. As for instances with more vessels, the CPLEX solver becomes more and more inefficient and cannot obtain optimal solutions within three hours for instances with beyond 30 vessels, though PSO can still get final solution within several minutes.

With regard to objective values, the proposed PSO can obtain optimal solutions for the instances with 8 vessels and most of the instances with 10 vessels and even one instance with 20 vessels; nearoptimal solutions can be obtained for the rest of the instances with 10 vessels and most of the cases with 15 vessels and even most of the cases with 25 vessels with quite small difference rate, which can be illustrated in column “Diff_Obj2” (Diff_Obj2 = (OBJ3 − OBJ2)/OBJ2 100%). It hints that the proposed PSO algorithm is also possible to get solutions of good quality for largescale instances though further studies should be made to test the condition of such performance.
Since it is observed in Table 3 that the gap between solutions obtained by the CPLEX solver and the PSO algorithm with the DLSM mode is relatively significant for some of the instances, a further comparison is made between the results obtained by PSO with DLSM mode and the optimal solutions obtained by the CPLEX solver with the SLSM mode.
As shown in Table 4, solutions obtained by the PSO algorithm with DLSM mode are better than the optimal solutions obtained by the CPLEX solver with the SLSM mode, and the former can save up to 35.81% of the cost (Diff_Obj3 = (OBJ3 − OBJ1)/OBJ1 100%) among all the instances tested in this study.

Considering that hundreds of vessels should be operated every day at huge container terminals, the proposed PSO will be much more practical than CPLEX for supporting the decisionmaking of the port operators to not only improve their working efficiency but also reduce operation costs related to berth scheduling operations.
7. Conclusions and Perspectives
The study aims at minimizing the total operation cost of the continuous berth scheduling problem by taking into account the DoubleLine Shipping Mooring (DLSM) mode, where both the additional operation cost for vessels not moored at their minimumcost berthing position and penalty cost related to vessels not being able to leave before its preplanned departure time are considered.
The problem is firstly formulated as a mixed integer programming model and solved by the CPLEX solver for smallscale instances. As for larger size instances that cannot be optimally solved by CPLEX solver, a PSO algorithm is proposed to obtain good quality solutions within reasonable execution time.
Numerical experiments are conducted to compare not only the efficiency between the traditional SingleLine Shipping Mooring (SLSM) mode and the innovative DLSM mode but also the performances between CPLEX solver and the proposed PSO algorithm. It can be concluded with the experimental results that (1) DLSM mode outperforms the SLSM mode in reducing not only total operation cost but also execution time. (2) The proposed PSO algorithm can generate optimal or nearoptimal solution for smallscale instances. (3) The proposed PSO algorithm is much more efficient than the CPLEX solver for largescale instances, which copes with the requirements of berthing management in Yangshan DeepWater Port, one of the busiest container terminals in the world.
To sum up, as the first research dedicated to BAP with DLSM mode, this study can help not only in validating the advantages of DLSM mode but also offering an efficient decision support tool to berth operators in busy ports to improve their working efficiency.
Motivated by the results obtained in this study, it is interesting to keep improving the efficiency of the proposed algorithm and to apply such method in the targeted port.
Data Availability
All the experimental data can be generated with the rules described in the paper.
Conflicts of Interest
The authors declare that there are no conflicts of interest regarding the publication of this paper.
References
 Q. Meng, S. Wang, H. Andersson, and K. Thun, “Containership routing and scheduling in liner shipping: overview and future research directions,” Transportation Science, vol. 48, no. 2, pp. 265–280, 2014. View at: Publisher Site  Google Scholar
 D. Kizilay and D. T. Eliiyi, “A comprehensive review of quay crane scheduling, yard operations and integrations thereof in container terminals,” Flexible Services and Manufacturing Journal, 2020. View at: Publisher Site  Google Scholar
 A. Imai, K. I. Nagaiwa, and C. W. Tat, “Efficient planning of berth allocation for container terminals in Asia,” Journal of Advanced Transportation, vol. 31, no. 1, pp. 75–94, 1997. View at: Publisher Site  Google Scholar
 A. Imai, E. Nishimura, and S. Papadimitriou, “The dynamic berth allocation problem for a container port,” Transportation Research Part B: Methodological, vol. 35, no. 4, pp. 401–417, 2001. View at: Publisher Site  Google Scholar
 V. H. Barros, T. S. Costa, A. C. M. Oliveira, and L. A. N. Lorena, “Model and heuristic for berth allocation in tidal bulk ports with stock level constraints,” Computers & Industrial Engineering, vol. 60, no. 4, pp. 606–613, 2011. View at: Publisher Site  Google Scholar
 L. Dai and L. Tang, “Berth allocation with service priority for container terminal of hub port,” in Proceedings of the 2008 4th International Conference on Wireless Communications, Networking and Mobile Computing, pp. 1–4, Logs Engineering & Management, Dalian, China, October 2008. View at: Publisher Site  Google Scholar
 T. Qin, Y. Du, and M. Sha, “Evaluating the solution performance of IP and CP for berth allocation with timevarying water depth,” Transportation Research Part E: Logistics and Transportation Review, vol. 87, pp. 167–185, 2016. View at: Publisher Site  Google Scholar
 L. Zhen, Z. Liang, D. Zhuge, L. H. Lee, and E. P. Chew, “Daily berth planning in a tidal port with channel flow control,” Transportation Research Part B: Methodological, vol. 106, pp. 193–217, 2017. View at: Publisher Site  Google Scholar
 K. H. Kim and K. C. Moon, “Berth scheduling by simulated annealing,” Transportation Research Part B: Methodological, vol. 37, no. 6, pp. 541–560, 2003. View at: Publisher Site  Google Scholar
 B. C. Jos, M. Harimanikandan, C. Rajendran, and H. Ziegler, “Minimum cost berth allocation problem in maritime logistics: new mixed integer programming models,” Indian Academy of Sciences/Sādhanā, vol. 44, p. 149, 2019. View at: Publisher Site  Google Scholar
 L. Zhen, H. Hu, W. Wang, X. Shi, and C. Ma, “Cranes scheduling in frame bridges based automated container terminals,” Transportation Research Part C: Emerging Technologies, vol. 97, pp. 369–384, 2018. View at: Publisher Site  Google Scholar
 E. LallaRuiz, J. L. GonzálezVelarde, B. MeliánBatista, and J. M. MorenoVega, “Biased random key genetic algorithm for the tactical berth allocation problem,” Applied Soft Computing, vol. 22, pp. 60–76, 2014. View at: Publisher Site  Google Scholar
 E. Nishimura, A. Imai, and S. Papadimitriou, “Berth allocation planning in the public berth system by genetic algorithms,” European Journal of Operational Research, vol. 131, no. 2, pp. 282–292, 2001. View at: Publisher Site  Google Scholar
 S. R. Seyedalizadeh Ganji, A. Babazadeh, and N. Arabshahi, “Analysis of the continuous berth allocation problem in container ports using a genetic algorithm,” Journal of Marine Science and Technology, vol. 15, no. 4, pp. 408–416, 2010. View at: Publisher Site  Google Scholar
 Y.M. Park and K. H. Kim, “A scheduling method for berth and quay cranes,” OR Spectrum, vol. 25, no. 1, pp. 1–23, 2003. View at: Publisher Site  Google Scholar
 M. A. Dulebenets, “Application of evolutionary computation for berth scheduling at marine container terminals: parameter tuning versus parameter control,” IEEE Transactions on Intelligent Transportation Systems, vol. 19, no. 1, pp. 25–37, 2018. View at: Publisher Site  Google Scholar
 M. A. Dulebenets, “An adaptive island evolutionary algorithm for the berth scheduling problem,” Memetic Computing, vol. 12, no. 1, pp. 51–72, 2020. View at: Publisher Site  Google Scholar
 M. Kavoosi, M. A. Dulebenets, O. Abioye et al., “Berth scheduling at marine container terminals: a universal islandbased metaheuristic approach,” Maritime Business Review, vol. 5, no. 1, pp. 30–66, 2020. View at: Publisher Site  Google Scholar
 R. C. Eberhart and J. Kennedy, “A new optimizer using particle swarm theory,” in Proceeding of the 6th International Symposium on Micromachine and Human Science, pp. 39–43, Nagoya, Japan, October 1995. View at: Publisher Site  Google Scholar
 C.J. Ting, K.C. Wu, and H. Chou, “Particle swarm optimization algorithm for the berth allocation problem,” Expert Systems with Application, vol. 41, no. 4, pp. 1543–1550, 2014. View at: Publisher Site  Google Scholar
 L. Zhen, “Modeling of yard congestion and optimization of yard template in container ports,” Transportation Research Part B: Methodological, vol. 90, pp. 83–104, 2016. View at: Publisher Site  Google Scholar
 P. Guo, W. Cheng, and Y. Wang, “A modified generalized extremal optimization algorithm for the quay crane scheduling problem with interference constraints,” Engineering Optimization, vol. 46, pp. 1411–1429, 2014. View at: Publisher Site  Google Scholar
 H.P. Hsu and C.N. Wang, “Resources planning for container terminal in a maritime supply chain using multiple particle swarms optimization (MPSO),” Mathematics, vol. 8, no. 5, p. 764, 2020. View at: Publisher Site  Google Scholar
 M. Zhong, Y. Yang, Y. Zhou, and O. Postolache, “Adaptive autotuning mathematical approaches for integrated optimization of automated container terminal,” Mathematical Problems in Engineering, vol. 2019, Article ID 7641670, 14 pages, 2019. View at: Publisher Site  Google Scholar
 Y. Shi and R. Eberhart, “A modified particle swarm optimizer,” in Proceedings of the IEEE world congress on Computational Intelligence, pp. 69–73, Anchorage, AK, USA, 1998. View at: Publisher Site  Google Scholar
 F. Meisel and C. Bierwirth, “Heuristics for the integration of crane productivity in the berth allocation problem,” Transportation Research Part E: Logistics and Transportation Review, vol. 45, no. 1, pp. 196–209, 2009. View at: Publisher Site  Google Scholar
Copyright
Copyright © 2020 Cheng Luo et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.